兩名數學家在一台個人電腦上花一小時破解了 SIKE 後量子加密

2022 年 8 月，在 NIST 選出四種後量子加密演算法、準備最終取代 RSA 與 Diffie-Hellman 的數週之後，魯汶大學電腦安全與工業密碼學組的研究人員發表了〈An Efficient Key Recovery Attack on SIDH〉——這是一種利用複雜數學、僅靠一台傳統個人電腦、約一小時就能還原保護 SIKE 交易之金鑰的技術。論文作者 Wouter Castryck 與 Thomas Decru 因此符合領取微軟 50,000 美元獎金的資格。

SIKE——超奇異同源金鑰封裝（Supersingular Isogeny Key Encapsulation）——是 NIST 推進作為潛在備援的四種附加演算法之一，一般認為它將祕密編碼於超奇異同源圖中，因而能抵抗量子電腦，這種構造長久以來被視為優雅而困難。這項新攻擊顯示，其基石協定 SIDH（超奇異同源 Diffie-Hellman）易受 glue-and-split 影響；該定理由數學家 Ernst Kani 於 1997 年證明，並結合 Howe、Leprévost 與 Poonen 在 2000 年的工具，建立在已知的 GPST 自適應攻擊之上。

其重要性立即可見：SIKE 很可能已退出標準化角逐，而 NIST 已選為標準的四種演算法——建立在完全不同的數學之上——則未受影響。滑鐵盧大學教授、SIKE 共同發明人 David Jao 稱此弱點「顯然是一大打擊」，並稱該攻擊「實在出乎意料」。

SIDH 一向隨附具有已知同源次數的輔助點；1997 年的一項定理（glue-and-split）把這項設計上的便利變成了一台金鑰還原機器。

這項攻擊重新利用了四分之一世紀前的數學，自 1997 年以來一直隱藏在眾目睽睽之下。

它不需要量子電腦——那正是 SIKE 所設計要防範的威脅——只需一個核心和一小時。

這個缺陷是結構性的：輔助點與已知的同源次數被內建於協定的設計之中。

此結果在發表後數日內就重新排列了一場政府標準化競賽的排名。

為協定設計的便利就是潛在的弱點：一個方案為了易用性而暴露的輔助資料，可能正是攻擊者所需的把柄。

SIKE 這個 NIST 備選候選方案實際上已被排除在考慮之外；已選出的四項後量子標準依賴不同的數學，未受波及。研究人員可望領取微軟的 50,000 美元懸賞，而 SIKE 共同發明人 David Jao 也公開證實了該攻擊的嚴重性。