什么是随机数生成最安全的种子?

什么是种子随机数发生器的最安全的熵源? 这个问题是独立于语言和平台的,适用于networking上的任何机器。 理想情况下,我正在寻找在托pipe公司提供的云环境或服务器中的机器可用的来源。

要牢记两个重要的弱点。 使用时间发送随机数字发生器违反了CWE-337 。 使用小的种子空间将违反CWE-339 。

这里有一些想法。 如果你不耐烦,最后跳到结论。

1.什么是安全种子?

安全性只是相对于攻击模式定义的。 我们在这里需要一个n比特的序列,对于攻击者来说有n比特的熵:简而言之,从攻击者的angular度来看,该序列的任何可能的2 n个值是同等可能的。

这是一个涉及攻击者可用信息的模型。 生成和使用种子的应用程序(通常在PRNG中)知道确切的种子; 种子是否“安全”不是种子的绝对属性,甚至不是种子生成过程的绝对属性。 重要的是攻击者对生成过程的信息量。 这种信息水平因情况而异, 例如在一个多用户系统上(比如类Unix,硬件强制分离应用程序),内存访问的精确时间可以揭示关于名义上受保护的进程如何读取内存的信息。 即使是远程攻击者也可以获取这些信息; (在实验室条件下)AESencryption(典型的AES实现使用内部表,访问模式取决于密钥;攻击者强制caching未命中,并通过服务器响应的精确时间检测)。

种子寿命必须考虑在内。 种子是安全的,只要攻击者不知道; 此属性必须事后保持。 特别是不可能从随后的PRNG产出摘录中恢复种子。 理想情况下,即使在某个时刻获得完整的PRNG状态,也不能提供PRNG预先生成的任何位。

我想在这里指出的是,种子只有在可以保持安全的情况下使用时才是“安全的”,这或多或less地意味着密码安全的PRNG和一些防篡改存储。 如果这样的存储是可用的,那么最安全的种子是很久以前生成一次的种子,并被用在由防篡改硬件托pipe的安全PRNG中。

不幸的是,这样的硬件是昂贵的(它被称为HSM,花费几百或几千美元),而且这种花费通常很难certificate是合理的(一个糟糕的种子不会妨碍系统运行;这是通常的不可testing性问题的安全)。 因此习惯上去“主要是软件”解决scheme。 由于软件不擅长提供长期的保密存储,因此种子寿命被任意缩短:定期获得新的种子。 在Fortuna中 ,这样的重新播种应该至less每兆字节产生一次伪随机数据。

综上所述,在没有HSM的情况下,安全种子是一种可以相对容易地获得的种子(因为我们会经常这样做)使用攻击者无法收集到的数据。

2.混合

随机数据源不会产生很好的统一比特(每个比特的值为1,概率正好为0.5 ,比特值彼此独立)。 相反,随机源在特定于源的集合中生成值。 这些值可以被编码为比特序列,但是你没有得到你的钱值得:有n比特的熵你必须有值,当编码时,使用多于n比特。

这里使用的encryption工具是一个PRF ,它接受任意长度的input,并产生一个n位输出。 这种types的密码安全PRF被build模为随机预言器 :简而言之,预测给定input上任何有关预言input而不尝试它的计算是不可行的。

现在,我们有散列函数 。 哈希函数必须满足一些安全属性,即对preimages,第二preimages和碰撞的抵抗。 我们通常通过尝试查看它们如何偏离随机预言模型来分析哈希函数。 这里有一个重点:一个遵循随机预言模型的PRF将是一个很好的散列函数,但是可以有很好的散列函数(对preimages和collisions有抵抗力),然而它很容易与随机预言区分开来。 特别是, SHA-2函数(SHA-256,SHA-512 …)被认为是安全的,但由于“长度扩展攻击”(给定h(m))而偏离随机预言模型,可能在不知道m 情况下为部分受限消息m'计算h(m || m' )。 长度扩展攻击似乎没有提供任何快捷方式来创buildpreimages或冲突,但它表明,这些哈希函数不是随机的神谕。 对于SHA-3竞赛 ,NIST表示,候选人不应该允许这样的“长度延长”。

因此,混合步骤并不容易。 现在,您最好的select是使用SHA-256或SHA-512,并在select时切换到SHA-3(这应该在2012年左右发生)。

3.来源

计算机是确定性的机器。 为了获得一些随机性,你必须混合物理世界的一些措施的结果。

