如何通过硬件真正实现随机数生成

使您的软件运行起来：消除偏差
如何通过硬件真正实现随机数生成

文档选项

将此页作为电子邮件发送

级别： 初级
Gary McGrawReliable Software Technologies
John ViegaReliable Software Technologies
2000 年 4 月 01 日
在本系列的第一部分中，Gary McGraw 和 JohnViega 讨论了精确随机数生成。在这一部分，即本系列的第二部分中，Gary和 John研究了随机数的硬件源。这些源有时可以提供比全软件解决方案更高的安全性保证（虽然我们也将处理基于硬件的随机数发生器中的缺点）。
从本专栏的上一部分中，我们知道了随机数通常会产生很重要的安全性后果。问题是确定性的机器很难实现随机。最佳答案就是使用好的物理度量来生成随机数（或至少是伪随机数发生器的种子）。许多自然现象就具备这种条件。其诀窍就是它们必须有一些可测量的特性，而且行为至少要尽可能随机（如果不能真正做到随机）。（这种随机性是在量子力学级别上提出的。还不知道随机性真正是量子力学的固有部分，还是我们的科学理论还不够好，不能预测我们应该能够预测的结果。）收集随机性的真正硬件设备是基于测量诸如原子的放射性衰变或热辐射中的波动（某些 Pentium III 处理器就测量后者）之类的事情。
在这一部分中，我们将研究随机数的硬件源。这些源有时可以提供比全软件解决方案更高的保证（虽然也有许多糟糕的硬件随机数发生器）。我们确实意识到基于硬件的解决方案并不总是可行，只要这句话就够了。例如，您也许希望将应用程序分发给全球数以万计的用户，而且还需要每部台式机上有好的随机数。直到世界上每台计算机都在硬件中安装了随机数发生器为止，总是需要一种尽可能接近真正随机性的软件。
在我们深入研究之前，我们需要考虑是否可能满足这种随机性需要。我们在上一部分中讨论了传统的伪随机数发生器，而且讨论了将它们用于注重安全性的用途上有多可怕。PRNG 算法也无法满足需要。硬件（在下面讨论）是一个好的选择，但是却很昂贵且不易使用。
幸好，有一个折中方法。使用软件执行合理的随机性作业，而不必求助于基于硬件的解决方案，这点是可能的。当然，您需要牢记这一点：硬件始终可以比软件做得更好，即使不是永远。我们将在下一部分中讨论替代软件解决方案。
真正的随机数发生器是非确定的。那表示，作为旁观者，应该永远无法以任何一致性猜测到设备的输出，即使您知道设备使用的算法。例如，如果设备输出一系列 0 和 1，0 和 1 在任何特定输出中出现的机会应该相等。即使掌握了设备内部工作的全部知识，任何猜中的可能性也只有 50% 左右（对于某些范围的行为）。
在计算机上执行非确定性事情的唯一方法是从一些自然的随机过程中收集数据。我们最喜欢的一种方法涉及使用电子 Geiger 计数器，每次当它检测到放射性衰变时，它就会生成一个脉冲。衰变之间的时间是一个实足的、纯粹的随机部分。尤其是，没有人可以预测到下一次衰变的时间大于还是小于自上次衰变以来的时间。那就产生了一位随机信息。我们可能得到更多。
比如说，假设我们正在观察某些我们期望每秒都发生衰变的材料，但衰变也许会前后相差十分之一秒发生。与其比较两次衰变之间的时间，不如记录衰变的时间，并且使用独立数字位作为独立的十进制随机数。也许百分之一秒是一个数字位，而千分之一秒是另一个数字位。我们可以根据计时器的精确程度来按比例抽取数字。此技术也许够好，也许不够好；在没有尝试使用它并对数据进行一些统计分析的情况下，很难下定论！如果表示百分之一秒的数字几乎总是 0，而表示偶尔发生的数字是 1，将会怎么样？那不是非常随机。如果我们的时钟没有那么强的功能，而且表示千分之一秒的数字始终是均匀的，或者至少很可能是均匀的，将会怎么样？
实际上，这种问题是经常遇到的。所有事都可能出错，从而使数据产生偏差。另一方面，如果我们保守一点，尝试以保守方式从衰变中抽取出数据的单一位，就很少有机会产生测量引起的偏差。不幸的是，如果有一些偏差，很难断定偏差有多大。我们关心的是平均信息量（真正的随机性）中有多少位是真正可用的。我们希望能够以某些精度测量该数字。为使我们的工作更简单，我们将只研究一位。
任何源都有潜在的偏差。我们检查了一种流行的硬件发生器，发现它返回 1 的概率是 49.81%，这表示发生器的偏差非常小，趋向于零。或许基本自然现象的偏差也是这样，但通常我们的测量工具（尚有不足之处）有错误。




