Volume 0x0b, Issue 0x3b, Phile #0x0f of 0x12


|=--------=[ CRYPTOGRAPHIC RANDOM NUMBER GENERATORS ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Author: DrMungkee <pub@drmungkee.com> ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Translator: winewind <winewind@163.com>]=-------=|



密码学里的随机数发生器

----| 介绍

对于密码系统的安全性来说，每个组件都是很重要的。一个组件设计的失败可能使其他所有的组件崩溃。密码随机数常常被用作密钥，补充信息，辅助信息和初始化向量。对每一个组件来说，使用一个好的随机数发生器（RNG）是必要的。利用计算机行为的可预测性,可以人为的制造很多复杂因素。本文的范围涵括了随时数产生器的设计，执行和分析。将要涉及的随机数发生器(RNG)包括：NoiseSpunge, Intel 随机数发生器（Intel RNG），Linux下的“/dev/random”和Yarrow。


----| 关键词：

RNG - 随机数发生器（Random Number Generator）
PRNG - 伪随机数发生器（Pseudo Random Number Generator）
信息熵（entropy） - 不可预知信息（Unpredictable information）
冗余信息（redundancy）- 可预知信息（Predictable or probabilistic information）

（译者注：entropy一词源于物理，是“熵”的意思。在信息技术中引入，从而有了“信息熵”的说法。“熵”的特性：在封闭系统中，系统的熵只会增加或保持不变，系统的平衡点是熵最大的时候。无线电中常翻译成“平均信息量”。我也不知道这里用信息熵的说法是否便于理解。如果觉得别扭，就理解成一种信息好了）

（译者注：这里我加入一段引来的文章，可能会让大家对这个名词了解得更好：现代信息学的基础是信息熵理论，即对被传送信息进行度量的一种平均值，单位是比特。四十年代，现代信息论创始人、美国贝尔实验室科学家闪农（C．Shannon）发明了信息熵理论，由此提出了数据优化编码、输入输出效率、通讯传递渠道效率、多余度和数据压缩等一系列信息科学基础理论和技术。信息熵是信息产业的地基。比如，不管计算机硬件软件如何更新换代，英文的字符平均信息熵（静态信息熵）是4．03比特，因而，处理和储存英文数据的每个字符的编码不能少于5比特；中文的汉字平均信息熵是9．65比特，因而，处理和储存中文数据的每个字符的编码不能少于10比特。）


1.0) 概述

设计一个随机数发生器(RNG)需要考虑各种因素。在白噪音环境中（译者注：在一定带宽内，在各个频率上，各种噪音的强度都是一样的），输出必须是不可识别的。输出的任何一部分都是不可预知的。而且基于已知的结果，无法推算出上一步（不可逆）和下一步的结果。如果一个随机数产生器不能遵照这个标准，那么产生的密码是不安全的。

1.1) 信息熵（entropy）的收集：

为了满足第一条和第二条要求，为这些信息熵找寻好的来源（信息源）就成了一个首选任务。这些信息源对于攻击者必须是不可监测的。而且任何对信息源的操作对攻击者来说都是不可知和无法重复的。

鼠标的移动常常被用作信息熵的一种。但是如果RNG不能正确的处理信息熵，将会产生大量的冗余信息。举个例子，鼠标移动的时间间隔是100毫秒。当鼠标在各方向快速移动时，其位置记录如下：


    X-轴          Y-轴
  0000001011110101  0000000100101100   注意：在各个坐标中只
  0000001000000001  0000000100001110   有最后九位是随机的。
  0000001101011111  0000001001101001   
  0000001000100111  0000000111100100
  0000001010101100  0000000011111110
  0000000010000000  0000000111010011
  0000001000111000  0000000100100111
  0000000010001110  0000000100001111
  0000000111010100  0000000011111000
  0000000111100011  0000000100101010

下面的例子演示了一个更加实际的信息熵的收集过程。保留X-坐标和Y-坐标的最后四位(因为它们最重要),和采样得到的时间作异或运算，并把它们随意排列如下：

   X    Y     时间    异或后
  1010  1001  00100110  01111111
  0100  1100  00101010  00000110
  0101  0010  01011111  01110101
  1001  1100  10110000  11111100
  0101  0100  11001110  11100010
  0101  1100  01010000  01111100
  1011  0000  01000100  00011100
  0111  0111  00010111  00101000
  0011  0101  01101011  01110110
  0001  0001  11011000  11010001

