抗量子計算的密碼就一定安全？

背景介紹

眾所周知，目前使用的公鑰加密算法都是基于某個數學困難問題，比如大整數分解問題和離散對數問題。但是一旦大型量子計算機研制成功，這兩個問題可以通過肖算法得到有效的解決。因此美國國家標準與技術研究院(NIST)在多年前發起了征集后量子時代密碼算法的項目。

NIST后量子時代標準化項目目前進行了三輪。第一輪主要關注算法在安全性上的評估；第二輪主要考慮算法的具體實現；第三輪關注算法在側信道攻擊下的安全性。

第三輪評審的四個候選算法中有三個都是基于格理論的算法，分別是基于NTRU方案的候選者NTRU，基于Learning With Errors(LWE)方案的Kyber和基于Learning With Rounding(LWR)方案的Saber。這三個算法的困難性都來源于向線性方程中插入未知噪聲。

在2021年的學術會議CHES上，Kalle Ngo等人實現了針對帶掩碼IND-CCA安全的Saber KEM算法實現的側信道攻擊。應用神經網絡學習高階模型，不需要知道隨機掩碼值，并且在建模階段不需要一個可以被完全控制的分析設備。其中，帶掩碼IND-CCA安全的Saber KEM算法由Michiel等人于2020年提出，該算法的開銷是無掩碼版本的2.5倍^[1]。

泄露分析

論文首先介紹了Saber的公鑰加密算法和密鑰封裝算法，具體算法過程如圖1和圖2所示。

圖1 Saber公鑰加密算法

圖1中是Saber的公鑰加密算法，同一般的公鑰加密算法，用戶需要生成一對公私鑰，發送方使用公鑰加密要傳遞的信息，接收方收到信息后使用私鑰解密。

圖2 Saber密鑰封裝算法

圖2是Saber的密鑰封裝算法，其中應用了圖1中的公鑰加解密算法。密鑰封裝算法一般是用于傳遞對稱加密算法的密鑰，其相比于直接用公鑰加密算法有效率上的優勢。這篇論文攻擊的是密鑰解封算法，具體就是圖2的第1行代碼。

論文提出了兩個問題，第一個問題是如何確定泄露位置，第二個問題是如何在不知道掩碼的情況下恢復信息message(也就是圖2中密鑰解封算法第一行的m')。

對于第一個問題，論文提出的解決方案是根據無掩碼的實現方案確定若干大概位置，對于每一個大概位置使用深度學習模型進行學習，如果模型可以學習到一個很高的準確度，則認為這些點有泄露，否則就平移窗口并重復訓練。

對于第二個問題，在目前場景下，message是一個256比特的數，每個比特是0或者1。對于message的每一個比特m，一階掩碼會將其分為兩個分量r和m?r。在訓練階段，模型將兩個分量對應的波形共同作為輸入，將m的值作為標簽。在攻擊階段，模型將兩個分量對應的波形共同作為輸入，輸出一個概率值，代表該比特為1的概率。

由于公鑰加密算法可以預計算一組對應于隨機或者選擇message的密文，因此本論文的攻擊方法可以在訓練階段在被攻擊設備上采集能量跡作為訓練集。

圖3是Saber帶掩碼和不帶掩碼的解密算法源碼，其中標紅的代碼是存在泄露的代碼。

圖3 不帶掩碼和帶掩碼的Saber解密算法的C源碼

可以看到，帶掩碼的解密算法存在兩種泄露，第一種泄露是在其第8行代碼，poly_A2A函數將帶掩碼的中間值的兩個分量作為輸入，對其逐比特進行操作。第二種泄露是在其第9和10行代碼，POL2MSG函數的功能是將比特數組轉換為字節數組，因此也存在泄露。

實驗環境與攻擊模型

圖4是這篇論文的實驗環境，包括一個ChipWhisperer-Lite板子，一個CW308 UFO板子和一個CW308T-STM32F4目標板。其中D1、D2和D3都是同一種芯片，但是D1和D2是同一廠商生產的芯片，D3是另一廠商生成的芯片。

圖4 用來采集能量跡的設備以及三種實驗中使用的板子

論文的攻擊模型取決于攻擊者擁有的攻擊時間長短。如果攻擊者有充足的時間在被攻擊設備上采波，則訓練集和測試集均來源于被攻擊設備，在這種情況下，D1用來訓練和攻擊；如果攻擊者的時間只夠用來采集攻擊波形，則攻擊者需要另一臺類似設備用來建模。在這種情況下， D1用來建模，D2和D3用來攻擊。

實驗過程與結果

在實驗的建模階段，采集若干能量跡，按照字節或者比特進行切分，因其是帶有一階掩碼防護的能量跡，因此通過將兩個分量對應的能量跡進行組合，可以將訓練集擴大32(按字節分段)或者256倍(按比特分段)。

對于poly_A2A函數的泄露，訓練一個模型即可，對于POL2MSG函數的泄露，由于用一個字節需要連續異或8個比特，每次異或時其余的比特狀態不同，因此需要訓練8個模型。

因為論文數據集中的能量跡在時間軸上非常整齊，因此作者發現MLP的效果要比CNN更好，所以論文最終使用的是MLP。

圖5(a)Saber密鑰解封部分的初始能量跡；(b)包含poly_A2A(v1，v2)，POL2MSG(v1，m1)和POL2MSG(v2，m2)的能量跡；(c)POL2MSG的兩個分量；(d)第一個分量的前15字節。

圖5是原始能量跡。論文作者首先根據無防護版本算法的經驗確定了一個大概的位置，根據poly_A2A函數中有一個大小為256的循環和POL2MSG函數中有一個大小為32的循環，確定了它們的具體位置。

圖5(c)是帶掩碼的中間值的兩個分量對應的能量跡，論文作者通過將兩個分量對應的能量跡按字節進行切分，并將對應字節的能量跡進行拼接，構造了神經網絡的訓練和測試集。

訓練階段，從D1上采集了50K條波，隨機密文和密鑰。對于poly_A2A函數的泄露，構建了4K×256=1.024M訓練集，對于POL2MSG函數的泄露，構建了50K×32=1.6M訓練集。測試階段，從D1，D2和D3上分別采集了1K的波形作為測試集，測試集是隨機密文和固定密鑰。

圖6 論文實驗結果，從上到下分別是只使用POL2MSG函數的泄露的結果，只是用poly_A2A函數的泄露的結果和兩個函數的泄露都使用的結果。

圖6是論文中實驗結果的截圖。分別是只使用POL2MSG函數的泄露結果、只使用poly_A2A函數的泄露結果和使用兩個函數的泄露結果。

由實驗結果發現，對于POL2MSG函數的泄露，第7個比特最難攻破，對于poly_A2A函數的泄露，第0個比特最難攻破。

為了解釋這一現象，論文對波形做了TVLA和SOST測試。結果如圖7和圖8所示。

圖7 m?r分量的第一個字節的poly_A2A泄露和POL2MSG泄露的t-test結果

圖8 POL2MSG泄露逐比特的t-test結果

論文作者分析后認為，對于poly_A2A泄露，只有第一個比特前的操作和其它比特不同，因此導致了第一個比特的泄露比其它比特低；對于POL2MSG泄露，越靠后異或的比特位的能量泄露越小。

在成功恢復出中間值message后，論文據此恢復出了密鑰。

總結

作者使用了24條能量跡恢復出了帶掩碼的Saber算法的密鑰，提出了模型的訓練過程可以在被攻擊設備上進行，發現了先前從未發現的泄露類型，并且在密鑰恢復階段展示了一種新的密鑰恢復方法可以抵消在中間值恢復時的一些錯誤。