algorithm - 是否可以使用 ping 到伪随机选择的 IP 地址来生成真正的随机数？

Question

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

这是唯一不依赖于非商品级硬件的建议。

随后，没有人会为了自己的名誉而明确地支持或反对它。

任何人都关心支持或反对的立场。如果是这样，如何提及可能的实现？

Answer 1

不。

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

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

从连接到您的机器的设备中提取熵是一个经过充分研究的原理，各种设备和测量方法的优缺点可以从 /dev/random 的实现中窃取。

[编辑：作为一般原则，在从事安全基础工作时（并且对大量真正随机数据的唯一实际需求是与安全相关的），您必须假设一个资源充足、坚定的攻击者会在他们的破坏你的系统的力量。

对于实际的安全性，您可以假设没有人那么想要您的 PGP 密钥，并在安全性与成本之间进行权衡。但是在发明算法和技术时，你需要给他们最强大的安全保证，这是他们可能面临的。因为我可以相信某个地方的某个人可能非常想要别人的私钥来构建这个工具包来击败你的提议，所以我不能接受它作为对当前最佳实践的进步。AFAIK /dev/random 非常接近在廉价家用 PC 上生成真正随机数据的最佳实践]

[另一个编辑：它在评论中建议（1）任何TRNG都可能影响物理过程，并且（2）安全问题无论如何都不适用于这里。

(1) 的答案是，在任何真正的硬件上都可能比 ping 响应时间做得更好，并且更快地收集更多的熵，因此这个提议不是解决方案。在 CS 术语中，很明显您无法在确定性机器上生成随机数，这就是引发问题的原因。但是在 CS 术语中，具有外部输入流的机器在定义上是不确定的，所以如果我们谈论 ping，那么我们就不是在谈论确定性机器。因此，有必要查看真实机器的真实输入，并将它们视为随机性的来源。无论您的机器是什么机器，原始 ping 时间在可用资源列表中都不高，因此可以在担心更好的资源有多好之前排除它们。

（2）的答案是哲学的。如果您不介意您的随机数具有可以随心所欲而不是偶然选择的属性，那么这个建议是可以的。但这不是我对“随机”一词的理解。仅仅因为某些事情不一致并不意味着它一定是随机的。

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

因此，您需要确定您愿意依赖的每个 ping 的熵位数。熵是随机变量的精确定义的数学属性，可以合理地被认为是衡量它实际上有多“随机”的量度。在实践中，您会找到一个您满意的下限。然后将多个输入散列在一起，并将其转换为小于或等于输入的总依赖熵的输出位数。“总计”并不一定意味着总和：如果输入在统计上是独立的，那么它就是总和，但对于 ping 而言，这不太可能是这种情况，因此您的熵估计的一部分将考虑相关性。这种散列操作的老大哥被称为“熵收集器”，所有好的操作系统都有一个。

但是，如果您使用数据为 PRNG 播种，并且 PRNG 可以使用任意大的种子输入，那么您不必散列，因为它会为您执行此操作。如果你想知道你的种子值有多“随机”，你仍然需要估计熵——你可以使用世界上最好的 PRNG，但它的熵仍然受到种子熵的限制。]

Answer 2

随机数太重要了，不能靠运气。

或外部影响/操纵。

Answer 3

简短的回答

单独使用 ping 时序数据不会是真正随机的，但它可以用作熵的来源，然后可以用来生成真正的随机数据。

更长的版本

ping 时间有多随机？

就其本身而言，来自网络操作（例如 ping）的计时数据不会均匀分布。（而且选择随机主机的想法是不切实际的——许多主机根本不会响应，主机之间的差异可能很大，响应时间范围之间存在差距——想想卫星连接）。

然而，虽然时间分布不会很好，但数据中会有一定程度的随机性。或者换句话说，存在一定程度的信息熵。将时序数据输入随机数生成器来播种是个好主意。那么存在什么级别的熵呢？

对于大约 50 毫秒的网络定时数据，测量到最接近的 0.1 毫秒，值的分布为 2 毫秒，您有大约 20 个值。向下舍入到最接近的 2 次幂（16 = 2^4），每个计时值有 4 位熵。如果它用于任何类型的安全应用程序（例如生成加密密钥），那么我会保守地说每次读取只有 2 或 3 位熵。 （注意我这里做了一个非常粗略的估计，忽略了被攻击的可能性）。

