[科普中国]-随机数生成器攻击

加密系统的安全性取决于秘密保护的数据，这些数据应该对已授权者可知，但是对其他人不可知且不可预测。实现不可预测特征的方法就是部署随机化。现代加密协议通常需要频繁生成随机的数量，在这个过程中破坏或利用弱点的攻击被称为随机数生成器攻击。

对于安全需求来说，高质量的随机数发生（RNG）的过程几乎总是有需要的。生成过程缺乏质量通常会导致受攻击时的脆弱性，因此导致密码系统缺乏安全性，甚至完全不安全。RNG的过程对于攻击者而言是特别有吸引力的，因为它通常位于一个孤立的易于定位的硬件或软件。 如果攻击者可以用一种他可以预测的伪随机数替换RNG过程，安全性就会受到完全损害，但是上游的测试对此通常是无法侦测到的。不仅如此，这种攻击只需要接入一次受攻击的系统，不需要向攻击者返回任何数据，换句话说，就是一个计算机病毒 ，偷取了密钥然后用电子邮件向一些接受点发送。

人工生成的随机数人工生成的随机数通常极差。魔术师，职业赌徒和骗子，他们都依赖于预测人的行为。 在第二次世界大战中，德国代码文员被指示随机挑选三个字母作为恩尼格玛密码机中每条消息的转子初始设置。但是，有些人选取了可预测的值，比如他们的女友的姓名的首字母，这大大帮助了盟军破译德国的加密系统。另一个例子就是计算用户选择密码的方式通常可以预测（参见密码破解）。

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

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

直接密码分析攻击

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

以输入为基础的攻击

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

状态妥协扩展攻击

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

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

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

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

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

防御将硬件生成的随机数与高质量流加密输出（比如逻辑异或)混合，并尽可能地接近使用点。流加密密钥与随机数种子应当可以用可审计的方式进行修改并从可信来源中派生，例如掷骰子。Fortuna随机数生成器就是一个使用这些机制的范例算法。

使用真正随机的来源生成密码。有些系统会代为用户选择随机密码而不让用户自行提交。

使用加密系统来记录随机数生成过程，并提供审计生成过程的方法。

用现有的硬件构建安全系统，最好以未告知预期用途的方式购买硬件，例如大型零售机构。从这个角度来说，声卡与网络摄像头对比硬件随机数生成器是更好的随机化来源。

在购买后保持对硬件的完全物理控制。

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

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

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

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

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

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

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

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

Java实时碰撞2013年八月，据透露Java类SecureRandom中的错误可以在用于Android设备上比特币软件中的knonce数值上生成冲突。当错误触发时，私钥可以恢复，因而导致包含钱包中的比特币失窃。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学