基于循環密文的格密碼模板攻擊方法

嚴迎建 常雅靜 朱春生 劉燕江

(戰略支援部隊信息工程大學 鄭州 450001)

1 引言

為應對量子計算對傳統公鑰密碼算法的威脅，全球的密碼學者都在積極開展后量子密碼算法(Post-Quantum Cryptography, PQC)的研究。2016年12月，美國國家標準與技術研究院(National Institute of Standards and Technology, NIST)啟動了全球范圍內的后量子公鑰密碼標準化項目，而基于格的后量子密碼以其具有線性計算復雜度、擴展性較好和功能設計多樣化等優勢，被認為是最有力的競爭者[1]。征集的后量子密碼在算法安全性和性能上都有一定的要求，其中特別強調了算法在具體實現和應用時的物理安全性，即抗側信道攻擊能力。

側信道攻擊首先由Kocher等人[2]提出，其中能量分析攻擊以其攻擊時間成本低、攻擊原理簡單、攻擊成功率高等特點在該領域中得到廣泛應用。能量分析攻擊主要利用密碼設備在運行時產生的能量泄露如功耗、電磁輻射等信息，并結合一定的分析手段來獲取秘密信息[3]。隨著后量子密碼算法標準化的到來，迫切需要研究算法實現過程中的能量分析攻擊和防護技術。

近年來，針對格密碼的側信道攻擊分為兩個方向：一是獲取長期使用的私鑰，二是恢復加密過程中的秘密消息與共享密鑰。在第1個方向中，Primas等人[4]和Pessl等人[5]將攻擊點選為數論變換(Number Theoretic Transforms, NTT)，而Ravi等人[6]將攻擊點選在糾錯碼和FO(Fujisaki-Okamoto)變換上；Aydin等人[7]利用橫向攻擊對Frodo算法軟硬件實現中的矩陣乘法進行攻擊；Xu等人[8]使用精心構建的密文對Kyber算法實施自適應電磁攻擊，實現完全的密鑰提?。辉诘?個方向中，Ravi等人[9]利用電磁泄露并結合聚類算法對1階掩碼保護的NewHope512算法進行攻擊；Amiet等人[10]針對NewHope算法提出單能量軌跡消息恢復方法；Sim等人[11]提出一種基于機器學習的攻擊方法，對部分格密碼的編碼過程進行攻擊；Ngo等人[12,13]利用深度學習技術對融合掩碼與洗牌技術的Saber算法進行安全性分析。

本文針對格密碼解封裝過程中的解碼操作提出一種秘密消息恢復方法。主要完成以下4方面內容：

(1)深入分析文獻[9]提出的單比特存儲泄露，利用歸一化類間方差(Normalized Inter-Class Variance, NICV)方法對目標字節中間值的漢明重量進行分類，減少預處理過程所需的能量跡；

(2)識別格密碼中存在的密文循環特性，并利用該特性構造特定密文，使得攻擊的比特寬度與之前的攻擊中的比特寬度不同，減少攻擊過程所需的能量跡；

(3)以Saber算法為例在ChipWhisperer平臺驗證適用性和有效性，證明所提模板攻擊方法可以極大地減少預處理和攻擊過程所需能量跡，并大幅提升攻擊的成功率；

(4)對本文方法的擴展性進行簡要定性分析。

2 相關基礎知識

2.1 Saber算法

Rq=Zq/φ(x) 表示模多項式φ(x)的多項式環，在本文中φ(x)=xn+1為不可約多項式。Bk表示長度為k的字節數組，對于m∈Bk，第i個字節用m[i]表示，m[i, j]表示m的第i個字節在第j個循環結束后的中間值結果，mi表示m的第i個比特，m[i]j表示m[i]的第j個比特。

Saber算法[14]的安全性是基于模上舍入學習(Module-Learning With Rounding, M-LWR)困難問題，該問題是帶錯誤學習(Learning With Errors,LWE)問題的一種變體。Saber算法以2的次冪作為模數，使用模塊結構并通過舍入引入誤差[15]，使得Saber算法有更高的加密效率。Saber算法包括滿足選擇明文攻擊下不可區分性(INDistinguishability under Chosen-Plaintext Attack, IND-CPA)的公鑰加密算法(Public Key Encryption, PKE)和選擇密文攻擊下的不可區分性(INDistinguishability under Chosen-Ciphertext Attack, IND-CCA)的密鑰封裝機制(Key Encapsulation Mechanism,KEM)。由于Saber PKE在選擇密文攻擊下是不安全的，因此Saber KEM在Saber PKE的基礎上，利用FO變換對解密出的消息進行重加密，并比對重加密密文c′和接收到的密文c，從而識別計算過程中是否存在選擇密文攻擊。算法1和算法2分別描述了Saber PKE解密算法和Saber KEM解封裝算法，更多Saber算法的相關說明可參考文獻[14]。

