Dual EC DRBG 后门事件

双椭圆曲线确定性随机比特生成器（Dual EC DRBG）是 NIST 在 SP 800-90A（2006 年）中标准化的四种 DRBG 之一。它使用椭圆曲线上的两个点 P 和 Q 生成伪随机比特：每一步先计算 r_i = x(s_i * P)（点乘结果的 x 坐标），然后计算 s_{i+1} = x(r_i * P) 来更新状态，并通过 output = x(r_i * Q) 生成比特。该生成器在学术记法中看起来是合理的。它被纳入 NIST SP 800-90A，后来又得到 RSA Security 的认可，并成为其 BSAFE 加密库中的默认机制，因此进入了企业和政府软件。

Dual EC DRBG 中的后门利用了 P 和 Q 之间的关系。如果对手知道秘密标量 e，使得 Q = e * P，那么给定任意输出块，就可以执行以下计算：从 output = x(r * Q) 出发，穷举 r*Q 的 y 坐标，然后计算 r*P = (1/e) * (r*Q) mod n。得到 r*P 后，就可以预测所有未来输出并恢复内部状态。知道 e 就是后门所在；它等价于 Q 关于 P 的离散对数。NIST 标准提供了 P 和 Q 的取值，却没有解释它们的选取方式，因此无法验证它们是在没有陷门的情况下随机生成的。

2007 年 8 月，丹·舒莫夫和尼尔斯·弗格森在 CRYPTO 的简短报告会上发表了一篇奠基性论文，题为《NIST SP800-90 Dual Ec Prng 中存在后门的可能性》。他们从形式上证明，如果某人知道 e（Q 相对于 P 的 ECDLP），那么只需大约 32 字节的输出，该人就可以预测 Dual EC DRBG 的全部输出。他们通过一个玩具示例展示了这一点。他们的演讲在密码学界引起了广泛关注。布鲁斯·施奈尔写道：“我们无法知道 NSA 是否能够读取 Dual_EC_DRBG 的输出。”尽管有这一警告，Dual EC DRBG 仍在标准中保留了六年之久。

2013 年 9 月，《纽约时报》《卫报》和 ProPublica 根据爱德华·斯诺登泄露的文件发表报道，揭示 NSA 曾秘密地在密码学标准中植入漏洞。一份题为《信号情报赋能项目》的文件描述了一项每年耗资 2.5 亿美元的计划，旨在“秘密影响”加密标准和产品。尽管该文件没有明确点名 Dual EC DRBG，但密码学界将其与舒莫夫和弗格森的数学论证结合起来后，普遍得出结论：NSA 通过选择具有已知关系 e 的 P 和 Q 植入了后门，同时对 e 保密，并将这些常数提交给 NIST。

路透社于 2013 年 12 月报道，NSA 曾向 RSA 安全公司支付 1000 万美元，使 Dual EC DRBG 成为 RSA 的 BSAFE 密码工具包中的默认算法。RSA 安全公司当时是 EMC 的一个部门，曾将 BSAFE 分发在企业软件中，而这些软件被金融机构、医疗保健公司和政府承包商使用。RSA 的声明否认其明知而实施了后门，但承认接受了这份合同。这一披露造成了尤其严重的损害：BSAFE 被作为安全产品销售，其客户正是因为密码学安全保障而专门选择了它。这起事件严重损害了 RSA 安全公司的声誉，并导致 2014 年对 RSA 大会的抵制。

斯诺登事件曝光后，NIST 采取了多项行动。2013 年 9 月，NIST 重新开放 SP 800-90A 以征求公众意见，并建议在审查期间不要使用 Dual EC DRBG。2014 年 4 月，NIST 发布 SP 800-90A 修订版 1，彻底移除了 Dual EC DRBG——只保留了 Hash_DRBG、HMAC_DRBG 和 CTR_DRBG。NIST 还启动了对其全部密码学标准和指南的审查，特别调查 NSA 的影响是否损害了其他标准。NIST 密码学标准与指南流程工作组也应运而生，旨在提高未来标准化工作的透明度和公众参与度。