这是一个好办法，因为从各坐标得到的四位数代表了在16像素平面上的任意方向（译者注：上面的数据表明，这个范围对纪录鼠标的运动已经足够大了），而不是 256*256平面上65536种移动方向。选用时间是因为虽然它们是连续的，但是它们的最后八位在CPU时钟周期内非常频繁的变化,这些比特位是无法人为预料的。异或运算用于合并两方面的信息熵。在合并数字并且保留各比特位的独立上，异或是个好办法：）

最常见的信息源包括用户的人为反应或某种经过排列变形后的高频时钟的序列。把上面两种合二为一得到的结果往往就是我们所需要的。用高精度采集用户触发事件的反应时间（击键，磁盘输入/输出，中断，鼠标点击）的方法有其优越性，因为用户个体行为和精确的时间是不可预知的。

有些信息看起来是足够随机的，但实际上未必。有时可以把网络的输运情况作为一种信息源，但我们并不推荐这样做，因为这种信息毕竟还是可以由某些外来因素控制的。另一个缺点是使用毫秒精度的时钟：对于比较高的要求，这种刷新频率显得的太慢了。

在讨论信息熵收集方法缺点方面，这里有一个不错的案例：Netscape公司使用的SSL加密协议是可破解，它并没有使用真正的RNG。（译者注：可以在下面的网址找到介绍 http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html）Netscape公司标志进程和父进程时使用时间和日期，并把它们当作唯一的信息源。在win9x中进程标志通常都是由一个小于100的值（每增加一个新进程就加一）和win9x第一次启动时的时间日期作异或运算得到。虽然由哈希函数得到的结果看起来是随机的，实际上猜测出那个值，计算并且得到正确的结果并不是件难事。如果可利用的信息熵非常有限，那么输出结果是不是真的随机也就不是很重要了（好像有点无奈的意思）。


1.2 信息熵的估算

我们不能忽视对收集到的信息熵总数的估算。这一步很重要。否则随机数产生器输出结果中信息熵的数量有可能超过输入的信息熵的数量。根据相应的系统参数，我们可以给各个信息源赋相应的值。比如，对于键盘活动，不管我们能够收集的信息熵总数是多少，我们都可以假设所有键盘活动产生的信息熵的大小都是4比特的。如果RNG在文件服务器上，并且把磁盘输入/输出作为信息源，我们可以根据某时刻正在访问磁盘的用户数相应的估计信息熵，而不是根据访问序列。如果基于后者，则可能产生多余的信息。对信息熵大小的估算不一定要和输入或输出的大小一样。这条准则在今后的计算中能起到安全预防的作用。

对信息熵的估算还有其他的方法。如果信息源超过一定时间间隔后还没有给我们提供数据，使用统计的方法计算偏差会获得更好的效果。我们可以从buffer收集大量的数据信息，经过压缩，得到压缩比的值。相对于之前输入的大量数据，统计测试表明，最后一次输入的数据对于检验当前输入数据整体属性起不到什么作用。但是对于RNG来说，则意味着可以把这些只能增加统计概率的输入数据舍弃。

最好的办法莫过于多试几次。在估算信息熵值时用一种方法往往是不够的。信息源的情况是复杂的，得到的信息熵也是多种多样的。可是在实际中，对所有的信息熵的大小往往赋同一个值。因此在做这种假设之前，必须仔细的分析一下。多尝试几个值是明智的选择。而最小的值往往是最准确的。


1.3) 信息熵的集合

没有任何信息源可以说是完美无缺的。确切点说，在计算机上是这样。这就是为什么我们在buffer（信息熵的集合）收集了信息之后还要进行一些处理。收集完毕后，信息熵就被输入到一个集合里。这个集合必须和输入有以下的关系：要知道包含元素的个数，把最后一次输入合并到之前收集的数据中并保持其一致性。另外，抛开那些收集到的信息熵的属性不论，集合还要为这些数据提供一个至少看起来随机的状态（相似的输出在这个集合里也应该是看起来随机的）。

对于某个集合状态，处理集合内容时（这里指把所有元素合并起来），既不能减少元素，也不能添加元素。如果经过某个合并函数的处理，集合变大了，那么必须保证这对信息熵的估算是没有影响的。只有那些负责收集信息熵的函数才能改变信息熵的大小。而且这些收集函数是分开作用的，彼此独立。

