14 随机数生成器

作者: yuan1028 | 来源:发表于2021-06-18 16:46 被阅读0次

14.1 介绍

很多密码学系统需要使用到随机数。目前为止，本书只是假设可以获取到随机数。本章将介绍密码学中的随机数的重要性以及一些机制。

产生随机数是一件相当复杂的过程。和密码学中很多其他事情一样，它非常容易出错，但是从表面上看却看起来好像一切都是对的。

随机数生成器分成3个范畴：

真正的随机数生成器
密码学安全的伪随机数生成器
伪随机数生成器

14.2 真正的随机数生成器

任何考虑用算术手段来产生随机数的人自然都是有原罪的. ——冯·诺伊曼

冯·诺伊曼,现代计算机之父，提出了他很明确的观点。不可能使用可预测的，决定性的数学来产生随机数。需要一个本质是随机的东西而不是一个确定性规则的序列。

真正的随机数生成器从物理过程中获取它们的随机性。历史上有很多系统被用来生成这些数字。其中的一些至今仍在使用。然而，在我们实际的密码学系统中，需要大量的随机数，而真正的随机数生成器通常太慢了以至于通常不可靠。

目前有很多更快也更可靠的随机源。目前的硬件随机数生成器通常使用以下物理过程来产生随机数。

量子过程。
热力学过程。
振荡器漂移。
时间事件。

并不是所有的选项都需要产生高质量的，真实的随机数。本章将进一步介绍他们是如何被成功应用的。

放射性衰变

量子物理过程应用到产生随机数的一个例子是放射衰变。众所周知，放射物质随着时间会慢慢衰变。无法知道下一个原子什么时候衰变；它是完全随机的。然而监测衰变何时发生，是容易的。通过监测独立衰变之间的时间，就可以产生随机数了。

散粒噪声

散粒噪声是另外一个量子物理过程应用到产生随机数的例子。散粒噪声是基于每个独立的粒子的运动引发光和电子：光的情况下是光子，电的情况下是电子。

抽样噪声

热力学过程应用到产生随机数的一个例子是抽样噪声。抽样噪声是发生在电荷载体（通常是电子）通过一定阻力的媒介时产生的噪声。微弱的电流流过电阻（电阻的电压会有微弱不同）。

这些共识对于没有了解过背后物理知识的人来说有点吓人，但是不用过于担心：并不需要真正的理解它们。如果你之前没有听说过这些，可以简单地假装这个值是平均值。△f是带宽，T是系统的开尔文温度，kB是玻尔兹曼常数。

从公式中可以看出，抽样早上是热力或者是温度独立的。幸运的是，一个攻击者通常没有办法打破随机数生成器的该项特性。某一个刻的温度在系统使用它的时候温度可能已经不在那个点了。

通过介绍这个公式，可以看出抽样噪声是很小的。在室温情况下，合理假设（10kHz带宽，1k欧电阻），抽样噪声在几百纳米伏特。即便是将范围调整为微伏特（1微伏特=1000纳伏特），依然是1百万分之一伏特，而一个简单的AA电池就有1.5V

然而，公式涉及到了平方根，该值将会是完全随机的分布。通过重复测量，可以产生高质量的随机数。在多数实际产品中，热力学噪声数字是高质量低偏差的。

14.3 密码学安全的伪随机数生成器

接下来几节将要介绍一些密码学安全的伪随机数生成器，记住这些算法只是可以使用，作为一个应用的开发者，你不需要在它们中做选择。如果真的需要生成随机数，你应该使用你自己操作系统支持的密码安雪的随机数生成器。在*NIX（Linux, BSDs 以及 OS X）上是/dev/urandom，在Windows上是CryptGenRandom. Python提供了使用系统随机数的接口os.urandom和random.SystemRandom.

为了保证安全，尽量避免使用用户层级的密码安全的随机数生成器，比方说OpenSSL中的随机数。使用这些有很多可能出错的情况，通常与它们的内部状态有关：它们可能没有做初始化，或者只是简单的初始化，或者是在不同的场景中重用相同的状态。这些情况都可能会导致密码系统彻底的崩溃。

