十年台式机，单核1小时破解后量子加密算法，密码学家：太突然了

未来的量子计算机可能会迅速攻破现代密码学。因此，数学家和密码学家们一直在寻找合适的新加密算法来抵抗量子计算机的攻击。这种能够抵抗量子计算机对现有密码算法攻击的新一代密码算法被称作「后量子加密（PQC，postquantum cryptography）」算法。

但最近，比利时鲁汶大学的研究人员发现，一种很有潜力的 PQC 加密算法可以在短短 1 小时内被完全破解（部分版本破解只需 4 分钟）。问题是，这个记录并不是由某台高端计算机创下的，而是来自一台搭载了十年高龄 CPU 的台式机，而且是单核运行。研究人员说，这一最新的、令人惊讶的失败凸显了后量子密码学在被采用之前需要克服的许多障碍。

论文链接：https://eprint.iacr.org/2022/975

从理论上讲，量子计算机可以快速解决传统计算机需要大量时间才能解决的问题。例如，现代密码学在很大程度上依赖于经典计算机在处理复杂数学问题时所面临的极端困难，如分解大数。而量子计算机原则上可以运行能够快速破解这种加密技术的算法。

为了应对这种威胁，世界各地的密码学家花了 20 年的时间设计后量子加密算法。这些算法基于量子计算机和经典计算机都难以解决的新数学问题。

多年来，美国国家标准与技术研究院（NIST）等机构的研究人员一直在研究哪些 PQC 算法应该成为全世界都可以采用的新标准。该机构在 2016 年宣布了正在寻找候选 PQC 算法的消息，并在 2017 年收到了 82 份提案。之后，经过三轮审查，NIST 宣布了四种即将成为标准的算法，另外四种将作为可能的竞争者（contender）进入下一轮审查。

审查还没结束，其中一位竞争者已经倒下了，而且是被一台 10 年的旧台式机攻破了。这个算法名叫 SIKE（Supersingular Isogeny Key Encapsulation），微软、亚马逊、Cloudflare 和其他公司都对其进行了研究。密歇根大学安娜堡分校的密码学家 Christopher Peikert 说：「这次攻击来得太突然了，是一颗银弹（具有极端有效性的解决方法）。」

SIKE 算法是什么？

SIKE 是一系列涉及椭圆曲线的 PQC 算法。「长期以来，椭圆曲线一直是数学家们的研究对象，」NIST 的数学家 Dustin Moody 表示。「它们由一个类似于 y^2 = x^3 + Ax + B 的方程描述，其中 A 和 B 是数字。比如，一条椭圆曲线可以是 y^2 = x^3 + 3x + 2。」

1985 年，「数学家想出了一种方法来制作涉及椭圆曲线的密码系统，这些系统如今已被广泛部署，」Moody 说道。「然而，这些椭圆曲线密码系统很容易受到来自量子计算机的攻击。」

大约在 2010 年，研究人员发现了一种在密码学中使用椭圆曲线的新方法。人们相信这个新想法不容易受到量子计算机的攻击。

这种新方法基于这样一个问题：椭圆曲线上的两点如何相加得到椭圆曲线上的另一个点。该算法名字中的「isogeny」表示同源性，是从一条椭圆曲线到另一条椭圆曲线的映射，它保留了这个加法定律。

「如果你让这种映射变得足够复杂，那么数据加密的挑战就成了，给定两条椭圆曲线，很难找到它们之间的同源性，」该研究的合著者、比利时鲁汶大学数学密码学家 Thomas Decru 说道。

SIKE 是一种基于超奇异同源 Diffie-Hellman（SIDH）密钥交换协议的基于同源的密码学形式。「SIDH/SIKE 是最早实用的基于同源的加密协议之一，」Decru 说。

然而 SIKE 的一个弱点是：为了使其工作，它需要向公众提供额外的信息，即辅助扭转点。「攻击者尝试利用这些额外信息已经有一段时间了，但一直未能成功利用它来攻破 SIKE，」Moody 说。「然而这篇新论文找到了一种方式，他们使用了一些相当先进的数学方法。」

为了解释这种新的攻击，Decru 说，虽然椭圆曲线是一维对象，但在数学中，椭圆曲线可以被可视化为二维或任何其他维数的对象。人们还可以在这些广义对象之间创建同源。

通过应用一个 25 年前的定理，新的攻击使用 SIKE 公开的额外信息来构建二维的同源。然后这种同源性就可以重建 SIKE 用来加密消息的密钥。 

「对我来说，最令人惊讶的是，这次攻击似乎是突然冒出来的」，马里兰大学帕克分校的密码学家 Jonathan Katz 说道。虽然没有参与这项新研究，但他表示：「之前很少有结果表明 SIKE 有任何弱点，而这次的结果突然给 SIKE 带来了完全毁灭性的攻击，因为它找到了完整的密钥，并且是在没有任何量子计算的情况下很快找到的。」

攻击十多年，破解四分钟

使用基于上述新攻击方式的算法，研究人员发现，一台搭载了十年「高龄」CPU（ Intel Xeon CPU E5-2630v2）的台式机最少只需要 4 分钟就能够找到由某种 SIKE 算法保护的密钥，而攻破被认为达到 NIST 量子安全一级标准的 SIKE 算法也只用了 62 分钟。这些实验都是在 CPU 的一个核上运行的。