回页首
我们如何消除偏差？一种常用方法是同时 XOR 位。如果某一位是 0 的概率是 0.5 + c，那么当我们同时从一个发生器中 XOR 两位时，概率就变成 0.5 + 2c2。如果我们 XOR 更多位，概率就会越来越接近均匀。当然，概率永远不会达到均匀，但每个 XOR 操作都会消除许多偏差；您只需确定愿意接受多少偏差。由于我们使用两位来创建一个偏差，我们就带来了新问题，因为我们现在生成随机位的速度只有以前的一半。
上述消除偏差的技术的一个潜在问题是即使在执行了 XOR 之后，两个连续位（或甚至是两个不相邻的位）之间有相关性，而攻击者也许会利用这一点。实际上，XOR 可以帮助消除任何偏差，但它放大了位之间的相关性。
请考虑我们给出的用于从计时事件中抽取单一位的技术。如果我们使用同样的技术尝试从敲击键盘中获取随机性，那会怎么样？基本思路是记录两次击键期之间的持续时间。如果某段持续时间大于前一段持续时间，则生成 1；否则生成 0。此技术在需要生成密钥的程序中很常见，并且会使那些让他们敲击键盘几分钟也不会抱怨的用户坐在计算机前。例如，某些版本的 PGP 就使用此技术（其它版本则利用鼠标事件执行类似的功能）。
但并非一切都能在意料之中。这里就是可能出错的地方。按键之间的计时并不完全是随机现象。我们已经看到了向用户提供需要反复输入的样本文本的程序。问题是某些键比其它键更易于触到。如果正在输入单词“kiss”，输入“i”和“s”之间的时间几乎总是大于输入两个“s”字符之间的时间。产生一个位的事件肯定与产生下一个位的事件相关，从而导致最终偏差的增加。
我们如何消除这种相关性呢？一个解决方案就是采用多个随机数据源，并且将数据流 XOR 到一起。按惯例，人们使用伪随机流作为数据的第二来源。当然，如果某人可以破坏伪随机流，那么仍可以辨别出相关性（而且可以使用相关性来对付您，就象我们将要演示的）。
怎么回事？谁会关心随机数发生器中是否有一点偏差？在理论上，偏差会使攻击者的工作变得更容易。然而，实际上，小的偏差并不太可能导致系统破坏。例如，Bruce Schneier 留意到即使发生器产生的数字中 55% 都是 0，每位仍然能产生 0.99277 位的平均信息量。那意味着，精确导向地强力搜索 168 位密钥，平均起来，2,109 次尝试中会成功一次，而不是如果不存在偏差时所预期的 2,111 次尝试中成功一次。但是，万一人们可能犯错，大多数人宁愿犯安全性方面的错误。
一种通过消除偏差而解决上述所有问题的常用解决方案是对随机字节流应用某种算法，该算法可以自然地消除任何统计趋势。通常都使用压缩算法和散列函数。




