0×00 前言


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

0×01 什么是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)减少熵池计数器值。

0×02 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)减小计数器。 依据如下算法:

0×03 弱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,由于导致弱密钥的原理相同,这里就不多做介绍了。