量子安全加密被 10 岁的 PC 破解

后量子密码学仍面临许多挑战

未来的量子计算机可能会迅速打破现代密码学。现在研究人员发现，一种旨在保护计算机免受这些高级攻击的有前途的算法可能会在 4 分钟内被破解。问题是 4 分钟的时间戳不是由尖端机器实现的，而是由一台普通的 10 年历史的台式计算机实现的。研究人员说，这一最新的、令人惊讶的失败凸显了后量子密码学在采用之前需要清除的许多障碍。

理论上，量子计算机可以快速解决经典计算机可能需要无数年才能解决的问题。例如，现代密码学的大部分依赖于经典计算机在处理大数等数学问题时面临的极端困难。然而，量子计算机原则上可以运行可以快速破解此类加密的算法。

为了领先于这种量子威胁，世界各地的密码学家在过去的二十年里一直在设计后量子密码学(PQC) 算法。这些都是基于量子计算机和经典计算机都难以解决的新数学问题。

“最令人惊讶的是，这次袭击似乎是凭空出现的。”
——Jonathan Katz，马里兰大学帕克分校

多年来，美国国家标准与技术研究院(NIST)等组织的研究人员一直在研究哪些 PQC 算法应该成为世界应该采用的新标准。NIST 于 2016 年宣布正在寻找候选 PQC 算法，2017 年收到了 82 份提交。7月，经过三轮审查，NIST 宣布了四种算法将成为标准，另外还有四种算法将作为可能的额外竞争者进入另一轮审查。

现在，一项新的研究揭示了一种方法，可以完全打破正在审查的这些竞争者之一，称为 SIKE，微软、亚马逊、Cloudflare和其他公司已经对其进行了调查。密歇根大学安娜堡分校的密码学家克里斯托弗·佩克特（ Christopher Peikert ）没有参与这项新工作，他说：“这次攻击出人意料，是一颗灵丹妙药。”

椭圆锻炼

SIKE（Supersingular Isogeny Key Encapsulation）是一系列涉及椭圆曲线的 PQC 算法。NIST 的数学家达斯汀·穆迪（Dustin Moody ）说：“长期以来，椭圆曲线一直在数学中进行研究，”他没有参与这项新工作。“它们由一个看起来像 y 2 = x 3 + Ax + B 的方程来描述，其中 A 和 B 是数字。例如，一条椭圆曲线可以是 y 2 = x 3 + 3x + 2。”

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

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

穆迪说，这种新方法基于如何在椭圆曲线上添加两个点以获得椭圆曲线上的另一个点。“同源”是从一条椭圆曲线到另一条椭圆曲线的映射，它保留了这个加法定律。

“如果你让这张地图足够复杂，那么允许数据加密的猜想难题是，给定两条椭圆曲线，很难找到它们之间的同源性，”该研究的合著者、 KU Leuven的数学密码学家Thomas Decru说。

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

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

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

“人们自然担心可能还有重大袭击事件有待发现，他们是对的。”
——Steven Galbraith，奥克兰大学

通过应用一个 25 年前的定理，新的攻击使用 SIKE 公开的额外信息来构建二维的同源。然后，这种同源性可以重建 SIKE 用来加密消息的密钥。Decru 和研究的资深作者Wouter Castryck于 8 月 5 日在Cryptology ePrint Archive中详细介绍了他们的发现。

“对我来说，最令人惊讶的是，这次攻击似乎是凭空出现的，”马里兰大学帕克分校的密码学家乔纳森·卡茨（Jonathan Katz）说，他没有参与这项新工作。“之前很少有结果表明 SIKE 有任何弱点，然后突然间，这个结果出现了完全毁灭性的攻击——即，它找到了整个密钥，并且在没有任何量子计算的情况下相对快速地找到了。”

一台 PC 如何 > 所有的量子比特（在这种情况下）

使用基于这种新攻击的算法，研究人员发现一台使用了 10 年的英特尔台式机需要 4 分钟才能找到由 SIKE 保护的密钥。

“通常，当提议的密码系统受到严重攻击时，这种情况会在系统提出后相对较快地发生，或者开始引起注意，或者随着时间的推移研究结果的进展，或者不会导致系统完全崩溃，而是会显着削弱系统。在这种情况下，我们什么都没看到，”Peikert 说。“自 SIDH 首次提出以来，对 SIDH/SIKE 的攻击从 11 年到 12 年基本上没有进展，到彻底中断。”

