原文地址:http://drops.wooyun.org/papers/9144

0x00 前言

在前两讲中，我们主要对SSL协议中CBC模式的弱安全性进行了系统的介绍。这一讲中我们对用于生成SSL中所用密钥的PRNG做一点简单介绍。

0x01 什么是PRNG？

PRNG（pseudo Random Noise Generation），即伪随机噪声生成，用于生成各种密码学操作中所需的随机数。

一般而言，Linux系统中的PRNG（简称为LRNG）可以被分为3个异步的部分。第一部分把系统事件转化为bit来表示潜在的熵；第二部分把这些bit加入到随机数生成池；第三部分使用连续的SHA-1操作处理生成池中的bit来产生输出，得到的反馈依然被放入生成池中来更新它。

每个从系统事件得到的随机性都被收集为两个32-bit的word。第一个word包含事件发生的时间，第二个word是事件的值，通常是一个按键、鼠标移动或者驱动访问的编码。

LRNG使用一个计数器来计算加入到生成池中物理随机性的估算值，这个值用一个不同事件发生频率的函数来计算。这个值被表示为熵。

Linux系统中PRNG的结构抽象如下图所示：

  • Pools and counters：上图描述了LRNG流程。内部状态保持在3个熵池里：primary、secondary、urandom，它们的大小分别为512、128、128字节。熵源向primary池添加数据；它的输出再给到secondary和urandom中，LRNG的输出是从secondary或者urandom中提取的。提取过程中，一个池子的内部状态会根据反馈行为更新。

    每个池子有一个熵值计数器。它是0到池子大小比特值之间的一个整数。输出从熵池中提取后，这个值就减小提取出熵值的比特数。

    熵值的增加比较复杂。（1）如果增加的bit来自某一熵源，那么会根据这个熵源最近几次事件的时序（timing）来评估它们的熵，然后相应增加计数器的值。（2）如果增加的bit来自primary，则接收池的计数器就直接增加接收到的bit数。

    secondary池的计数器很重要，它用来判断当前secondary池中的熵是否足够用来生成随机数，如果不够，就进行阻塞并等待，并从primary池中提取熵，直到熵计数器的值大于某一阈值。

  • Adding physical entropy： 桌面及服务器PC使用的熵源有4个：鼠标、键盘活动，磁盘输入输出以及特殊中断。事件发生时，会产生一个32bit的word表示时间（系统开机到现在经历的毫秒数），一个word编码它的属性（事件类型、）。此外，同一类型连续事件的时序会被用来估算该事件提供的熵值。

    收集到的熵分批加入池子，每分钟几次。默认加入primary，满了的话加入secondary，不会加入urandom。

  • Generating output：当用户使用/dev/urandom时，从urandom中提取随机bit；当用户使用/dev/random时，从secondary中提取随机bit；当这两个池子熵不够时从primary池提取随机bit。 /dev/random和/dev/urandom这两种生成随机数的方式特点如下：

    1. /dev/random 会生成非常安全的随机bit，当随机bit数不够时，它可能阻塞用户直到随机bit都被生成；
    2. /dev/urandom 输出的随机bit相对不那么安全，它会根据请求返回任意数量的伪随机bit，但它的输出不会被阻塞。

    熵提取过程包括3个步骤：（1）更新熵池内容；（2）提取随机bit到输出；（3）减少熵池计数器值。

0x02 Linux中PRNG的运作原理

  • Linux中PRNG的初始化 操作系统启动时会初始化LRNG，使用固定的操作系统参数和当前时间，以及额外的磁盘操作或系统事件。这样的操作序列很容易被攻击者预测，并且如果没有额外事件发生，LRNG的熵会很有限。导致LRNG的输出具有可预测性。

    可以使用一个脚本解决这个问题，在系统关闭时保存一个随机种子，在开机时把它写回到池子中。关机时，脚本从/dev/urandom中读取512个字节并写入到一个文件，开机时再把这写字节写回到/dev/urandom设备。写回这些字节改变primary池的状态，效果类似于发生一系列事件。然后由primary池更新secondary及urandom池。

    这个脚本是Linux发行包中的一部分，而不是内核的一部分。在KNOPPIX及OpenWRT发行版中没有这个脚本，他们的LRNG初始状态是可预测的，安全性较低。

  • 估算熵值 LRNG仅适用一个时间函数估算事件的熵，而与事件类型无关。

    事件的熵为：

  • 更新熵池 熵池的更新机制基于TGFSR（Twisted Generalized Feedback Shift Register）。

    TGFSR的唯一输入是状态的初始值（一个p*w bit的种子），每个循环中内部状态被用来生成新的状态。

    LRNG中用的移位寄存器是基于TGFSR的，区别在于它在每次循环中增加熵。LRNG中的熵池被定义为长度为m个word的数组。

    熵通过运行add(pool, j, g）算法来增加，g是新的熵word。

    每个池子基于一个本原多项式来更新。多项式根据池子大小来选，secondary和urandom用的多项式相同。

    从熵池中提取随机bit的方式为：（1）对提取的bit做hash；（2）修改池子状态；（3）减小计数器。 依据如下算法：

0x03 弱PRNG对SSL的影响

OpenSSL的PRNG是一个确定性函数，知道输入和调用次序的攻击者可以预测输出。为了使PRNG安全，熵池必须从/dev/random或者其它攻击者不知道的熵源中取种。2006年，在Debian Linux发布版本中的OpenSSL增加了一个漏洞修复，而这个漏洞修复引入了一个新的漏洞，它在修复另一个漏洞时把生成随机数选种过程的代码给删掉了，这导致初始选种时使用到的唯一的随机值是当前进程ID-pid，Linux平台默认最大进程号是32,768，所以生成随机数的种子值范围很小。这个漏洞到2008年才被发现，受影响的Debian Linux版本的可用熵都很有限，产生的公私钥对是可预测的，这样导致生成的SSL协议中使用的服务器私钥具有脆弱性。由于漏洞存在，攻击者可以事先生成公私钥对，一旦发现有跟公钥匹配的就知道了对应私钥。加州大学圣地亚哥分校的研究人员在漏洞发布不久对流行的SSL服务器进行扫描，发现1.5%左右的服务器使用了弱密钥证书。

事实上，因为弱PRNG生成的RSA和DSA弱密钥在TLS和SSH服务器中广泛存在。在2012年的一项调查中发现，0.75%的TLS证书因为熵不足共享了密钥，其他还有1.7%的设备采用了相同实现，很可能也存在此类问题。0.5%的TLS主机和0.03%的SSH主机RSA私钥可被获取，因为它们的公钥存在共享公因子现象。RSA公钥的分解是很困难的，但是如果两个公钥共享了某一素因子，那么只要计算出这个素因子，就可以将这两个公钥分解，从而计算出对应的私钥。

这一现象是由于PRNG在生成随机数时，如果用于产生RSA公钥的两个随机数都是在熵源不足的情况下生成的，那么采用相同实现的设备就可能生成两个相同的素因子，导致对应的私钥相同。如果两个随机数中，仅有一个是在熵源不足的情况下生成，那么两台采用相同实现的不同设备生成的RSA公钥就可能共享一个素因子，导致这两个RSA公钥均可很容易地被分解。

弱PRNG导致的弱RSA和DSA密钥问题在嵌入式设备如路由器、闭路电视等中也广泛存在，因为这类设备的熵源有限（缺少鼠标键盘等熵源）。关于嵌入式设备中弱密钥的问题具体可以参考USENIX Security 14年的文章A Large-Scale Analysis of the Security of Embedded Firmwares，由于导致弱密钥的原理相同，这里就不多做介绍了。