14.4 Yarrow

Yarrow算法是密码学安全的伪随机数生成算法。

该算法在FreeBSD中被用作CSPRNG，并被Mac OS X系统继承。在这俩种系统中，它都是被用来实现/dev/random。在Linux系统中/dev/urandom仅仅只是/dev/random的别名。

14.5 Blum Blum Shub

TODO：介绍该算法的优点（可证明），但是为什么又不使用它（慢）。

14.6 双椭圆曲线随机比特生成器（Dual_EC_DRBG）

Dual_EC_DRBG是NIST的密码学安全的伪随机比特生成标准。该标准引发了大量的争议。尽管被用来作为官方的密码学标准，但是它很快被证明了它是不够好。

密码学专家最终演示了该标准可以在其常量中隐藏一个后门，就会造成不特定攻击可能会整个摧毁该随机数生成器的潜在风险。

一些年之后，一份泄漏的文档中推荐使用后门在一个未命名的NIST标准中，而这一年正好是Dual_EC_DRBG发布的年份，使得该标准更加的可疑。这也使得官方从推荐该标准到停用该标准，这个情况在当时的环境中是前所未见的。

背景

很长一段时间，由NIST产生的官方标准都缺饭很好的现代密码学安全的伪随机生成数算法。有一些其他的简陋的选择，但是该选择的标准化有几个严重的问题。

NIST为了强调这个问题发表了被称为SP 800-90的文章，其中包括一些新的密码学安全的伪随机数生成算法。该文章包含了很多基于各种不同的密码学机制的算法：

密码学函数函数
HMAC
块加密
椭圆曲线

最后一项立刻就引人注目了。使用椭圆曲线来产生随机数是非常少见的。标准希望能够是最先进的，并且依然是保守的。椭圆曲线在之前的学术文章中被考虑过，但是离其被推荐作为一个标准被广泛使用还有很遥远的距离。

第二个原因是椭圆曲线看起来很奇怪。HMAC和块加密都很明显是对称算法。哈希函数通常在非对称算法例如数字签名中被应用。但是它们自身并不是非对称的。而椭圆曲线，专门被用于非对称加密：签名，密钥交换，非对称加密。

这也就是说，这个选择并不是完全来自于蓝海。密码学安全的随机数生成算法的一个基于很少能听到的很强的数论基础的例子：Blum Blum Shub相比其他选择就太慢了。例如在同一个标准中，Dual_EC_DRBG要比它的同辈们慢一些，排在第三位。通常强的数学证明是值得性能上的损失的。例如，我们相信因数分解是很困难的，但是hash函数和加密就没有那么确信。RSA是1977年发明的，自从那个时候开始的测试都是非常好的。而DES两年后被提出，现在已经完全被攻破。MD4和MD5在十年后被提出，现在也已经被攻破了。

问题在于，这个标准并没有真正地拿出安全性证据。标准提出了这个生成器但是仅仅是提出它至少是和解决椭圆曲线问题一样的难。作为对比Blum Blum Shub就可以证明要攻破它，至少和解决二次剩余困难性问题一样难。目前我们最好的问题是因数分解问题，我们可以确定该问题特别的难。

省略证明是愚蠢的，因为你没有理由要使用一个和Dual_EC_DRBG一样慢的伪随机数生成算法除非你有证据你在牺牲性能的情况下能获得些什么。

NIST本该在提出来的时候就进行的工作，密码学家后来对其进行了证明，这些分析强调了一些问题。

算法概述

该算法包括两部分：

在椭圆曲线上生成一个伪随机数点，然后将其作为生成器的中间状态。
将这些点转化为伪随机比特。

本节将图形化地来详述该过程，图片是以Shumow和Ferguson的工作为基础。两位密码学家强调了该算法的主要问题。

image-20210618135435769.png