最好的合并函数是哈希算法（译者注：又称散列法）。哈希算法能够接受任意大小的输入，它的大范围输出可以反映信息熵合并的速度，并且这个算法的输出是不确定的。为了保护那些合并后的信息熵（译者注：保证没有信息丢失），哈希函数输入的大小不大于输出的。也就是说，如果哈希函数的输出是160位的，那么之前的输入最多160位。如果哈希函数用于密码处理上是安全的（事实上的确如此），那么输出的信息熵的个数应该和输入的一样。但是如果输出的多于输入，并不能认为信息熵集合里的态一定增加了。

处理大集合有以下几种途径：一种方法是把这个集合线性hash（杂化）。使用这种方法，你可能需要一个buffer保存最近的一次输入。hash从buffer的尾部开始，一次只hash一块（块的大小和输出的大小相同）。每次把当前输出和前一个块的hash结果作异或运算，以次保证整个集合只被最近的一次输入作用，而不会改写以前的结果。这只是一个例子。不管你选择什么样的处理方式，必须保证这种方式遵守前面所说的各条准则。

另一个处理大集合的方法是“multiple hash(多样杂化)”，使集合的内容互相影响。一个常见的用途就是用于处理包含“不可操作的信息熵”的集合。一旦这个集合满了，它就会被hash并用于更新另一个集合。更新的方式可以是更新hash的关系，也可以是直接作异或运算。这样尽可能多的集合就串联了起来。为了避免丢失已有的信息熵，一些集合只有在它们的父集合（更新这些集合的集合）被更新若干次（译者注：更新次数事先定义好的）后才能被操作。比如，只有当第一个hash集合被更新了8次后，下一个集合才能被更新。只有下一个集合被更新满了3次，它才能用于hash第三个集合。在这种方法里，第三个集合包含了经过24次hash的信息熵。这样保留下来的原始信息熵变少了（受杂化关系的限制）但是这些信息熵的性质却更好了。因为第三个集合里的信息源完全基于24次输入的信息熵。

向一个集合中输入信息熵往往称为更新或播种。这种信息熵的集合和基于它自身构建的输出函数实际上是一个PRNG。在收集信息熵的过程中获得的真正的随机种子才是得到RNG的原因。只要输入了一个好的信息熵，RNG就产生一个无界区域（没有输出模式）。这和PRNG正好相反。相对于RNG的无界区域，后者是从一个半确定的点开始，重复以前的所有输出，并且重复的顺序和RNG是一样的。

信息熵的集合对于防范攻击者推算RNG以前的输出和以后的输出结果至关重要。对RNG的攻击就是基于三部分：对信息熵集合性质的了解，信息熵的输入和以前的输出结果。要防止别人了解集合当前的状态，就要对以后的输出结果做一些处理。因此，集合必须不时地做一些大的变动，删除一部分或是全部的信息熵。这个过程叫做再播种。再播种，总是（译者注：用逗号隔开是为了强调），在输出之前用一些新的信息熵替换那些已经被删除的。如果没有上面的替换，这个集合的安全性就很成问题了。RNG不需要再播种，但是如果没有这步，就必须不停的添加信息熵的输入，添加的速度还要高于输出的。

并不是任何时候都要再播种的。只有当未用过的信息熵积累了足够多并且占了集合空间的一大部分时才使用再播种。要注意的是，对集合中信息熵的估算要随着输入数据的大小作相应的调整。再播种不能频繁的使用。是否使用它的唯一根据就是随机数生成器输出的比特位数和整个集合的大小。当集合里95%的信息熵都已经输出时采用再播种，这是一个比较适当的频率。这里我们假设信息熵的输入是在RNG输出的空隙间完成的。如果不是这样，那么使用再播种的次数有可能应该更多一些。在输出空隙间输入的信息熵越少，攻击者就越容易找到输出方式的蛛丝马迹，从而推算出上一次输出的结果（这样循环往复，一个链式的逆向推算就有可能成功地得到攻击者想要的东西）。（译者注：这里我们并不规定两次输出之间只能有一次输入。相反，输入的数据应该多于输出。这样，可以想象，在集合里用不到的数据会越来越多。等他们多到一定程度时，如上文的95%，一次性的替换掉。这就是一次的再播种。）

1.4）输出函数

