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

　　机器之心报道
　　机器之心编辑部
　　或许没有一种加密算法是真正可靠的。即使暂时没发现问题，也只能说，经过很多聪明人的大量研究，没有人发现该密码系统有任何漏洞。
　　未来的量子计算机可能会迅速攻破现代密码学。因此，数学家和密码学家们一直在寻找合适的新加密算法来抵抗量子计算机的攻击。这种能够抵抗量子计算机对现有密码算法攻击的新一代密码算法被称作后量子加密（PQC，postquantumcryptography）算法。
　　但最近，比利时鲁汶大学的研究人员发现，一种很有潜力的PQC加密算法可以在短短1小时内被完全破解（部分版本破解只需4分钟）。问题是，这个记录并不是由某台高端计算机创下的，而是来自一台搭载了十年高龄CPU的台式机，而且是单核运行。研究人员说，这一最新的、令人惊讶的失败凸显了后量子密码学在被采用之前需要克服的许多障碍。
　　论文链接：https：eprint。iacr。org2022975
　　从理论上讲，量子计算机可以快速解决传统计算机需要大量时间才能解决的问题。例如，现代密码学在很大程度上依赖于经典计算机在处理复杂数学问题时所面临的极端困难，如分解大数。而量子计算机原则上可以运行能够快速破解这种加密技术的算法。
　　为了应对这种威胁，世界各地的密码学家花了20年的时间设计后量子加密算法。这些算法基于量子计算机和经典计算机都难以解决的新数学问题。
　　多年来，美国国家标准与技术研究院（NIST）等机构的研究人员一直在研究哪些PQC算法应该成为全世界都可以采用的新标准。该机构在2016年宣布了正在寻找候选PQC算法的消息，并在2017年收到了82份提案。之后，经过三轮审查，NIST宣布了四种即将成为标准的算法，另外四种将作为可能的竞争者（contender）进入下一轮审查。
　　审查还没结束，其中一位竞争者已经倒下了，而且是被一台10年的旧台式机攻破了。这个算法名叫SIKE（SupersingularIsogenyKeyEncapsulation），微软、亚马逊、Cloudflare和其他公司都对其进行了研究。密歇根大学安娜堡分校的密码学家ChristopherPeikert说：这次攻击来得太突然了，是一颗银弹（具有极端有效性的解决方法）。
　　SIKE算法是什么？
　　SIKE是一系列涉及椭圆曲线的PQC算法。长期以来，椭圆曲线一直是数学家们的研究对象，NIST的数学家DustinMoody表示。它们由一个类似于y2x3AxB的方程描述，其中A和B是数字。比如，一条椭圆曲线可以是y2x33x2。
　　1985年，数学家想出了一种方法来制作涉及椭圆曲线的密码系统，这些系统如今已被广泛部署，Moody说道。然而，这些椭圆曲线密码系统很容易受到来自量子计算机的攻击。
　　大约在2010年，研究人员发现了一种在密码学中使用椭圆曲线的新方法。人们相信这个新想法不容易受到量子计算机的攻击。
　　这种新方法基于这样一个问题：椭圆曲线上的两点如何相加得到椭圆曲线上的另一个点。该算法名字中的isogeny表示同源性，是从一条椭圆曲线到另一条椭圆曲线的映射，它保留了这个加法定律。
　　如果你让这种映射变得足够复杂，那么数据加密的挑战就成了，给定两条椭圆曲线，很难找到它们之间的同源性，该研究的合著者、比利时鲁汶大学数学密码学家ThomasDecru说道。
　　SIKE是一种基于超奇异同源DiffieHellman（SIDH）密钥交换协议的基于同源的密码学形式。SIDHSIKE是最早实用的基于同源的加密协议之一，Decru说。
　　然而SIKE的一个弱点是：为了使其工作，它需要向公众提供额外的信息，即辅助扭转点。攻击者尝试利用这些额外信息已经有一段时间了，但一直未能成功利用它来攻破SIKE，Moody说。然而这篇新论文找到了一种方式，他们使用了一些相当先进的数学方法。
　　为了解释这种新的攻击，Decru说，虽然椭圆曲线是一维对象，但在数学中，椭圆曲线可以被可视化为二维或任何其他维数的对象。人们还可以在这些广义对象之间创建同源。
　　通过应用一个25年前的定理，新的攻击使用SIKE公开的额外信息来构建二维的同源。然后这种同源性就可以重建SIKE用来加密消息的密钥。
　　对我来说，最令人惊讶的是，这次攻击似乎是突然冒出来的，马里兰大学帕克分校的密码学家JonathanKatz说道。虽然没有参与这项新研究，但他表示：之前很少有结果表明SIKE有任何弱点，而这次的结果突然给SIKE带来了完全毁灭性的攻击，因为它找到了完整的密钥，并且是在没有任何量子计算的情况下很快找到的。
　　攻击十多年，破解四分钟
　　使用基于上述新攻击方式的算法，研究人员发现，一台搭载了十年高龄CPU（IntelXeonCPUE52630v2）的台式机最少只需要4分钟就能够找到由某种SIKE算法保护的密钥，而攻破被认为达到NIST量子安全一级标准的SIKE算法也只用了62分钟。这些实验都是在CPU的一个核上运行的。
　　通常，密码系统受到严重攻击都发生在该系统提出之后不久，或者该系统刚开始吸引大家注意力的时候。随着时间的推移攻击逐渐变强，或是显著削弱系统。但这次的攻击，没有任何前兆，密码系统突然就被完全攻破。Peikert说：自SIDH被首次提出以来，对SIDHSIKE的攻击近12年来几乎没有任何进展，直到这次彻底攻破。
　　尽管研究人员已经对SIKE进行了十多年的测试，但SIKE未被选中作为标准的原因之一是人们担心它太新且研究还不够充分。奥克兰大学的数学家StevenGalbraith表示：人们担心SIKE可能有被重大袭击的风险，事实证明这是对的。
　　那么，为什么直到现在人们才检测到SIKE的漏洞？Galbraith认为，一个重要原因是新的攻击应用了非常高级的数学知识。Katz表示同意，他说：我怀疑世界上只有不到50人同时掌握PQC底层的数学和必要的密码学知识。
　　此外，PQC初创公司SandboxAQ的密码学家DavidJoseph曾说：无论是从实现角度还是从理论角度讲，同源问题都是出了名的困难，这使得其根本性缺陷更有可能在较晚的时候被发现。
　　此外，还应该注意的一点是，在NIST进行几轮筛审查之前，可供分析的PQC算法是非常多的，因此研究精力被摊薄了。而经过几轮筛选之后，研究人员已经能够专注于一小撮算法了。Joseph说。
　　SIKE的发明者之一、加拿大滑铁卢大学教授DavidJao表示：我认为这项新成果是一项了不起的工作，我对作者们给予了最高的评价。起初，我对SIKE的破解感到难过，因为它在数学上是一个如此优雅的方案。
　　但新发现只不过是反映了科学的运作方式：我们提出了一个系统，当时每个人都认为它好像还不错，然后经过分析，有人找到了它的弱点。他们花了10多年的时间才找到弱点，这点是不寻常的，但除此之外，这件事并没有超出普通科学进展的范围。DavidJao补充说。
　　在Jao看来，SIKE现在被破解是一件好事，毕竟它还没有被广泛部署。
　　SIKE被破解意味着什么？
　　SIKE是今年第二个被破解的NISTPQC候选算法。今年2月，苏黎世IBM研究院的密码学家WardBeullens透露，他可以用笔记本电脑破解参与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自己的想法他们的主要方案很可能是基于格密码学（latticebased）的，但他们想要一个非格密码学方案备选。
　　Decru指出，其他研究者已经开始开发新版本的SIDHSIKE，他们认为这可能会阻止这种新型攻击。我预计到会有这样的结果，当攻击升级之后，人们试图修补SIDHSIKE，Decru说。
　　总而言之，事实表明这种新攻击的起点是一个与密码学完全无关的定理，并且揭示了进行纯数学基础研究以理解密码系统的重要性，Galbraith表示。
　　Decru对此表示同意，并指出在数学中，并非所有东西都能立即适用。有些事情几乎永远不会适用于任何现实生活中的情况。但这并不意味着我们不应该让研究导向这些更晦涩的议题。
　　参考内容：
　　https：spectrum。ieee。orgquantumsafeencryptionhacked