如何生成真正的随机数据

对于真正的随机数，您需要将数据发送到按照/dev/random设计的东西中，它将收集熵，将其分布在数据存储中（使用某种散列函数，通常是安全的）。同时，熵估计增加。因此，对于 128 位 AES 密钥，在熵池有足够的熵之前需要 64 次 ping 时间。

为了更加健壮，您可以添加来自键盘和鼠标使用情况、硬盘响应时间、主板传感器数据（例如温度）等的计时数据。它增加了熵收集的速率，使攻击者难以监控所有熵的来源。事实上，这就是现代系统所做的。MS Windows 熵源的完整列表在这篇文章的第二条评论中列出。

更多阅读

要讨论对随机数生成器的（计算机安全）攻击，以及密码安全随机数生成器的设计，您可能会比阅读Bruce Schneier和 John Kelsey的yarrow 论文做得更糟。（BSD 和 Mac OS X 系统使用 Yarrow）。

Answer 4

不。

拔下网线（或/etc/init.d/networking stop），熵基本降为零。

在它正在 ping 的机器上执行拒绝服务攻击，您还可以获得可预测的结果（ping 超时值）

Answer 5

我想你可以。有几点需要注意：

• 即使 ping 随机 IP 地址，前几跳（从您到 ISP 网络中的第一个真正的 L3 路由器）对于每个数据包都是相同的。这为往返时间设置了一个下限，即使您在第一个存在点对数据中心中的某些内容执行 ping 操作。所以你必须小心规范时间，往返有一个下限。
• 您还必须小心网络中的流量整形。路由器中典型的漏桶实现每 M 微秒释放 N 个字节，这有效地将您的时间扰乱到特定的时隙而不是连续的时间范围内。因此，您可能需要丢弃时间戳的低位。

但是，我不同意商品硬件中没有好的熵来源的前提。过去几年的许多 x86 芯片组都包含随机数生成器。我熟悉的那些使用相对敏感的 ADC 来测量芯片上两个不同位置的温度，然后减去它们。这种温差的低位可以显示（通过卡方分析）是强随机的。当您增加系统上的处理负载时，整体温度会上升，但芯片的两个区域之间的差异仍然不相关且不可预测。

Answer 6

我见过的商品硬件随机性的最佳来源是一个人从他的网络摄像头上取下过滤器或其他东西，在镜头上涂上不透明的胶水，然后能够轻松地从撞击 CCD 的宇宙射线中检测到单个白色像素。它们尽可能接近完全随机，并通过量子效应免受外部窥探。

Answer 7

一个好的随机数生成器的一部分是所有数字的概率相等，如 n -> 无穷大。

因此，如果您计划生成随机字节，那么从良好的 rng 获得足够的数据，每个字节应该有相同的返回概率。此外，返回的某些数字不应该有模式或可预测性（在某些时间段内的概率峰值）。

我不太确定使用 ping 你将测量什么来获取随机变量，它是响应时间吗？如果是这样，您可以非常确定某些响应时间或响应时间范围会比其他响应时间更频繁，因此可能会产生不安全的随机数生成器。

Answer 8

如果你想要商品硬件，你的声卡应该可以做到。只需调高模拟输入的音量，您就有了便宜的白噪声源。无需网络的廉价随机性。

Answer 9

它不如使用大气噪声好，但它仍然是真正随机的，因为它取决于以随机不可重复行为而臭名昭著的网络特性。

有关随机性的更多信息，请参见Random.org。

这是一个实现的尝试：

@ips  : list = getIpAddresses();
@rnd         = PseudorandomNumberGenerator(0 to (ips.count - 1));

@getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime }

Answer 10

测量某些东西以生成随机种子的方法似乎是一种非常好的方法。O'Reilly 的书Practical Unix and Internet Security提供了一些类似的附加方法来确定随机种子，例如要求用户键入几个击键，然后测量击键之间的时间。（书中指出，PGP 使用这种技术作为其随机性的来源。）

我想知道系统 CPU 的当前温度（测量到许多小数位）是否可能是随机种子的可行组件。这种方法的优点是不需要访问网络（因此当网络连接断开时随机生成器不会变得不可用）。