一个哲学笔记:在某些时候,你必须相信一些聪明的人,那些可能穿实验室外套或得到报酬做基础研究。 当你使用SHA-256这样的哈希函数时,实际上你信任了一大堆密码学家,他们告诉你:我们查找漏洞,真的很难,好几年,没有发现。 当你用盖革计数器使用放射性物质时,你相信一些物理学家说:我们很难预测下一个primefaces核何时会熄灭,但是我们什么也没有发现。 请注意,在这个具体情况下,“物理学家”包括贝克勒尔,卢瑟福,玻尔或爱因斯坦等人,而“真正的困难”则意味着“一个多世纪的积累的研究”,所以在这里你并不完全没有受到影响。 然而,对安全仍有一点信心。

一些计算机已经包括产生随机数据的硬件(即,使用和测量物理过程,就物理学家而言,它足够随机)。 威盛C3(一个兼容x86的CPU)具有这样的硬件。 奇怪的是,30年前的家用计算机Commodore 64也有一个硬件RNG(至less维基百科是这样说的)。

除了特殊的硬件,你必须使用任何你可能得到的物理事件。 通常情况下,您可以使用击键,传入的以太网数据包,鼠标移动,硬盘访问…每个事件都带有一些数据,并在一个可测量的瞬间(现代处理器具有非常精确的时钟,由于周期计数器)发生。 那些时刻和事件数据内容可以被累积为熵源。 操作系统本身(可直接访问硬件)比应用程序要容易得多,因此收集种子的正常方式是询问操作系统(在Linux上称为/dev/random/dev/urandom [都有优点和问题,select你的毒药];在Windows上,调用CryptGenRandom() )。

一个极端的例子是1.2之前的Java小应用程序,在添加java.security.SecureRandom之前; 由于Java在将应用程序代码与硬件隔离方面非常有效,因此获取随机种子是一项艰巨的挑战。 通常的解决scheme是让两个或三个线程同时运行并且疯狂地进行线程切换,以便每秒线程切换的次数是随机的(实际上,这试图通过OS调度器动作的时间提取随机性,关于机器上还发生了什么,包括与硬件相关的事件)。 这是相当不满意的。

与时间有关的措施的一个问题是攻击者也知道什么是当前时间。 如果攻击者可以访问机器,那么他也可以读取循环计数器。

有些人build议通过将放大器设置为最大(即使现在的服务器都有audio)来使用声卡作为“白噪声”的来源。 其他人则认为,为摄像头供电(我们知道,摄像头video是“嘈杂的”,即使networking摄像头面对墙壁,这对随机性也很好)。 但带有摄像头的服务器并不常见。 您也可以ping外部networking服务器(例如www.google.com )并查看返回所花费的时间(但可能会被攻击者监视networking)。

具有散列函数的混合步骤的美妙之处在于,熵只能累积; 即使数据不是随机的,添加数据也没有什么坏处。 只要尽可能通过散列函数的东西。 散列函数非常快(一个好的SHA-512实现将在一个典型的PC上使用一个单核来处理超过150MB / s),而播种不会经常发生。

4。结论

使用HSM 。 他们花费数百或数千美元,但是不是你的秘密值得比这更多? 一个HSM包括RNG硬件,运行PRNGalgorithm,并存储种子篡改抵抗。 而且,大多数HSM已经通过各种国家法规(例如美国的FIPS 140和欧洲的EAL水平)的authentication。

如果你这么便宜,你不会购买一个HSM,或者如果你想保护实际上不是很有价值的数据,那么使用通过散列许多物理措施获得的种子build立一个密码安全的PRNG。 任何来自某些硬件的数据都应该散列,以及获取数据的瞬间(读“循环计数器”)。 你应该在这里以兆字节散列数据。 或者更好的是, 要这样做:只需使用由您的操作系统提供的已经包含这样的代码的工具。

最安全的种子是具有最高级别的熵(或者不能被预测的大部分比特)。 时间通常是一个糟糕的种子,因为它有一个小的熵(例如,如果你知道交易发生的时间,你可以猜测时间戳在几个比特内)。 硬件熵源(例如来自衰变过程)是非常好的,因为它为每一个种子产生一个熵位。

通常硬件资源对于大多数需求来说是不切实际的,所以这会导致您依赖于混合一些低质量的熵源来产生更高的熵源。 通常这是通过估计每个采样的熵位数然后收集足够的采样使得熵源的search空间足够大以至于攻击者search不切实际(128位是一个好的经验法则)。

