使用ping到伪随机select的IP地址可以生成一个真正的随机数字吗?

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

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

随后没有人会把他们的声誉放在争议上来争辩或反对。

任何人都在意支持或反对。 如果是这样的话,那么可以如何实施呢?

我会把我的代表线(至less,每downvote 2点)。

没有。

您的networking上的恶意机器可能会使用ARP欺骗(或许多其他技术)来拦截您的ping并在一段时间后回复它们。 那么他们不仅会知道你的随机数字是什么,而且会控制它们。

当然,还有一个问题就是你的本地networking是如何确定性的,所以它可能不像实践中那么容易。 但是,既然你没有从互联网上ping随机IP的好处,你也可以从以太网stream量中抽取熵。

从附属于您的机器的设备中绘制熵是一个研究得很好的原则,各种设备和测量方法的优缺点可能会从执行/ dev / random中被盗取。

[ 编辑 :作为一般原则,当工作在安全的基础(和大量的真正的随机数据的唯一的实际需要是安全相关的),你必须假设一个非常资源充足,坚定的攻击者将尽其一切破坏你的系统的能力。

为了实际的安全性,你可以假定没有人想要你的PGP密钥,并且为了安全而牺牲成本。 但是,当发明algorithm和技术时,你需要给予他们最有可能面对的最强安全保证。 既然我可以相信某个人在某个地方可能需要别人的私人钥匙,build立这样的工具箱来打败你的build议,我不能接受它作为当前最佳实践的进步。 AFAIK / dev / random跟一个便宜的家用电脑上真正的随机数据的最佳实践相当接近]

