曲线包裹的谜语 (2015)

如果您正在寻找大量的密码阴谋论，并想阅读一些知识渊博的密码学家的论文，我正好有适合您的论文。由 Neal Koblitz 和 Alfred J. Menezes 撰写的题为“谜团包裹的谜语”，它解决了 2015 年最大的谜团之一。即：为什么美国国家安全局只是吓坏了，把它的 Suite B 程序扔进了马桶？ Koblitz 和 Menezes 是著名的密码学家和数学家，共同负责数十篇论文，包括最近的一系列立场文件，例如“另一种可证明的安全性”（本博客之前提到过）和“密码学中大胆假设的美丽新世界” ”。 （是的，这是一个真正的论文标题。）他们最新的论文非常易于访问，几乎没有包含任何数学知识，因此现在值得您花时间阅读它。如果你不这样做，或者不能处理在 LaTeX 中排版的阅读内容，我将尽我所能总结他们的论点要点，然后谈谈为什么这一切都很重要。什么是套件 B，您所说的 NSA“吓坏了”是什么意思？在过去一个世纪的大部分时间里，美国国家安全局（及其前身）都小心翼翼地垄断着先进的密码学。这种方法在 1980 年代相当有效，然后迅速变得不可持续。这有几个原因。首先，PC 革命使 NSA 无法将加密技术排除在普通用户和行业之外——就像 NSA 试图做到这一点一样。其次，国会厌倦了为昂贵的定制计算机系统付费，并决定国防部应该像其他人一样购买现成的计算设备。结果是密码现代化计划和套件 B——第一个公共密码学标准，包括经过认证可用于加密机密和绝密数据的非机密算法。 Suite B 在 1990 年代中/后期为行业标准化，并以其对（当时新的）椭圆曲线加密 (ECC) 领域的公钥加密和密钥协议的独家依赖而著称。在采用 Suite B 时，ECC 对非机密世界来说相对较新。许多工业界和学术界的密码学家并不认为它得到了合理的研究（科布利茨和梅内泽斯在这方面的轶事是无价的）。 ECC 值得注意的是使用比其他公钥算法（如 RSA 和“经典”Diffie-Hellman）短得多的密钥，这主要是因为在这些设置中起作用的新的次指数攻击在 ECC 世界中似乎没有任何类似物。

美国国家安全局努力推动采用。由于他们拥有最好的数学家，而且如果事情向南发展，显然损失最大，标准机构被说服了。 Suite B 的算法是标准化的，除了一些知识产权问题外，甚至被非机密社区也逐渐采用。正如您对世界上最大的间谍机构所期望的那样，这是一次安静的恐慌。但它在密码学家中引起了巨大的轰动。出于对量子计算未来发展的担忧，该机构更新了 Suite B 网站，宣布在未来几年从 Suite B 快速过渡到一套新的抗量子算法。为什么突然和直接关注量子计算机？好吧，国家安全局显然不愿意谈论这个。但截至 2013 年，从斯诺登缓存泄露的幻灯片没有显示任何大规模量子突破即将出现的真实证据，这需要从 ECC 快速过渡。我们应该转向哪些抗量子算法？好问题。密码学家尚未就任何问题达成一致。这使得这个公告的时间特别神秘。因此，让我说明一下：尽管量子计算机似乎还有很长的路要走，并且无处可见合理的抗量子替代算法，但 NSA 决定公开宣布这一消息，而不是在幕后悄悄宣布。更奇怪的是，如果你还没有升级到套房 B，你现在被敦促不要升级。在实践中，这意味着一些公司将继续使用 RSA 等算法，而不是完全过渡到 ECC。而且 RSA 也容易受到量子攻击。当记者终于到达国家安全局征求意见时，线路上唯一的声音是玻璃破碎和挖掘的声音。 （不，我是在开玩笑——但 NSA 确实再次更新了他们的网站，只是为了表明他们不是在玩某种严重误导的愚人节恶作剧。）这就是 Koblitz/Menezes 论文的背景。谜底是：美国国家安全局知道我们不知道什么？