您可以使用的一些来源是:当前时间(以微秒为单位)(取决于分辨率,通常是非常低的1/2熵,以及攻击者是多么容易猜测),UI事件的到达时间等。

操作系统资源(如/ dev / random)和Windows CAPI随机数生成器通常提供这些低熵源的预混合来源,例如Windows生成器CryptGenRandom包括:

  • 当前进程ID(GetCurrentProcessID)。
  • 当前的线程ID(GetCurrentThreadID)。
  • 自引导时间(GetTickCount)开始的滴答计数。
  • 当前时间(GetLocalTime)。
  • 各种高精度性能计数器(QueryPerformanceCounter).-
  • 用户环境块的MD4哈希,包括用户名,计算机名称和searchpath。 […] –
  • 高精度内部CPU计数器,如RDTSC,RDMSR,RDPMC

一些PRNG具有内置策略,允许从低质量来源混合熵来产生高质量的结果。 一个非常好的发电机是Fortuna发电机。 它特别使用策略来限制任何熵源被破坏的风险。

最安全的种子是一个真正的随机的种子,你可以在今天的实际计算系统中使用,以降低的置信度列出:

  • 特殊的硬件
  • 您的操作系统提供的设备可以捕获磁盘读取和鼠标移动(/ dev / random)等混乱事件。 在这个“捕捉不可预知的事件”的线上的另一个select是使用一个独立的进程或机器来捕获它发生的情况作为一个熵池,而不是操作系统提供的“安全”随机数发生器,例如,见EntropPool
  • 使用糟糕的种子(即时间),并将其与其他只有你自己知道的数据结合起来(例如,用一个秘密和一些其他标准(如PID或应用程序/操作系统的内部状态)来散列时间,所以它不会必然按时间增减)

作为一个有趣的一次性垫子,每当我从事间谍活动,我有一个系统,我只需要传达几个字母。 比如说,我最后一次向大芬威克公国出售秘密计划build立烤面包机时,我只需要低声说:

enonH

我的同伙 她知道要获得http://is.gd/enonH- (这是一个“安全的”扩展器URL,它将把你带到is.gd展开页面,然后指向一个完整的青蛙SFW图像)。 这给了我们409k的一次性键盘,或者如果我在耳语“enonH”的时候眨眼睛 – 她知道把图像的哈希值作为下一次传输的解码密钥。

由于JPEG图像中的压缩,它们往往是相对较好的熵源,如ent所报道的:

$ ent frog.jpg
熵=每个字节7.955028比特。

最佳压缩将使这个51092字节文件的大小减less0%。

51092样本的卡方分布为4409.15,随机超过这个数值的百分之零点一。

数据字节的算术平均值是129.0884(127.5 =随机)。
Pi的Monte Carlo值是3.053435115(误差2.81%)。
序列相关系数为0.052738(完全不相关= 0.0)。相关系数= 0.0)。

结合我几乎不可能猜到的形象,我指示她和我的秘密烤面包机计划是安全的人。

答案是Linux机器上的/dev/random 。 这与“真实”随机数生成器非常接近,如果熵池干燥, 可以通过PRNG生成/dev/urandom 。 以下引用来自Linux内核的random.c这整个文件是一个美丽的阅读,大量的意见。 它的自己的代码是从PGP采用的。 它的美是不受C的约束的,C是以访问者包装的全局结构为标志的。 这是一个简单的敬畏鼓舞人心的devise。

这个例程收集来自设备驱动程序等的环境噪声,并返回适合encryption使用的好随机数。 除了显而易见的encryption用途之外,这些数字对于播种TCP序列号以及其他希望具有不仅是随机的,而且很难由攻击者预测的数字的地方也是有利的。

操作理论

计算机是非常可预测的设备。 因此,这是非常困难的
在计算机上产生真正的随机数字—而不是
伪随机数,这可以很容易地通过使用一个
algorithm。 不幸的是,攻击者很容易猜测伪随机数生成器的序列,以及一些伪随机数生成器的序列
这是不可接受的应用程序。 相反,我们必须从计算机环境中收集“环境噪音”,这对于外部攻击者来说是难以观察的,并用它来产生随机数。 在Unix环境下,最好从内核完成。