整个算法中，ϕ是一个函数，它的输入为椭圆曲线的点，输出为一个整数：算法需要两个椭圆曲线上的点：P和Q。这些是固定的，在规范中定义的。算法有一个内部状态s。当产生一个新的比特块时，算法将s转化成一个不同的值r，使用ϕ函数，以及和P做椭圆曲线的乘法。

这个值r既会用来产生输出的比特也会用来更新生成器的内部状态。为了产生输出的比特，需要用到椭圆曲线的另一个点Q。输出的比特是将r乘以Q，再将该结果竟一个一个转化函数 θ的处理：

为了更新状态，r会再次乘以P，然后将结果转化为整数。这个整数就是新的状态s。

问题和问题标志

首先，ϕ是很简单的：它仅仅是椭圆曲线点的x坐标，而舍弃了y坐标。这也就意味着攻击者如果能看到ϕ的输出，那么攻击者就容易找到椭圆曲线上的这个点。在它自身来讲，不是一个很大的问题；但是如我们所见，这是后门可能性的一个因素。

另一个缺陷是点转化为伪随机比特的过程。函数θ仅仅是简单地舍弃了16比特。之前的设计舍弃了更多的信息：对于256比特椭圆曲线，设计在一些场景中舍弃了120-175比特。

错误地舍弃重要的比特使得生成器有了小的偏差。下一个比特的特性被违反了，攻击者有大于50%的几率可以猜出下一个比特的正确值。虽然在一千次中仅仅有一次是大于50%的；但是这对于被认为是最完美的密码学安全的伪随机数生成器来说依然是不可接受。

舍弃仅仅16位比特还带来另一个问题。因为这16比特是被丢弃的，只需要猜测2^16种可能就可以找到得到该输出的ϕ(rQ)的值。这是一个很小的数字：简单地进行枚举就可以了。这些值是ϕ的输出，也就是椭圆曲线坐标的x。由于我们知道它是椭圆曲线上的点，只需要将其代入到椭圆曲线方程，即可验证我们的猜测。

常量a，b，p都是由曲线决定的。只需要简单地猜测一个x的值，就只有y是未知的了。我们可以有效地计算它，计算等式右边的值然后检查它是不是一个平方数y^2=q.如果它是,A=(x,√q)=(x,y)就是椭圆曲线上的点。这就给出了一个可能的点A，也就是用来产生输出的rQ。

通常情况下这并不是一个问题。为了找出算法的状态，攻击者需要找到r，这样他们就可以得到内部状态s。对于已知rQ，他们依然需要去解决椭圆曲线离散对数问题，来找到r。我们假定这个问题是非常非常难的。

记住椭圆曲线最开始是用来做非堆成加密的。该问题通常被认为是很难解的，但是如果我们有额外的信息呢？如果有一个秘密的e，使得eQ=P？

假设攻击者恰恰知道e。重复上面的数学公式。尝试之前找出的A也就是rQ。然后计算

最后的步骤和e，P，Q有很大的关系。这个就非常有趣了，因为ϕ(rP)就是算法中计算的s，算法的新的状态。也就是意味着如果攻击者知道e，就可以从任意输出很容易地计算出新的状态s，他们就可以预测生成器的所有未来的值了。

这个假设攻击者的A就是正确的A。因为仅仅有16比特被丢弃，也就只有16比特数据需要去猜测。也就是有2^{16个可能的x坐标。实验显示，有一半的x坐标可以找到椭圆曲线上对应的点，也就是有2}15种可能的点A，其中一个是rQ。对于现代计算机来说这是一个很小的值，小到完全可以去尝试所有可能性。因此可以说如果攻击者知道这个秘密的e值，那么他就可以攻破生成器算法。

如果有一个神奇的e，使得eQ=P，然后选择P和Q（不用解释P和Q是从哪里得来的），这样你就可以破解这个生成器。你会怎么挑选这些值。

为了强调它的可能性，研究者从NIST的曲线点P的p值开始，然后使用他们自己的Q‘。他们只需要从P开始，选择一个随机数d（保持它的私密性），然后设置Q’=dP。这里的技巧是如果知道Q'=dP里的d，那么可以有效地计算eQ‘=P里的e。这个e就是之前攻击需要的值。当他们尝试找出这个值，他们实验了所有的情况（也就是，很多的d），能看到输出的32个字节就可以决定内部状态s。