[ 另一个编辑 :它在评论中提出:(1)任何TRNG都可以影响物理过程,(2)安全问题不适用于此。

对(1)的回答是,在任何现实的硬件上都可以比ping响应时间做得更好,并且可以更快地收集更多的熵,这个提议是不可行的。 用CS术语来说,显然你不能在确定性的机器上产生随机数,这就是引发这个问题的原因。 但是在CS中,任何外部inputstream的机器都是非确定性的,所以如果我们谈论的是ping,那么我们并不是在谈论确定性机器。 因此,观察真实机器的真实input是合理的,并将其视为随机性的来源。 无论你的机器是什么,原始的ping时间在可用的源代码列表中都不高,所以可以排除它们,然后再担心好的程序。 假设一个networking没有被破坏是一个比假设你自己的硬件没有被破坏更大(也是不必要的)的假设。

(2)的答案是哲学的。 如果你不介意你的随机数具有可以随机select的属性,那么这个提议是可以的。 但这不是我所理解的“随机”这个词。 只是因为有些不一致并不意味着它是随机的。

最后,按照要求解决提议的实现细节:假设您接受ping时间为随机,您仍然不能使用未处理的ping时间作为RNG输出。 你不知道它们的概率分布,而且它们当然不是均匀分布的(这通常是人们从RNG中得到的)。

所以,你需要决定你愿意依靠多less比特的熵。 熵是一个随机variables的精确定义的math性质,它可以合理地被认为是它实际上是如何“随机”的度量。 在实践中,你会发现一个你感到满意的下界。 然后将多个input散列在一起,并将其转换为输出的小于或等于input的总依赖熵的多个比特。 “总数”并不一定意味着总和:如果input是统计独立的,那么它就是总和,但是这对于ping来说不太可能,所以你的熵估计的一部分就是考虑相关性。 这个哈希操作的复杂大姐被称为“熵收集器”,所有好的操作系统都有一个。

如果您使用数据来种子PRNG,而PRNG可以使用任意大的种子input,那么您不必散列,因为它会为您做。 如果你想知道你的种子价值是如何“随机的”,你仍然必须估计熵 – 你可以使用世界上最好的PRNG,但是它的熵仍然受到种子熵的限制。

随机数字太重要了,以至于没有机会。

或外部影响/操纵。

简短的回答

使用ping时序数据本身并不是真正的随机数据,但是它可以作为一个熵源,然后用来生成真正的随机数据。

更长的版本

ping时间有多随意?

networking运营(如ping)的计时数据本身并不是均匀分布的。 (而select随机主机的想法是不实际的 – 很多根本不会响应,主机之间的差异可能是巨大的,响应时间范围之间的差距 – 考虑卫星连接)。

然而,虽然时间不会很好,但数据中会有一定程度的随机性。 或者换句话说, 信息熵是存在的。 把定时数据input一个随机数发生器来播种它是一个好主意。 那么熵是什么水平呢?

对于大约50ms的networking计时数据,测量精确到0.1ms,传播值为2ms,你有大约20个值。 舍入到2(16 = 2 ^ 4)的最近幂,每个定时值有4位熵。 如果是用于任何types的安全应用(如生成encryption密钥),那么我会保守,说每个阅读只有2或3比特的熵。 (请注意,我在这里做了一个非常粗略的估计,并忽略了攻击的可能性)。

如何生成真正的随机数据

对于真正的随机数,你需要将数据发送到/ dev / random的行中,这些数据将收集熵,在数据存储中分发(使用某种散列函数 ,通常是安全 函数 )。 同时熵估计值增加。 所以对于一个128位的AES密钥,在熵池有足够的熵之前需要64个ping时间。

为了更加强大,您可以添加来自键盘和鼠标使用,硬盘响应时间,主板传感器数据(如温度)等的时序数据。它增加了熵收集的速度,并使攻击者难以监控所有来源的熵。 事实上,现代系统也是如此。 MS Windows熵源的完整列表在本文的第二评论中列出。

更多的阅读

为了讨论(计算机安全)对随机数发生器的攻击,以及devise一个密码安全的随机数发生器,你可能会比阅读布鲁斯·施奈尔 ( Bruce Schneier)和约翰·凯尔西(John Kelsey)的亚略(yarrow)论文更糟糕。 (Yarrow被BSD和Mac OS X系统使用)。

没有。

拔下网线(或/etc/init.d/networking stop ),熵基本上降为零。

在正在执行ping的计算机上执行拒绝服务攻击,并且还会得到可预测的结果(ping超时值)

我想你可以。 有几件事要注意:

  • 即使对随机IP地址进行ping操作,前几跳(从ISP到ISPnetworking中的第一个真正的L3路由器)对于每个数据包也是一样的。 即使您在第一个存在点的数据中心中ping某些内容,这也会使往返时间下限。 所以你必须小心时间的正常化,往返有一个下限。
  • 您还必须小心networking中的stream量整形。 路由器中典型的漏桶实施每M微秒释放N个字节,这有效地扰乱了您的时间到特定的时隙,而不是一个连续的时间范围。 所以你可能需要丢弃时间戳的低位。

但是我不同意商品硬件中熵不好的前提。 过去几年的许多x86芯片组都包括随机数发生器。 我熟悉的那些使用相对敏感的ADC来测量芯片上两个不同位置的温度,并将其减去。 这个温度差的低阶位可以显示(通过卡方分析)是强烈随机的。 当你增加系统的处理负载时,总体温度上升,但是死亡的两个区域之间的差异仍然是不相关和不可预测的。

在我看到的商品硬件上,随机性的最佳来源是一个从他的摄像头中删除了一个filter或者其他东西的人,把不透明的胶粘在镜头上,然后能够很容易地检测到来自撞击CCD的宇宙射线的单个白色像素。 这些都尽可能接近完全随机,并通过量子效应保护外部窥探。

好的随机数发生器的一部分就是所有数的概率都是n – >无穷。

因此,如果您计划生成随机字节,那么从良好的rng中获得足够的数据,则每个字节应该具有相等的返回概率。 此外,在某些数字被归还的情况下,不应出现任何模式或可预测性(某些时间段内出现概率高峰)。

我不太清楚使用ping你将测量得到随机variables,是响应时间? 如果是这样,你可以肯定的是,一些响应时间或响应时间的范围将比其他响应时间更频繁,因此会造成一个潜在的不安全的随机数发生器。

如果你想要商品硬件,你的声卡应该差不多了。 只需调高模拟input的音量,便可获得便宜的白噪声源。 便宜的随机性,而不需要networking。

测量东西来产生一个随机的种子似乎是一个很好的方法。 O'Reilly的“ 实用的Unix和互联网安全 ”( Practical Unix and Internet Security)给出了一些确定随机种子的其他方法,例如要求用户键入一些击键,然后测量击键之间的时间。 (该书指出,这种技术被PGP用作随机性的来源。)

我想知道一个系统CPU的当前温度 (测量出多less位小数)可能是一个随机种子的可行组成部分。 这种方法具有不需要访问networking的优点(所以当networking连接断开时,随机生成器不会变得不可用)。

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

它不如使用大气噪声,但它仍然是真正的随机,因为它取决于networking的特点是臭名昭着的随机不可重复的行为。

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

这是一个实现的尝试:

 @ips : list = getIpAddresses(); @rnd = PseudorandomNumberGenerator(0 to (ips.count - 1)); @getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime } 

