可以使用ping伪随机选择的IP地址生成真正的随机数吗？ [英] Could a truly random number be generated using pings to pseudo-randomly selected IP addresses?

问题描述

提出的问题是在第二届Comp Science演讲期间提出的，当时他讨论了不可能在确定性计算设备中生成数字。

The question posed came about during a 2nd Year Comp Science lecture while discussing the impossibility of generating numbers in a deterministic computational device.

这是唯一的建议

因此，没有人会把自己的声誉放在网上来明确地支持或反对它。

Subsequently nobody would put their reputation on the line to argue definitively for or against it.

任何人都愿意支持或反对。如果是这样，那么提及可能的实现方式呢？

Anyone care to make a stand for or against. If so, how about a mention as to a possible implementation?

推荐答案

否。

您网络上的恶意计算机可能使用ARP欺骗（或许多其他技术）来拦截您的ping，并在一定时间后对其进行回复。这样，他们不仅会知道您的随机数是什么，而且还可以控制它们。

A malicious machine on your network could use ARP spoofing (or a number of other techniques) to intercept your pings and reply to them after certain periods. They would then not only know what your random numbers are, but they would also control them.

当然，仍然存在本地网络的确定性问题，因此可能不像实践中的那么容易。但是，由于您无法从ping互联网上的随机IP中获得任何好处，因此您也可能会从以太网流量中吸取熵。

Of course there's still the question of how deterministic your local network is, so it might not be as easy as all that in practice. But since you get no benefit from pinging random IPs on the internet, you might just as well draw entropy from ethernet traffic.

从与计算机连接的设备中提取熵是一个经过充分研究的原理，各种设备和测量方法的优缺点可以例如

Drawing entropy from devices attached to your machine is a well-studied principle, and the pros and cons of various kinds of devices and methods of measuring can be e.g. stolen from the implementation of /dev/random.

[ Edit ：作为一般原则，在安全性基础（以及只有对大量真正随机数据的实际需求才是与安全相关的），您必须假设资源奇妙，果断的攻击者将竭尽所能破坏您的系统。

[Edit: as a general principle, when working in the fundamentals of security (and the only practical needs for significant quantities of truly random data are security-related) you MUST assume that a fantastically well-resourced, determined attacker will do everything in their power to break your system.

为了获得实际的安全性，您可以假设没有人非常想要您的PGP密钥，并且愿意在安全性与成本之间进行权衡。但是，在发明算法和技术时，您需要为它们提供可能遇到的最强大的安全保证。由于我可以相信某个地方的某人可能会严重想要其他人的私钥以构建此套件来击败您的建议，因此我不能接受它是当前最佳实践的进步。 AFAIK / dev / random遵循最佳实践，可以在廉价的家用PC上生成真正的随机数据]

For practical security, you can assume that nobody wants your PGP key that badly, and settle for a trade-off of security against cost. But when inventing algorithms and techniques, you need to give them the strongest security guarantees that they could ever possibly face. Since I can believe that someone, somewhere, might want someone else's private key badly enough to build this bit of kit to defeat your proposal, I can't accept it as an advance over current best practice. AFAIK /dev/random follows fairly close to best practice for generating truly random data on a cheap home PC]

[另一种编辑：它具有在评论中建议：（1）确实可以影响物理过程的任何TRNG，以及（2）无论如何这里都不会涉及安全问题。

[Another edit: it has suggested in comments that (1) it is true of any TRNG that the physical process could be influenced, and (2) that security concerns don't apply here anyway.

（1）的答案是，在任何实际的硬件上，比ping响应时间做得好得多，并且更快地收集更多的熵是可能的，因此该建议不是解决方案。用CS术语来说，很明显，您无法在确定性计算机上生成随机数，这正是引发此问题的原因。但是从CS的角度来看，具有外部输入流的计算机在定义上是不确定的，因此，如果我们谈论的是ping，那么我们就不是在谈论确定性的机器。因此，有必要查看真实机器具有的真实输入，并将其视为随机性的来源。不管您的机器是什么，原始ping时间在可用的来源列表中都不会很高，因此可以在担心更好的来源之前将其排除。与不假设您自己的硬件未被颠覆相比，假定网络未被颠覆是一个更大（且不必要）的假设。

The answer to (1) is that it's possible on any real hardware to do so much better than ping response times, and gather more entropy faster, that this proposal is a non-solution. In CS terms, it is obvious that you can't generate random numbers on a deterministic machine, which is what provoked the question. But then in CS terms, a machine with an external input stream is non-deterministic by definition, so if we're talking about ping then we aren't talking about deterministic machines. So it makes sense to look at the real inputs that real machines have, and consider them as sources of randomness. No matter what your machine, raw ping times are not high on the list of sources available, so they can be ruled out before worrying about how good the better ones are. Assuming that a network is not subverted is a much bigger (and unnecessary) assumption than assuming that your own hardware is not subverted.

对（2）的回答是哲学上的。如果您不介意随机数具有可以一时兴起而不是偶然选择的属性，那么此建议是可以的。但这不是我所理解的随机一词。

The answer to (2) is philosophical. If you don't mind your random numbers having the property that they can be chosen at whim instead of by chance, then this proposal is OK. But that's not what I understand by the term 'random'. Just because something is inconsistent doesn't mean it's necessarily random.

最后，要按要求处理提案的实施细节：假设您接受ping时间为随机，仍然不能使用未处理的ping时间作为RNG输出。您不知道它们的概率分布，而且它们肯定不是均匀分布的（这通常是人们从RNG中想要的）。

Finally, to address the implementation details of the proposal as requested: assuming you accept ping times as random, you still can't use the unprocessed ping times as RNG output. You don't know their probability distribution, and they certainly aren't uniformly distributed (which is normally what people want from an RNG).

因此，您需要确定您愿意依靠每个ping多少熵。熵是随机变量的精确定义的数学属性，可以合理地认为它是衡量其实际随机性的量度。实际上，您会找到自己满意的下限。然后将多个输入散列在一起，并将其转换为小于或等于输入的总依赖熵的输出位数。 总计并不一定意味着总和：如果输入在统计上是独立的，则它是总和，但是ping不太可能是这种情况，因此您的熵估算的一部分将用于考虑相关性。这种哈希运算的复杂姊妹被称为熵收集器，所有好的OS都有一个。

So, you need to decide how many bits of entropy per ping you are willing to rely on. Entropy is a precisely-defined mathematical property of a random variable which can reasonably be considered a measure of how 'random' it actually is. In practice, you find a lower bound you're happy with. Then hash together a number of inputs, and convert that into a number of bits of output less than or equal to the total relied-upon entropy of the inputs. 'Total' doesn't necessarily mean sum: if the inputs are statistically independent then it is the sum, but this is unlikely to be the case for pings, so part of your entropy estimate will be to account for correlation. The sophisticated big sister of this hashing operation is called an 'entropy collector', and all good OSes have one.

如果您使用数据播种PRNG，但是，PRNG可以使用任意大的种子输入，因此您不必进行哈希处理，因为它将为您完成此操作。如果您想知道种子值的随机性，您仍然必须估算熵-您可以使用世界上最好的PRNG，但是它的熵仍然受到种子熵的限制。]

If you're using the data to seed a PRNG, though, and the PRNG can use arbitrarily large seed input, then you don't have to hash because it will do that for you. You still have to estimate entropy if you want to know how 'random' your seed value was - you can use the best PRNG in the world, but its entropy is still limited by the entropy of the seed.]

这篇关于可以使用ping伪随机选择的IP地址生成真正的随机数吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！