这一些，当然，都只是为了强调P和Q的特定值可能是一个秘密的后门。并没有证据显示这个实际的值存在后门。然后，这个标准里从来不解释，他们是怎么得来这个神奇的Q的，这就不能给人多大的信心。典型地，密码学标准使用隐藏备用的数字，例如一些常量，比方说π，或者自然对数的底数e。

如果一些人知道后门，后续明显是毁灭性的。本章已经论述了密码学安全的伪随机数生成器的必要性：攻破了随机数等于其他的使用这个生成器的其他密码系统也会被完全攻破。

有两种途径来试图纠正该算法：

让θ更复杂一些，使其难以逆运算，而不是仅仅只舍弃16比特。这样会使得寻找潜在的点很难，也就很难施行攻击。一个显而易见的方式是舍弃更多的比特。另一个方式是使用密码学安全的hash函数，或者将两个方法结合到一起。
每次运行算法的时候生成一个随机数Q，可能是选择一个随机d然后设置Q=dP。当然d需要是足够大的真正的随机：如果θ没有改变，而d也仅仅有几个值的话，攻击者依然可以按照上述方法进行攻击。

这些都只是修复措施，更好的办法是使用别的算法。这些建议没有解决它很慢，很奇怪的问题，现在它已经被从标准中删除。

14.7 Mersenne Twister

Mersenne Twister是一个很通用的随机数生成器。它有很多优点，很高的性能，很大的区间2^19937-1=4*106001,它也通过了所有需要随机性的测验。尽管它有这么多的优点，但是它不是密码学安全的。

深入了解Mersenne Twister

为了强调为什么Mersenne Twister不是密码学安全的，本节将深入来看一下算法的工作机制。幸运的是，它并不是很复杂。

标准的Mersenne Twister算法有一个内部状态的数组S，包含了624个无符号32位整数，和一个指向当前整数的索引i。它包括三个步骤：

一个优化的初始化函数，它将从一个初始化的随机值（种子）来产生初始状态。
一个状态生成函数，用来从旧的状态产生新的状态
一个扩展函数，也被称为是回火函数，它会从当前的状态（i指向的元素）产生一个随机数。

当调用扩展函数的时候，索引值会加一。当所有的状态都被用来产生过随机数之后，初始化函数再次被调用。状态初始化函数在第一个数字被扩展之前也需要被调用。

然后，状态被重新生成，随后每一个元素再次执行扩展函数，直到用完。这个过程无限重复。

本节将对每一步进行简单介绍。扩展的工作是超出了本书的范畴，但是我们仅是简单地介绍一下就足以看出为什么Mersenne Twister不是密码学安全的随机数生成器。

初始化函数

初始化函数创建一个Mersenne Twister的状态数组，以及一个很小的数（种子）作为初始化随机数。

这个数组以种子作为开始，然后下一个元素是从一个常量，上一个元素，以及新元素的索引共同产生的。元素被逐个产生直到达到624个。

下面是Python的源代码：

def uint32(n):
    return 0xFFFFFFFF & n
def initialize_state(seed):
    state = [seed]
    for i in range(1, 624):
        prev = state[-1]
        elem = 0x6c078965 * (prev ^ (prev >> 30)) + i
        state.append(uint32(elem))
    return state

对于没有接触过Ptyhon或者它的位操作的人来说：

">>"和“<<”是右移和左移
"&"是二进制与，0&0=0&1=1&0=0&0=0，1&1=1
"^{"是二进制异或，"}="是异或和赋值到左侧，所以x^=k和x=xk是一回事。

状态重新生成函数

状态重生成函数输入当前状态，输出一个新状态。在第一数字被扩展之前被调用，之后每624个元素被用完之后被调用。

该函数的Python的源代码非常的简单。注意它是在数组元素的位置上修改，而不是产生一个新的数组。

