破解椭圆曲线算法中的NSA秘密种子

美国国家安全局(NSA)故意选择弱算法而产生的安全隐患是可怕的，而找到用于生成椭圆曲线加密算法种子的原始文本则可帮助业界消除担忧。

近日，密码学专家 Filippo Valsorda 宣布，在多位密码学和网络安全业界知名人士参与和资助下，发起一项破解NIST椭圆曲线算法种子的挑战赛：为首位能够破解NIST椭圆曲线算法种子并找出生成它们的原始文本的人提供12288美元的悬赏。如果获奖者选择将金额捐赠给慈善机构，悬赏金额将增至36864美元。

一同参与发起该挑战赛的知名安全专家包括：约翰·霍普金斯大学教授 Matt Green、PKI​​ 和 Chromium 贡献者 Ryan Sleevi、浏览器安全专家 Chris Palmer、“ Logjam attack”开发人员 David Adrian 以及 AWS 加密工程师 Colm MacCárthaigh。

密码学的根基

椭圆曲线加密算法（ECC）是一种基于椭圆曲线数学的公开密钥加密算法。 ECC的主要优势是它相比RSA加密算法使用较小的密钥长度并提供相当等级的安全性。ECC的另一个优势是可以定义群之间的双线性映射，后者已经在密码学领域得到广泛应用，例如基于身份的加密。

在现代密码学领域，椭圆曲线加密（ECC）起着至关重要的作用，是目前最流行的公钥加密算法，而美国国家标准与技术研究院（NIST）的椭圆曲线算法在这方面占据着核心地位。

构建现代IT和互联网的三大基础安全技术：TLS（安全传输层协议）、PGP（基于RSA的邮件加密系统）和SSH（安全外壳协议），以及比特币等数字货币加密技术都采用了椭圆曲线加密算法。

NSA的秘密种子

椭圆曲线加密算法依赖于定义在有限字段上的椭圆曲线的数学概念，以生成相对短但安全的密钥。使用曲线确保对于选定的点（在曲线上），不可计算出用于生成点的倍数（标量），从而为加密提供基础。

在椭圆曲线加密算法中，种子是用作加密算法或过程的初始输入的值或值集，用于产生加密密钥。最终用户和开发人员不必直接与这些种子交互，而是使用所选加密协议中的曲线参数。真正对种子的起源感兴趣的是那些关心系统完整性和安全性的人。

NIST椭圆曲线算法（P-192, P-224, P-256, P-384, 和 P-521），首次在2000年通过NIST的FIPS 186-2（关于“数字签名标准”）引入，并在1997年使用由美国国家安全局（NSA）提供的种子生成。这些曲线由它们的参数和一个随机种子值指定，而派生密钥的确定性过程是透明的且可验证的，以减轻隐藏漏洞的担忧。

但是目前，没有人知道原始种子具体是如何生成的，有传言和研究表明，它们是NSA提供给Jerry Solinas的（五个）英语句子的哈希值（下图）。Solinas据信使用了一个哈希算法（可能是SHA-1）来生成种子，并可能永远忘记了这些短语。

Valsorda在博客中提到：“NIST椭圆曲线是大部分现代加密技术的基础，它们是在90年代末通过哈希NSA提供的种子生成的。但种子具体是如何生成的呢？有传言说它们是英语句子的哈希值。由于Solinas博士已经在2023年初去世，留下了一个密码学谜题和很多阴谋论，但这也促成了一个历史性的密码破解挑战。”

Filippo Valsorda在社交媒体X上宣称：任何拥有足够GPU能力和密码短语暴力破解经验的人都可能破解（假定的）SHA-1 哈希值并推导出原始句子。

安全社区的担忧

多年来，密码学社区对椭圆曲线加密算法始终忧心忡忡，起初是关于Dual_EC_DRBG的争议，声称NSA在算法中设置了后门。最令人担忧的质疑是NIST曲线算法中是否故意嵌入了漏洞，因为这将使解密敏感数据成为可能。尽管这些质疑缺乏实质性的证据，但椭圆曲线种子的起源仍然是未知的，这在社区中制造了恐惧和不确定性。

挑战的意义

考虑到NIST椭圆曲线加密算法在现代密码学中的基础地位，破解椭圆曲线加密算法种子的挑战赛具备重大的历史意义和现实意义。美国国家安全局故意选择弱曲线算法而产生的安全隐患是可怕的，而找到用于生成算法种子的（五条）原始句子可一劳永逸地消除这些担忧。

同时由于椭圆曲线加密算法种子本身是密码学界多年的悬疑，这给整个事件增添了神秘色彩。

参考链接：

https://words.filippo.io/dispatches/seeds-bounty/