2.2 測試向量泄露評估

測試向量泄露評估(Test Vector Leakage Assessment, TVLA)是一種基于一致性的評估方法[16]，通過假設檢驗來判斷加密過程中的能量消耗是否存在顯著性差異，其中Welch t檢驗評估方法[17]是使用最廣泛、研究方案最完善的假設檢驗工具。假設兩組能量測量值分別為Tr和Tf，則這兩組能量測量值之間的TVLA值可以表示為

算法1 Saber PKE解密算法

其中，Xr, σr和Nr分別代表測試集Tr的均值、標準差和基數，對Tf同理。Welch t檢驗通常將拒絕零假設的閾值設為4.5，當且僅當t檢驗結果的絕對值大于4.5時，才能以99.999 9%的置信度拒絕零假設，表示兩組測量值之間存在明顯差異，可能會導致秘密信息的泄露。

2.3 NICV

NICV[18]是一種單變量方差分析F檢驗，是以類別為條件的泄露均值方差與總泄露方差之間的比率。NICV與TVLA都可用作側信道評估指標，但TVLA通常用于區分兩個不同的類別，而NICV可以同時區分兩個或以上的類別。假設C(X)為給變量X的類別，若測量到X的泄露表示為T，則以式(2)計算NICV

其中，E[·]表示單變量均值，Var[·]表示標準差。雖然NICV沒有確切的閾值，但是給定點的NICV值越大，每個類之間的泄露差異就越顯著。

3 Saber KEM泄露分析

能量分析的攻擊點通常選擇與明文或者密鑰有直接聯系的關鍵操作。Ravi等人[9]提出了增量存儲漏洞，稱為Single_Bit_Update，該漏洞利用存儲單比特信息時產生的泄露實現完整的秘密消息恢復。Saber算法的解封裝過程如圖1所示，圖1的解碼操作用于實現消息的多項式形式向字節形式的轉換，其中存在Single_Bit_Update，下面進行簡要分析。

圖1 Saber KEM解封裝過程結構圖

Saber算法利用POLmsg2BS函數實現消息的解碼過程，C代碼片段可以參考算法3[19]。POLmsg2BS函數將一個具有256個系數的給定多項式a轉換為消息數組m∈B32。該函數分為兩個循環，外循環是以字節為單位進行運算，而內循環則是對目標字節按位進行運算。首先在外循環中將消息字節m[j]初始化為0 (見第(4)行)，隨后在內循環中將多項式a的每個系數a [8×j + i]通過計算轉化為中間值t(a即為算法3中的data，見第(6)行)，通過移位和按位或操作將t更新為m[j]i(其中i∈[0,7]，見第(7)行)，m[j]i的更新共重復256次。通過分析可以發現，對于m的每個消息比特mi，都只與多項式a的一個系數a[i]有關，因此秘密消息m從固定值0開始每次迭代更新1位。在相鄰的兩次迭代中，消息m只存在1 bit差異，這種處理消息單個比特的方式成為側信道攻擊的有效目標。

使用ARM工具鏈(arm-none-eabi-gcc)對上述C語言代碼進行編譯生成匯編，對應的匯編代碼片段如圖2所示。在經過按位與和移位操作后，寄存器r3中存儲的值t通過strb指令存入地址為(fp-24)的內存單元中(見第(14)行)，每一個消息字節m[j]在經過8次迭代后即可實現字節的完全轉換。存儲指令(strb)在執行過程中會產生能量消耗，這些能量消耗與存儲中間值的漢明重量之間有一定關系，通過分析兩次相鄰迭代之間的中間值的漢明重量關系，可以推斷出中間值，從而還原關鍵的秘密消息。

圖2 Saber POLmsg2BS匯編代碼片段

4 基于模板與密文循環特性的消息恢復方法

依據第3節對Single_Bit_Update的分析，消息字節m[i]在8次迭代后完成全部更新，且每個消息字節都是以相同的方式進行更新的，因此考慮以字節為單位進行秘密消息恢復。本節將介紹基于模板與密文循環特性的消息恢復方法并分析其實現可能性。

4.1 預處理階段

