美国国家安全局是如何破解这么多密码的？(2015)

多年来一直有传言称，美国国家安全局可以解密很大一部分加密的互联网流量。2012年，詹姆斯·班福德(James Bamford)发表了一篇文章，援引匿名的前NSA官员的话说，NSA已经实现了“计算突破”，使他们“有能力破解当前的公共加密”。斯诺登的文件还暗示了一些非凡的能力：它们显示，NSA已经建立了广泛的基础设施来拦截和解密VPN流量，并暗示该机构可以按需解密至少一些HTTPS和SSH连接。

然而，这些文件没有解释这些突破是如何工作的，关于可能的后门或崩溃的算法的猜测在技术界一直很猖獗。昨天，在领先的安全研究场所之一ACM CCS，我们和12位合著者提交了一篇论文，我们认为这篇论文解决了这个技术之谜。

具有讽刺意味的是，关键是Diffie-Hellman密钥交换，这是我们和其他许多人倡导的一种算法，作为抵御大规模监控的一种防御。Diffie-Hellman是用于VPN、HTTPS网站、电子邮件和许多其他协议的现代密码学的基石。我们的论文表明，由于数论和糟糕的实现选择的交汇，Diffie-Hellman的许多现实世界用户很可能容易受到国家级攻击者的攻击。

对于观众中的书呆子来说，问题是：如果客户机和服务器在说Diffie-Hellman，他们首先需要就一个具有特定形式的大素数达成一致。似乎没有理由不让每个人都使用相同的素数，事实上，许多应用程序倾向于使用标准化的或硬编码的素数。但在数学家和实践者之间的翻译中，有一个非常重要的细节被遗漏了：对手可以执行一次巨大的计算来“破解”一个特定的素数，然后很容易地中断任何使用该素数的个体连接。

你会问，计算量有多大？这可能是自二战期间Enigma密码分析以来未曾见过的规模(相对于当时的计算状态)的技术壮举。由于所涉及的算法的复杂性，即使是估计难度也是棘手的，但我们的论文给出了一些保守的估计。对于Diffie-Hellman(1024位)最常见的优点来说，建造一台基于专用硬件的机器每年可以破解一个Diffie-Hellman素数，需要花费数亿美元。

对于一个情报机构来说，这值得吗？由于少数素数被如此广泛地重复使用，就它们可以解密的连接而言，回报将是巨大的。破解单个通用的1024位主数将允许NSA被动解密到全球三分之二的VPN和四分之一的SSH服务器的连接。破解第二个1024位素数将允许对前100万个HTTPS网站中近20%的连接进行被动窃听。换句话说，对大规模计算的一次性投资将使窃听数万亿加密连接成为可能。

美国国家安全局可以负担得起这样的投资。作为斯诺登缓存的一部分泄露的2013年“黑色预算”请求称，NSA已将“投资于突破性的密码分析能力，以击败敌意加密和利用互联网流量”作为优先事项。报告显示，该机构的预算每年约为100亿美元，其中超过10亿美元专门用于计算机网络开发，几个子项目每年数亿美元。

根据我们掌握的证据，我们不能确定美国国家安全局确实在这么做。然而，我们提出的Diffie-Hellman Break比任何竞争的解释都更符合关于它们大规模解密能力的已知技术细节。例如，斯诺登的文件显示，NSA的VPN解密基础设施涉及拦截加密连接，并将某些数据传递给超级计算机，超级计算机返回密钥。该系统的设计不遗余力地收集特定的数据，这些数据对于攻击Diffie-Hellman是必要的，但不是为了替代解释，比如AES或其他对称密码的破解。虽然这些文件清楚地表明，NSA使用其他攻击技术，如软件和硬件“植入”，来破解特定目标的密码，但这些文件并没有解释为什么有能力对VPN流量进行大规模的被动窃听。

由于Diffie-Hellman的薄弱使用在标准和实现中很普遍，即使考虑到现有的安全建议和我们的新发现，这些问题也需要很多年才能消失。与此同时，其他大国政府可能会实施类似的攻击，如果他们还没有这样做的话。

我们的发现说明了美国国家安全局两项任务之间的紧张关系，这两项任务是收集情报和保卫美国计算机安全。如果我们的假设是正确的，该机构一直在大力利用薄弱的迪菲-赫尔曼法案，同时只采取了很小的步骤来帮助解决问题。在防御方面，美国国家安全局建议实施者过渡到椭圆曲线密码系统，目前还不知道这种密码系统存在这个漏洞，但如果没有明确的理由或证据，这样的建议往往会被忽视。这个问题变得更加复杂，因为在显然努力借壳加密标准之后，安全界在接受NSA的建议时犹豫不决。

这种情况使每个人的安全都处于危险之中。这种规模的漏洞是不分青红皂白的-它影响到每个人的安全，包括美国公民和公司-但我们希望，对政府监控背后的密码分析机制有更清晰的技术理解，将是朝着提高每个人的安全迈出的重要一步。

有关更多细节，请参阅我们的研究论文：不完美的前向保密：Diffie-Hellman如何在实践中失败。(更新版：我们刚刚获得了CCS 2015最佳论文奖！)。

J·亚历克斯·霍尔德曼(J.Alex Halderman)是密歇根大学(University Of Michigan)计算机科学与工程副教授，密歇根州计算机安全与社会中心(Center For Computer Security And Society)主任。

Nadia Heninger是宾夕法尼亚大学计算机和信息科学的助理教授。