量子計算機運行能夠快速破解加密的算法

未來的量子計算機可能會迅速突破現(xiàn)代密碼學(xué)。現(xiàn)在研究人員發(fā)現(xiàn)，一種設(shè)計用于保護(hù)計算機免受這些高級攻擊的有前途的算法可能在4分鐘內(nèi)即被破壞。問題是，這4分鐘的時間還不是由現(xiàn)如今的尖端機器完成的，而是由一臺使用了10年的普通臺式計算機實現(xiàn)的。研究人員說，這一最新的令人驚訝的失敗凸顯了后量子密碼術(shù)在采用前需要清除的許多障礙。

理論上，量子計算機可以快速解決問題，而經(jīng)典計算機可能需要更多難以預(yù)測的時間才能解決。例如，許多現(xiàn)代密碼學(xué)依賴于經(jīng)典計算機在處理數(shù)學(xué)問題時所面臨了極端困難，如分解大量數(shù)字。然而，量子計算機原則上可以運行能夠快速破解這種加密的算法。

為了在這一量子威脅面前保持領(lǐng)先，世界各地的密碼學(xué)家在過去二十年中一直在設(shè)計后量子密碼（postquantum cryptography，PQC）算法。這些都是基于量子和經(jīng)典計算機都難以解決的新數(shù)學(xué)問題。

多年來，國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）等組織的研究人員一直在研究哪些PQC算法應(yīng)該成為世界應(yīng)該采用的新標(biāo)準(zhǔn)。NIST于2016年宣布正在尋找候選PQC算法，并于2017年收到82份提交。7月，經(jīng)過三輪審查后，NIST宣布四種算法將成為標(biāo)準(zhǔn)，另外四種算法被認(rèn)定為是候補選手，將進(jìn)入下一輪的篩選。

現(xiàn)在，一項新的研究揭示了一種方法，可以完全打破這些被審查的競爭者之一SIKE，微軟、亞馬遜、Cloudflare和其他公司已經(jīng)對此進(jìn)行了調(diào)查。要知道，他們破解的算法SIKE一直以來都被寄予厚望，過去12年都無人破解。密歇根大學(xué)安娜堡分校的密碼學(xué)家Christopher Peikert有參與這項新的研究，他說：“這是突然發(fā)生的，是一顆銀彈?！?/p>

SIKE （Supersingular Isogeny Key Encapsulation） 是一種涉及橢圓曲線的PQC（后量子計算）算法。NIST的數(shù)學(xué)家Dustin Moody說：“橢圓曲線在數(shù)學(xué)中已經(jīng)研究了很長時間了。它們由方程y2=x3+Ax+B描述，其中A和B是數(shù)字。例如，橢圓曲線可以是y2=x3+3x+2?！?/span>

在1985年，“數(shù)學(xué)家們找到了一種方法來制作涉及橢圓曲線的密碼系統(tǒng)，這些系統(tǒng)已經(jīng)被廣泛應(yīng)用，”Moody說，“然而，這些橢圓曲線密碼系統(tǒng)很容易受到量子計算機的攻擊。”

大約在2010年，研究人員發(fā)現(xiàn)了一種在密碼中使用橢圓曲線的新方法。Moody說：“人們相信這一新想法不會受到量子計算機的攻擊?！?這種新方法是基于如何在橢圓曲線上添加兩個點，以獲得橢圓曲線上的另一個點?！巴瑯?gòu)”是從一條橢圓曲線到另一條保持該加法定律的橢圓曲線的映射。

“如果你把這張地圖弄得足夠復(fù)雜，那么可以對數(shù)據(jù)進(jìn)行加密的推測難題是，給定兩條橢圓曲線，很難找到它們之間的同構(gòu)關(guān)系，”該研究的合著者、比利時庫魯汶的數(shù)學(xué)密碼學(xué)家Thomas Decru如此表示。

SIKE是一種基于超奇異同根Diffie-Hellman（SIDH）密鑰交換協(xié)議的同根密碼學(xué)?！癝IDH/SIKE是第一個實用的基于同構(gòu)的密碼協(xié)議，”Decru說。

