機(jī)器之心報道

機(jī)器之心編輯部

或許沒有一種加密算法是真正可靠的。即使暫時沒發(fā)現(xiàn)問題，也只能說，「經(jīng)過很多聰明人的大量研究，沒有人發(fā)現(xiàn)該密碼系統(tǒng)有任何漏洞。」

未來的量子計算機(jī)可能會迅速攻破現(xiàn)代密碼學(xué)。因此，數(shù)學(xué)家和密碼學(xué)家們一直在尋找合適的新加密算法來抵抗量子計算機(jī)的攻擊。這種能夠抵抗量子計算機(jī)對現(xiàn)有密碼算法攻擊的新一代密碼算法被稱作「后量子加密（PQC，postquantum cryptography）」算法。

但最近，比利時魯汶大學(xué)的研究人員發(fā)現(xiàn)，一種很有潛力的 PQC 加密算法可以在短短 1 小時內(nèi)被完全破解（部分版本破解只需 4 分鐘）。問題是，這個記錄并不是由某臺高端計算機(jī)創(chuàng)下的，而是來自一臺搭載了十年高齡 CPU 的臺式機(jī)，而且是單核運(yùn)行。研究人員說，這一最新的、令人驚訝的失敗凸顯了后量子密碼學(xué)在被采用之前需要克服的許多障礙。

論文鏈接：https://eprint.iacr.org/2022/975

從理論上講，量子計算機(jī)可以快速解決傳統(tǒng)計算機(jī)需要大量時間才能解決的問題。例如，現(xiàn)代密碼學(xué)在很大程度上依賴于經(jīng)典計算機(jī)在處理復(fù)雜數(shù)學(xué)問題時所面臨的極端困難，如分解大數(shù)。而量子計算機(jī)原則上可以運(yùn)行能夠快速破解這種加密技術(shù)的算法。

為了應(yīng)對這種威脅，世界各地的密碼學(xué)家花了 20 年的時間設(shè)計后量子加密算法。這些算法基于量子計算機(jī)和經(jīng)典計算機(jī)都難以解決的新數(shù)學(xué)問題。

多年來，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）等機(jī)構(gòu)的研究人員一直在研究哪些 PQC 算法應(yīng)該成為全世界都可以采用的新標(biāo)準(zhǔn)。該機(jī)構(gòu)在 2016 年宣布了正在尋找候選 PQC 算法的消息，并在 2017 年收到了 82 份提案。之后，經(jīng)過三輪審查，NIST 宣布了四種即將成為標(biāo)準(zhǔn)的算法，另外四種將作為可能的競爭者（contender）進(jìn)入下一輪審查。

審查還沒結(jié)束，其中一位競爭者已經(jīng)倒下了，而且是被一臺 10 年的舊臺式機(jī)攻破了。這個算法名叫 SIKE（Supersingular Isogeny Key Encapsulation），微軟、亞馬遜、Cloudflare 和其他公司都對其進(jìn)行了研究。密歇根大學(xué)安娜堡分校的密碼學(xué)家 Christopher Peikert 說：「這次攻擊來得太突然了，是一顆銀彈（具有極端有效性的解決方法）。」

SIKE 算法是什么？

SIKE 是一系列涉及橢圓曲線的 PQC 算法?！搁L期以來，橢圓曲線一直是數(shù)學(xué)家們的研究對象，」NIST 的數(shù)學(xué)家 Dustin Moody 表示?！杆鼈冇梢粋€類似于 y^2 = x^3 + Ax + B 的方程描述，其中 A 和 B 是數(shù)字。比如，一條橢圓曲線可以是 y^2 = x^3 + 3x + 2?！?/p>

1985 年，「數(shù)學(xué)家想出了一種方法來制作涉及橢圓曲線的密碼系統(tǒng)，這些系統(tǒng)如今已被廣泛部署，」Moody 說道?！溉欢?，這些橢圓曲線密碼系統(tǒng)很容易受到來自量子計算機(jī)的攻擊。」