預處理階段包括泄露檢測和模板構建兩個部分，通過對包含不同消息的密文進行解封裝運算并采集相應的能量曲線，利用TVLA檢測泄露并構建泄露點集合，利用NICV對不同消息中間值的漢明重量進行分類，從而針對消息的漢明重量分類建立相應的簡化模板。

算法3 Saber POLmsg2BS

4.1.1 泄露檢測

以第1個消息字節m[0]的泄露為例，并使用Welch t檢驗實現泄露檢測。首先構建兩組各包含l個隨機密文的密文集CT0和CT1，其中CT0的第1個消息字節m[0] = 0，其余消息字節m[i]隨機選擇，CT1的第1個消息字節m[0] = 1，其余消息字節m[i]隨機選擇，i∈[1,31]。這保證了在解碼過程中，對于?j ∈[0,7]，CT0都有m[0, j]=0，而CT1則滿足m[0, j]=1。這使得在8個中間值更新的循環中，始終有1 bit差別，而這個差別可以測量出來。泄露檢測的具體過程為：

(1) 采集能量曲線。針對CT0和CT1，各采集了兩組l條能量曲線，分別表示為T0和T1，并令T=T0∪T1；

(2) 能量曲線歸一化。通過移除測量集中每條曲線ti自身的均值來減少環境因素的影響，即=ti-，其中ti∈Tj, i∈[1, l-1], j∈{0,1}；

(3) 識別測量集中的泄露點。利用式(1)計算兩組測量集的TVLA值，當TVLA絕對值大于閾值Thsel時，代表在該點兩組測量集有明顯差異；

(4) 識別泄露窗口。根據計算出的TVLA值和m[0]的更新存儲順序可以區分每次泄露的時間窗口，記為Wj，其中j∈[0,7]。

4.1.2 模板構建

基于第3節對Single_Bit_Update泄露機理的分析，本文采用漢明重量模型，以HW(m[i, j])為分類標準構建模板，通過恢復m[i, j]的漢明重量來推導出m[i]的值。由于m[i]在最開始被初始化為0，因此對于m[i]的第1個中間值m[i,0]有HW(m[i, 0]) =m[i]0，繼而m[i]的其他比特m[i]j可以由式(3)的關系推導出來

當j = 0時，m[i, j]只可能為0或1，因此HW(m[i, 0])也只有兩個可能值(0或1)。而在之后的每次迭代中，HW(m[i, j])的可能值數目隨迭代次數增加1，在最后一次迭代中(j = 7)，HW(m[i, j])有9個可能值，即HW(m[i, j])∈[0,8]。因此在每次迭代中，HW(m[i, j])有(j + 2)個可能值。

以HW(m[0, j])為例說明模板構建過程，其中j∈[0,7]，具體步驟如下：

(1) 選擇m[0]滿足HW(m[0, j]) = k的密文集進行解封裝操作，其中k∈[0, j+1]。這些密文集除m[0]外的其余字節均為隨機選擇，并采集能量曲線表示為；

(2) 利用NICV區分不同的HW(m[0, j])，并選擇泄露點。利用式(2)對計算NICV，并選擇時間窗口Wj中NICV值大于閾值的點為泄露點P(0,j)；

(3) 根據P(0,j)構建簡化曲線集，計算的平均值記為，該平均值即為每一個分類的簡化模板，因此在第j次迭代時會產生(j + 2)個模板。

4.2 模板匹配階段

首先利用密文循環特性構造特定的密文 ct′，采集 ct′的解封裝能量曲線，并利用這些能量曲線與預處理階段建立的模板進行匹配。這些特定密文雖然是無效的，即無法通過最后的多項式比較，但依舊會在設備上進行解封操作，給能量分析攻擊創造了可能性。

4.2.1 密文循環特性

大多數格基后量子密碼算法都是基于LWE問題及其變體構造的。如Round5算法及其變體是在循環多項式Rq=Zq/(xn+1-1)上運算的，其中(xn+1-1)是可約多項式，因此對于這一類算法而言，多項式a ∈Rq與環上多項式gp(x)=xp相乘滿足：ap[i]=Rotr(a,p)[i]，表示a的第i個系數循環旋轉p個位置，其中Rotr(·)的定義如式(4)所示

而Kyber, Saber等算法是在反循環多項式環Rq=Zq/(xn+1) 上運算的，其中 (xn+1)是不可約多項式，因此a ∈Rq與gp(x)=xp的乘積為ap[i]=Anti_Rotr(a,p)[i]，表示a的第i個系數以反循環的方式旋轉p個位置，其中Anti_Rotr(·)的定義為

