Dual_EC_DRBG后门

（公式与图太多，不好贴，所以后续内容粘过来很乱。。。详情请大家下载pdf。。。论坛附件限制，所以传到百度盘了）

http://pan.baidu.com/s/1qWuFITQ

1 时间线（翻译于wiki）：

December 2005

NIST SP 800-90A草案公开发布，其包含四个随机数生成算法：HASH_DRBG, HMAC_DRBG, CTR_DRBG, DUAL_EC_DRBG。

16 March 2006

Kristian Gjøsteen公开了其报告，称“Dual_EC_DRBG is not cryptographically sound”，并构造了一个具有0.0011优势的bit-predictor，证明了其不满足CSPRNG（CryptographicallySecurePseudo-RandomNumberGenerator）密码学安全的随机数发生器设计原理。

29 March 2006

        在Crypto 2007（原美密会，现为国际密码会议）会议上，Bruce Schneier的报告宣布该标准中存在技术后门，使得拥有某特殊资源的攻击者能够轻而易举地攻击其中的Dual ECC DRBG 随机数产生器算法，从而得到该算法后续的所有随机数值。

6 June 2013       

Edward Snowden泄露的NSA得第一份文件被曝光。

5 September 2013

        基于Edward Snowden泄漏的文件，NSA's Bullrun项目被曝光，其显示该项目尝试向世界范围内软硬件开发者所遵循的加密标准中引入weakness

10 September 2013

        New York Times 发表了一篇文章，声称Edward Snowden泄漏的内部备忘录，NSA在Dual_EC_DRBG中植入了一个后门。在同一天，NIST公共事务办公室主任称：“NIST不会在加密标准中故意留后门”。在随后的报告中，多家媒体将“NIST在Dual_EC_DRBG中添加后门”默认为事实。

19 September 2013

        美国EMC公司的RSA事业本部于2013年9月19日（当地时间）宣布，该公司已向其加密工具“RSA BSAFE”及“RSA Data Protection Manager”的客户发出呼吁，不要使用随机数生成算法的技术标准“Dual_EC_DRBG”。RSA同时引用NIST在9月12日的发言：美国国家标准技术研究院（NIST）建议用户不要使用该算法。
早期的报告显示，RSA公司的BSafe工具和数据保护管理其软件均默认使用Dual_EC_DRBG技术算法。因此，早已遭到众多密码学家的批评。RSA的首席技术官Sam Curry则在一次Ars Technica的采访中对RSA的选择做了解释和辩护。他表示，RSA目前正在审查其所有的产品。

20 December 2013       

路透社报道，NSA与RSA之间存在一笔$10 million的交易，其要求RSA在BSAFE中将Dual_EC_DRBG 设为默认的CSPRNG。

22 December 2013       

RSA公司发表声明，直接否认与NSA有任何的秘密接触，以便在BSAFE加密库中放置有缺陷的随机数生成器算法。但是RAS并没有否认或者解释之前与NSA之间$10 million的交易。

总结：
Dual_EC_DRBG算法可能潜伏着一个后门。如果以特定方式选择定义算法的一个参数，NSA将可能预测出算法产生的随机数。此次，受影响的加密工具“RSA BSAFE”及“RSA Data Protection Manager”中， RSA BSAFE是用来开发安全应用的工具套件，因此，使用该工具开发的很多应用都可能使用了“Dual_EC_DRBG”，并在市场上使用。RSA Data Protection Manager是用来进行数据加密的工具。这些产品的默认随机数生成算法均为“Dual_EC_DRBG”。

2 随机数生成器
2.1 随机数定义
随机数是一组同时具有无偏性和不可预测性的值，它是均匀分布的随机过程（Random
Process）输出，而且输出的值之间是统计独立的。
1） 无偏性（Unbiased）：如果某集合中各个元素被选取的概率是相同的，那么我们称从它中取得的值是无偏的。否则，称之为有偏的(Biased)。
2） 不可预测性（Unpredictable）：在本文涉及的领域中，一组输出比特流是不可预测的，如果一个攻击者仅能以可忽略不计优势（本质上跟直接猜测无异）正确地预测到将来输出，即便事先获得了过去和当前的输出。
3）不可回溯（Backtracking Resistance）性：即不能从当前或者将来的输出来得到过去的输出（NIST  SP800-90 标准）。
4） 均匀分布（Uniformly Distributed）：在本文涉及的领域中，是指统计学上的离散均匀分布，即有限集中每个事件（值）出现的概率是相同的。

2.2 随机数生成器分类
由于随机数被广泛用于密钥产生、初始化向量、时间戳、认证挑战码、密钥协商、大素数产生等等方面，因此随机数在密码学中的具有十分重要的地位。随机数产生器就是用于产生随机数的算法、函数以及设备。因此它的安全性也就对密码系统的安全性带来重要影响。可以这么说，攻破了随机数产生器在大多数情况下也就攻破了整个密码系统。所以，分析、设计和实现安全的随机数产生器具有重要的实际意义。进一步地，随机数产生器包括非确定性（真随机）数产生器（Non-deterministic Random Bit Generators (NRBG)）和确定性（伪随机）数产生器（Deterministic Random Bit Generators (DRBG)）两类。