回页首
偏差的另一个源（特别隐秘的一种）是在外部现象中，即攻击者有一些控制，或者有机会进行复制。如果攻击者对所测量现象的影响程度足够产生重大的偏差，那么必将发生一个攻击高潮，尤其是在一段很长的时期内。例如，如果将网络流量用作测量的现象，那么这个攻击就很可行。攻击者可以偷偷地控制到您机器的网络流量，并且以这种方法产生很大的偏差。应该避免这些容易受到控制或影响的现象。另一种技巧就是从 WAV 文件或声卡提取背景噪声（通常没有连接话筒）。许多时候，这些源都没有很多平均信息量；如果它们受到攻击，那么就会变得毫无价值。同样，实际上偏差可能是不相关的，但应该防患于未然。
也许常用的随机数最佳来源是测量放射性衰变。它根本不易于产生偏差，而是会带来相对较小的自然偏差。另一个好的来源是测量半导体二极管散发的热噪声，然而如果得不到正确防护，附近的硬件可能会使输出产生偏差。
生成随机数的几种硬件设备都是商业用的。也许最广泛使用的设备是 ComScire QNG（请参阅参考资料 ），它是使用并行端口连接到 PC 的外部设备。人们都认为此设备是经过精心设计的，而且在其输出的统计分析方面做得极其好。它可以在每秒钟生成 20,000 位（2,500 字节），这对于大多数注重安全性的应用程序来说已经足够了。即使发生器产生的数据还不够时，发生器的数据可以预先存储，或者可以使用多个发生器。这个包的另一个好处是：当生成数字时，设备驱动程序会对它们进行统计测试，而且如果开始生成在统计上非随机的数据，它会返回错误。在撰写本文时，该设备价值 295 美元，可以从 ComScire 购得。Robert Davies 撰写的关于此发生器的无偏见评论（请参阅参考资料）声称它“看来是唯一为统计目的而特别设计的发生器，而且制造商花了一定的精力来了解最终产生的数字上的偏差和相关性的作用。”
一种类似设备来自 Tundra 的 RBG 1210（请参阅参考资料）。它们的设备有时会产生小的偏差，然而在别的方面却通过了许多统计测试。明确建议使用转换来消除偏差。此产品过去常常有一些装配问题而通常会导致彻底失效，但相信它们会得到修复。
RBG 1210 是 PC 的内部卡，它有可变采样率。如果采样过多，连续的位就会有很高的相关性，因为内部硬件不会很快更改输出以符合采样率。但是，此设备将会每秒产生最多 160,000 位（20,000 字节）。
另一种很好玩的资源是 lavarand（请参阅参考资料 ）。这种热闹的方法依赖于一组正在工作的 Lava Lite 灯中固有的混乱。一架数字照相机安置在六盏 lava 灯前，用于每隔一段时间拍摄一张照片。所产生的“噪音”数字图像然后被以密码方式散列到 140 位的种子值中。然后，将这个种子值馈送给出色的伪随机数发生器（我们将在下一部分中讨论）。但是，不要在注重安全性的代码中使用 lavarand！请记住，每个人，包括坏蛋们，可以在 Web 上看到 lavarand 序列。SGI 并不销售 lavarand 安装程序。如果您遵循 lavarand 网页上细致、详细的建议，亲自构建 lavarand 并不困难。
但是，lavarand 并不希望与我们讨论过的其它设备竞争。大多数安装都很昂贵（因为近来 lava 灯的高价），并且发生器每秒只输出 550 位（略少于 70 字节）。这样一个设备对空间要求很高，需要一盏灯和一架照相机。最后，它很容易失败，如坏掉的硬件。要解决后一个问题，SGI 使用六盏灯作为自动计时器，其中三盏始终打开。系统中每样东西都工作得格外好，只是带宽相当低。问题的部分原因是需要拍摄和扫描照片。但是，问题的大部分是因为数据很可能有统计偏差，因此大量精力花在了使用七个密码散列和一个相当慢（但非常好）的伪随机数发生器来消除此类问题上。
当去年 Intel 宣布他们将开始在其芯片组中添加基于热能的硬件随机数发生器，而且基本上不会增加客户的成本时，许多安全性社区都变得很兴奋。当著名的密码人员宣称该发生器是随机数的优秀来源时，人们变得更兴奋了。迄今为止，已经交付了一些带有硬件 RNG 的 CPU。所有带 8xx 芯片组（810 或更高）的 Pentium III 都应该拥有此功能。由于我们熟悉带这种发生器的硬件，当此功能可用时，我们会给您一些代码供您使用。（我们已经听说一个令人不愉快的谣言：RNG 正遭到长期禁止，因为人们对它失去了兴趣。我们希望这最终只是一个谣言。）
还有其它鲜为人知的产品用于在硬件中生成随机数。在 Web 上有几个资源可以向熟悉构建硬件的人们演示如何廉价构建自己的随机数发生器（请参阅参考资料）。