在信任往返ping作为熵之前,我会尽早使用像ISAAC这样的更强大的PRNG。 正如其他人所说的那样,对于某个人来说,不仅仅是猜测你的数字,还可能在不同程度上控制它们。

其他伟大的熵源存在,其他人已经提到。 一个没有提到的(这可能是不实际的)是从车载audio设备采样噪声..即使没有麦克风连接,通常会有点吵。

我进行了9轮试图为我正在写的客户机/服务器RPC机制提供强大(快速)的PRNG。 双方有一个相同的密钥,由1024行32个字符的密码组成。 客户端会发送AUTH xx,服务器会返回AUTH yy ..双方都知道用哪个密钥生成blowfish秘密(+ salt)。 然后,服务器将发送一个SHA-256摘要(encryption),客户端知道它正在与具有正确密钥的东西交谈。会话继续。 是的,对于中间人来说,保护非常薄弱,但是公共密钥是不可能被使用的。

所以,你有一个非阻塞服务器,必须处理多达256个连接。不仅PRNG必须强大,它必须是快速的。 使用较慢的方法来收集客户端的熵并不是一件很困难的事情,但是这在服务器中是不能提供的。

所以,我不得不问你的想法..它将有多实用?

没有math计算可以产生一个随机的结果,但在“现实世界”的计算机不只是紧缩的数字… …有一点点的创造力,应该有可能产生随机结果的那种没有已知的方法复制或预测确切的结果。

我见过的最容易实现的想法之一是在所有系统上普遍使用的方法是使用来自计算机声卡线路/静音端口的静态。

其他想法包括热噪声和高速caching线的低电平时序。 许多具有TPM芯片的现代个人电脑已经拥有encryption质量的硬件随机数发生器。

我的膝盖反应平(特别是如果使用ICMP)是你的作弊太bladerly。 在这一点上,你也可以甩出一个盖格计数器,并使用背景辐射作为随机源。

是的,这是可能的,但是…恶魔的细节。

如果你打算产生一个32位的整数,你需要收集大于32位的熵(并且使用足够的混合函数来获得熵的传播,但这是已知的和可行的)。 最大的问题是:

平时有多less熵?

这个问题的答案取决于对networking和攻击模型的各种假设,在不同情况下有不同的答案。

如果攻击者能够完全控制ping时间,那么每ping命令就会得到0比特的熵,无论你多less混合,你都不能总共得到32比特的熵。 如果他们对ping时间的控制不够完善,你会得到一些熵,并且(如果你不高估你所收集的熵的数量)会得到完全随机的32位数。

您可以使用XKCD方法:

随机数发生器

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

随机是,如果没有人能预测下一个状态。

虽然我不能明确地站点赞成或反对,这个实施有它的问题。