大約在 2010 年，研究人員發(fā)現(xiàn)了一種在密碼學(xué)中使用橢圓曲線的新方法。人們相信這個新想法不容易受到量子計算機(jī)的攻擊。

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

「如果你讓這種映射變得足夠復(fù)雜，那么數(shù)據(jù)加密的挑戰(zhàn)就成了，給定兩條橢圓曲線，很難找到它們之間的同源性，」該研究的合著者、比利時魯汶大學(xué)數(shù)學(xué)密碼學(xué)家 Thomas Decru 說道。

SIKE 是一種基于超奇異同源 Diffie-Hellman（SIDH）密鑰交換協(xié)議的基于同源的密碼學(xué)形式。「SIDH/SIKE 是最早實用的基于同源的加密協(xié)議之一，」Decru 說。

然而 SIKE 的一個弱點是：為了使其工作，它需要向公眾提供額外的信息，即輔助扭轉(zhuǎn)點?！腹粽邍L試?yán)眠@些額外信息已經(jīng)有一段時間了，但一直未能成功利用它來攻破 SIKE，」Moody 說?！溉欢@篇新論文找到了一種方式，他們使用了一些相當(dāng)先進(jìn)的數(shù)學(xué)方法。」

為了解釋這種新的攻擊，Decru 說，雖然橢圓曲線是一維對象，但在數(shù)學(xué)中，橢圓曲線可以被可視化為二維或任何其他維數(shù)的對象。人們還可以在這些廣義對象之間創(chuàng)建同源。

通過應(yīng)用一個 25 年前的定理，新的攻擊使用 SIKE 公開的額外信息來構(gòu)建二維的同源。然后這種同源性就可以重建 SIKE 用來加密消息的密鑰。

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

攻擊十多年，破解四分鐘

使用基于上述新攻擊方式的算法，研究人員發(fā)現(xiàn)，一臺搭載了十年「高齡」CPU（ Intel Xeon CPU E5-2630v2）的臺式機(jī)最少只需要 4 分鐘就能夠找到由某種 SIKE 算法保護(hù)的密鑰，而攻破被認(rèn)為達(dá)到 NIST 量子安全一級標(biāo)準(zhǔn)的 SIKE 算法也只用了 62 分鐘。這些實驗都是在 CPU 的一個核上運(yùn)行的。

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

盡管研究人員已經(jīng)對 SIKE 進(jìn)行了十多年的測試，但 SIKE 未被選中作為標(biāo)準(zhǔn)的原因之一是人們擔(dān)心它太新且研究還不夠充分。奧克蘭大學(xué)的數(shù)學(xué)家 Steven Galbraith 表示：「人們擔(dān)心 SIKE 可能有被重大襲擊的風(fēng)險，事實證明這是對的?！?/p>

那么，為什么直到現(xiàn)在人們才檢測到 SIKE 的漏洞？Galbraith 認(rèn)為，一個重要原因是新的攻擊「應(yīng)用了非常高級的數(shù)學(xué)知識」。Katz 表示同意，他說：「我懷疑世界上只有不到 50 人同時掌握 PQC 底層的數(shù)學(xué)和必要的密碼學(xué)知識?！?/p>

此外，PQC 初創(chuàng)公司 Sandbox AQ 的密碼學(xué)家 David Joseph 曾說：「無論是從實現(xiàn)角度還是從理論角度講，同源問題都是『出了名的困難』，這使得其根本性缺陷更有可能在較晚的時候被發(fā)現(xiàn)?！?/p>

此外，「還應(yīng)該注意的一點是，在 NIST 進(jìn)行幾輪篩審查之前，可供分析的 PQC 算法是非常多的，因此研究精力被攤薄了。而經(jīng)過幾輪篩選之后，研究人員已經(jīng)能夠?qū)Ｗ⒂谝恍〈樗惴恕！笿oseph 說。

SIKE 的發(fā)明者之一、加拿大滑鐵盧大學(xué)教授 David Jao 表示：「我認(rèn)為這項新成果是一項了不起的工作，我對作者們給予了最高的評價。起初，我對 SIKE 的破解感到難過，因為它在數(shù)學(xué)上是一個如此優(yōu)雅的方案?！?/p>