但是，CPU 的内部传感器可能不太可能将 CPU 温度准确测量到足够多的小数位，以使该值作为随机数种子真正可行；至少，不是问题中提到的“商品级硬件”！

Answer 11

在信任往返 ping 作为熵之前，我会更早地使用像ISAAC这样的东西作为更强的 PRNG。就像其他人所说的那样，一个人不仅要猜你的数字，而且还可能在不同程度上控制它们，这太容易了。

存在其他重要的熵来源，其他人已经提到过。没有提到的一个（可能不实用）是从板载音频设备中采样噪声。即使没有连接麦克风，它通常也会有点吵。

我进行了 9 轮尝试为我正在编写的客户端/服务器 RPC 机制提出一个强大（且快速）的 PRNG。双方都有一个相同的密钥，由 1024 行 32 个字符的密码组成。客户端将发送 AUTH xx，服务器将返回 AUTH yy .. 双方都知道使用哪两行密钥来生成河豚秘密（+盐）。然后服务器将发送整个密钥（加密）的 SHA-256 摘要，客户端知道它正在与具有正确密钥的东西交谈..会话继续。是的，对中间人的保护非常弱，但是对于设备的使用方式，公钥是不可能的。

所以，你有一个非阻塞服务器，它必须处理多达 256 个连接.. PRNG 不仅必须强大，而且必须快速。使用较慢的方法在客户端收集熵并没有那么困难，但在服务器中无法提供。

所以，我不得不问一下你的想法......它有多实用？

Answer 12

没有数学计算可以产生随机结果，但在“现实世界”中，计算机不仅仅只是处理数字......只要有一点创造力，就应该有可能产生没有已知方法的那种随机结果再现或预测准确的结果。

我见过的在所有系统上通用的最容易实现的想法之一是使用来自计算机声卡线路输入/麦克风端口的静态。

其他想法包括热噪声和高速缓存行的低级时序。许多带有 TPM 芯片的现代 PC 已经板载了加密质量的硬件随机数生成器。

我对 ping 的下意识反应（尤其是使用 ICMP 时）是您的作弊过于明目张胆。那时，您不妨拿出一个吉格计数器并使用背景辐射作为您的随机源。

Answer 13

是的，这是可能的，但是……魔鬼在细节中。

如果要生成 32 位整数，则需要收集 >32 位的熵（并使用足够的混合函数来使熵散布，但这是已知且可行的）。最大的问题是：

ping时间有多少熵？

这个问题的答案取决于对网络和您的攻击模型的各种假设，并且在不同的情况下有不同的答案。

如果攻击者能够完全控制 ping 时间，那么每次 ping 获得的熵为 0 位，并且无论混合多少，您都无法获得 32 位的熵。如果他们对 ping 时间的控制不够完美，您将获得一些熵，并且（如果您不高估所收集的熵量）将获得完全随机的 32 位数字。

Answer 14

YouTube 展示了一个正在运行的设备：http ://www.youtube.com/watch?v=7n8LNxGbZbs

随机是，如果没有人可以预测下一个状态。

Answer 15

呃，我发现这种问题很快就引发了关于“真正随机”含义的讨论。

我认为测量 ping 会产生质量不错的随机位，但速度不足以发挥很大作用（除非你愿意做一些严重的 DDOS 攻击）。

而且我认为它不会比测量计算机的模拟/机械特性或操作它的肉袋的行为更随机。

（编辑）实际上，这种方法让您了解网络上有人操纵您的“随机”数字生成器的可能性。

Answer 16

虽然我不能明确地支持或反对，但这个实现有它的问题。

这些IP地址是从哪里来的，如果它们是随机选择的，当它们不回复或回复迟到时会发生什么，是否意味着随机数出现的速度会更慢。

此外，即使您将制作 100.000 个结果的可视化图表并计算出这些数字之间没有相关性或相关性很少，但这并不意味着它是真正随机的。正如dilbert所解释的:)

Answer 17

它并没有让我觉得它是随机性的良好来源。

您将使用什么指标——显而易见的指标是响应时间，但您可以合理预期的值范围很小：几十毫秒到几千毫秒。响应时间本身将遵循钟形曲线，并且不会随机分布在任何间隔（您将如何选择间隔？）因此您必须尝试从数字中选择一些“随机”位。

LSB 可能会给你一个随机的比特流，但你必须考虑时钟粒度问题——也许由于中断的工作方式，在某些系统上你总是会得到 2ms 的倍数。

