随机数生成器攻击

隨機數生成器攻擊（英語：Random number generator attack），是針對加密系統中，隨機數生成（RNG）的環節進行破壞或弱點利用的攻擊。

一個密碼系統的安全性取決於機密訊息只能由已授權人員可知，其他人不可知且不可預測。為了達到不可預測性，通常會採用一些隨機化的過程。為了系統的安全性，必須要有一個高品質的隨機數生成方式，低品質的生成方式會產生安全漏洞，導致系統發生洩密。^[1]由於亂數生成的部分通常只牽涉到單個孤立的硬體或軟體，非常容易尋找，所以對攻擊者而言特別有吸引力。如果攻击者可以用一种他可以预测的伪随机数替换RNG过程，安全性就会受到完全损害，但是上游的测试对此通常是无法侦测到的。此外，對於已被破解的系統，攻擊者只需進行一次訪問，不需要再進行回傳。與之相較，電腦病毒在偷取密鑰後，還需要透過電子郵件等方式將密鑰回傳給攻擊者。

人工生成的随机数

對於產生亂數這件事，人類通常表現不佳。魔術師、職業賭徒和詐騙犯都仰賴於人類行為的可預測性。在第二次世界大戰中，德國的譯電員們在使用恩尼格瑪密碼機時會依照指示隨機選擇三個字母作為轉子的初始設定。然而有些人會選用一些可預測的字母，比如他們自己或女友的名字縮寫，這大大的幫助了盟軍破解這些加密系統。另一個例子是電腦的使用者常常會選用一些容易預測方式選擇密碼。

尽管如此，Ran Halprin 与 Moni Naor 研究了在混合策略游戏中的一些特定情况下，使用的人玩游戏时的熵来产生随机性。^[2]

攻击

软件随机数生成器

仅作为加密系统的其它组件而言，软件随机数发生器在设计上应该能抵抗一定的攻击。攻击类型可能包括^[3]：

直接密码分析攻击

若攻击者可以获得随机数生成序列的一部分，并且可以据此将发生器的输出从真正的随机流中区分出来时，此类攻击可行。

以输入为基础的攻击

修改发生器的输入来进行攻击，例如通过将现存的熵“清洗”出现有的系统，并把系统设置为已知的状态。

状态妥协扩展攻击

在内部保密状态的发生器在某个时间是已知的，据此可以预测未来发生器的输出或恢复之前的输出。 这可能发生在发生器刚刚启动并且发生器仅拥有少量或没有拥有任何熵的时候（特别是计算机刚刚启动并且正在执行一个非常标准的操作序列的时候），因此在这个状态下，攻击者可能能够获得初步的猜测值。

硬件随机数生成器

许多针对硬件随机数生成器的攻击都是有可能的，包括尝试捕获计算机的射频发射（例如从电机噪音中推断硬盘中断时间），或者尝试将受控的信号反馈到假定的随机源当中（比如关闭熔岩灯中的灯光或是将已知的强信号反馈到声卡）。

随机数生成器颠覆

颠覆随机数可以在密码学安全伪随机数生成器中使用随机数种子值来生成，种子值虽然隐藏在软件中，但是对攻击者已知。相对较短，比如24到40比特，种子可以是真正随机的，可以防止重复，但是并不足以防止攻击者恢复“随机”生成的密钥。

随机数在使用前会通过数层特定的软件和硬件。数据可能在外围设备中生成，通过电缆传输，由操作系统组件收集并由系统调用进行检索。这一过程中的任何一点都可以替换颠覆的数据，并且几乎无法检测。

