后量子密码SIKE再次被破解，到底还有多少漏洞？

今年7月，美国国家标准与技术研究院(NIST)后量子密码(PQC)竞赛公布了进入第四轮评估的算法——BIKE、Classic McEliece、HQC、SIKE，进一步探讨是否将其标准化。然而，短短一个月以来，后量子密钥交换算法SIKE已经被破解了两次，并且是两种不同的方法。

第一次是比利时鲁汶大学(KU Leuven)通过一个名为Magma的程序，在62分钟的时间内，使用单核处理器，完成了安全级别为level 1的SIKEp434的有效密钥恢复攻击。对于具有更高安全级别的SIKEp503 (level 2)、SIKEp610 (level 3)和SIKEp751 (level 5)，分别在2小时19分钟、8小时15分钟和21小时37分钟内被破解。

现在，布里斯托大学团队在其最新文章《对任意起始曲线的SIDH的攻击》中[1]再次破解了SIKE：通过一种称为“挠点”(torsion point)的方法显著降低了SIKE的安全性。

01

什么是SIKE？

SIKE全称Supersingular Isogeny Key Encapsulation(超奇异同源密钥封装)，基于超奇异同源Diffie-Hellman（SIDH）协议，2011年由David Jao提出，它利用了椭圆曲线之间的同源性。

如下图所示，如果我们有两条椭圆曲线(E1和E2)，我们可以创建一个函数，将E1上的点(P)映射到E2上的点Q。这个函数被称为同源。如果我们能映射这个函数，E1上的每一点都可以映射到E2。秘密密钥是同源的，公开密钥是椭圆曲线。对于密钥交换，Alice和Bob互相将其同源曲线混合，以生成一条秘密曲线。

SIDH的安全性与寻找两条具有相同点数的超奇异椭圆曲线之间的同源映射问题密切相关。

以SKIE为例来说明上图中的密钥交换，首先，Alice和Bob从同一条曲线(E0)开始，然后他们随机离开曲线。这就产生了EA(Alice曲线)和EB(Bob曲线)。Alice和Bob相互把他们的曲线发给对方。然后，Alice再次从EB开始随机行走，并重复她的随机行走。Bob从EA开始行走，重复他的随机行走，然后最终在一条新的秘密曲线处相遇。这是一条只有他们知道的曲线，他们可以用它来创建一个新的密钥，因为没有人知道这条曲线，除非他们知道Bob、Alice的随机行走。

02

什么是挠点？

所谓挠点，假设有两个点P、Q，那么PQ连线与曲线的第三个交点R对x轴的镜像点，就是P+Q。因为椭圆曲线是上下对称的，所以P+Q也一定在曲线上。

那么P点和它自己相加（P+P）怎么计算？想象一下Q点越来越靠近P点，最后PQ两点的连线就变成P点处的切线，所以P+P就是这个切线与椭圆曲线交点的镜像点。如果P点反复加上自己，经过有限次加法后（P+P+……+P）又回到P点，那么P就叫做“挠点”（torsion point）。

03

针对SIKE的攻击

SIKE的破解难度依赖于“超奇异同源问题”(SSI)，也就是前文所说在两个给定的超奇异椭圆曲线之间找到某种映射（称为同源）。这是一个已经分析了10多年的问题。但与纯粹依靠同源问题的密码系统相比，SIKE的难度假设较弱，因为秘密同源下的一些挠点的图像也被揭示，从而产生了下面更精确地描述的超奇异同源挠率（SSI-T）问题。

布里斯托大学团队最新提出的算法可以在合理的时间内解决SSI-T问题，而不需要预先知道任何关于起始曲线的相关属性。

这大大降低了SIDH和SIKE的安全性，最重要的是，这意味着在经典计算机上就可以破解算法，根本不需要量子计算机。

SSI-T问题的数学解释。给出共素整数A和B，两条超等椭圆曲线E0/Fp²和EA/Fp²由一个未知程度的A-同源φA：E0→EA连接，并给出φ对E0（起始曲线）的B-扭转的限制，恢复一个同源体φ与这些限制匹配。

针对这些威胁，SIKE的主要提出者David Jao表示[2]：“对SIKE的攻击虽然对SIKE来说不是好消息，但它是一个积极的信号，表明研究界正在认真对待这一挑战。如果研究界仍然没有达成共识，那么这本身就表明SIKE还没有准备好被标准化。这个结果没有任何问题。事实上，从研究的角度来看，它可能是最令人兴奋的应用场景。但NIST的PQC标准化需要稳定性。”

目前，SIKE团队已经通过电子邮件与NIST就初步修复进行了讨论。通常来说，这些缺陷可以通过对算法进行小的修改来解决。但如果仍无法修复，那么SIKE算法将从后量子密码标准化的进一步考虑中被放弃。

参考链接：

[1]https://eprint.iacr.org/2022/1026.pdf

[2]https://www.fedscoop.com/cracked-nist-cryptography-candidate-has-time/