转载

SSL协议安全系列：SSL中弱PRNG带来的安全问题

在前两讲中，我们主要对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这两种生成随机数的方式特点如下：

/dev/random 会生成非常安全的随机bit，当随机bit数不够时，它可能阻塞用户直到随机bit都被生成；

/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%左右的服务器使用了弱密钥证书。

[1] [2] 下一页

正文到此结束