Dual EC DRBG 后门对密码学界对标准制定机构的信任产生了深远影响。它表明，一个国家情报机构愿意蓄意削弱全球使用的密码学标准，受影响的不只是对手，还包括盟友、企业和普通公民。这起事件加速了带有无玄机常数的开放、可审计算法的采用：SHA-3 的 Keccak 使用有文档记录的算法生成其常数；BLAKE2 和 BLAKE3 从数学常数的小数部分推导常数；Curve25519 使用质数 2^255 - 19，该质数经过专门选择，便于审计。椭圆曲线参数的“可验证随机”生成成为标准做法。

Dual EC DRBG 丑闻推广了“无玄机”（NUMS）常数这一概念——即从公开可验证的来源生成、因而不可能包含隐藏陷门的密码学参数。例如：SHA-2 使用由前 8 个质数的平方根推导出的初始哈希值；轮常数则来自前 64 个质数的立方根。BLAKE2 从 pi 和其他数学常数的小数展开中推导常数。Ed25519 使用质数 2^255 - 19，以及一个相对于任何其他点的离散对数都能被证明未知的基点（该基点被选为某个字符串的哈希值）。这些做法使任何人都能够验证这些常数并非利用秘密信息选定。

2015 年 12 月，瞻博网络披露，未经授权的代码自 2012 年起就存在于 ScreenOS（其防火墙 OS）中。调查发现了两个后门：其中一个将 Dual EC DRBG 的 Q 常数替换为攻击者控制的值，使知道对应 e 的攻击者能够解密 VPN 流量；另一个后门位于 SSH 管理密码中。Dual EC 的 Q 替换尤其复杂：瞻博网络原本就使用了一个非标准的 Q 值，攻击者又将其替换为自己的 Q，从而两次利用了 Dual EC 的陷门结构。这表明，即使某些实现偏离了 NIST 的 P/Q 值，任何放入自己 Q 值的人仍然可以发动攻击。

Dual EC DRBG 事件带来了几项经验。(1) 透明度：密码学参数必须有可验证的来源——缺少推导文档的常数值得怀疑。(2) 算法设计：算法不应具有可能隐藏陷门的结构（与更简单的 DRBG 设计相比，Dual EC 的 Q/P 关系没有安全收益）。(3) 利益冲突：标准化机构必须严格管理与情报机构之间的利益冲突。(4) 社群审查：应当让学术密码学家能够在标准发布之前提出疑虑，而不是等到发布之后。(5) 部署警惕性：组织应审计其密码库使用了哪些 DRBG，并主动移除不推荐的选项。

Dual EC 被移除后，推荐的 DRBG 格局逐渐集中于 Hash_DRBG、HMAC_DRBG 和 CTR_DRBG。开源社群还在不信任 NIST 标准的场景中采用了非 NIST 的 DRBG：基于 ChaCha20 的 RNG（自 Linux 内核 5.17 起使用，也用于 OpenBSD 和 libsodium）被广泛认为能够抵抗后门，因为 ChaCha20 是一种简单的流密码，不具有陷门结构。Fortuna（用于 FreeBSD 和较旧版本的 macOS）早于 SP 800-90A，并且仍然受到信任。Dual EC 事件还重新引发了人们对将硬件 RNG（RDRAND）作为熵源的兴趣——不过，RDRAND 也遭到可能被植入后门的指控，因此有人建议将 RDRAND 与软件熵混合使用，而不是完全依赖它。

什么数学关系使 Dual EC DRBG 后门成为可能？

Dual EC DRBG 于 2006 年被纳入 NIST SP 800-90A 标准。舒莫夫和弗格森于 2007 年证明，掌握 e（其中 Q=e*P）后，仅凭 32 字节输出即可预测全部输出。2013 年的斯诺登泄露文件确认了 NSA 对密码学标准的影响。据报道，RSA 安全公司收到了 1000 万美元，使 Dual EC 成为 BSAFE 中的默认算法。NIST 在 SP 800-90A 修订版 1（2014 年）中移除了 Dual EC。2015 年的瞻博事件表明，这一陷门曾在真实产品中被利用。经验包括：NUMS 常数、透明推导、利益冲突管理以及标准制定后的审计流程。基于 ChaCha20 的 RNG 成为了受信任的替代方案。