RNG的输出函数必须是单向的。单向的意思是输入的数据经过函数处理可以得到输出，但是根据输出的数据无法计算出输入的原始数据（译者注：就是不可逆啦，饶舌）。单向的hash函数是一个非常好的选择。更复杂的方法是把集合中的一部分元素作为key data（译者注：不好意思，我一时还想不出什么好的词），使用对称加密算法，对另一部分加密，并且输出密文。压缩-解压缩也是一个效率很高的单向函数。为了达到目的，我们可以把集合中一部分元素当作PRNG的种子，生成多种输出（根据PRNG的种子大小而定）。然后把这些输出统统放进一个杂化函数得到结果。这样做保证了效率，因为处理时很多中间态（解压缩）hash的结果都是一样的，真正起作用的只是解压缩前的那个初始态。

RNG每次输出时，对它信息熵的估算都要随输出的大小而减少。这样做的前提是假设输出的数据都是由信息熵组成。由于输出的信息熵仍然保留在集合里，这些东西现在就成了冗余信息，也不该再把它们当作信息熵了（在集合里）。如果集合的大小是512位，且每次输出信息熵的大小是160位，那么三次输出之后，基本上所有的信息熵都被hash了，这个集合也就需要再播种了。

在处理信息熵集合时，有一个几乎不可能解决的问题：我们没办法确定信息熵的哪些位是要输出的，哪些不是。缓解这个问题最好的办法是：即便你看到了RNG的输出结果，我们也根本不让你知道哪些信息熵被用了几次。（译者注：看起来有点掩耳盗铃，但的确管用。我偷偷地用，用几次谁也不知道。感觉差不多了，我就再播种了。神不知鬼不觉）当一次输出完成后，集合的态发生变化，重新排序。这样，在既不添加信息熵也不再播种的情况下，RNG的输出结果也不会重复。集合的态的重新排序必须通过单向函数完成，而且输出函数必须满足前面提到的各条原则。只要处理的过程不违反前面的规定，我们认为集合里信息熵的大小在排序前后总是一致的。

1.5）执行

如果执行时不顺利的话，我们前面所作的所有努力都是白费。这里关于执行我们要谈三个方面的东西：媒质，硬件/软件和输出的使用。

在未加密状态，储存媒质和通信媒质各占了一个风险。下表列出了各种媒质的风险程度。对于风险程度的比例说明是这样的：

0 - no risk    无风险
1 - low risk    低风险
2 - medium risk  中等风险
3 - high risk   高风险

MEDIA （媒质）                 RISK（风险）
---------------------------------------------------
RAM          <storage>（储存）      0 *&
Hard Drive     <storage>（储存）      1 *&
Shared memory   <transfer>（传输）      1 *&
Removable disks  <transfer>（传输）      2
LAN          <communication>（通讯）  2 &
WAN          <communication>（通讯）  3

任何正确加密的媒质的风险都是0。
*如果储存媒质是在一台与网络相连的计算机上时，风险度还要加1。
&如果可以通过物理途径到达的话（computer/Lan），风险度也要加1。

所有媒质的最高风险都应该被解释成执行风险（向脆弱的机制说再见吧:）。高风险在实际中是不可接受的。媒质的风险程度是否可被接受取决于RNG的输出值（想想这在攻击者眼中的价值吧）。除非在你的壁橱里有许多的万能钥匙，否则一本私人日记就足以应付介质风险了（译者注：这里可能不太好了解。但就我的经历，国外用的日记本大多是带锁的。国内也有这种日记本，不过好像比较贵）。有关工业机密的一定要采用零风险的RNG。虽然什么样的风险是可以接受的往往取决于程序员，但是用户应该清楚地知道自己的选择。

硬件的RNG需要有监测能力。如果硬件发生了任何的物理修改，RNG就停止输出。这可以防止外界探测信息熵集合状态和输出。同时，外界无法通过频率，辐射，电压或者其他由RNG运行时产生的信息监控硬件的运转。一旦上述的任何一项可被探测，对于集合或输出来说都是一个危险。所以，所有的RNG硬件都要适当的屏蔽起来。

软件的执行就微妙的多了。防范逆向工程始终是个大问题，除非可执行文件发出的数字信号是在和操作系统一样的层次上执行的。否则，任何对逆向工程的防御措施只能是“缓兵之计”。所以，程序员一定要尽量减少软件的风险因素（上面的风险系数表对逆向工程依然适用）。