新型攻擊輕松淘汰備選抗量子加密算法

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已經完了，至少目前這輪是完了。剩余三個候選方案的時間表目前尚未可知。