通過分析Saber的POLmsg2BS函數(見算法3)可以發現，秘密消息mi只與秘密消息多項式系數a[i]有關。多項式a是在解密階段由密文c和私鑰s運算產生的，而密文c由多項式向量b′和多項式cm級聯而成。由于Saber算法是以2的次冪為模數，因此所有的模約操作均可通過簡單的移位來實現。對m0的解碼操作可具體表示為

其中，F(·)表示算法實現過程中的解碼操作。因此可以構造密文ci=(cmi,) ，其中cmi=Anti_Rotr(cm,i),=Anti_Rotr(b′,i)。由此可以計算出利用反循環特性之后的為

其中，k = (n - i) mod n。h2是一個常數多項式，用于實現運算舍入，每次運算中都會進行模約，從而保證每次運算后的系數均為正整數。因此在密文構建過程中，只需改變i即可完成密文的循環移位。

4.2.2 模板匹配

由于本文是對秘密消息的漢明重量可能值構建模板，因此在模板匹配階段并不需要使用與預處理階段相同的公私鑰對。結合4.2.1節的密文循環特性構造密文，并利用4.1節構建的模板對秘密消息進行恢復，具體過程如下：

(1) 對于j∈[0,7]，對給定密文ct進行解封裝，并采集對應能量曲線tr，根據模板構建過程完成對tr的歸一化，并根據P(0,j)建立簡化曲線；

根據Γk的大小判斷HW(m[0, j])，當Γk最小時，對應的分類即為HW(m[0, j]) = k，并根據式(3)推導出mj；

(3) 利用密文循環特性對給定的有效密文ct進行密文構造，得到不同的構造密文cti(i∈[1,31])。重復步驟(1)和步驟(2)，得到HW(m[i, j])并推導出m[i]。

本文提出的秘密消息恢復方法完整過程如算法4所示，其中Recover(·)利用式(3)判斷消息比特的值。在恢復秘密消息后，即可通過Saber KEM封裝算法恢復共享密鑰。

5 實驗驗證與分析

5.1 實驗平臺

實驗平臺包括PC, LeCroy示波器和測試設備ChipWhisperer工具套件，其包括：一塊搭載了ARM Cortex-M4微控制器的STM32F3目標板、CW308 UFO基板、ChipWhisperer-Lite采集板，如圖3所示。PC發送和接收明密文，ChipWhisperer-Lite控制目標板與PC之間的通信，同時示波器采集目標板運行過程中產生的功耗曲線并保存。實驗采用的是pqm4[19]中針對Cortex-M4微控制器進行優化后的算法，使用ARM工具鏈進行編譯，并選擇最高編譯器優化級別-O3，因為在此優化級別下，編譯后的算法最難通過側信道手段進行破解。STM32F3目標板以7.39 MHz運行，采樣率設置為44.34 MHz/s，并在目標操作前后增加觸發信號來幫助對齊功耗曲線。

圖3 實驗環境設置圖

算法4 針對Saber算法的消息恢復方法

5.2 泄露點檢測

strb指令會泄露有關消息字節中間值的信息，因此消息恢復的第1步是識別與內存中消息字節更新相對應的能量跡特征。圖4是Saber KEM解封裝操作的部分能量跡，其中能量跡的?段為目標函數POLmsg2BS，其放大后的能量跡如圖5所示。

圖4 Saber KEM解封裝過程部分能量跡

圖5 POLmsg2BS函數能量跡

按照4.1.1節的泄露檢測步驟對Saber KEM進行泄露點檢測，計算的TVLA結果如圖6藍色曲線所示?？梢钥吹接嬎愠龅腡VLA曲線有8個明顯的尖峰，根據上述分析可知這8個尖峰是由m[0]j的存儲產生的，在此基礎上識別出各中間值更新時的時間窗口Wj，其中j∈[0,7]。同時對CT0(m[0] = 0)和CT2(m[0] = 2)這兩組密文集進行了相同的泄露檢測，檢測結果如圖6紅色曲線所示?？梢钥吹竭@兩組的TVLA結果有7個明顯的尖峰，與藍色曲線相比缺少W0中的尖峰，這是由于CT0和CT2這兩組密文在解碼的過程中都存在m[0, 0] = 0這個中間過程，因此在第1個循環中并不能找到兩組密文解碼時的顯著差異。

圖6 Saber KEM解碼階段部分TVLA結果