这些IP地址是从哪里来的,如果是随机select的,当他们没有回复或迟到回复时会发生什么,这是否意味着随机数字会慢慢出现。

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

这并不是我随意性的一个很好的来源。

你会用什么度量标准 – 显而易见的是响应时间,但是你可以合理预期的数值范围很小:几十毫秒到几千个。 响应时间本身将遵循一个钟形曲线,而不是随机分布在任何时间间隔(你将如何select间隔?),所以你将不得不尝试从数字中select一些“随机”位。

LSB可能会给你一个随机比特stream,但是你不得不考虑时钟粒度问题 – 也许由于中断的工作原理,在某些系统上总会得到2ms的倍数。

有可能有更好的“有趣的”方式获得随机位 – 也许谷歌随机单词,抓住第一页,并select页面的第N位。

呃,我发现这样的问题很快就引起了对“真正随机”的意义的讨论。

我认为,测量ping将产生质量好的随机数据,但是速度不够快(除非你愿意做一些严重的DDOS)。

而且我没有看到它比测量计算机的模拟/机械特性,或者肉袋操作它的行为更加随机。

(编辑)在一个实际的说明,这种方法打开你的networking上的人操纵你的“随机”号码发生器的可能性。

在我看来,真正的随机性是无法言喻的 – 没有办法知道一个序列是不是随机的,因为根据定义,无论多么不可能,它都可以包含任何东西 。 保证一个特定的分布模式降低了随机性。 “模式”这个词有点意思。

  I MADE UA RANDOM NUMBER BUT I EATED IT 

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

问“如果我把他们build立在平台上,我的价值是多么的随意?” 实际上是在问“ping是多么随意?”。 您可以通过收集足够多的数据(例如1百万坪)来估计,并及时地绘制其分布曲线和行为。 如果分布是平坦的,行为难以预测,那么数据似乎更加随机。 更不平衡的分布或可预测的行为表明随机性较低。

您还应该考虑样本分辨率。 我可以想象,结果在某种程度上被舍入到了一个毫秒,所以对于你可以有0到500之间的整数值。这不是很多的分辨率。

在实践方面,我会build议反对它,因为ping可以被预测和操纵,进一步减less它们的随机性。

一般来说,我build议不要“自己动手”随机生成器,encryption方法和哈希algorithm。 看起来似乎很有趣,但其中大部分是非常恐怖的math。

至于如何构build一个非常好的熵发生器 – 我想这可能是一个密封的盒子,输出一些primefaces级或次级primefaces级的交互结果。 我的意思是,如果你使用的是熵的来源,敌人也可以很容易地阅读,他只需要找出你的algorithm。 任何forms的连接都是一个可能的攻击媒介,所以你应该把熵的来源放在尽可能靠近服务的地方。

我有一些代码可以用traceroute创build随机数字。 我也有一个使用ping的程序。 一年前我做了一个class级项目。 它所做的只是运行跟踪路由和地址,并且占用ms次数的最小信号位。 它在得到随机数字方面工作得很好,但我真的不知道它与真正的随机数有多接近。

这是我运行它时得到的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; } 

很简单,因为networking服从规定的规则,结果不是随机的。

摄像头的想法听起来(略)合理。 Linux的人们通常build议只使用没有麦克风的声卡的随机噪音。

这里是我的build议:

1-select尽可能远离您所在位置的网站。 例如,如果你在美国尝试一些网站,有他们的服务器IP在马来西亚,中国,俄罗斯,印度..等等。 高stream量的服务器更好。

2-在你国家高速互联网stream量的时候(我国就是像晚上7点到11点)多次ping多个网站,拿每个ping结果(只用整数值)计算它的模数2从每个ping操作你得到一个位:0或1)。

3-重复几天的过程,logging结果。

4-收集你从你所有的ping(你可能会得到成千上万的位)所有的位,并从他们中select你的位。 (也许你想通过使用上面提到的同样的方法来select一些数据:))

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