「通常，密码系统受到严重攻击都发生在该系统提出之后不久，或者该系统刚开始吸引大家注意力的时候。随着时间的推移攻击逐渐变强，或是显著削弱系统。但这次的攻击，没有任何前兆，密码系统突然就被完全攻破。Peikert 说：「自 SIDH 被首次提出以来，对 SIDH/SIKE 的攻击近 12 年来几乎没有任何进展，直到这次彻底攻破。」

尽管研究人员已经对 SIKE 进行了十多年的测试，但 SIKE 未被选中作为标准的原因之一是人们担心它太新且研究还不够充分。奥克兰大学的数学家 Steven Galbraith 表示：「人们担心 SIKE 可能有被重大袭击的风险，事实证明这是对的。」

那么，为什么直到现在人们才检测到 SIKE 的漏洞？Galbraith 认为，一个重要原因是新的攻击「应用了非常高级的数学知识」。Katz 表示同意，他说：「我怀疑世界上只有不到 50 人同时掌握 PQC 底层的数学和必要的密码学知识。」

此外，PQC 初创公司 Sandbox AQ 的密码学家 David Joseph 曾说：「无论是从实现角度还是从理论角度讲，同源问题都是『出了名的困难』，这使得其根本性缺陷更有可能在较晚的时候被发现。」

此外，「还应该注意的一点是，在 NIST 进行几轮筛审查之前，可供分析的 PQC 算法是非常多的，因此研究精力被摊薄了。而经过几轮筛选之后，研究人员已经能够专注于一小撮算法了。」Joseph 说。

SIKE 的发明者之一、加拿大滑铁卢大学教授 David Jao 表示：「我认为这项新成果是一项了不起的工作，我对作者们给予了最高的评价。起初，我对 SIKE 的破解感到难过，因为它在数学上是一个如此优雅的方案。」

「但新发现只不过是反映了科学的运作方式：我们提出了一个系统，当时每个人都认为它好像还不错，然后经过分析，有人找到了它的弱点。他们花了 10 多年的时间才找到弱点，这点是不寻常的，但除此之外，这件事并没有超出普通科学进展的范围。」David Jao 补充说。

在 Jao 看来，SIKE 现在被破解是一件好事，毕竟它还没有被广泛部署。

SIKE 被破解意味着什么？

SIKE 是今年第二个被破解的 NIST PQC 候选算法。今年 2 月，苏黎世 IBM 研究院的密码学家 Ward Beullens 透露，他可以用笔记本电脑破解参与 NIST 第三轮审查的 Rainbow 算法。「这表明所有 PQC 方案都需要进一步研究」，Katz 说道。

不过，Moody 指出，尽管 SIKE 被破解了，但其他基于同源的密码系统，如 CSIDH 或 SQIsign，还没被破解，「有些人可能以为基于同源的密码学已经死了，但事实远非如此，我认为基于同源的密码学还有很多东西要研究，」Decru 表示。

此外，这项新工作可能也无法反映 NIST 的 PQC 研究水平。正如 Decru 所说，SIKE 是 NIST 收到的 82 份提案中唯一一个基于同源的密码系统；同样，Rainbow 是这些提交中唯一的多变量算法。

那些被 NIST 采纳为「标准」或进入其第四轮审查的算法都是基于已经被密码学家研究、分析了很久的数学思想，Galbraith 说。「这并不能保证它们是安全的，只是意味着它们经受住了更长时间的攻击。」

Moody 同意这一点，并指出「总是会发现一些惊人的突破性结果来破解密码系统。对于任何密码系统，我们都没有绝对的安全保证。最好的说法是，经过很多聪明人的大量研究，没有人发现该密码系统有任何漏洞。」

「我们的程序被设计为允许攻击和破解，」Moody 说。「我们在每一轮评估中都见过它们。这是获得对安全的信心的唯一途径。」 Galbraith 对此表示赞同，并指出这样的研究「正在发挥作用」。

尽管如此，「我觉得，Rainbow 和 SIKE 的双双陨落会让更多的人认真考虑，是否需要为 NIST 后量子标准化过程中出现的任何赢家制定后备计划，」Decru 说。「仅仅依靠一个数学概念或方案可能太冒险了。这也是 NIST 自己的想法——他们的主要方案很可能是基于格密码学（lattice-based）的，但他们想要一个非格密码学方案备选。」

Decru 指出，其他研究者已经开始开发新版本的 SIDH/SIKE，他们认为这可能会阻止这种新型攻击。「我预计到会有这样的结果，当攻击升级之后，人们试图修补 SIDH/SIKE，」Decru 说。

总而言之，事实表明这种新攻击的起点是一个「与密码学完全无关」的定理，并且「揭示了进行纯数学基础研究以理解密码系统的重要性」，Galbraith 表示。

Decru 对此表示同意，并指出「在数学中，并非所有东西都能立即适用。有些事情几乎永远不会适用于任何现实生活中的情况。但这并不意味着我们不应该让研究导向这些更晦涩的议题。」