[科普中国]-双椭圆曲线确定性随机数发生器

双椭圆曲线确定性随机数发生器（Dual_EC_DRBG），也被称作双椭圆曲线随机数发生器，是一种使用椭圆曲线密码学实现的密码学安全伪随机数发生器(CSPRNG)。直到2017年被撤销之前，尽管受到了大量密码学家们的批评，被认为存在潜在的后门，该算法自2016年6月左右被公开起，在七年的时间内都是NIST SP 800-90A定义的4个（现为3个）标准的CSPRNG之一。1

简介这是一个由美国国家标准协会（NIST）制定并被美国国家安全局（NSA）大力提倡的随机数发生器。Dual_EC_DRBG利用椭圆曲线算法的机制生成随机数。这个算法涉及到在曲线上取点并反复在椭圆曲线上进行“打点”操作。该算法公布之后，据报道可能存在一个后门程序，可以根据一个密码完全预测其返回的数字顺序。最近，RSA公司由于其安全产品生产线上的随机数发生器被设置为默认的伪随机数发生器而召回了它的部分产品。无论这种随机数发生器是否被写了后门程序都不会改变椭圆曲线技术本身的力量，但这确实引起了关于对椭圆曲线标准化过程的一些问题。这也是我们应该将注意力用在确保系统充分使用随机数的部分原因。

弱点：一个潜在的后门在算法成为ANSI，ISO以及之前由美国国家标准与技术研究院（NIST）认可的正式标准的一部分之前，算法的加密安全性的弱点是众所周知的并且公开批评。公开发现的弱点之一是该算法有可能为那些知道盗版后门 - 美国政府的国家安全局（NSA） - 而不是其他人 - 提供有利的盗版后门。 2013年，“纽约时报”报道，他们拥有但从未向公众发布的文件“似乎证实”后门是真实的，并且作为其Bullrun解密计划的一部分被NSA故意插入。在2013年12月，路透社一篇文章称，在2004年，NIST标准化Dual_EC_DRBG之前，NSA支付RSA安全千万$的秘密协议使用Dual_EC_DRBG作为RSA BSAFE加密库默认，导致RSA信息安全成为最重要的不安全算法的分销商。RSA回答说，他们“断然否认”他们曾经故意与国家安全局勾结，采用一种众所周知的有缺陷的算法，并说“我们从来没有[与NSA]的关系保持秘密”。

某时在2004年的第一个已知的出版之前，可能kleptographic后门是与Dual_EC_DRBG的设计发现，与具有不同寻常的特性，这是任何人理论上是不可能Dual_EC_DRBG的设计，但Dual_EC_DRBG的设计师（NSA）确认后门的存在。 Bruce Schneier在标准化后不久就得出结论，“相当明显的”后门（以及其他缺陷）意味着没有人会使用Dual_EC_DRBG。后门将允许NSA解密，例如使用Dual_EC_DRBG作为CSPRNG的SSL/TLS加密。

最初提交Dual_EC_DRBG的ANSI标准组的成员了解潜在后门的确切机制以及如何禁用它，但没有采取足够的步骤无条件地禁用后门或广泛宣传它。在Dan Shumow和Niels Ferguson的出版物，或Certicom的Daniel R. L. Brown和Scott Vanstone的2005专利申请描述后门机制之前，一般的加密社区最初并未意识到潜在的后门。

在2013年9月，纽约时报报道，由爱德华·斯诺登泄露的内部NSA备忘录指出，美国国家安全局在标准化进程已经努力最终成为Dual_EC_DRBG标准的独立的一个编辑，并得出结论认为，Dual_EC_DRBG标准确实包含国家安全局的后门。作为回应，NIST表示“NIST不会刻意削弱加密标准。”根据纽约时报的报道，NSA每年花费2.5亿美元在软件和硬件中插入后门作为Bullrun计划的一部分。总统顾问委员会随后成立，负责审查美国国家安全局的行为，其中包括美国政府“全力支持而不是破坏制定加密标准的努力”。

2014年4月21日，NIST从其关于随机数发生器的指南草案中撤回了Dual_EC_DRBG，该指南建议“尽快将当前用户的Dual_EC_DRBG转换为其余三种已批准的算法之一。”2