2.2.1 非确定性数产生器
真随机数产生器：一般基于物理或化学熵源，比如原子运行轨迹、环境噪音、电路噪声，空气中颗粒数等等，这种随机数产生器的特点是随机性非常好，完全不可预测和回溯，但这些方法一般需要依靠特定的物理系统环境条件才能获取，所以应用范围有限。
例如，利用集成电路电信号方法可生成三种常用的非确定性随数产生器：
（1）直接放大器（Direct amplification）：它使用了一个高带宽的放大器将一个热源或者短噪声源的交流电压信号放大，然后通过一个比较器，按时钟取得比特流。
（2）振荡采样法（Oscillator sampling）：一般使用多相噪声源振荡器（理想情况是MOSFET 热噪声）来进行采样或者随机序列。
（3）离散时间混沌系统（Discrete-time chaos）：离散时间噪声源通过模拟/数字信号转换得到随机比特流。

2.2.2 确定性数产生器
伪随机数产生器：之所以被称为确定性随机数产生器，是因为在确定输入（种子）的情况下，它的输出也就确定了，相同的输入必然导致相同的输出，这类随机数产生器一般只依赖软件算法实现，对系统要求较低，应用范围广泛。因此确定性随机数产生器的安全性应当成为研究的重点。
确定性随机数产生器的种类非常多，例如：

（1）        线性同余法

相关文献中提出了评价该类随机数发生器的三个标准：
a） 产生函数应该是全周期的，即重复周期与m相等，亦即0 到m 之间的所有数都可能。
b） 产生的序列应该接近随机，因为是采用确定性随机数产生算法，所以并非真随机，但是有多种统计测试的方法可以评估其随机程度。

线性同余算法的安全性依赖乘数和模数选择。如果选择得当（即产生大周期的序列），用算法产生的随机数序列统计特性几乎与真随机数相当。但是，除了初始值外，算法没有任何其余的部分是随机的，一旦初始值确定了，后续随机数也就确定了。这也是确定性随机数发生器的一大问题，容易被密码分析者利用。因此，如果攻击者知道了上述算法及参数m， a和c ，那么他只要知道一个随机数，就可以获得后续的所有序列，也就是可以预测后续的所有值，破坏了随机数定义中的不可预测性。
另外，即便攻击者不知道m，a和c的参数值，他只要获得产生序列中的三个值，就可以利用中国剩余定理理论计算出m，a和c 。建议使用内部系统时钟来修正随机数流，一种方法是每隔N个数就以时钟值对m取模，以作为新的种子来产生新的序列。还有种方法是直接将随机数加上时钟值再对m取模。

（2）        计数器循环加密法
使用了主密钥生成会话密钥的过程，用一个周期为N 的计数器作为加密逻辑的输入。
循环加密算法的安全性取决与采用的加密算法和计数器周期，相关文献指出一种比较合理的想法是采用跟密钥长度相同周期的计数器，这样产生的伪随机数是全周期的。由于主密钥的保护，所以由产生的随机数不能推出后续的随机数。所以具有不可预测性，另外回溯也是不可行的。但是如果计数器是线性增长的，可以给攻击者获得部分信息。

（3）        分组加密反馈移位寄存器法

（4）        BBS 发生器

（5）        ANSI X9.17 伪随机发生器。

2.3 随机数产生器测试方法
1） 单比特测试（The Monobit Test）：
a) 获得随机数产生器的一个20,000bit 的序列，计算bit位为1的位的个数X。
b) 如果这个个数X介于9,654与10,346 之间，那么就认为该随机数产生器通过了测
试。

分析（均值分析）：
标准方法的单比特测试（The Monobit Test）就是一个均值分析，对于理想的随机数产生器来说，每次产生的1 个bit 为0 和1 的概率应该是相同的，对于nbit 的序列来说，出现1 的次数满足特殊的二项分布。
标准中给出的9,654 与10,346 之间即是包含10000 的范围，也就是期望偏差在0.346%以内，如果用正态分布拟合，即要求落在该区间内的概率超过99.9 %

2） 扑克测试（The Poker Test）：
a) 获得随机数产生器的一个20,000bit 的序列，将其分为5000 个连续的4bit 分组。计算这4bit 分组的所有16 种可能值出现的个数。设f(i)为4bit 值i 的分组出现的次数，其中0 ≤ i ≤ 15
b) 计算下面式子的值：

c) 如果 X 介于1.03 与57.4 之间，那么就认为该随机数产生器通过了测试。

分析（均匀性分析）：
一个理想随机数产生器，不仅要求序列中0，1 等概率分布，而且对于序列每个小区间内的0 和1 也要符合等概率分布，这样才能满足随机数特性要求中的均匀分布的特性。

3） 游程测试（The Runs Test）
a) 所谓游程就是连续的全0 或者全1 的最长序列。它们是随机数产生器的一个20,000bit 序列的一部分。也就是说，序列中所有长度游程都要被计算和存储。
b) 如果游程长度和对应出现的次数满足表1，那么就认为该随机数产生器通过了测试。其中0 和1 的游程分别要满足此表，并且长度大于6 的游程被认为是6。

