本文来自微信公众号“数世咨询”，作者/nana。
SIKE入选后量子计算加密第四轮备选方案，但研究人员用一台PC仅花费一小时就破解了。美国政府试图在量子计算机时代保护数据安全的征选仍在继续，但强大的新型攻击只用一台传统计算机就完全攻破了第四轮备选方案之一，凸显出标准化下一代加密算法涉及的种种风险。
去年7月，美国国家标准与技术研究院（NIST）选出了四种后量子计算加密算法来替换RSA、Diffie-Hellman和椭圆曲线Diffie-Hellma等无法抵御量子计算机攻击的传统加密算法。
NIST额外提出了其他四种算法，作为留待进一步测试的潜在替代品，希望其中一种或多种也能成为后量子时代的加密替代选项。这后面四种额外算法之一的SIKE就被新型攻击攻破了。NIST甄选通过的那四种后量子密码（PQC）算法仰赖完全不同于SIKE的数学技巧，倒是不受该攻击的影响。
Getting Totally SIKEd
鲁汶大学计算机安全与工业密码组研究人员公布了研究成果之后，SIKE（超奇异同源密钥封装）如今可能已不在备选行列。研究论文题为《对SIDH的高效密钥恢复攻击（初版）》，其中描述的技术采用一台传统PC以复杂数学技巧恢复出受SIKE保护的交易所用的加密密钥。整个过程甚至只用了大约一小时时间。研究人员Wouter Castryck和Thomas Decru的这一壮举为自己赢得了斩获NIST五万美元大奖的资格。
加拿大滑铁卢大学教授、SIKE共同发明人David Jao在电子邮件中写道：“新发现的漏洞显然是对SIKE的重大打击。这种攻击真令人出于意料。”
上世纪70年代提出的公钥加密是一个重大突破，能使从未谋面的各方安全交易加密材料而无需担心会被对手破解。公钥加密依赖非对称密钥，其中私钥用于解密消息，而单独的公钥用于加密。公钥人尽可知。只要私钥保密，该密码体制就是安全的。
实际上，公钥密码时常过于笨重，所以很多系统依靠密钥封装机制，这一机制可供此前从未谋面的各方通过互联网等公共媒介共同商定对称密钥。不同于对称密钥算法，今天在用的密钥封装机制很容易被量子计算机破解。新攻击出现之前，研究人员认为SIKE采用名为超奇异同源图的复杂数学构造能够避免此类漏洞。
SIKE的基石是名为SIDH（超奇异同源Diffie-Hellman）的协议。研究人员发表的论文描述了SIDH是怎么被破解的，其中用到了数学家Ernst Kani于1997年提出的“合并与分割（glue-and-split）”定理，以及同为数学家的Everett W.Howe、Franck Leprévost和Bjorn Poonen于2000年设计的一些工具。这项新技术建立在2016年一篇论文中描述的GPST自适应攻击的基础上。新攻击方法背后的数学对于大多数非数学家而言是无法理解的。你只需要知道：
“该攻击利用了SIDH具有辅助点且秘密同源度已知的事实。”GPST自适应攻击中的“G”、奥克兰大学数学教授Steven Galbraith在关于新攻击的简短评论中解释道，“SIDH中的辅助点一直是个麻烦和潜在弱点，可利用来进行故障攻击、GPST自适应攻击、扭转点攻击等等。”
IEEE会员、马里兰大学计算机科学系教授Jonathan Katz在电子邮件中写道：“相比理解背后的数学原理，更需要注意的是该攻击完全经典，根本不需要量子计算机。”
经验教训
SIKE是去年NIST指定无效的第二个PQC候选。去年2月，IBM博士后研究员Ward Beullens发表的研究破解了安全密码签名方案Rainbow。根据Cryptomathic的说法，Rainbow“依赖于在有限域上求解大型多元二次方程组问题的难度”。
NIST的PQC替代方案征选活动已运营了五年之久。简述如下：
●第一轮（2017年）：69个候选方案
●第二轮（2019年）：甄选出26个候选方案
●第三轮（2020年）：选出7个入围方案，另有8个候补方案
●第四轮（2022年）：3个入围方案和1个候补方案被选为标准。SIKE和另外3个候补方案晋级第四轮。
Rainbow在第3轮被淘汰。SIKE一直挺到了第4轮。
Katz说道：
“有点令人担忧的是，这是过去六个月来，进入NIST第3轮审查过程的方案第二次遭经典算法完全破解。（上一个遭破解的是Rainbow，时间是去年2月。）四个PQC方案中的三个都依赖于相对较新的假设，其确切难度尚未可知，因此最新的攻击表明，我们可能仍需谨慎/保守地推进标准化进程。”
至于为什么该漏洞直到SIKE算法发展的相对后期才暴露出来的问题，SIKE共同发明人Jao的回答颇富洞察力。他说：
“攻击确实用的是上世纪90年代和本世纪初出现的数学原理。从某种意义上说，该攻击不需要新的数学，任何时候都会被人发现。攻击一个出乎意料的方面是采用了属2曲线来攻击椭圆曲线（属1曲线）。这两类曲线之间的联系相当出人意料。举例而言，几十年来，大家一直试图攻击常规椭圆曲线密码，有些人已经试过用基于属2曲线的方法了。但这些尝试均告失败。所以，这次在同源领域取得成功真是个令人意外的发展。”
“总的说来，数学文献中已然发表了许多深度数学理论，但密码学家对此并不十分了解。我把自已归入从事密码研究但对数学了解得不够深的那许多研究人员行列。所以，有时候，我们需要的只是有人能够意识到现有理论数学对这些新密码体制的适用性而已。该攻击就是这种情形。”
提交给NIST的SIKE版本生成密钥只用了一步。潜在的SIKE变体可以采用两步。Jao表示，这后续变体可能不易受到可致破解的数学因素的影响。不过，就目前而言，SIKE已经完了，至少目前这轮是完了。剩余三个候选方案的时间表目前尚未可知。