仅仅需要数平方毫米就可以使用集成电路建造一个用于生成颠覆随机数的硬件电路。通过将这种芯片放置在上游任何随机性来源数字化的地方，就可以破坏最先进的硬件随机数生成器，例如在输出驱动芯片中甚至在把计算机与生成器连接起来的电缆中。破坏芯片可以带有一个时钟来来把操作启动时间限制到单位初次启动之后，并且还能通过接受测试，也可以带有用于开关控制的无线电接收器。破坏芯片的安装可以是国家情报服务机构对制造商的要求，或者是之后任何有物理访问权的人。用于替换内置硬件随机数生成器的CPU芯片的可以是任意的兼容芯片，其固件中可以包含已颠覆的随机数生成器。

防御

• 将硬件生成的随机数与高质量流加密输出（比如逻辑异或）混合，并尽可能地接近使用点。流加密密钥与随机数种子应当可以用可审计的方式进行修改并从可信来源中派生，例如掷骰子。Fortuna随机数生成器就是一个使用这些机制的范例算法。
• 使用真正随机的来源生成密码。有些系统会代为用户选择随机密码而不让用户自行提交。
• 使用加密系统来记录随机数生成过程，并提供审计生成过程的方法。
• 用现有的硬件构建安全系统，最好以未告知预期用途的方式购买硬件，例如大型零售机构。
• 在购买后保持对硬件的完全物理控制。

设计一个安全随机数生成器至少要求与设计密码系统的其它部分一样高的水平。

突出例子

可预测的网景随机数种子

在早期版本的网景传输层安全性协议（SSL）中的加密协议中使用了伪随机数，来源是伪随机数生成器根据三个变量派生的：一天中的时间、进程ID与父进程ID。这些伪随机数相对而言通常是可预测的，因此熵值很低并且也少于随机数，亦因此发现这一版本的SSL并不安全。Phillip Hallam-Baker于1994年向网景公司报告了问题所在，随后也向CERN网络团队的一位研究员报告。但是问题在发布前并未修复。1995年，Ian Goldberg与David Wagner发现了这一问题^[4]，二人当时因为网景公司拒绝透露其随机数字生成器（静默安全性）的细节，而不得不对目标代码进行逆向工程。随机数生成器在后来的版本（第二版及更高）中通过更强的随机数种子（即从攻击者的角度来看，更随机和更高的熵）得到修复。

Microsoft Windows 2000/XP 中的随机数生成器

微软使用未发布的算法来为其Windows操作系统生成随机数值，并通过CryptGenRandom实用工具提供给用户。2007年11月，来自耶路撒冷希伯来大学与海法大学的Leo Dorrendorf et al. 发布了一篇名为《Windows操作系统中的随机数生成器的密码学分析》（Cryptanalysis of the Random Number Generator of the Windows Operating System）的论文。^[5] 文中指出了当时微软的生成方法中的严重缺陷，结论基于对Windows 2000中代码的反汇编，但是根据微软的说法，这些代码也存在于Windows XP。^[6] 微软已经表示，文中描述的问题已经在Windows的后续版本中得到解决，后者使用了不同的随机数生成实现。

椭圆曲线DRBG中可能的后门

美国国家标准技术研究所（NIST）发布了“确定性随机位发生器”，并且推荐于NIST的特刊800至890期中。^[7]其中叫Dual_EC_DRBG的生成器受到了国家安全局（NSA）的青睐。^[8] Dual_EC_DRBG使用椭圆曲线加密并包含一组推荐使用的常量。2007年八月，来自微软的Dan Shumow与Niels Ferguson显示这些常量可以通过在算法中创建一个窃密学（英语：kleptography）后门的方式来构建。^[9] 2013年九月，《纽约时报》（The New York Times）发文称“NSA向NIST于2006年接纳的一向标准中植入了后门...名为Dual EC DRBG标准”，^[10]从而揭示了NSA对美国人民进行了恶意软件攻击。2013年12月，据路透社报道，爱德华·斯诺登（Edward Snowden）发布的文件显示，NSA已经向RSA安全公司支付了1000万美元，将Dual_EC_DRBG作为后者的默认加密软件，也因此出现更多关于该算法包含NSA后门的担忧。^[11]出于这些担忧，2014年，NIST从其关于随机数发生器的指导草案中撤销了，推荐“现有的Dual EC DRBG用户尽快切换到其余三个算法。”^[12]