来自环境的随机来源包括键盘间键盘
定时,来自某些中断的中断时间,以及(a)非确定性和(b)外部观察者难以测量的其他事件。 来自这些来源的随机性被添加到“熵池”中,其使用类似CRC的函数混合。 这不是密码强的,但假设随机性不被恶意select是足够的,并且足够快以至于在每个中断上进行这种操作的开销是非常合理的。 随机字节被混合到熵池中,例程保持随机数发生器内部状态存储了多less位随机性的估计。

当需要随机字节时,它们通过采用SHA获得
“熵池”内容的散列。 SHA哈希避免了暴露熵池的内部状态。 相信在计算上不可能从其输出中导出关于SHAinput的任何有用的信息。 即使有可能以某种巧妙的方式分析SHA,只要从发生器返回的数据量小于固有熵
池,输出数据是完全不可预知的。 由于这个原因,例行程序减less了熵输出中包含“真随机性”多less比特的内部估计,因为它输出随机数。 如果这个估计值为零,程序仍然可以产生随机数; 然而,攻击者可能(至less在理论上)能够根据先前的输出来推断发电机的未来输出。 这需要SHA的成功的密码分析,这被认为是不可行的,但是有一个遥远的可能性。 尽pipe如此,这些数字对绝大多数目的都是有用的。

写一个互联网广播客户端,使用广播中的随机样本。 有几个站的池可供select和/或回落。

如果你读了密码理论,很明显最安全的种子将是一个由混沌事件产生的种子。 在最近的历史中,秘密行动已经利用了被称为“一次性垫”的事实,这被certificate是不可能破解的。 通常情况下,这些都是通过散布在无处不在的大气哨所的各种各样的产生。 大气噪声足够混乱,被认为是随机的。 这种方法的主要问题是一次性物stream的物stream是相当可观的。

我对你的build议是find一个足够混乱的事件来从中提取数据。

詹姆斯是对的。 另外,还有可以购买的硬件,它会给你随机的数据。 不知道我在哪里看到它,但我想我读了一些声卡附带这样的硬件。

您也可以使用http://www.random.org/

好的,假设客户端需要一个强大的种子,并且您正在使用云计算,这里是一个解决scheme,对于一些硬件随机数生成器,您可以在这里查看:

http://en.wikipedia.org/wiki/Hardware_random_number_generator

所以,这假设每个客户端都有一个公钥/私钥对,服务器知道每个客户端的公钥。 要生成密钥,您可以使用类似于PGP所做的一些事情,一开始您可以将键击之间的时间差别视为某种types,因为这是不可猜测的。

所以,客户提交一个随机数的请求。 服务器使用硬件生成器,使用公钥对其进行encryption,并用服务器的私钥对其进行签名。 然后客户端可以validation它来自哪里,然后对其进行解密。

这将确保您可以生成一个随机数并以安全的方式将其传回。

更新:

你最好的select是看计算机编程艺术或任何数值方法书,或者看看布鲁斯·施奈尔写的东西,比如这些链接: http : //www.schneier.com/blog/archives/2006/ 06 / random_number_g.html http://www.cryptosys.net/rng_algorithms.html http://www.schneier.com/blog/archives/2006/06/random_number_g.html http://www.schneier.com/blog /archives/2006/06/random_number_g.html关于软件中随机数生成的build议, ftp: //ftp.rsasecurity.com/pub/pdfs/bull-1.pdf

你也可以看看有Crypto ++这一代,或者至less看看魏岱是怎么做的, http://www.cryptopp.com/

Random.org提供了一个真正的随机数字发生器networking服务 ,由大气噪声“播种”。

你每天可以免费获得20万个随机位,最多可达100万个随机位,之后你应该把自己的账户加起来,每个美元便宜400万比特。

4 – 非常随机掷骰子select。 🙂

如果没有额外的随机硬件可用,简单的解决方

使用毫秒,mouseX和mouseY来生成一个种子。

由于密码学的共识是强硬的随机数必须从硬件派生。 一些处理器具有这种function(英特尔芯片在其他)。 声卡也可以通过测量广告转换器中的低位波动来使用。

但是由于硬件的需要,没有语言和平台独立的答案。 几乎任何更大的操作系统都将支持安全的随机数字。 实现一个好的随机数生成器也是很难的,因为你必须跟踪池中剩余的熵。

所以第一步是确定你将使用什么语言。 有些确实拥有强大的随机数支持 – 如果情况并非如此,那么您将不得不抽象这一代来调用与平台相关的随机数据源。

根据您的安全需求,对“在线”消息来源感到厌倦,因为中间人可能会对未经validation的在线消息来源构成严重威胁。