然而，SIKE的一個弱點是，為了使其工作，它需要向公眾提供額外的信息，稱為輔助扭轉(zhuǎn)點。Moody說：“攻擊者試圖利用這些額外信息已有一段時間，但未能成功地利用這些信息來破壞SIKE。然而，這篇新論文找到了一種方法，使用了一些相當(dāng)先進(jìn)的數(shù)學(xué)方法?！?/p>

為了解釋這種新的攻擊，Decru說，盡管橢圓曲線是一維對象，但在數(shù)學(xué)上，橢圓曲線可以被視為二維或任意其他維度的對象。也可以在這些廣義對象之間創(chuàng)建同構(gòu)。

通過應(yīng)用一個已有25年歷史的定理，新的攻擊利用了SIKE公開的額外信息來構(gòu)造二維同構(gòu)。然后，這種同構(gòu)可以重構(gòu)SIKE用來加密消息的密鑰。Decru和研究資深作者Wouter Castryck于8月5日在Cryptology ePrint Archive中詳細(xì)介紹了他們的發(fā)現(xiàn)。

馬里蘭大學(xué)帕克分校的密碼學(xué)家Jonathan Katz說：“對我來說，最令人驚訝的是，這次攻擊似乎是無緣無故的。之前很少有結(jié)果顯示SIKE存在任何弱點，然后突然出現(xiàn)了一個完全破壞性的攻擊，即它找到了整個密鑰，并且在沒有任何量子計算的情況下相對快速地完成了。”

使用基于這種新攻擊的算法，研究人員發(fā)現(xiàn)，一臺使用了10年的Intel臺式機需要4分鐘就找到了由SIKE保護(hù)的密鑰。

“通常，當(dāng)一個提出的密碼系統(tǒng)受到嚴(yán)重攻擊時，這發(fā)生在系統(tǒng)被提出后，或開始引起注意后，或隨著時間的推移，研究結(jié)果的進(jìn)展，或不是完全破壞，而是系統(tǒng)的顯著削弱。在這種情況下，我們沒有看到任何情況，”Peikert說，“對SIDH/SIKE的襲擊從最初提出SIDH以來的11年到12年中基本上沒有進(jìn)展，直到完全中斷?！?/p>

盡管研究人員對SIKE進(jìn)行了十多年的測試，“SIKE未被選為標(biāo)準(zhǔn)化的原因之一是人們擔(dān)心它太新，研究不夠，”新西蘭奧克蘭大學(xué)的數(shù)學(xué)家Steven Galbraith說（他沒有參與這項新工作），“人們自然會擔(dān)心可能仍舊存在重大襲擊有待發(fā)現(xiàn) —— 他們是對的?！?/p>

到目前為止，SIKE的漏洞尚未被檢測到的一個原因是，新的攻擊“應(yīng)用了非常先進(jìn)的數(shù)學(xué)——“我想不出還有哪種情況下，與被破壞的系統(tǒng)相比，攻擊使用了如此深入的數(shù)學(xué)，”Galbraith說。Katz對此表示贊同，他說：“我懷疑世界上只有不到50個人理解基本的數(shù)學(xué)和必要的密碼術(shù)?！?/p>

此外，加州帕洛阿爾托PQC初創(chuàng)公司Sandbox AQ的密碼學(xué)家David Joseph說，同族基因“從實現(xiàn)和理論角度來看都是出了名的‘困難’（他沒有參與這項新工作）?！斑@使得更可能的是，根本性缺陷在競爭中持續(xù)到很晚才被發(fā)現(xiàn)?！?/p>

“We proposed a system， which everyone agrees seemed like a good idea at the time， and after subsequent analysis someone is able to find a break. It is unusual that it took 10 years， but otherwise nothing to see here.”

—David Jao， University of Waterloo

此外，“需要注意的是，在前幾輪中有更多的算法，密碼分析的傳播更為稀疏，而在過去幾年中，研究人員能夠?qū)Ｗ⒂谳^小的一批算法，”Joseph說。

