种子随机数生成器最安全的熵源是什么？此问题与语言和平台无关,适用于网络上的任何计算机.理想情况下,我正在寻找托管公司提供的云环境或服务器中的计算机可用的源.
要牢记两个重要的弱点.使用时间发送随机数发生器违反了CWE-337.使用小种子空间将违反CWE-339.
这里有一些想法.如果你不耐烦,最后跳到结论.
1.什么是安全的种子？
安全性仅相对于攻击模型定义.我们在这里需要一个n比特的序列,对于攻击者而言具有n比特的熵:简单地说,从攻击者的角度来看,该序列的任何可能的2 n值都是同样可能的.
这是一个与攻击者可用信息相关的模型.生成和使用种子的应用程序(通常在PRNG中)知道确切的种子; 种子是否"安全"不是种子的绝对属性,甚至也不是种子生成过程的绝对属性.重要的是攻击者对生成过程的信息量.这种信息水平因情况而异; 例如,在多用户系统(比如类Unix,硬件强制分离应用程序)上,内存访问的精确计时可以揭示名义上受保护的进程如何读取内存的信息.即使是远程攻击者也可以获取此类信息; 这已被证明 (在实验室条件下)关于AES加密(典型的AES实现使用内部表,访问模式取决于密钥;攻击者强制缓存未命中并通过服务器响应的精确计时检测它们).
必须考虑种子寿命.只要攻击者不知道种子就是安全的; 之后这个属性必须成立.特别是,不可能从随后的PRNG输出的摘录中恢复种子.理想情况下,即使在某个时刻获得完整的PRNG状态也不应该提供关于PRNG事先生成的任何比特的线索.
我想在这里提出的观点是,种子只有在它可以保持安全的环境中使用时才是"安全的",这或多或少意味着加密安全的PRNG和一些防篡改存储.如果这样的存储是可用的,那么最安全的种子是已生成的一个一次,很久以前,在由防篡改硬件托管安全PRNG使用.
不幸的是,这种硬件很昂贵(它被称为HSM并且花费数百或数千美元),并且这种成本通常证明难以证明(坏种子不会阻止系统运行;这是通常的不可测试性问题安全).因此习惯于选择"主要是软件"的解决方案.由于软件不擅长提供长期保密存储,因此种子寿命可以任意缩短:定期获得新种子.在Fortuna中,这种重新播种应该至少每兆字节生成一次伪随机数据.
总而言之,在没有HSM的设置中,安全种子是可以使用攻击者无法收集的数据相对容易地(因为我们将经常这样做)获得的种子.
2.混合
随机数据源不会产生漂亮的统一位(每个位的值为1,概率恰好为0.5,并且位值彼此独立).相反,随机源在特定于源的集合中生成值.这些值可以编码为位序列,但是你没有得到你的钱:要有n位熵你必须有值,当编码时,使用的值远远超过n位.
这里使用的加密工具是PRF,它接受任意长度的输入,并产生n位输出.这种加密安全的PRF被建模为随机预言:简而言之,在不尝试的情况下预测给定输入上的oracle输出的任何内容在计算上是不可行的.
现在,我们有哈希函数.散列函数必须满足一些安全属性,即对preimages,第二个preimages和碰撞的抵抗.我们通常通过试图看看它们如何偏离随机预言模型来分析散列函数.这里有一个重点:遵循随机预言模型的PRF将是一个很好的散列函数,但是可以有很好的散列函数(在对前映像和碰撞的抵抗意义上),但它们很容易与随机预言区分开来. .特别是,SHA-2函数(SHA-256,SHA-512 ......)被认为是安全的,但是由于"长度扩展攻击"(给定h(m),它离开了随机oracle模型,它是可以计算h(m || m')对于部分约束的消息m',不知道m).长度扩展攻击似乎没有提供任何创建前映像或冲突的快捷方式,但它表明这些散列函数不是随机的神谕.对于SHA-3比赛,NIST表示候选人不应允许这种"长度延长".
因此,混合步骤并不容易.现在,你最好的选择是使用SHA-256或SHA-512,并在选择时切换到SHA-3(这应该在2012年中期左右).
3.来源
计算机是确定性机器.为了得到一些随机性,你必须混合物理世界的一些测量结果.
一个哲学说明:在某些时候,你必须相信一些聪明的人,那些可能穿实验室外套或获得报酬进行基础研究的人.当你使用像SHA-256这样的散列函数时,你实际上是在信任一群密码学家时告诉你:我们寻找缺陷,真的很难,而且几年来都找不到.当你使用Geiger计数器使用腐烂的放射性物质时,你相信一些物理学家说:我们看起来真的很难预测下一个原子核会什么时候会发生,但我们没有找到.请注意,在这种特殊情况下,"物理学家"包括像贝克勒尔,卢瑟福,玻尔或爱因斯坦这样的人,"真正的努力"意味着"超过一个世纪的累积研究",所以你并不完全处于未受影响的领域.然而,对安全仍有一点信心.
一些计算机已经包括生成随机数据的硬件(即,使用和测量物理过程,就物理学家而言,它是足够随机的).威盛C3(x86兼容CPU系列)有这样的硬件.奇怪的是,30年前的家用电脑Commodore 64也有一个硬件RNG(左右至少是维基百科).
除非使用特殊硬件,否则您必须使用您可能获得的任何物理事件.通常,您将使用击键,传入以太网数据包,鼠标移动,硬盘访问......每个事件都附带一些数据,并且在可测量的瞬间发生(现代处理器具有非常精确的时钟,这要归功于循环计数器).那些时刻和事件数据内容可以作为熵源累积.对于操作系统本身(可直接访问硬件)而言,这比应用程序更容易,因此收集种子的常规方法是询问操作系统(在Linux上,这称为/dev/random或者/dev/urandom[都有优点和问题] ,选择你的毒药];在Windows上,打电话CryptGenRandom()).
一个极端的例子是1.2之前的Java小程序,在添加之前java.security.SecureRandom; 由于Java在将应用程序代码与硬件隔离方面非常有效,因此获取随机种子是一项艰巨的挑战.通常的解决方案是让两个或三个线程同时运行并疯狂地进行线程切换,这样每秒的线程切换次数有些随机(实际上,这会尝试通过OS调度程序操作的时序提取随机性,这取决于关于机器上发生的事情,包括与硬件相关的事件.这非常令人不满意.
时间相关措施的一个问题是攻击者也知道当前时间是多少.如果攻击者具有对机器的应用访问权限,那么他也可以读取循环计数器.
有些人建议通过将放大器设置为最大值来使用声卡作为"白噪声"的来源(即使服务器现在也有音频).其他人主张为网络摄像头供电(我们知道网络摄像头视频"嘈杂",即使网络摄像头面向墙壁,这对随机性也很好); 但是带网络摄像头的服务器并不常见 您还可以ping一个外部网络服务器(例如www.google.com)并查看返回所需的时间(但是这可以通过监视网络的攻击者来观察).
具有散列函数的混合步骤的优点在于熵只能累积; 添加数据没有任何害处,即使该数据不是随机的.通过哈希函数尽可能多地填充.散列函数非常快(一个好的SHA-512实现将在典型的PC上使用单个核处理超过150 MB/s)并且通常不会发生播种.
4.结论
使用HSM.它们花费了几百或几千美元,但这不是你的秘密吗？HSM包括RNG硬件,运行PRNG算法,并存储具有防篡改功能的种子.此外,大多数HSM已经获得了各种国家法规的认证(例如美国的FIPS 140和欧洲的EAL水平).
如果你是如此便宜,你不会购买HSM,或者如果你想保护实际上不值得的数据,那么使用通过散列大量物理测量获得的种子建立一个加密安全的PRNG .来自某些硬件的任何东西都应该被散列,以及获得该数据的瞬间(读取"循环计数器").您应该在这里按兆字节哈希数据.或者,更好的是,不要这样做:只使用操作系统提供的设施,其中已包含此类代码.
最安全的种子是具有最高熵水平(或无法预测的大多数位数)的种子.时间通常是一个糟糕的种子,因为它有一个小的熵(即如果你知道交易何时发生,你可以猜到时间戳在几位内).硬件熵源(例如来自衰变过程)非常好,因为它们为每个种子位产生一位熵.
通常硬件源对于大多数需求来说是不切实际的,因此这会导致您依赖混合多个低质量熵源来生成更高的熵源.通常,这是通过估计每个样本的熵位数然后收集足够的样本来完成的,这样熵源的搜索空间足够大,以至于攻击者搜索是不切实际的(128位是一个很好的经验法则) ).
您可以使用的一些来源是:以微秒为单位的当前时间(通常非常低的1/2位,具体取决于分辨率以及攻击者猜测的容易程度),UI事件的到达时间等.
诸如/ dev/random和Windows CAPI随机数生成器之类的操作系统源通常提供这些低熵源的预混合源,例如Windows生成器CryptGenRandom包括:
当前进程ID(GetCurrentProcessID).
当前线程ID(GetCurrentThreadID).
自启动时间(GetTickCount)以来的滴答计数.
当前时间(GetLocalTime).
各种高精度性能计数器(QueryPerformanceCounter).-
用户环境块的MD4哈希,包括用户名,计算机名和搜索路径.[...] -
高精度内部CPU计数器,例如RDTSC,RDMSR,RDPMC
一些PRNG具有内置策略,允许从低质量源混合熵以产生高质量结果.一个非常好的发电机是Fortuna发电机.它专门使用策略来限制风险,如果任何熵源受到损害.
最安全的种子是一个真正随机的种子,你可以在今天的实际计算系统中使用,以降低的置信度列出:
特殊硬件
您的操作系统提供的设施,用于捕获磁盘读取和鼠标移动(/ dev/random)等混乱事件.此"捕获不可预测事件"行的另一个选项是使用一个独立的进程或机器来捕获它作为熵池发生的事情,而不是操作系统提供的"安全"随机数生成器,例如,请参阅EntropyPool
使用坏种子(即时间)并将其与您只知道的其他数据相结合(例如,使用秘密和其他一些标准(例如PID或应用程序/操作系统的内部状态)对时间进行散列,因此它不会必须根据时间增加和减少)
作为有趣的一次性垫,每当我从事间谍活动时,我都有一个系统,我只需要传达几个字母.例如,我最后一次出售秘密计划为Grand Fenwick公爵建造烤面包机时,我只需要低声说:
enonH
我的同盟者.她知道得到http://is.gd/enonH-(这是一个"安全"的扩展程序网址,它会将您带到is.gd扩展页面,该页面又指向青蛙的完全SFW图像).这给了我们一次一密或409K位-如果我眨眨眼,而窃窃私语"enonH" -她知道取图像的哈希值,并用它作为我的下一个传输解码密钥.
由于JPEG图像中的压缩,它们往往是相对较好的熵源,如ent所报告的:
$ ent frog.jpg
熵=每字节7.955028位.最佳压缩会将此51092字节文件的大小减小0%.
为51092米的样品卡方分布是4409.15,并随机地将超过该值0.01倍的百分比.
数据字节的算术平均值是129.0884(127.5 =随机).
对于Pi蒙特卡洛值是3.053435115(误差2.81%)的.
序列相关系数为0.052738(完全不相关= 0.0).uncorrelated = 0.0).
再加上几乎是不可能的猜测形象,我就冲着她和我的秘密烤面包机的计划是从该名男子的安全.
答案是/dev/random在Linux机器上.这非常接近"真实"随机数发生器,如果熵池干涸,/dev/urandom 可以由PRNG生成.以下引用取自Linux内核的random.c 这整个文件是一个很好的阅读,很多评论.它自己的代码来自PGP.它的美丽不受C的约束,它受到访问者包裹的全局结构的影响.这是一个简单令人敬畏的设计.
该例程从设备驱动程序等收集环境噪声,并返回适合加密用途的良好随机数.除了明显的加密用途之外,这些数字也适用于播种TCP序列号,以及其他需要的数字不仅是随机的,而且很难被攻击者预测的地方.
运作理论计算机是非常可预测的设备.因此,
在计算机上生成真正的随机数非常困难- 与
伪随机数相反,伪随机数很容易通过
算法生成.不幸的是,攻击者很容易猜测伪随机数生成器的序列,对于某些
应用程序来说这是不可接受的.因此,我们必须尝试从计算机环境中收集"环境噪音",外部攻击者必须难以观察,并使用它来生成随机数.在Unix环境中,最好从内核中完成.来自环境的随机性源包括键盘
间定时,来自某些中断的中断间定时,以及(a)非确定性和(b)外部观察者难以测量的其他事件.来自这些源的随机性被添加到"熵池",其使用类似CRC的函数混合.这在加密方面并不强大,但是假设不是恶意选择随机性就足够了,并且它足够快以至于在每次中断上执行它的开销非常合理.当随机字节被混合到熵池中时,例程保持估计随机数发生器的内部状态中存储了多少位随机性.当需要随机字节时,通过获取
"熵池"内容的SHA 哈希来获得它们.SHA哈希避免暴露熵池的内部状态.从输出中获得关于SHA输入的任何有用信息被认为在计算上是不可行的.即使可以以某种巧妙的方式分析SHA,只要从发生器返回的数据量小于固有的熵,
在游泳池中,输出数据完全不可预测.由于这个原因,例程减少了其在熵池中包含多少比特"真随机性"的内部估计,因为它输出随机数.如果此估计值为零,则例程仍然可以生成随机数; 但是,攻击者可能(至少在理论上)能够从先前的输出推断出发电机的未来输出.这需要成功的SHA密码分析,这被认为是不可行的,但是存在远程可能性.尽管如此,这些数字应该对绝大多数目的有用....
京公网安备 11010802040832号 | 京ICP备19059560号-6 