你最安全的方法将来自大自然。 也就是说,发生在您的计算机系统之外的事情,超出了我们预测其模式的能力。

例如,许多研究人员使用密码安全的PRNG将使用放射性衰变作为模型,其他人则可能考虑分形,等等。 现在有创build真正的RNG的手段

我最喜欢的PRNG实现方式之一是用户与计算机交互。 比如,这个职位不是我过去一系列职位的前瞻性工程所能预先确定的。 我把鼠标放在屏幕上的地方非常随意,它所做的线索也是随机的。 从用户交互看。 滥用提供特定input的手段,使得产生特定的数字可以通过使用用户input的“群体”并计算它的“vector”来减轻,只要你的系统中没有每个用户都是夏娃,那么你应该没事。 这不适用于许多应用程序,因为您的数字池与用户input成正比。 实施这可能有它自己的问题。

对RNG感兴趣的人已经做了如下的事情:

  1. 使用networking摄像头,无论在屏幕上的随机闪烁散列,当这辆卡车经过,这是所有的随机数据。
  2. 如前所述,辐射
  3. 大气层
  4. 用户交互(如上所述)
  5. 系统 EDG中发生了什么事情 。

安全的种子来自大自然。

编辑:根据你在做什么,我可能会build议使用你的云服务器的EDG的聚合。

首先,您需要定义随机数发生器的实际使用/用途,您为什么认为必须通过如此高的安全标准? 我问的原因是你提到从可能性中挑选它 – 如果你确实是为了安全目的而使用它,那么确保源和通道发送出去比任何人的学术挑选要重要得多。

第二个元素是你需要的实际随机数的大小 – 大的种子是好的,但只有当生成的数字也很大 – 否则你只会读取生成的数字的一小部分,这会增加你的风险。

研究可重构的密码,而不是SHA或AES之类的东西。 这里有2篇研究论文,如果你想阅读和validation他们的工作方式和原因:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.6594&rep=rep1&type=pdf http://www.springerlink.com/index/q29t6v1p45515186.pdf

或者抓取你在网上find的任何可重新configuration的GOST密码源代码,然后给它提供任何基本的种子(如串联的“ticker”加上一个web服务器节点ID(如果它在网上农场中),加上部分响应任何时候都会改变最新消息的互联网新闻网站,或者你可以给它高度控制的初始种子(你可以自己做),并使用一个轻的伪随机序列来select进一步的密码configuration,即使是国家安全局也不能打破一:-)因为它总是一个不同的密码。 对于实际的encryption目的,实际上必须使用非常受控的初始种子才能够复制validation的序列。 这就是我们回到第一项的地方 – 确保资源和分配。

使用random.org他们声称提供真正的随机数字给互联网上的任何人 ,他们也有一个HTTP API,你可以使用。 他们提供免费和付费服务。

免责声明:我不以任何方式隶属于random.org

在Linux中,答案是/ dev / random(在Windows中,我认为equivallent被称为CryptGenRand)。

但是,在云环境中,/ dev / random可能会被严重耗尽,并且可能没有足够的熵来回答您的请求。

为了解决这个问题,我们公司正在开发一种真正的随机数发生器,可以同时为数以千计的服务器和虚拟机提供很好的随机数(量子起源)。 如果设备安装在您的云数据中心的局域网中,您所需要的就是我们的deamon在您的机器上运行。 这个deamon监视/ dev /随机熵级别,并且当需要熵向设备请求时(通过networking)并且将接收到的随机数据放入内核的熵池中。

如果您想了解更多关于我们解决scheme的信息,请访问我们的网站(www.sqrtech.com)或通过info@sqrtech.com与我们联系。

朱利安

你可以赚取放射性衰变产生的随机数字。 听起来有点奇怪,但你得到真正的随机数字。

放射性衰变

另一篇文章

这是一个猜测! 如果我错了,请encryptionencryption

此时,UUID / GUID的官方algorithm将返回通过encryption哈希函数运行的结果 – 它将time,mac addr和计数器等已知信息组成一个UUID / GUID,然后通过encryption散列以确保无法提取mac地址。

我相信你可以把这种情况异或到一个种子所需要的位数上,这样可以很好的保证结果值在你所希望的位数所定义的数字空间上平均分配。 注意我并不是说这是安全的,只是这个操作应该产生一个值,在整个位空间内均匀分布。

(((PI X current thread ID) X current process ID) / tick count) x pi