MIFARE Crypto-1

Crypto-1是由NXP开发的用于MIFARE芯片的加密系统。作为专有系统，其算法最初并未公布。根据对芯片的逆向工程，来自弗吉尼亚大学与Chaos Computer Club的研究人员发现了针对Crypto-1中随机数发生器的初始化不良漏洞。^[13]

Debian OpenSSL

2008年五月，安全研究员Luciano Bello透漏了一项发现，关于2006年在随Debian GNU/Linux和其他基于Debian的发行版，例如Ubuntu，中分发的OpenSSL软件包中随机数生成器的变化。这些变化大大降低了生成值的熵值，使得各种安全密钥易受攻击。^[14][15]这个安全漏洞是由于Debian开发者为解决冗余代码的编译器警告，随即对OpenSSL代码做出了这些修改，^[16]从而导致了密钥在世界范围内的大量重构，尽管所有人都注意到了这个问题，但可以推测出许多旧密钥仍在使用中。受影响的密钥类型包含SSH密钥、OpenVPN密钥、DNSSEC密钥、SSL/TLS连接中使用的X.509证书密钥材料与会话密钥。使用GnuPG或GnuTLS生成的密钥由于使用了不同的方法来生成随机数而未受到影响。由非Debian系的Linux发行版生成的密钥也未受到影响。接到报告之后，漏洞及时得到修补，但是任何仍然使用由旧代码生成的密钥的服务仍然是脆弱。许多软件包现在都包含针对弱密钥黑名单的检查，以试图预防使用剩余的弱密钥，但是研究人员仍旧陆续发现了薄弱的密钥实现。^[17]

PlayStation 3

2010年12月，一个自称fail0verflow 的团体宣布了恢复椭圆曲线数字签名算法（ECDSA）私钥的方法。索尼公司使用这种私钥来为PlayStation 3来签名游戏包。攻击的可能性来源于由于索尼未能为每个签名产生一个新的随机数。^[18]

RSA公钥分解

2012年，Lenstra、Hughes、Augier、Bos、Kleinjung与Wachter发布了一篇关于从互联网收集数百万个RSA公钥的分析。他们仅使用了欧几里得算法就分解了0.2%的密钥，^[19][20]利用的是基于整数分解的密码系统特有的弱点。若 n = pq 是一个公钥，n′ = p′q′ 是另一个，那么如果偶然间 p = p′，那么简单计算gcd(n,n′) = p 因数都是 n 和 n′，完全破坏了两个密钥。一个进行过类似实验的组织的一员Nadia Heninger说，劣质密钥几乎完全出现于嵌入式系统中，由两组结果发现的共享素数问题是由于伪随机数发生器最初做种不良，然后在第一个和第二个素数的产生之间发生了重新做种。

Java实时碰撞

2013年八月，据透露Java类SecureRandom （页面存档备份，存于互联网档案馆）中的错误可以在用于Android设备上比特币软件中的k nonce数值上生成冲突。当错误触发时，私钥可以恢复，因而导致包含钱包中的比特币失窃。^[21]

另见

• 伪随机数生成器
• 密码学安全伪随机数生成器
• 密钥生成
• 一次性密码本
• 盐
• Nonce

参考资料