4） 长游程测试（The Long Run Test）
a) 所谓长游程就是长度在34 以上的全0 或者全1 的序列。
b) 如果在随机数产生器的一个20,000bit 序列中没有长游程，那么就认为该随机数产生器通过了测试。

分析（独立性分析）：
理想的随机数产生器每bit 之间应该是互相独立的。可以通过计算序列中k 个bit 的独立性来进行分析，当然也可以采用序列相关系数来进行分析。游程测试和长游程测试就是为了进行独立性分析的。

3 NIST SP800-90 标准
3.1 简介
NIST(National Institute of Standards and Technology：美国国家标准技术管理委员会)于2006 年6 月发布了确定性随机数产生器推荐标准（SP800-90），并于2007 年3 月发布了其修订版。这是一个推荐性的标准，描述了一些产生随机比特流的方法，这些随机比特流可能被用于直接或者间接的产生随机数，并用于相关使用密码学的应用中。
这个标准中的确定性随机数产生器是基于确定性随机数产生器系统，并包含一个熵源输入。确定性随机数产生器系统使用某种算法，这种算法以一个熵源输入决定的随机数种子作为初始值。一旦种子确定，初始值也就确定了，这样随机数产生器就被称作已初始化的状态。   
由于确定性随机数产生器的本质，它产生的不是真随机数，而是伪随机数。所以种子必须包含一定的熵来保证随机性。如果种子是保密的而且算法设计得很完善，那么输出的比特就是不可预测的（基于初始化的安全强度）。
使用确定性随机数产生器的安全性是一个关于系统实现上的问题。在标准中值得注意的是，在实际应用中如果要评估某随机数产生器的安全性，那么它使用何种熵源也因作为一个考量因素。  
这个推荐标准包含如下内容：
1） 使用确定性随机数产生器系统的要求。
2） 确定性随机数产生器系统的规格参数，包括使用的hash 函数，分组密码以及数论问题。
3） 算法实现
4） 保证性考量

3.2 框架结构
NIST SP800-90 标准定义了一个确定性随机数产生器的模型，这个模型包含5 个基础函数：
1） 初始化函数或实例化函数（The Instantiate Function）：取得熵输入，并将其与时间随机数和个性化字符串混合（如果有的话），来产生种子，创建初始化的内部状态。
2） 产生函数（The Generate Function）：使用当前的内部状态，根据要求产生伪随机比特流，并为下一个请求产生一个新的内部状态。
3） 补种函数（The Reseed Function）：取得新熵输入，并将其与当前内部状态和任何提供的额外输入混合，产生一个新种子和一个新的内部状态。
4） 复位函数或去实例化函数（The Uninstantiate function）：将内部状态置零（擦除）。
5） 健康度测试函数（The Health Test Function）：判断确定性随机数产生器（DRBG）系统是否工作正常。
确定性随机数产生器系统模型如图2所示。

3.3 特性
3.3.1 种子的生成
SP800-90 标准中，DRBG 的种子产生都需要熵输入、时间随机数和个性化字符串（可选），如下图所示。

在补种时，上面三个输入将变为：内部状态值、熵输入和附加输入（可选）。这是该标准的比较有特点的地方之一。

3.3.2 不可回溯
SP800-90 标准中的所有算法都具有不可回溯（Backtracking Resistance）的特性。

具体来说，不可回溯就是指：
1）        State1到State2状态输出的比特流与随机产生的比特流是不可区分的。
2）        即便掌握了StateX的秘密信息，也无法恢复State1…StateX-1这些前驱状态输出比特流。

3.3.3 不可预测
只有在请求的间隔中，DRBG 得到了有效的补种情况下，SP800-90 标准中的所有算法才满足不可预测（Backtracking Resistance）的特性。我们观察上图。
所谓不可预测就是指：
1） Statex+1 以及将来状态输出的比特流与理想随机比特流是对于攻击者来说是不可区分的。
2） 即便掌握了Statex 的秘密信息， 也无法预测Statex+1 这些后续状态输出的比特流。

3.4 NIST SP800-90 标准算法
    NIST SP800-90 提供了4 种标准算法。即Hash_DRBG、HMAC_DRBG、CTR_DRBG、
Dual_EC_DRBG。

4 Dual_EC_DRBG算法
4.1 算法简介
这里Dual_EC_DRBG采用了椭圆曲线密码算，利用了数论中的离散对数这个困难问题。DRBG 系统具体定义如下表所示。标准中指定了3 个素数域上的椭圆曲线，其位长分别为256bit，384bit 和512bit。使用的椭圆曲线方程为：
y2 = x3 − 3x + b(mod p)

4.2 Dual_EC_DRBG漏洞
有

如果条件①additional_input 为空值。那么有：

另外如果条件②攻击者知道Q =aP中的a，并且条件③能得到一个ri 值，那么他就可以计算出下一次的ri+1 。推导过程如下：

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课