11.3. 随机数

在许多情况下,安全程序必须生成无法被攻击者猜测的“随机”数。示例包括会话密钥、公钥或私钥、对称密钥、许多协议中使用的 nonce 和 IV、盐等等。理想情况下,您应该使用真正随机的数据源来生成随机数,例如基于放射性衰变(通过精确计时盖革计数器点击)、大气噪声或电路中热噪声的值。有些计算机具有充当真随机值生成器的硬件组件,如果可用,您应该使用它。

但是,大多数计算机没有生成真随机值的硬件,因此在大多数情况下,您需要一种生成随机数的方法,这种随机数要足够随机,以至于攻击者无法预测。一般来说,这意味着您需要三件事

通常,PRNG 使用状态来生成一些值,然后使用其某些值和其他不可猜测的输入来更新状态。有很多方法可以攻击这些系统。例如,如果攻击者可以控制或查看状态的输入(或部分输入),则攻击者可能能够确定您所谓的“随机”数。

PRNG 的真正危险在于,大多数计算机语言库都包含大量不适合安全目的的伪随机数生成器 (PRNG)。让我再说一遍:不要将典型的随机数生成器用于安全目的。典型的库 PRNG 旨在用于模拟、游戏等;它们的随机性不足以用于密钥生成等安全功能。大多数非加密库 PRNG 都是“线性同余生成器”的某种变体,其中“下一个”随机值计算为“(aX+b)�mod�m”(其中 X 是先前的值)。良好的线性同余生成器速度快且具有有用的统计特性,使其适用于其预期用途。此类 PRNG 的问题在于,攻击者可以轻松推断出未来的值(尽管它们可能看起来是随机的)。其他快速生成随机数的算法,例如二次生成器和三次生成器,也已被破解 [Schneier 1996]。简而言之,您必须使用密码学上强大的 PRNG 在安全应用程序中生成随机数 - 普通的随机数库是不够的。

未能正确生成密钥的真随机值已导致许多问题,包括 Kerberos、X 窗口系统和 NFS 中的漏洞 [Venema 1996]。

如果可能,您应该使用系统服务(通常由操作系统提供),这些服务专门设计用于创建密码学上安全的随机值。例如,Linux 内核(自 1.3.30 起)包含一个随机数生成器,它足以满足许多安全目的。此随机数生成器从设备驱动程序和其他来源收集环境噪声到一个熵池中。当作为 /dev/random 访问时,仅在熵池中估计的噪声位数内返回随机字节(当熵池为空时,调用会阻塞,直到收集到额外的环境噪声)。当作为 /dev/urandom 访问时,即使熵池已耗尽,也会返回请求的字节数。如果您在 Linux 上将随机值用于加密目的(例如,生成密钥),请使用 /dev/random。 *BSD 系统也包含 /dev/random。 带有 SUNWski 软件包的 Solaris 用户也拥有 /dev/random。 请注意,如果硬件随机数生成器可用且其驱动程序已安装,则将改用它。 更多信息请参见系统文档 random(4)。

在其他系统上,您需要找到另一种方法来获得真随机结果。 对于其他类 Unix 系统的一种可能性是熵收集守护进程 (EGD),它监视系统活动并将其散列为随机值;您可以从 http://www.lothar.com/tech/crypto 获取它。 您可以考虑对 PRNG 输出使用加密哈希函数(例如,SHA-1)。 通过使用哈希算法,即使 PRNG 最终被证明是可猜测的,这也意味着攻击者现在还必须破解哈希函数。

如果您必须自己实现一个强大的 PRNG,那么密码学上强大(且未受专利保护)的 PRNG 的一个好选择是 Yarrow 算法;您可以从 http://www.counterpane.com/yarrow.html 了解有关 Yarrow 的更多信息。 其他一些 PRNG 可能有用,但许多广泛使用的 PRNG 都存在已知的弱点,这些弱点可能对您的应用程序很重要,也可能不重要。 在自己实现 PRNG 之前,请查阅文献,例如 [Kelsey 1998] 和 [McGraw 2000a]。 您还应该查看 IETF RFC 1750。 NIST 有一些有用的信息;请参阅 NIST 出版物 800-22NIST 勘误表。 您应该了解 diehard 测试。 您可能想查看题为“英特尔如何检查其 PRNG”的论文,但不幸的是,该论文现在似乎无法获得。