5.3 模板構建與匹配

在識別出每次迭代的時間窗口后，本文選擇了9個密文集表示為CTk，分別滿足HW(m[0, j])=k，其中j∈[0,7], k∈[0,8]。同時這些密文集對應的加密消息mk滿足m0= 0和mk= 2mk-1+1 (k∈[1,8])，在這種方式下可以用較少的能量跡完成模板構建。對于每個密文集分別采集了100條能量跡，共900條能量跡即可完成對恢復m[0]所需模板的構建。按照4.1.2節對HW(m[0, j])進行模板構建，圖7為HW(m[0, j])各分類之間NICV值分布圖，可以看到計算得到的各尖峰均分布在Wj中。選擇NICV值高于0.2的點作為泄露點，并根據4.1.2節構建模板。接著利用密文循環特性構造密文，并根據4.2.2節進行模板匹配，得到最終結果。

圖7 Saber KEM解碼階段部分NICV結果

5.4 實驗結果

在能量分析攻擊中，信噪比(Signal-to-Noise Ratio, SNR)是影響攻擊成功率的重要因素，提高SNR的方法眾多，如使用高精度探頭、模擬/數字濾波器等，本文采用多次測量取平均值的方式作為提高SNR的手段，實驗結果如表1和表2所示。

表1 不同方案實驗結果

表2 不同SNR條件下恢復秘密消息的成功率

LightSaber算法、Saber算法和FireSaber算法通過增加模塊維度k以達到更高的安全級別[14]。New-Hope算法、Kyber算法與Saber算法所需要恢復的秘密消息均為32 Byte，因此考慮將文獻[9]和文獻[10]的中秘密消息恢復結果納入對比分析。

在預處理階段所需能量跡數量上，本文所提方法建模所需的能量跡為900條，與文獻[9]中以字節為單位進行秘密消息恢復所需能量跡(12 800條)相比減少93%，與文獻[11]訓練神經網絡所需的能量跡相比減少90%。雖然文獻[9]中以比特為單位進行秘密消息恢復的方法僅需200條能量跡進行預處理，但由于預處理只需要進行一次，因此其在預處理上所帶來的優勢并不明顯。

在攻擊階段所需能量跡數量上，本文提出的方法每次還原1個消息字節，因此需要32條能量跡，與文獻[9]中以字節進行恢復所需能量跡數量相同，與文獻[9]中以比特進行恢復相比減少87.5%。與文獻[10]相比有所增加，這是因為文獻[10]提出的方案通過將1條攻擊能量跡劃分為32個子片段并分別進行模板匹配。本文提出的方法同樣可以利用1條攻擊能量跡恢復完整秘密消息，只需同時對所有消息字節進行模板構建，但是會帶來模板數量的增加。

在秘密消息恢復成功率上，本文提出的方法有較高的成功率。文獻[10]最終恢復秘密消息的成功率在96%左右，文獻[11]在1 000次實驗中的成功率最終達到96.71%。在未提高SNR的情況下，本方案恢復Saber算法中秘密消息的成功率達到66.71%，而在4次測量取平均值的情況下成功率即可達到95.64%，最終成功率在98.43%左右，如圖8所示。對于恢復錯誤的秘密消息位，只需通過窮舉搜索即可實現秘密消息的完全恢復，其窮舉搜索復雜度為25(256×0.02≈5)。

圖8 Saber KEM消息恢復成功率

本文雖然以Saber算法為例進行實驗驗證，但提出的方法適用于其他格密碼算法及其變體的算法中，如NIST公布的KEM標準化算法CRYSTALKyber算法、中國密碼學會第2輪公鑰競賽入選算法LAC算法、AKCN算法、OKCN算法等。這是因為Single_Bit_Update是難以避免的，且絕大多數格密碼算法均滿足密文循環特性，可以通過循環密文實現特定密文的構造，從而還原秘密消息與共享密鑰。

6 結束語

本文分析格密碼中存在的Single_Bit_Update，提出一種基于密文循環特性的模板攻擊方法，利用NICV方法對解碼階段的狀態中間值的漢明重量可能值構建模板，并使用密文循環特性構造特定密文，以實現秘密消息與共享密鑰的恢復，并在Chip-Whisperer STM32F303平臺上進行了驗證。在對Saber算法的秘密消息恢復需要900條預處理能量跡和32條攻擊能量跡，且在合適的SNR條件下，恢復秘密消息的成功率可以達到98.43%，在預處理數據量和成功率上都有較大優勢。