Koblitz 和 Menezes 详尽地详细说明了 NSA 宣布这一消息的可能原因，从直截了当——NSA 实际上在开发量子计算机方面取得了巨大进步——到彻头彻尾的离奇。他们甚至提出了这样一种可能性，即 NSA 对被抓到篡改国家标准感到非常尴尬，以至于他们刚刚决定扭转局面，表现得像个疯子。我将跳过大部分细节，不是因为它不有趣，而是因为我想专注于我认为论文中最有趣的假设。也就是说，美国国家安全局根本不担心量子计算机，而是他们在椭圆曲线离散对数问题的经典密码分析方面取得了重大进展——结果是恐慌。让我奠定基础。大多数 EC 密码系统的安全性依赖于一些基本数学问题的假定难处理性。其中最重要的称为椭圆曲线离散对数问题 (ECDLP)。这个问题一定非常难解决，否则几乎所有建立在 ECC 上的密码系统都会很快解开。 “硬”的定义在这里很重要。我们在 ECC 上下文中的意思是，解决 ECDLP 的最著名算法需要许多操作，这些操作在安全参数中是完全指数的。实际上，这意味着我们可以使用在 256 位字段中设置的椭圆曲线实现 128 位等效安全性——这意味着类似的小密钥和密文。要使用 RSA 实现等效的安全性，其中应用次指数算法，您的密钥需要至少 3072 位 (!) 长。但是，虽然使用（相对）微小的椭圆曲线点的能力对实现者来说非常棒，但它没有留下任何错误的余地。如果 NSA 的数学家开始在解决 ECDLP 的最先进技术方面取得哪怕是适度但持续的进步，那么整个领域都会处于危险之中。从最小的标准曲线 P-256 开始，它现在提供的安全性低于所需的 128 位。当然，没有理由相信经典密码分析在这里有问题。 NSA 可能真的有理由相信量子计算的发展速度比 2013 年要快。也有可能他们只是草率，并没有意识到你刚刚宣传了多年的密码学的公开狂热可能不是个好主意。但这似乎值得怀疑。您可以阅读 Koblitz 和 Menezes 的论文，了解他们对所有替代假设的看法。我想用最后几段来讨论一个稍微切题的问题，这个问题一直是我们社区非常恐慌的主题。

Koblitz 和 Menezes 论文的一个更好的观点是它解决了 NSA 故意对 NIST 椭圆曲线进行后门处理的论点。这个论点可以在互联网的各个地方找到。它起源于有成就的密码学家，他们非常正确地将怀疑论应用于古怪和临时过程。然后它前往疯狂镇。不管人们承认与否，这种担忧对 CFRG 和 IETF 最近采用非 NIST 替代曲线产生了巨大影响。对 NSA 的指控可以简单描述。众所周知，NIST 伪随机曲线是由 NSA 通过 SHA1 散列“种子”以生成曲线参数而生成的。这个过程应该通过消除 NSA 随意篡改参数的能力来让公众放心。然而，没有人想过限制 NSA 对输入种子的选择——这导致了潜在的攻击，他们尝试了许多不同的随机种子，直到发现一条包含 NSA 稍后可以利用的弱点的曲线。 Koblitz 和 Menezes 以基本常识、历史和数学为基础处理这个论点。当然，常识论点是你不要在你吃的地方胡闹。换句话说，NSA 不会刻意选择弱椭圆曲线，因为他们计划在未来 20 年内使用它们来加密机密和绝密数据。但常识说服不了任何人。数学论证有点微妙，并且可能在不符合自身利益的情况下起作用。粗略地说，Koblitz 和 Menezes 指出，尽管 NSA 拥有强大的计算能力，但不能尝试所有可能的种子。鉴于他们使用 1990 年代的设备生成这些曲线，并且评估（计算点数）椭圆曲线的过程需要大量计算，因此这一点尤其正确。因此，他们假设 NSA 只能尝试测试 2^{48} 条左右不同的曲线来验证他们假设的弱点。通过计算可能的曲线家族的数量，Koblitz 和 Menezes 表明大部分曲线（对于 P-256，大约 2^{209} 中的 2^{257}）必须是弱的，以便 NSA在这次攻击中取得成功。如此大量的脆弱曲线对ECC领域的影响是非常糟糕的。它使之前所有已知的弱曲线类别相形见绌，并且会质疑使用 ECC 的决定。换句话说，Koblitz 和 Menezes 是说，如果你在心里接受弱曲线假设，解决方案不是用任何东西代替 NIST 椭圆曲线，而是尽快离开建筑物，也许不出去的时候关上门。不是开玩笑。

令人抓狂的是，这听起来很像 NSA 目前正在实施的计划。也许我们应该担心。