尽管研究人员已经对 SIKE 进行了十多年的测试，但“SIKE 未被选中进行标准化的原因之一是人们担心它太新而且研究还不够充分，”奥克兰大学的数学家Steven Galbraith说，在新西兰，谁没有参与这项新工作。“人们自然担心可能还有重大袭击事件有待发现，他们是对的。”

直到现在才检测到 SIKE 的漏洞的一个原因是，新的攻击“应用了非常高级的数学——我想不出另一种情况，与被破坏的系统相比，攻击使用了如此深的数学，”Galbraith 说。Katz 表示同意，他说：“我怀疑世界上只有不到 50 人了解基础数学和必要的密码学。”

此外，加利福尼亚州帕洛阿尔托的 PQC 初创公司 Sandbox AQ 的密码学家David Joseph说，同源“是出了名的‘困难’，无论是从实现角度还是从理论角度来看，”他没有参与这项新工作。“这使得根本性缺陷更有可能在比赛的最后阶段持续存在而未被发现。”

“我们提出了一个系统，当时每个人都认为这似乎是一个好主意，经过后续分析，有人能够找到突破口。花了 10 年时间是不寻常的，但除此之外什么都看不到。”
——David Jao，滑铁卢大学

此外，“应该注意的是，在前几轮中有更多的算法，密码分析的传播范围要小得多，而在过去的几年里，研究人员已经能够专注于一小批算法，”约瑟夫说。

SIKE 的共同发明人、加拿大滑铁卢大学教授 David Jao 说：“我认为这项新成果是一项了不起的工作，我向作者们致以最崇高的敬意。” 起初，“我对 SIKE 被无效感到难过，因为它是一个数学上如此优雅的方案，但新发现只是反映了科学是如何运作的，”他说。“我们提出了一个系统，当时每个人都认为这似乎是一个好主意，经过后续分析，有人能够找到突破口。花了 10 年的时间是不寻常的，但除了普通的进步过程之外，这里什么也看不到。“

此外，“SIKE 现在被破坏要好得多，而不是在一些假设的替代世界中，SIKE 被广泛部署并且每个人都在它被破坏之前依赖它，”Jao 说。

系统中断

SIKE 是今年第二个被打破的 NIST PQC 候选人。2 月，苏黎世 IBM 研究院的密码学家Ward Beullens透露，他可以在周末用笔记本电脑破解第三轮候选人 Rainbow。“因此这表明所有 PQC 方案仍需要进一步研究，”Katz 说。

尽管如此，这些新发现打破了 SIKE，但并未打破其他基于同源的密码系统，例如CSIDH或SQIsign，Moody 指出。“外界的人可能认为基于同源的密码学现在已经死了，但这远非事实，”Decru 说。“如果你问我，还有很多东西要研究。”

此外，这项新工作也可能无法以一种或另一种方式反映 NIST 的 PQC 研究。SIKE 是 NIST 收到的 82 份提交中唯一基于同源的密码系统。同样，Rainbow 是这些提交中唯一的多变量算法，Decru 说。

“我们对任何密码系统都没有绝对的安全保证。最好的说法是，经过很多聪明人的大量研究，没有人发现任何裂缝。”
——达斯汀穆迪，NIST

Galbraith 说，NIST 正在采用作为标准或已进入 NIST 第四轮的其他设计“基于数学思想，这些思想在密码学家的研究和分析方面具有较长的跟踪记录”。“这并不能保证它们是安全的，但这只是意味着它们经受住了更长时间的攻击。”

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

尽管如此，“我们的流程旨在允许攻击和中断，”穆迪说。“我们在每一轮评估中都见过他们。这是获得对安全的信心的唯一途径。” 加尔布雷思对此表示赞同，并指出这样的研究“正在发挥作用”。

尽管如此，“我觉得 Rainbow 和 SIKE 下降的结合会让更多的人认真考虑是否需要为 NIST 后量子标准化过程中出现的任何赢家制定后备计划，”Decru 说。“仅仅依靠一个数学概念或方案可能太冒险了。这也是 NIST 自己的想法——他们的主要方案很可能是基于点阵的，但他们想要一个非点阵备份。”

Decru 指出，其他研究人员已经在开发新版本的 SIDH/SIKE，他们认为这可能会阻止这种新攻击。“我预计会有更多这样的结果，人们试图修补 SIDH/SIKE，以及改进我们的攻击，”Decru 说。

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

德克鲁对此表示同意，并指出“在数学中，并非所有东西都能立即适用。见鬼，有些事情几乎肯定永远不会适用于任何现实生活中的情况。但这并不意味着我们不应该让研究不时地引导这些更晦涩的话题。”

原文始发于微信公众号（网络研究院）：“量子安全”加密被 10 岁的 PC 破解