十年台式機，單核心1小時破解後量子加密演算法，密碼學家：太突然了

未來的量子電腦可能會迅速攻破現代密碼學。因此，數學家和密碼學家一直在尋找合適的新加密演算法來抵抗量子電腦的攻擊。這種能夠抵抗量子電腦對現有密碼演算法攻擊的新一代密碼演算法被稱為「後量子加密（PQC，postquantum cryptography）」演算法。

但最近，比利時魯汶大學的研究人員發現，一種很有潛力的PQC 加密演算法可以在短短1 小時內被完全破解（部分版本破解只需4分鐘）。問題是，這個紀錄並不是某台高階電腦創下的，而是來自一台搭載了十年高齡 CPU 的桌上型電腦，而且是單核心運作。研究人員說，這一最新的、令人驚訝的失敗凸顯了後量子密碼學在被採用之前需要克服的許多障礙。

論文連結：https://eprint.iacr.org/2022/975

從理論上講，量子電腦可以快速解決傳統電腦需要大量時間才能解決的問題。例如，現代密碼學在很大程度上依賴經典電腦在處理複雜數學問題時所面臨的極端困難，例如分解大數。而量子電腦原則上可以運行能夠快速破解這種加密技術的演算法。

為了回應這個威脅，世界各地的密碼學家花了 20 年的時間設計後量子加密演算法。這些演算法是基於量子計算機和經典計算機都難以解決的新數學問題。

多年來，美國國家標準與技術研究院（NIST）等機構的研究人員一直在研究哪些 PQC 演算法應該成為全世界都可以採用的新標準。該機構在 2016 年宣布了正在尋找候選 PQC 演算法的消息，並在 2017 年收到了 82 份提案。之後，經過三輪審查，NIST 宣布了四種即將成為標準的演算法，另外四種將作為可能的競爭者（contender）進入下一輪審查。

審查還沒結束，其中一位競爭者已經倒下了，而且是被一台 10 年的舊桌上型電腦攻破了。這個演算法叫做 SIKE（Supersingular Isogeny Key Encapsulation），微軟、亞馬遜、Cloudflare 和其他公司都對其進行了研究。密西根大學安娜堡分校的密碼學家Christopher Peikert 說：「這次攻擊來得太突然了，是一顆銀彈（具有極端有效性的解決方法）。」

##SIKE 演算法是什麼？

SIKE 是一系列涉及橢圓曲線的 PQC 演算法。 「長期以來，橢圓曲線一直是數學家的研究對象，」NIST 的數學家 Dustin Moody 表示。 「它們由一個類似y^2 = x^3 Ax B 的方程式描述，其中A 和B 是數字。例如，一條橢圓曲線可以是y^2 = x^3 3x 2。」

1985 年，「數學家想出了一種方法來製作涉及橢圓曲線的密碼系統，這些系統如今已被廣泛部署，」Moody 說。 「然而，這些橢圓曲線密碼系統很容易受到來自量子電腦的攻擊。」

大約在2010 年，研究人員發現了一種在密碼學中使用橢圓曲線的新方法。人們相信這個新想法不容易受到量子電腦的攻擊。

這個新方法是基於這樣一個問題：橢圓曲線上的兩點如何相加得到橢圓曲線上的另一個點。這個演算法名字中的「isogeny」表示同源性，是從一條橢圓曲線到另一條橢圓曲線的映射，它保留了這個加法定律。

「如果你讓這種映射變得足夠複雜，那麼資料加密的挑戰就變成了，給定兩條橢圓曲線，很難找到它們之間的同源性，」該研究的合著者、比利時魯汶大學數學密碼學家Thomas Decru 說。

SIKE 是一種基於超奇異同源 Diffie-Hellman（SIDH）金鑰交換協定的基於同源的密碼學形式。 「SIDH/SIKE 是最早實用的基於同源的加密協定之一，」Decru 說。

然而 SIKE 的一個弱點是：為了使其工作，它需要向公眾提供額外的信息，即輔助扭轉點。 「攻擊者嘗試利用這些額外資訊已經有一段時間了，但一直未能成功利用它來攻破 SIKE，」Moody 說。 「然而這篇新論文找到了一種方式，他們使用了一些相當先進的數學方法。」

為了解釋這種新的攻擊，Decru 說，雖然橢圓曲線是一維對象，但在數學中，橢圓曲線可以被視覺化為二維或任何其他維數的對象。人們也可以在這些廣義物件之間創建同源。