「但新發(fā)現(xiàn)只不過是反映了科學(xué)的運(yùn)作方式：我們提出了一個系統(tǒng)，當(dāng)時每個人都認(rèn)為它好像還不錯，然后經(jīng)過分析，有人找到了它的弱點。他們花了 10 多年的時間才找到弱點，這點是不尋常的，但除此之外，這件事并沒有超出普通科學(xué)進(jìn)展的范圍。」David Jao 補(bǔ)充說。

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

SIKE 被破解意味著什么？

SIKE 是今年第二個被破解的 NIST PQC 候選算法。今年 2 月，蘇黎世 IBM 研究院的密碼學(xué)家 Ward Beullens 透露，他可以用筆記本電腦破解參與 NIST 第三輪審查的 Rainbow 算法。「這表明所有 PQC 方案都需要進(jìn)一步研究」，Katz 說道。

不過，Moody 指出，盡管 SIKE 被破解了，但其他基于同源的密碼系統(tǒng)，如 CSIDH 或 SQIsign，還沒被破解，「有些人可能以為基于同源的密碼學(xué)已經(jīng)死了，但事實遠(yuǎn)非如此，我認(rèn)為基于同源的密碼學(xué)還有很多東西要研究，」Decru 表示。

此外，這項新工作可能也無法反映 NIST 的 PQC 研究水平。正如 Decru 所說，SIKE 是 NIST 收到的 82 份提案中唯一一個基于同源的密碼系統(tǒng)；同樣，Rainbow 是這些提交中唯一的多變量算法。

那些被 NIST 采納為「標(biāo)準(zhǔn)」或進(jìn)入其第四輪審查的算法都是基于已經(jīng)被密碼學(xué)家研究、分析了很久的數(shù)學(xué)思想，Galbraith 說?！高@并不能保證它們是安全的，只是意味著它們經(jīng)受住了更長時間的攻擊?！?/p>

Moody 同意這一點，并指出「總是會發(fā)現(xiàn)一些驚人的突破性結(jié)果來破解密碼系統(tǒng)。對于任何密碼系統(tǒng)，我們都沒有絕對的安全保證。最好的說法是，經(jīng)過很多聰明人的大量研究，沒有人發(fā)現(xiàn)該密碼系統(tǒng)有任何漏洞?！?/p>

「我們的程序被設(shè)計為允許攻擊和破解，」Moody 說。「我們在每一輪評估中都見過它們。這是獲得對安全的信心的唯一途徑。」 Galbraith 對此表示贊同，并指出這樣的研究「正在發(fā)揮作用」。

盡管如此，「我覺得，Rainbow 和 SIKE 的雙雙隕落會讓更多的人認(rèn)真考慮，是否需要為 NIST 后量子標(biāo)準(zhǔn)化過程中出現(xiàn)的任何贏家制定后備計劃，」Decru 說。「僅僅依靠一個數(shù)學(xué)概念或方案可能太冒險了。這也是 NIST 自己的想法——他們的主要方案很可能是基于格密碼學(xué)（lattice-based）的，但他們想要一個非格密碼學(xué)方案備選?！?/p>

Decru 指出，其他研究者已經(jīng)開始開發(fā)新版本的 SIDH/SIKE，他們認(rèn)為這可能會阻止這種新型攻擊?！肝翌A(yù)計到會有這樣的結(jié)果，當(dāng)攻擊升級之后，人們試圖修補(bǔ) SIDH/SIKE，」Decru 說。

總而言之，事實表明這種新攻擊的起點是一個「與密碼學(xué)完全無關(guān)」的定理，并且「揭示了進(jìn)行純數(shù)學(xué)基礎(chǔ)研究以理解密碼系統(tǒng)的重要性」，Galbraith 表示。

Decru 對此表示同意，并指出「在數(shù)學(xué)中，并非所有東西都能立即適用。有些事情幾乎永遠(yuǎn)不會適用于任何現(xiàn)實生活中的情況。但這并不意味著我們不應(yīng)該讓研究導(dǎo)向這些更晦澀的議題?！?/p>