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

語言: CN / TW / HK

機器之心報道

機器之心編輯部

或許沒有一種加密算法是真正可靠的。即使暫時沒發現問題,也只能説,「經過很多聰明人的大量研究,沒有人發現該密碼系統有任何漏洞。」

未來的量子計算機可能會迅速攻破現代密碼學。因此,數學家和密碼學家們一直在尋找合適的新加密算法來抵抗量子計算機的攻擊。這種能夠抵抗量子計算機對現有密碼算法攻擊的新一代密碼算法被稱作「後量子加密(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 對此表示同意,並指出「在數學中,並非所有東西都能立即適用。有些事情幾乎永遠不會適用於任何現實生活中的情況。但這並不意味着我們不應該讓研究導向這些更晦澀的議題。」

參考內容:

https://spectrum.ieee.org/quantum-safe-encryption-hacked

國家部委主辦、高端產業平台!國內規格最高的人工智能大賽火熱報名中!

首屆 “興智杯” 全國人工智能創新應用大賽以 “興智賦能” 為主題,聚焦人工智能技術創新、行業賦能和生態構建等發展痛點、難點,吸引國內外人工智能領域的優秀人才同場競技,以賽促研、以賽促用、以賽育人,加速人工智能技術創新和產業化落地。

大賽包括技術創新、行業賦能、生態構建三項專題賽和總決賽,專題賽決賽分別在上海、廣州、深圳三地舉行,總決賽將於今年 12 月在深圳舉辦。