def regenerate(s):
    for i in range(624):
        y = s[i] & 0x80000000
        y += s[(i + 1) % 624] & 0x7fffffff
        z = s[(i + 397) % 624]
        s[i] = z ^  (y >> 1)
        if y % 2:
            s[i] ^= 0x9908b0df

表达式s[(i + n) % 624]中的"%"表示状态的下一个元素，当没有下一个元素的时候它将会从第一个元素重新开始。

值0x80000000和0x7fffffff解析为32位数字的时候有特定的含义。0x9=80000000只有第一位是1，0x7fffffff除了第一位以外全都是1.循环的前两行中的二进制与操作，y包含了状态元素的最高位以及下一个元素的除了最高位之后的位。

回火函数

在产生随机数之前回火函数被应用在状态的当前元素上。源码如下

_TEMPER_MASK_1 = 0x9d2c5680
_TEMPER_MASK_2 = 0xefc60000

def temper(y):
    y ^= uint32(y >> 11)
    y ^= uint32((y << 7) & _TEMPER_MASK_1)
    y ^= uint32((y << 15) & _TEMPER_MASK_2)
    y ^= uint32(y >> 18)
    return y

它可能不是很明显，尤其是当你没有使用过二进制的逻辑运算，这个函数是双射或者说一对一的，每一个32比特的整数输入数组映射到一个输出。反过来，每一个32比特的数字的输出仅有一个32比特的数字作为输入。因为它使用了左移和右移的操作，可能会觉得它舍弃了一些数据，然后可能无法做逆运算。这些操作确实丢弃了一些比特，然后这个严格的计算异或：这些移位只是用来和回火掩码进行异或。异或操作是可逆的，因为每一个独立的操作都是可逆的，他们的组合也是。

因为回火函数是一对一的，它有一个逆函数：一个函数用来计算一个数的逆火数。如果对于二进制计算不是很熟悉，这个操作可能不是那么明显，但是没关系，最差情况也可以暴力地计算。假设尝试了每一个32位整数，然后记录这个对照关系在一张大表里。当需要结果的时候，查询一下表，找到原始值。这个表会有32*2^ 32比特大小，17GB，很大，但是不是不可能的。

幸运地是，有简单的方法来计算回火函数的逆。下一节将介绍为什么Mersenne Twister不是密码学安全的。对于对逆火函数感兴趣的，其源码如下：

def untemper(y):
    y ^= y >> 18
    y ^= ((y << 15) & _TEMPER_MASK_2)
    
    y = _undo_shift_2(y)
    y = _undo_shift_1(y)
    return y
 
def _undo_shift_2(y):
    t = y
    for _ in range(5):
        t <<= 7
        t = y ^ (t & _TEMPER_MASK_1)
    return t
  
def _undo_shift_1(y):
    t = y
    for _ in range(2):
        t >>= 11
        t ^= y
    return t

密码学安全

密码学安全指的是：它不能预测到未来的输出也不能用现在的输出覆盖过去的输出。Mersenne Twister不具备这个特性。

伪随机数生成器，包括这些密码学安全的和不安全的，都定义了他们的内部状态。毕竟它们是确定性的算法：它们只是努力地假装它们不是。密码学安全的和原始的随机数生成器的本质区别是密码学安全，算法不能泄漏任何有关于它们内部状态的信息，而一般的算法则无所谓。

记住Mersenne Twister，随机数是由当前的状态的元素产生，使用回火函数，然后得到结果。并且回火函数有逆函数。也就是得到了算法的输出，然后使用逆函数，就可以得到状态的624个元素中的一个。

假设我是唯一一个看到算法输出的人，然后你在状态的开始阶段也就是算法的一个新的实例，这也就意味着仅需要产生624个随机数，我就可以克隆你的状态。

尽管攻击者并不能看到所有624个数字，他们通常也可以重构未来的状态，这主要是由于过去状态与未来状态之间简单的构造函数。

再次，这不是Mersenne Twister的弱点。它被设计的快速并且强随机。它并不是用来不可预测的，而这恰恰是密码学安全的随机数生成算法的特性。