可能有更好的“有趣”方式来获取随机位——也许谷歌搜索一个随机词，抓取第一页并从页面中选择第 N 位。

Answer 18

在我看来，真正的随机性是不可言喻的——没有办法知道一个序列是否是随机的，因为根据定义它可以包含任何东西，无论多么不可能。保证特定的分布模式可以减少随机性。“模式”这个词有点赠品。

    I MADE U A RANDOM NUMBER
           BUT I EATED IT

Answer 19

随机性不是二元属性——它是一个介于 0 和 1 之间的值，它描述了预测流中下一个值的难度。

问“如果我基于 ping，我的值会有多随机？” 实际上是在问“ping 有多随机？”。您可以通过收集足够大的数据集（例如 100 万次 ping）并及时绘制它们的分布曲线和行为来估计这一点。如果分布是平坦的并且行为难以预测，则数据似乎更加随机。越颠簸的分布或可预测的行为表明随机性越低。

您还应该考虑样本分辨率。我可以想象结果以某种方式四舍五入到一毫秒，因此使用 ping 你可以有 0 到 500 之间的整数值。这不是很多分辨率。

在实际方面，我建议不要这样做，因为可以预测和操纵 ping，从而进一步降低它们的随机性。

一般来说，我建议不要“滚动你自己的”随机生成器、加密方法和散列算法。尽管看起来很有趣，但它主要是很多非常令人生畏的数学。

至于如何构建一个非常好的熵发生器——我认为这可能必须是一个密封的盒子，它可以输出某种原子或亚原子级别的交互结果。我的意思是，如果您使用敌人也可以轻松读取的熵源，那么他只需要找出您的算法即可。任何形式的连接都是可能的攻击向量，因此您应该将熵源放置在尽可能靠近使用它的服务的位置。

Answer 20

您可以使用 XKCD 方法：

Answer 21

我得到了一些使用 traceroute 创建随机数的代码。我还有一个使用 ping 执行此操作的程序。一年多前，我为一个班级项目做了这件事。它所做的只是在和地址上运行 traceroute，它占用 ms 次中最小的 sig 数字。它在获取随机数方面效果很好，但我真的不知道它与真正的随机数有多接近。

这是我运行它时得到的 8 个数字的列表。

455298558263758292242406192

506117668905625112192115962

805206848215780261837105742

095116658289968138760389050

465024754117025737211084163

995116659108459780006127281

814216734206691405380713492

124216749135482109975241865

#include <iostream>
#include <string>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <fstream>

using namespace std;

int main()
{
system("traceroute -w 5 www.google.com >> trace.txt");

string fname = "trace.txt";
ifstream in;
string temp;

vector<string> tracer;
vector<string> numbers;

in.open(fname.c_str());
while(in>>temp)
tracer.push_back(temp);

system("rm trace.txt");

unsigned index = 0;

string a = "ms";
while(index<tracer.size())
{
if(tracer[index]== a)
numbers.push_back(tracer[index-1]);
++index;
}


std::string rand;

for(unsigned i = 0 ; i < numbers.size() ; ++i)
{
std::string temp = numbers[i];
int index = temp.size();
rand += temp[index - 1];
}

cout<<rand<<endl;

return 0;

}

Answer 22

很简单，由于网络遵循规定的规则，结果不是随机的。

网络摄像头的想法听起来（有点）合理。Linux 人员通常建议仅使用未连接麦克风的声卡中的随机噪声。

Answer 23

这是我的建议：

1-选择离您所在位置尽可能远的网站。例如，如果您在美国，请尝试一些其服务器 IP 位于马拉西亚、中国、俄罗斯、印度等的网站。流量大的服务器比较好。

2-在您所在国家/地区的高互联网流量期间（在我的国家/地区，大约是晚上 7 点到 11 点）多次 ping 这些网站，获取每个 ping 结果（仅使用整数值）并计算其模数 2（即从每个 ping 操作中，您会得到一位：0 或 1）。

3-重复这个过程几天，记录结果。

4- 收集从所有 ping 中获得的所有位（可能您将获得数十万位）并从中选择您的位。（也许你想通过使用上面提到的相同方法的一些数据来选择你的位:)）

小心：在你的代码中你应该检查超时..等