1. Michael Jenkins; Lydia Zieglar. . IETF draft draft-jenkins-cnsa-cmc-profile-00. U.S. National Security Agency. September 28, 2018 [2021-01-19]. （原始内容存档于2019-03-23）. The use of inadequate pseudo-random number generators (PRNGs) can result in little or no security. The generation of quality random numbers is difficult. 
2. Halprin, Ran. (PDF). [2017-12-17]. （原始内容 (PDF)存档于2018-02-05）. 
3. Kelsey, J. . Fast Software Encryption, Fifth International Workshop Proceedings. Springer-Verlag: 168–188. 1998 [15 August 2013]. （原始内容存档于2015-07-15）. 
4. Goldberg, Ian. . Dr. Dobb's Journal. January 1996 [2017-12-17]. （原始内容存档于2016-05-22）. 
5. Dorrendorf, Leo; Gutterman, Zvi; Pinkas, Benny. Cryptanalysis of the random number generator of the Windows operating system (PDF). ACM Transactions on Information and System Security. 1 October 2009, 13 (1): 1–32 [2017-12-17]. doi:10.1145/1609956.1609966. （原始内容 (PDF)存档于2012-09-06）. 
6. Keizer, Gregg. . Computerworld. November 21, 2007 [2017-12-17]. （原始内容存档于2014-08-14）. 
7. Barker, Elaine. Recommendation for Random Number Generation Using Deterministic Random Bit Generators (PDF). NIST. January 2012 [2017-12-17]. （原始内容 (PDF)于2013-10-09）. 
8. Schneier, Bruce. Did NSA Put a Secret Backdoor in New Encryption Standard?. Wired. November 15, 2007 [2017-12-17]. （原始内容于2008-05-11）. 
9. Shumow, Dan. On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng (PDF). http://cr.yp.to/. 21 August 2007 [2017-12-17]. （原始内容存档 (PDF)于2014-02-26）. 
10. Perlroth, Nicole. Government Announces Steps to Restore Confidence on Encryption Standards. The New York Times. 10 September 2013 [2017-12-17]. （原始内容于2014-07-12）. 
11. Menn, Joseph. Exclusive: Secret contract tied NSA and security industry pioneer. San Francisco. Reuters. December 20, 2013 [December 20, 2013]. （原始内容于2015-09-24）. 
12. NIST Removes Cryptography Algorithm from Random Number Generator Recommendations. National Institute of Standards and Technology. 21 April 2014 [2017-12-17]. （原始内容于2016-08-29）. 
13. Nohl, Karsten. . SS'08 Proceedings of the 17th conference on Security symposium. USENIX: 185–193. 2008-07-31 [2017-12-17]. （原始内容存档于2019-03-23）. 
14. . Debian Security Advisory. 13 May 2008 [2017-12-17]. （原始内容存档于2014-02-20）. 
15. . CVE. January 9, 2008 [2017-12-17]. （原始内容存档于2021-05-06）. OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems uses a random number generator that generates predictable numbers, which makes it easier for remote attackers to conduct brute force guessing attacks against cryptographic keys. 
16. Schneider, Bruce. . May 19, 2008 [2017-12-17]. （原始内容存档于2021-05-10）. 
17. . [2017-12-17]. （原始内容存档于2019-12-08）. 
18. Bendel, Mike. . Exophase.com. 2010-12-29 [2011-01-05]. （原始内容存档于2019-04-07）. 
19. Markoff, John. . The New York Times. February 14, 2012 [2017-12-17]. （原始内容存档于2021-04-17）. 
20. Lenstra, Arjen; Hughes, James P.; Augier, Maxime; Bos, Joppe Willem; Kleinjung, Thorsten; Wachter, Christophe. (PDF). Santa Barbara: IACR: 17. 2012 [2017-12-17]. （原始内容 (PDF)存档于2021-04-28）. 
21. Chirgwin, Richard. Android bug batters Bitcoin wallets. The Register. 12 August 2013 [2017-12-17]. （原始内容存档于2013-08-17）. 

延伸阅读

• Gutterman, Zvi; Benny Pinkas; Tzachy Reinman. (PDF). IEEE S&P. Oakland Conference. May 2006: 371–385 [2017-12-17]. （原始内容 (PDF)存档于2017-12-07）. 
• Eastlake, D. . RFC. IETF. June 2005 [2017-12-17]. （原始内容存档于2018-05-09）.