SIKE的共同發(fā)明人、加拿大滑鐵盧大學(xué)教授David Jao表示，“我認(rèn)為這項新成果是一項偉大的工作，我對作者給予了最高的贊揚?！彼f，“起初，我對SKIE被宣告無效感到難過，因為這是一個數(shù)學(xué)上的方案，但新發(fā)現(xiàn)只是反映了科學(xué)是如何運作的。我們提出了一個系統(tǒng)，當(dāng)時每個人都認(rèn)為這是一個好主意，在隨后的分析之后，有人能夠找到一個突破。這是不尋常的，它花了10年，但除正常的進(jìn)展過程外，這里什么都看不到?！?/p>

此外，Jao說，“現(xiàn)在打破SIKE比在一些假設(shè)的替代世界中要好得多，在這個世界中，SIKE被廣泛部署，每個人都會在它被打破之前依賴它?！?/p>

BREAKS IN THE SYSTEM

SIKE是今年第二位被破解的NIST PQC候選人。二月份，蘇黎世IBM研究中心的密碼學(xué)家Ward Beullens透露，他可以在周末用筆記本電腦破解第三輪候選人Rainbow?！耙虼?，這表明所有PQC方案仍需要進(jìn)一步研究，”Katz說。

指出，盡管如此，這些新發(fā)現(xiàn)打破了SIKE，但沒有打破其他基于同構(gòu)的密碼系統(tǒng)，如CSIDH或SQIsign?！皝碜酝獠康娜丝赡苷J(rèn)為基于同構(gòu)的密碼術(shù)已經(jīng)死了，但這遠(yuǎn)非事實，”Decru說，“如果你問我的話，還有很多需要研究?！?/p>

此外，這項新工作也可能不會以某種方式反映NIST的PQC研究。SIKE是NIST收到的82份提交文件中唯一基于同構(gòu)的密碼系統(tǒng)。Decru說，同樣，Rainbow是這些提交文件中唯一的多元算法。

Galbraith說，NIST正在采用的其他設(shè)計作為標(biāo)準(zhǔn)或已進(jìn)入NIST第四輪的設(shè)計“基于數(shù)學(xué)思想，密碼學(xué)家的研究和分析記錄更長。這并不能保證他們一定是安全的，但這只是意味著他們經(jīng)受了更長時間的攻擊?！?/span>

Moody同意這一觀點，并指出“總是會發(fā)現(xiàn)一些驚人的突破性結(jié)果，打破密碼系統(tǒng)。我們無法絕對保證任何密碼系統(tǒng)的安全性。我們能說的最好的是，經(jīng)過許多聰明人的大量研究，沒有人在密碼系統(tǒng)中發(fā)現(xiàn)任何裂縫”。

Moody表示：“我們的程序設(shè)計為允許攻擊和中斷。我們在每一輪評估中都看到了它們。這是獲得對安全的信心的唯一途徑。”Galbraith表示同意，并指出這種研究“正在進(jìn)行”。

盡管如此，“我覺得Rainbow和SIKE的結(jié)合會讓更多人認(rèn)真考慮為NIST后量子標(biāo)準(zhǔn)化過程中出現(xiàn)的任何贏家制定一個后備計劃，”Decru說，“僅僅依靠一個數(shù)學(xué)概念或方案可能太危險。這也是NIST自己認(rèn)為的。他們的主要方案很可能是基于晶格的，但他們需要非晶格備份。”

Decru指出，其他研究人員已經(jīng)在開發(fā)SIDH/SIKE的新版本，他們認(rèn)為可能會阻止這種新的攻擊。Decru說：“我預(yù)計接下來會有更多這樣的結(jié)果，人們試圖修補SIDH/SIKE，并改進(jìn)我們的攻擊。”

總而言之，這一新攻擊的起點是一個“與密碼學(xué)完全無關(guān)”的定理，這一事實也表明了“為了理解密碼系統(tǒng)，純數(shù)學(xué)基礎(chǔ)研究的重要性，”Galbraith說。

Decru同意這一觀點，并指出“在數(shù)學(xué)中，不是所有的東西都能立即適用。有些東西幾乎肯定永遠(yuǎn)不會適用于任何現(xiàn)實生活中的情況。但這并不意味著我們不應(yīng)該讓研究不時轉(zhuǎn)向這些更模糊的話題?！?/p>