透過應用一個 25 年前的定理，新的攻擊使用 SIKE 公開的額外資訊來建構二維的同源。然後這種同源性就可以重建 SIKE 用來加密訊息的金鑰。 

「對我來說，最令人驚訝的是，這次攻擊似乎是突然冒出來的」，馬裡蘭大學帕克分校的密碼學家 Jonathan Katz 說。雖然沒有參與這項新研究，但他表示：「之前很少有結果表明SIKE 有任何弱點，而這次的結果突然給SIKE 帶來了完全毀滅性的攻擊，因為它找到了完整的密鑰，並且是在沒有任何量子計算的情況下很快找到的。」

攻擊十多年，破解四分鐘

使用基於上述新攻擊方式的演算法，研究人員發現，一台搭載了十年「高齡」CPU（ Intel Xeon CPU E5-2630v2）的桌上型電腦最少只需要4 分鐘就能夠找到由某種SIKE 演算法保護的金鑰，而攻破被認為達到NIST量子安全一級標準的SIKE 演算法也只花了62 分鐘。這些實驗都是在 CPU 的一個核上運行的。

「通常，密碼系統受到嚴重攻擊都發生在該系統提出之後不久，或是該系統剛開始吸引大家注意力的時候。隨著時間的推移攻擊逐漸變強，或是顯著削弱系統。但這次的攻擊，沒有任何前兆，密碼系統突然就被完全攻破。Peikert 說：「自SIDH 被首次提出以來，對SIDH/SIKE 的攻擊近12 年來幾乎沒有任何進展，直到這次徹底攻破。」

#儘管研究人員已經對SIKE 進行了十多年的測試，但SIKE 未被選中作為標準的原因之一是人們擔心它太新且研究不夠充分。奧克蘭大學的數學家Steven Galbraith 表示：「人們擔心SIKE 可能有被重大攻擊的風險，事實證明這是對的。」

那麼，為什麼直到現在人們才檢測到SIKE 的漏洞？ Galbraith 認為，一個重要原因是新的攻擊「應用了非常高級的數學知識」。 Katz 表示同意，他說：「我懷疑世界上只有不到50 人同時掌握PQC 底層的數學和必要的密碼學知識。」

此外，PQC 新創公司Sandbox AQ的密碼學家David Joseph 曾說：「無論是從實現角度還是從理論角度講，同源問題都是‘出了名的困難’，這使得其根本性缺陷更有可能在較晚的時候被發現。」

此外，「還應該注意的一點是，在NIST 進行幾輪篩審查之前，可供分析的PQC 演算法是非常多的，因此研究精力被攤薄了。而經過幾輪篩選之後，研究人員已經能夠專注於一小撮演算法了。」Joseph 說。

SIKE 的發明者之一、加拿大滑鐵盧大學教授David Jao 表示：「我認為這項新成果是一項了不起的工作，我對作者們給予了最高的評價。起初，我對SIKE 的破解感到難過，因為它在數學上是一個如此優雅的方案。」

「但新發現只不過是反映了科學的運作方式：我們提出了一個系統，當時每個人都認為它好像還不錯，然後經過分析，有人找到了它的弱點。他們花了10 多年的時間才找到弱點，這一點是不尋常的，但除此之外，這件事並沒有超出普通科學進展的範圍。」David Jao 補充說。

在 Jao 看來，SIKE 現在被破解是一件好事，畢竟它還沒有被廣泛部署。

SIKE 被破解代表什麼？

SIKE 是今年第二個被破解的 NIST PQC 候選演算法。今年 2 月，蘇黎世 IBM 研究院的密碼學家 Ward Beullens 透露，他可以用筆記型電腦破解參與 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 自己的想法——他們的主要方案很可能是基於格密碼學（lattice-based）的，但他們想要一個非格密碼學方案備選。」

Decru 指出，其他研究者已經開始開發新版本的SIDH/SIKE，他們認為這可能會阻止這種新型攻擊。 「我預計到會有這樣的結果，當攻擊升級之後，人們試圖修補 SIDH/SIKE，」Decru 說。

總而言之，事實表明這種新攻擊的起點是一個「與密碼學完全無關」的定理，並且「揭示了進行純數學基礎研究以理解密碼系統的重要性」，Galbraith 表示。

Decru 對此表示同意，並指出「在數學中，並非所有東西都能立即適用。有些事情幾乎永遠不會適用於任何現實生活中的情況。但這並不意味著我們不應該讓研究導向這些更晦澀的議題。」

#

以上是十年台式機，單核心1小時破解後量子加密演算法，密碼學家：太突然了的詳細內容。更多資訊請關注PHP中文網其他相關文章！