安全性在NIST SP 800-90A中包含Dual_EC_DRBG的既定目的是其安全性基于数论的计算硬度假设。数学安全性降低证明可以证明，只要理论问题的数量很难，随机数发生器本身就是安全的。但是，Dual_EC_DRBG的制造商没有公布Dual_EC_DRBG的安全性降低，并且在NIST草案发布后不久就发现了Dual_EC_DRBG确实不安全，因为它每轮输出太多比特。太多位的输出（以及精心选择的椭圆曲线点P和Q）是使NSA后门成为可能的原因，因为它使攻击者能够通过强力猜测来恢复截断。在最终发布的标准中没有更正过多位的输出，使得Dual_EC_DRBG既不安全又无后顾之忧。
在许多其他标准中，意味着任意的常数是通过我的套数原则选择的，其中常数是从例如pi中得出的，其方式几乎没有调整的余地。但是，Dual_EC_DRBG没有指定如何选择默认的P和Q常量，可能是因为它们是由NSA构造为后门的。由于标准委员会意识到了后门的可能性，因此包括了实施者选择自己的安全P和Q的方法。但是标准中的确切表述是这样的，即FIPS 140-2验证需要使用所谓的后向P和Q，因此OpenSSL项目选择实施后门P和Q，即使他们意识到潜在的后门并且更愿意生成他们自己的安全P和Q. 纽约时报后来写道，国家安全局在标准化过程中起作用，最终成为该标准的独立的一个编辑。
后来由Daniel RL Brown和KristianGjøsteen为Dual_EC_DRBG发布了安全证明，表明生成的椭圆曲线点与均匀随机椭圆曲线点无法区分，并且如果在最终输出截断中输出的位数较少，如果两个椭圆曲线点P和Q是独立的，如果显示三个问题很难（通常只接受其中一个是硬的），那么Dual_EC_DRBG是安全的。证据依赖于三个问题很难的假设：决策性的Diffie-Hellman假设（通常被认为很难），以及两个通常不被认为难以解决的新问题：截断点问题和x-对数问题。与许多替代CSPRNG（没有安全性降低）相比，Dual_EC_DRBG相当慢，但Daniel R.L.Brown认为安全性降低使得慢速Dual_EC_DRBG成为一种有效的替代方案（假设实现者禁用明显的后门）。请注意，Daniel R.L. Brown为椭圆曲线加密专利的主要所有者Certicom工作，因此在推广EC CSPRNG时可能存在利益冲突。
所谓的NSA后门将允许攻击者通过查看单轮（32字节）的输出来确定随机数生成器的内部状态;然后可以容易地计算随机数发生器的所有未来输出，直到用外部随机源重新接种CSPRNG。这使得例如SSL / TLS易受攻击，因为TLS连接的设置包括以明文形式发送随机生成的加密随机数。NSA所谓的后门将取决于NSA知道e * Q = P的单个e - 这是一个难题，给定Q和P，但如果你可以选择P和Q则容易生成。因此，e是一个秘密密钥，据推测只有NSA才知道，所谓的后门是一个盗版非对称隐藏后门。Matthew Green的博客文章“Dual_EC_DRBG的多重缺陷”通过使用Crypto 1997中引入的离散日志kleptogram，对所谓的NSA后门如何工作进行了简化解释。

包含可能后门的软件和硬件使用Dual_EC_DRBG的实现通常是通过库获得的。 至少RSA Security（BSAFE库），OpenSSL，Microsoft和Cisco都有包含Dual_EC_DRBG的库，但只有BSAFE默认使用它。 据路透社的文章透露，RSA Security和NSA之间达成了1000万美元的秘密协议，RSA Security的BSAFE是该算法中最重要的分销商。OpenSSL的Dual_EC_DRBG实现存在一个缺陷，使其无法在测试模式之外工作，OpenSSL的Steve Marquess从中得出结论，没有人使用OpenSSL的Dual_EC_DRBG实现。

NIST提供了经过CSPRNG实施FIPS 140-2验证的产品清单。已验证的CSPRNG列在Description/Notes字段中。 请注意，即使Dual_EC_DRBG列为已验证，默认情况下也可能未启用。 许多实现来自库实现的重命名副本。

BlackBerry软件是非默认使用的示例。它包括对Dual_EC_DRBG的支持，但不支持默认值。但黑莓有限公司并没有向可能使用它的任何客户发出咨询，因为他们认为可能的后门不是漏洞。杰弗里卡尔引用黑莓的一封信：
Dual EC DRBG算法仅适用于第三方开发人员通过[Blackberry]平台上的Cryptographic API。对于Cryptographic API，如果第三方开发人员希望使用该功能并明确设计和开发了一个请求使用API的系统，则可以使用它。
Bruce Schneier指出，即使未默认启用，将后备CSPRNG作为选项实施也可以使NSA更容易监视具有软件控制命令行开关以选择加密算法的目标，或者“注册表“系统，像大多数Microsoft产品，如Windows Vista：
特洛伊木马非常非常大。不能说这是一个错误，这是收集按键的大量代码。但是，将[bit-one]更改为[在注册表中更改机器上的默认随机数生成器]的第二位可能不会被检测到。获得后门是一种低阴谋，高度否定的方式。因此，将它放入库和产品中是有好处的。- Bruce Schneier
2013年12月发布了一个概念验证后门，它使用泄漏的内部状态来预测随后的随机数，这种攻击在下次重新开始之前是可行的。
2015年12月，瞻博网络宣布他们的ScreenOS固件的一些修订使用了Dual_EC_DRBG和可疑的P和Q点，在他们的防火墙中创建了一个后门。最初它应该使用Juniper选择的Q点，它可能或者可能没有以可证明的安全方式生成。然后使用Dual_EC_DRBG为ANSI X9.17 PRNG播种。这会使Dual_EC_DRBG输出混淆，从而杀死后门。但是，代码中的“错误”暴露了Dual_EC_DRBG的原始输出，从而危及系统的安全性。然后这个后门被一个改变了Q点和一些测试向量的未知方所取代。有关NSA通过Juniper防火墙进行持久后门访问的指控已于2013年由Der Spiegel发布。
盗版后门是NSA的NOBUS政策的一个例子，它具有只有他们可以利用的安全漏洞。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所