原作: Lejla Batina, Stjepan Picek, Bas Westerbaan

譯: PQCSF

最近一篇論文的新聞報(bào)道以這樣的標(biāo)題引起了一些轟動(dòng)，標(biāo)題為:「在AI幫助下破解了NIST推薦的后量子加密演算法」。新聞文章聲稱所討論的加密演算法Kyber已被「破解」，然而Kyber已在全球部署。更加戲劇性的是，新聞文章聲稱「這項(xiàng)研究的革命性在于將深度學(xué)習(xí)分析應(yīng)用于旁路差分分析」，這似乎旨在讓讀者擔(dān)心人工智慧（AI）會(huì)破解下一個(gè)什么東西？

有關(guān)這篇論文的報(bào)導(dǎo)非常不準(zhǔn)確: Kyber并未被破解，而且AI被應(yīng)用于旁路攻擊已經(jīng)行之有年了。這里要澄清，我們關(guān)注的是論文周圍的新聞報(bào)導(dǎo)，而不是論文本身的質(zhì)量。在本博客文章中，我們將解釋AI在密碼分析中的實(shí)際幫助，并深入研究這篇被新聞?wù)`導(dǎo)的 Dubrova、Ngo和G?rtner（DNG）的論文。我們很榮幸邀請(qǐng)到在將AI應(yīng)用于旁路攻擊方面的世界知名專家Prof. Dr. Lejla Batina和Dr. Stjepan Picek，加入我們的博客。

在深入探討這篇論文之前，我們先介紹一下旁路攻擊和Kyber的背景。

密碼學(xué)的破解

當(dāng)人們一提到破解密碼學(xué)時(shí)，往往會(huì)想像一個(gè)房間里擠塞了數(shù)學(xué)家，他們對(duì)被攔截的訊息細(xì)微的特征進(jìn)行解讀，并且借助大型電腦來(lái)找出密鑰。在二戰(zhàn)中，納粹的恩尼格瑪密碼機(jī)就是透過(guò)這種方式被破解，讓盟軍能夠?qū)用艿耐ㄐ胚M(jìn)行偷聽(tīng)。

而現(xiàn)今成熟的密碼技術(shù)被以這種方式破解已經(jīng)是極為罕見(jiàn)的了，最后一次被大規(guī)模破解的加密算法是1987年設(shè)計(jì)的RC4，而1998年設(shè)計(jì)的AES幾乎沒(méi)有任何被破解的跡象。最后一次對(duì)一個(gè)哈希算法的重大突破是對(duì)1995年設(shè)計(jì)的SHA-1的攻擊，而2001年發(fā)布的SHA-2至今仍未被實(shí)際攻破。

那么，如果你不能直接破解密碼，該怎么辦？那就要想出巧妙的方法。

旁路攻擊(Side-channel attacks)

你能猜出下面這個(gè)門的密碼嗎?

你應(yīng)該能很容易的注意到，某些按鍵磨損的特別明顯，這表示這幾個(gè)按鍵經(jīng)常被使用，這個(gè)訊息可以讓我們獲得一些密碼的特征，但不能確定正確的密碼順序，可能是1580，8510，甚至是115085，但比起嘗試所有密碼容易的多。這是旁路攻擊最經(jīng)典的案例。這個(gè)例子展示了使用安全功能（輸入密碼）時(shí)可能會(huì)產(chǎn)生一些意外后果（磨損涂料），從而泄漏了一些信息。

遠(yuǎn)端時(shí)間旁路攻擊(Remote timing side channel)

當(dāng)編寫密碼學(xué)程式時(shí)，演算法的運(yùn)行時(shí)間就是一個(gè)典型的旁路案例。舉個(gè)例子，當(dāng)我們建一個(gè)RSA簽名，需要用一個(gè)私鑰d來(lái)簽屬信息m，我們計(jì)算簽名s為m^d（mod n），計(jì)算一個(gè)數(shù)的大次方不是一件容易事，而慶幸的是，我們只需要做模運(yùn)算，所以有一些平方和乘法的技巧。這是一個(gè)偽代碼(Pseudocode）的簡(jiǎn)單實(shí)現(xiàn)：

該算法遍歷密鑰的每個(gè)位元(bits)，如果當(dāng)下位元為1，就做一次乘法。顯然，這個(gè)代碼的運(yùn)行時(shí)間取決于密鑰。這并不好，如果攻擊者只能對(duì)完整運(yùn)行進(jìn)行計(jì)時(shí)，那么他們只能了解密鑰中"1"的數(shù)量。針對(duì)RSA比較嚴(yán)重的計(jì)時(shí)攻擊反而是隱藏在“mod n”的后面。在這上面這個(gè)簡(jiǎn)單的實(shí)現(xiàn)中，如果要進(jìn)行模數(shù)運(yùn)算的數(shù)字大于等于 n，那么減法的速度會(huì)較慢。這使得攻擊者可以發(fā)送訂制的信息來(lái)逐位挑出密鑰，類似的攻擊非常實(shí)用。

因此密碼學(xué)應(yīng)該要以「常數(shù)時(shí)間」運(yùn)行為原則。這意味著運(yùn)行時(shí)間不會(huì)取決于任何秘密信息。在上述例子中，要消除第一個(gè)時(shí)間問(wèn)題，可以使用等效于"if"的其他語(yǔ)句來(lái)代替：

功率旁路攻擊(Power side-channel)

對(duì)于功率旁路攻擊，情況完全不同。同樣，以RSA簽名為例。如果我們連接示波器到一張智能卡，而這張智能卡在簽名之前使用了一種簡(jiǎn)單的演算法，并測(cè)量其功耗，我們可以直接透過(guò)肉眼讀取私鑰。

即使我們使用常數(shù)時(shí)間的實(shí)現(xiàn)，仍然有微小的功率使用變化可以被檢測(cè)到。其根本問(wèn)題在于，切換的硬件閘(gates)的使用比不切換的消耗更多的功率。例如，計(jì)算 127 + 64 消耗的功率比 64 + 64 更多。

遮蔽(Masking)

遮蔽是對(duì)抗功率旁路攻擊的常見(jiàn)對(duì)策。在使用機(jī)密信息之前，該信息會(huì)被隨機(jī)分成數(shù)個(gè)部分。然后，計(jì)算的大部分工作都是在這些部分進(jìn)行，最終再將它們組合起來(lái)。

在RSA的情況下，創(chuàng)建新簽名之前，可以生成一個(gè)隨機(jī)數(shù)r，然后分別計(jì)算m^(d+r) *(mod n)*和m^r (mod n)。通過(guò)這些值，可以在一些額外的注意事項(xiàng)下計(jì)算最終的簽名m^d (mod n)。

遮蔽不是一種完美的防御方法。分割或組合共享值的部分特別容易受到攻擊。但這確實(shí)提高了攻擊難度：他們需要收集更多的功耗來(lái)突破雜訊。在我們的例子中，我們使用了兩個(gè)共享值，但我們也可以增加它們的數(shù)量。功率旁路攻擊的抵抗力和實(shí)現(xiàn)成本之間存在一個(gè)權(quán)衡。

在這個(gè)領(lǐng)域中最具挑戰(zhàn)性的部分之一是估計(jì)實(shí)際通過(guò)跟蹤泄露的機(jī)密信息的數(shù)量以及如何提取它。這就是機(jī)器學(xué)習(xí)介入的地方。

機(jī)器學(xué)習(xí)：從微小的線索中提取密鑰

機(jī)器學(xué)習(xí)，其中深度學(xué)習(xí)領(lǐng)域的一部分，是系統(tǒng)通過(guò)數(shù)據(jù)提取模式來(lái)獲取知識(shí)的能力 - 在這種情況下，是從功耗曲線中提取密鑰的能力。機(jī)器學(xué)習(xí)可以根據(jù)它們的學(xué)習(xí)風(fēng)格分為幾個(gè)類別。旁路攻擊中最流行的是遵循監(jiān)督學(xué)習(xí)(supervised learning approach)。在監(jiān)督學(xué)習(xí)中，有兩個(gè)階段：1）訓(xùn)練，在這里，機(jī)器學(xué)習(xí)模型基于已知的標(biāo)記示例（例如，我們知道密鑰的旁路測(cè)量）進(jìn)行訓(xùn)練，2）測(cè)試，在測(cè)試階段，基于訓(xùn)練好的模型和額外的旁路測(cè)量（現(xiàn)在，使用未知的密鑰），攻擊者猜測(cè)密鑰。下面的圖表顯示了這類攻擊的常見(jiàn)描述。

雖然該威脅模型聽(tīng)起來(lái)有些反常，但實(shí)實(shí)際上很容易理解，攻擊者將會(huì)取得（并控制）與被攻擊的裝置相似的裝置。

在旁路分析中，依照這兩個(gè)階段（訓(xùn)練與測(cè)試）所進(jìn)行的攻擊被稱為分析攻擊(profiling attacks)。

分析攻擊并不是什么新東西。最早的一種分析攻擊稱為“模板攻擊”，于2002年出現(xiàn)。自2010年以來(lái)，不同的機(jī)器學(xué)習(xí)技術(shù)被用于分析攻擊，報(bào)告顯示這些技術(shù)都能取得良好的成果，并且能夠破解各種目標(biāo)。然而，真正的突破是在2016年，當(dāng)分析社群開(kāi)始使用深度學(xué)習(xí)時(shí)。這大大提高了功率分析攻擊的有效性，無(wú)論是對(duì)對(duì)稱密鑰還是公鑰加密，即使目標(biāo)受到了遮罩或其他反制措施的保護(hù)。要清楚的是：它并不能神奇地找到密鑰，但它能夠更好地從少量功率跟蹤中提取泄漏的位元。

雖然以機(jī)器學(xué)習(xí)為基礎(chǔ)的旁路攻擊很強(qiáng)大，但它們也有限制。精心實(shí)施的對(duì)策可以使攻擊變得更加困難。找到一個(gè)能夠破解目標(biāo)的好的機(jī)器學(xué)習(xí)模型可能并不容易：這個(gè)階段通常稱為調(diào)整，可能需要在強(qiáng)大的集群上持續(xù)進(jìn)行數(shù)周。

未來(lái)機(jī)器學(xué)習(xí)/人工智慧在旁路分析中會(huì)有什么發(fā)展？我們希望看到更強(qiáng)大、更易于使用的攻擊方法。你可能會(huì)認(rèn)為這會(huì)使我們處境更糟，但結(jié)果恰恰相反，這將使我們能夠更好地估計(jì)設(shè)備泄漏的實(shí)際信息量。我們也希望能夠更好地理解為什么某些攻擊有效（或無(wú)效），以便開(kāi)發(fā)更具成本效益的對(duì)策。因此，機(jī)器學(xué)習(xí)在旁道分析中的未來(lái)前景非常璀璨，尤其是對(duì)于安全評(píng)估人員，但我們?nèi)匀贿h(yuǎn)未能在現(xiàn)實(shí)應(yīng)用中破解大多數(shù)目標(biāo)。

KYBER

Kyber是一種后量子（PQ）金鑰封裝方法（KEM）。經(jīng)過(guò)全球六年的競(jìng)爭(zhēng)，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）選擇了Kyber作為他們將標(biāo)準(zhǔn)化的后量子金鑰協(xié)議。金鑰協(xié)議的目的是讓兩個(gè)之前沒(méi)有通過(guò)任何方式交流的雙方在安全的情況下達(dá)成共識(shí)，以建立一個(gè)用于對(duì)稱加密（例如Chacha20Poly1305）的共享密鑰。作為KEM，Kyber的工作方式略有不同，使用不同的術(shù)語(yǔ)，與傳統(tǒng)的Diffie-Hellman金鑰協(xié)議（例如X25519）有所不同：

當(dāng)客戶端連接到網(wǎng)站時(shí)，客戶端首先會(huì)產(chǎn)生一組新的臨時(shí)金鑰對(duì)，包括一個(gè)私鑰和一個(gè)公鑰?？蛻舳藢⒐€發(fā)送給伺服器。伺服器使用該公鑰封裝一個(gè)共享金鑰，得到一個(gè)隨機(jī)的共享金鑰，并將其保留，同時(shí)返回一個(gè)密文（其中隱藏了共享金鑰）給客戶端?？蛻舳丝梢允褂闷渌借€來(lái)解密來(lái)自密文中的共享金鑰?，F(xiàn)在，伺服器和客戶端可以使用共享金鑰互相通信。

在量子計(jì)算機(jī)攻擊中，金鑰協(xié)議的安全性特別重要。原因是攻擊者可以存儲(chǔ)今天的流量，并在未來(lái)破解金鑰協(xié)議，揭示共享金鑰和以后使用該金鑰加密的所有通信。這就是為什么我們已經(jīng)在我們的網(wǎng)絡(luò)中部署了對(duì)Kyber的支持。

DNG 論文

在我們有了上面的背景知識(shí)后，現(xiàn)在可以開(kāi)始閱讀 DNG 論文了。該論文作者對(duì)他們自己實(shí)現(xiàn)的 Kyber 掩蔽版本（使用六個(gè) share）進(jìn)行了一次功率旁路攻擊。

攻擊的重點(diǎn)

他們攻擊的目標(biāo)是解密步驟。在解密步驟中，共用密鑰被提取后，會(huì)再次進(jìn)行封裝，然后與原密文進(jìn)行比較，以檢測(cè)篡改。對(duì)于這個(gè)重新加密的步驟，共用密鑰的前驅(qū)（我們稱之為“密鑰前驅(qū)”）會(huì)被逐位編碼成多項(xiàng)式。準(zhǔn)確地說(shuō)，256位的密鑰需要被轉(zhuǎn)換為一個(gè)256個(gè)系數(shù)模q = 3329的多項(xiàng)式，其中第i個(gè)系數(shù)是(q + 1) / 2，如果第i位是1，否則為零。

這個(gè)函數(shù)聽(tīng)起來(lái)很簡(jiǎn)單，但創(chuàng)建掩碼版本則很棘手。問(wèn)題在于，創(chuàng)建密鑰的共用版本的自然方式是要有共用版本，這些版本互相進(jìn)行XOR操作以得到密鑰，而分享多項(xiàng)式的自然方式則是需要有共用版本，這些版本互相相加以得到所需的多項(xiàng)式。

這是DNG論文攻擊的兩個(gè)共用版本的實(shí)現(xiàn)方式:

這段程式碼會(huì)重復(fù)執(zhí)行兩個(gè)分享位元的位元。對(duì)于每個(gè)位元，它創(chuàng)建一個(gè)遮罩，如果該位元為1，則該遮罩為0xffff，否則為0。然后，如果適當(dāng)，使用此遮罩將(q+1)/2添加到多項(xiàng)式分享中。處理1將使用更多功率。沒(méi)有必要是AI也可以想出這將是一個(gè)有泄漏風(fēng)險(xiǎn)的函數(shù)。事實(shí)上，這種模式于2016年被指出是脆弱的，并在2020年明確提到了是遮罩Kyber的風(fēng)險(xiǎn)之一。順便提一下，緩解這種情況的一種方法是同時(shí)處理多個(gè)位元 - 對(duì)于最先進(jìn)的技術(shù)，請(qǐng)收聽(tīng)2023年4月的NIST PQC研討會(huì)。暫時(shí)讓我們接受這份論文的弱點(diǎn)。

作者在這里沒(méi)有宣稱任何新的攻擊。相反的，他們通過(guò)兩種方式改進(jìn)了攻擊的效果：他們?nèi)绾斡?xùn)練神經(jīng)網(wǎng)絡(luò)，以及如何通過(guò)更改發(fā)送的密文更有效地使用多個(gè)微小的信息。那么他們實(shí)現(xiàn)了什么呢？

有效性

為了測(cè)試這種攻擊，他們使用了一塊Cortex M4 CPU核心的Chipwhisperer-lite開(kāi)發(fā)板，他們把它降頻到24Mhz。功率的使用是以24Mhz的頻率進(jìn)行采樣，精度高達(dá)10bits。

為了訓(xùn)練神經(jīng)網(wǎng)絡(luò)，他們收集了150,000個(gè)功率跟蹤，用于解密不同密文（使用已知共享密鑰）的封裝內(nèi)容，以獲取相同的KEM密鑰對(duì)。這已經(jīng)是一種相對(duì)于現(xiàn)實(shí)攻擊而言較為不尋常的情況：對(duì)于密鑰協(xié)定（KEM），密鑰對(duì)是短暫的；只會(huì)被生成和使用一次。盡管如此，長(zhǎng)期的KEM密鑰對(duì)仍然存在合法的用例，例如身份驗(yàn)證、HPKE，特別是ECH。

訓(xùn)練是關(guān)鍵的一步：即使來(lái)自同一制造商的不同設(shè)備在運(yùn)行相同代碼時(shí)的能耗軌跡也可能有很大的不同。即使兩個(gè)設(shè)備是同一型號(hào)，它們的能耗軌跡仍可能有顯著差異。

作者強(qiáng)調(diào)的主要貢獻(xiàn)是，他們訓(xùn)練了神經(jīng)網(wǎng)絡(luò)來(lái)攻擊具有6個(gè) shares 的實(shí)現(xiàn)，并開(kāi)始使用訓(xùn)練用于攻擊具有5個(gè) shares 的實(shí)現(xiàn)的神經(jīng)網(wǎng)絡(luò)。一個(gè)神經(jīng)網(wǎng)絡(luò)訓(xùn)練用于攻擊4個(gè) shares 的實(shí)現(xiàn)，以此類推。因此，對(duì)于這150,000個(gè)能耗軌跡中，必須有五分之一來(lái)自具有6個(gè) shares 的實(shí)現(xiàn)，另外五分之一來(lái)自具有5個(gè) shares 的實(shí)現(xiàn)，以此類推?？雌饋?lái)不太可能有任何人會(huì)部署一個(gè)攻擊者可以隨時(shí)在掩蔽使用的 share 數(shù)量之間切換的設(shè)備。

在考慮了這些因素后，攻擊正式開(kāi)始。作者報(bào)告說(shuō)，從一個(gè)具有兩個(gè) share 的解密的單個(gè)能耗軌跡中，他們可以在理想情況下以概率 0.12％ 恢復(fù)共享密鑰。對(duì)于單次軌跡攻擊超過(guò)兩個(gè) share，他們沒(méi)有報(bào)告數(shù)字。

當(dāng)我們?cè)试S多個(gè)相同的解密的軌跡時(shí)，那么利用旁路攻擊就會(huì)更加有效。第二個(gè)技巧是這個(gè)攻擊的一個(gè)巧妙的轉(zhuǎn)折：作者將密文旋轉(zhuǎn)，以使共享密鑰的位于更有利的位置。使用 4 個(gè)相同訊息的旋轉(zhuǎn)軌跡，對(duì)于具有兩個(gè) shares 的實(shí)現(xiàn)，成功概率提高到 78％。六個(gè) shares 的實(shí)現(xiàn)的成功率仍為 0.5％。當(dāng)允許來(lái)自具有六個(gè) shares 的實(shí)現(xiàn)的 20 個(gè)軌跡時(shí)，共享密鑰可以以 87％ 的概率被恢復(fù)。

在實(shí)際應(yīng)用中

這個(gè)實(shí)驗(yàn)所使用的硬體可能與智能卡相當(dāng)，但與高端設(shè)備（例如智慧手機(jī)、桌面電腦和伺服器）非常不同。即使是在只有1GHz的嵌入式處理器上，簡(jiǎn)單的功率分析旁路攻擊也更具挑戰(zhàn)性，需要使用高端示波器連接到處理器附近，使用數(shù)萬(wàn)個(gè)信息。對(duì)于這種物理存取的攻擊，有更好的攻擊途徑：只需將示波器連接到記憶體匯流排即可。

除了特別脆弱的應(yīng)用程式（例如智能卡和HSMs），功率旁路攻擊被廣泛認(rèn)為是不可行的。雖然有時(shí)候，當(dāng)星球排列得恰當(dāng)時(shí)，一種特別有效的功率旁路攻擊可能會(huì)因?yàn)楣?jié)流而轉(zhuǎn)化為遠(yuǎn)程定時(shí)攻擊，就像Hertzbleed所演示的那樣。明確地說(shuō)：目前的攻擊還遠(yuǎn)遠(yuǎn)不到這個(gè)層次。

即使對(duì)于這些脆弱的應(yīng)用程式，例如智能卡，這種攻擊也不是特別有效或令人驚訝的。在實(shí)際中，問(wèn)題不在于遮蔽實(shí)現(xiàn)是否會(huì)泄露其密碼，因?yàn)樗偸菚?huì)泄露。問(wèn)題在于實(shí)際執(zhí)行攻擊的難度有多大。像DNG論文這樣的論文有助于幫助制造商估計(jì)需要實(shí)施多少對(duì)抗措施，使攻擊變得更加昂貴。這不是第一篇研究Kyber功率旁路攻擊的論文，也不會(huì)是最后一篇。

總結(jié)來(lái)說(shuō)

人工智慧并沒(méi)有完全破壞新的加密技術(shù)，反而是一個(gè)有用的工具，可以處理雜訊數(shù)據(jù)，并發(fā)現(xiàn)其中的漏洞。直接破解密碼和電源旁路攻擊之間有很大的區(qū)別。 Kyber沒(méi)有被破解，所呈現(xiàn)的電源旁路攻擊也不足以引起警惕。

原文:?https://blog.cloudflare.com/kyber-isnt-broken/