回页首
一旦拥有了随机数的硬件源，您应该问：“我的随机数够随机吗？”答案也许并不总是“是的”，您当然想要知道什么时候发生这种情况。在开始使用他人的发生器之前先进行测试，一点不为过。但是当构建自己的随机数发生器时，认真测试就尤其重要（但是，这样做很容易扰乱我们的建议，我们建议购买一个高质量的发生器，而不是构建一个）。
现在有许多统计测试。它们采用各种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现如果数据真是随机的，是否可以在还没有显示的数据中找到任何模式。ComScire 设备在您使用它时会执行这些测试，如果测试不成功，它会在运行时失败。那是种很好的安全措施，但实际上，人们通常（也许很少）只在第一次使用之前预先检查流，以确保发生器正在开足马力运行。
确保数据流随机性的最广为人知的测试套件就是 George Marsaglia 的 DIEHARD 软件包（请参阅参考资料 ）。它对数据流执行无数的测试。另一个适合此类测试的合理软件包是 pLab（请参阅参考资料）。这些测试做什么或者不做什么其实并不重要；我们只是必须相信它们正在测试发生器的质量，并且认真听从我们正在使用的发生器是否没有通过测试。
在构建用于随机数的硬件设备时，有一些诸如 DIEHARD 这样的测试套件也捕捉不到的缺陷。例如，某些类型的偏差不会在大多数统计测试中显示出来。由于这个原因，我们强烈建议：如果有可能的话，使用信誉好的商业硬件源来生成随机数，而不要构建自己的硬件源，因为您也许最终会不正确地测试您的发生器。如果您仍认定需要亲自测试发生器，我们建议您阅读文章“True Random Number Generators”（请参阅参考资料）。




回页首
在前两部分中，我们展示了随机数生成的两个极端。一个极端是传统的伪随机数发生器，它很容易被攻破，因此不适合注重安全性的应用程序。另一个极端是基于硬件的随机数发生器，它可以执行非常好的性能，但通常由于其昂贵的价格或缺少普遍可用性而不实用。
下次，我们将研究折中方法，在此方法中，随机数确实很好，即使它们是在不使用硬件设备的情况下生成的，即使它们的生成速度有一点慢。我们将讨论一类功能更加强大的伪随机数发生器，并讨论如何在不借助于特殊硬件的情况下从好的来源中收集随机性。
您可以参阅本文在 developerWorks 全球站点上的英文原文.
请访问 developerWorks 上这个讲述随机数生成系列的第一篇文章“使您的软件运行起来：摆弄数字”。
请访问ComScire 以了解关于 ComScire QNG 的信息。
请阅读 Robert Davies 撰写的评论“True Random Number Generators”。
请访问Tundra 以了解关于 Tundra RBG 1210 的信息。
请访问DIEHARD 以获取一组随机数发生器的测试。
请访问pLab，这是一个用于生成和测试随机数的面向对象系统。
Reliable Software Technologies.

 

Gary McGraw 是 Reliable Software Technologies 负责企业技术的副总裁，该公司位于美国弗吉尼亚州杜勒斯（Dulles）。他从事咨询服务和研究工作，帮助决定技术研究和开发方向。McGraw 在 Reliable Software Technologies 从一个研究科学家作起，从事软件工程和计算机安全性方面的研究。他拥有印第安那大学认知科学和计算机科学双博士学位，弗吉尼亚大学的哲学学士学位。他为技术刊物撰写了 40 余篇经同行审查的文章，担任过主要的电子贸易供应商，包括 Visa 和 Federal Reserve 的顾问职务，并在空军研究实验室、DARPA、国家科学基金会，以及 NIST 的高级技术项目赞助下担任其首席调研员。
McGraw 是移动代码安全性方面著名的权威人士，并且与普林斯顿的教授 Ed Felten 合作撰写了“Java Security: Hostile Applets, Holes, & Antidotes”（Wiley, 1996）以及“Securing Java: Getting down to business with mobile code”（Wiley, 1999）。McGraw 和 RST 创始人之一、首席科学家 Dr. Jeffrey Voas 一起编写了“Software Fault Injection: Inoculating Programs Against Errors”（Wiley, 1998）。McGraw 定期为一些受欢迎的商业出版物撰稿，而且其文章经常在全国出版的文章中所引用。
 

 

John Viega 是一名高级副研究员，Software Security Group 的共同创始人，并担任 Reliable Software Technologies 的高级顾问。他是 DARPA 赞助的开发标准编程语言安全性扩展的首席调研员。John 已撰写了 30 余篇涉及软件安全性和测试领域的技术性文章。他负责在主要网络和电子贸易产品中查找一些众所周知的安全性脆弱性，包括最近在 Netscape 安全性中的缺陷。他还是开放源码软件社区的重要成员，编写过 Mailman、 GNU Mailing List Manager 以及最近发布的 ITS4（一种在 C 和 C++ 代码中查找安全性脆弱性的工具）。Viega 拥有弗吉尼亚大学的计算机科学硕士学位。

太差！ (1)
需提高 (2)
一般；尚可 (3)
好文章 (4)
真棒！(5)