SM4密碼算法的階梯式相關能量分析

叢 旌，韋永壯*，劉爭紅

（1.廣西密碼學與信息安全重點實驗室（桂林電子科技大學），廣西桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室（桂林電子科技大學），廣西桂林 541004）

（*通信作者電子郵箱walker_wyz@guet.edu.cn）

0 引言

2012 年3 月，國家密碼管理局發布SM4 作為密碼行業的標準。過去十年，專家學者們已經對SM4 密碼算法的實現展開了一系列分析研究，特別是在側信道分析（Side Channel Analysis,SCA)，如差分能量分析［1］、相關能量分析（Correlation Power Analysis,CPA)［2-3］等方面取得了若干重要進展。

側信道分析通過分析密碼算法實現過程中的中間值的信息泄露進行破譯。時間［4］、功耗［5］、電磁波［6-7］等信息均可被用于分析密碼系統。簡單能量分析是側通道分析中最經典的一種，即：不同的操作可能產生不同的功耗。通過觀察采集到的設備加密過程中的能量波形，可以直接得到設備執行的具體操作，并進一步推測設備中的數據。1999 年，差分能量分析由Kocher 等［5，8］首先提出，后來由Messerges 等［9］將其形式化。差分能量分析僅利用1 位功率信息對能量跡進行分類［10］，是側通道分析中使用最廣泛的分析方法。為了改進原有的差分能量分析，Bevan 等［11］、Messerges 等［12］引入了多位差分功耗分析（Differential Power Analysis，DPA）。然后，基于漢明距離泄漏模型的相關能量分析在文獻［13］中提出，該方案通過計算功率樣本與密碼算法中間值漢明距離之間的相關系數確定正確的密鑰。該泄漏模型同樣適用于以S 盒為單位的部分密鑰；故當密鑰空間較大時，可以通過分而治之的方法逐個恢復部分密鑰，從而獲得完整密鑰。近幾年，人工智能（Artificial Intelligence，AI）算法也開始應用于側通道分析當中［14-15］。

注意到，為了追求效率，密碼算法在硬件實現時通常采用并行實現的方案。此時，傳統的基于單個S 盒的泄漏模型不再足夠精確。文獻［16］將傳統相關能量分析中基于單個S 盒的泄漏模型改進為基于多個S 盒的泄漏模型，并通過引入遺傳算法以對抗擴大的搜索空間。文獻［17］在此基礎上進行了改進，設計了基于多種群遺傳算法的相關能量分析，以應對遺傳算法過早收斂的問題。兩者均大幅降低了恢復密鑰所需的能量跡的條數，但都存在離線計算量較大、樣本不足時得不到任何結果等問題。如何以盡可能小的計算量減少噪聲，提高泄漏信息的利用率，成為研究的難點。

本文針對密碼算法并行實現下相關能量分析效率低下的現象分析了原因，并提出了新的方法：階梯式相關能量分析。其核心思想是優化傳統相關能量分析的流程，提高能量跡的利用率，從而提高分析效率，減少能量跡的條數需求。階梯式相關能量分析通過構造一種新的階梯式方案并引入confidence 指標，可以在分析時回避正確性較低的分析結果，以確保每一次分析的結果有盡可能高的正確率。同時，隨著階梯式流程的推進，原本作為干擾項的部分噪聲也將被逐一消除。整個分析過程變得越來越準確，這使得原本容易受噪聲干擾的部分密鑰的恢復過程變得不再容易出錯。將階梯式相關能量分析應用于SM4 密碼算法的分析，本文得到了優于傳統相關能量分析的結果。其計算量與傳統相關能量分析相當，但明顯減少了恢復完整輪密鑰所需求的能量跡條數。

1 預備知識

1.1 SM4密碼算法

SM4 密碼算法與數據加密標準（Data Encryption Standard，DES）［18］及高級加密標準（Advanced Encryption Standard，AES）［19］類似，均為分組密碼。SM4的分組長度和密鑰長度均為128 比特，加密算法與密鑰擴展算法均采用32 輪非線性迭代結構，以32 比特為單位進行加密運算。SM4 密碼算法的加、解密算法的結構相同、使用的輪密鑰相反，其解密輪密鑰是加密輪密鑰的逆序。

SM4密碼算法的整體結構如圖1所示。

圖1 SM4算法結構Fig.1 Structure of SM4 algorithm

明文輸入為：

密文輸出為：

第i輪運算輸入為：

輪密鑰為：

則輪函數定義為：

其中T為非線性變換和線性變換復合而成的合成置換。非線性變換由4個平行的S盒構成，S盒的數據均采用16進制。線性變換公式如下：

其中B為非線性變換得到的字。

最后一輪加密變換時，輸出為：

其中R為反序變換。

1.2 相關能量分析

文獻［20］給出了相關能量分析的具體分析步驟，概括如下：

步驟1 選擇中間值。選擇合適的分析點是進行具體相關能量分析的前提。通過分析具體的密碼算法，找到加解密過程中的一個中間值。這個中間值通常由一個函數f(p，k)生成，其中p是明文的一部分，k是與p相對應的密鑰的一部分。滿足這種條件的中間值可以泄露k。

步驟2 采集能量跡。搭建實驗平臺，進行d次加密或解密，每次采集長度為l的能量跡，構成大小為d×l的矩陣T。同時記錄每次加密或解密時計算中間值f(p，k)所需的p，構成長度為d的向量P=(p1，p2，…，pd)。采集到的能量跡需要進行預處理（如對齊操作等），確保矩陣P中每一列數據對應的功耗均由相同的操作產生。

步驟3 計算假設中間值。對k進行窮舉，記為向量K=(k1，k2，…，kn)，其中n表示k所能取到的所有值的數量。根據所有d次加密或解密對應的p和所有n個密鑰假設，計算v=f(p，k)，構成大小為d×n的矩陣V。

步驟4 將中間值映射為功耗。選擇合適的功耗模型，對V中的每個假設中間值計算對應的假設功耗值，得到由中間值矩陣V映射而成的功耗矩陣H，其大小依然為d×n。

步驟5 求相關系數。對矩陣H中的每一列hi與矩陣T中的每一列tj求相關系數，構成大小為n×l的矩陣R。其中的元素ri，j越大，表示hi與tj的匹配性越好。最大元素所對應的列標即為所求密鑰。相關系數計算公式如下：

2 階梯式相關能量分析

2.1 并行實現下的相關能量分析

在相關能量分析中，采集到的能量分為兩部分：信息與噪聲。信息，即分析對象對應的S 盒在運行時產生的能量；噪聲，包括密碼設備運行時其他模塊產生的能量與白噪聲。特別的，在密碼算法并行實現的條件下，其他S 盒的能量信息也會包含在采集到的能量中。這些能量將被視為該次分析中的噪聲，對分析結果產生干擾。

從圖2中可以明確得知，單次分析的密鑰比特數越多，噪聲越小，但相應的搜索空間也會越大；反之，搜索空間減小，但受噪聲的影響更大。如何權衡兩者之間的關系，或者找到新的方法在同一數量級的計算量上提高分析的效率是研究的關鍵。傳統相關能量分析采用分而治之的思想，每一次分析恢復一個S 盒對應的部分密鑰，多次分析恢復完整輪密鑰。但實際上在每一次部分密鑰的恢復后，一些本可以被利用的信息被忽略掉了。

圖2 采集能量的構成Fig.2 Composition of collected power

2.2 階梯式方案

相關能量分析的傳統方案通過分而治之的思想，利用多次分析分別恢復每個S 盒對應的部分密鑰，如圖3 所示：第一次分析第一個S盒對應的部分密鑰，之后每次分析下一個S盒對應的部分密鑰，直到分析完所有S 盒對應的部分密鑰，構成完整輪密鑰。圖3中m表示完整輪密鑰包含的數據字的個數。每一次分析的過程是相互獨立的，即一次分析的結果不會對其他分析造成任何影響。當噪聲較大或能量跡條數過少時，分析的成功率降低。而任意一次分析的失敗都將導致完整密鑰恢復的失敗，這是相關能量分析失敗最常見的原因。

圖3 傳統相關能量分析方案Fig.3 Classic CPA scheme

然而，成功完成其中任意一次分析后，所獲的部分密鑰對下一次分析而言并不是沒有任何意義的。將一次分析的結果納入下一次的分析目標，將在維持搜索空間不變的前提下，有效減少噪聲、增加信息。如：第一次分析以第一個字節的密鑰為分析目標，得到分析結果：k1=01010101。第二次分析，將第一字節與第二字節同時作為分析目標。其中第一字節固定為k1=01010101 不變，第二字節k2從00000000 遍歷至11111111。每次分析的密鑰字節數越來越長，由圖2 可知噪聲將會減少。但是因為每次分析只添加一個字節的新密鑰，其他密鑰都是已知的、固定不變的，所以搜索空間依然是28=256。具體方案為：第一次分析第一個S盒對應的8比特密鑰，之后每次分析都將下一個S 盒對應的8 比特密鑰納入攻擊范圍。在保持前一次分析結果不變的前提下，遍歷下一個S 盒對應的8比特密鑰，直到最后一次分析，獲得完整的輪密鑰。

階梯式方案的優勢在于：隨著階梯式流程的推進，分析的密鑰字節數越來越長，噪聲越來越少。這意味著后分析的部分密鑰將有越來越高的正確率。但相關能量分析的成功，即完整密鑰的恢復，取決于每一次對部分密鑰分析的成功與否，而非單次分析成功率的最大值。前幾次分析的正確性成了階梯式方案的短板。單純的階梯式方案并不能對前幾次分析的成功率產生有效影響，而后幾次分析成功率的提升對完整密鑰恢復的成功率提升非常有限，所以需要進一步引入文獻［21］中提及的confidence指標（下文中簡稱c指標）：

其中：r1為一次相關能量分析中獲得的最大的相關系數；r2為同一次相關能量分析中獲得的第二大的相關系數。c 指標為兩者之差，它可以有效地衡量這一次相關能量分析結果的正確性。指標數值越大，結果為正確的可能性越大，反之則越有可能是受噪聲干擾所得的錯誤結果。

具體分析流程如圖4。描述如下：第一次分析，依次對4個S 盒對應的部分密鑰進行分析，并計算每次分析的c 指標。保留c 指標最高的一次分析所得的密鑰。第二次分析，將已恢復的密鑰納入分析目標，繼續分析其余3個S盒對應的部分密鑰，并計算每次分析的c 指標。如：第一次分析已恢復k3，則依次分析k1|k3，k2|k3，k4|k3，其中k3固定為已恢復的值，k1，k2，k4依次遍歷256種候選值。保留c指標最高的一次分析所得的密鑰。以此類推，直到第四次分析結束，恢復出完整輪密鑰。為了便于理解具體流程，表1 給出了階梯式相關能量分析實例中每一次分析的具體參數。

圖4 階梯式相關能量分析方案Fig.4 Stepwise CPA scheme

表1 階梯式相關能量分析實例Tab.1 Example of stepwise CPA

c 指標的引入在一定程度上解決了前幾次分析正確率得不到保證的問題。可以說，依據c 指標篩選分析結果是在資源已定的情況下被動地提升成分析的功率，而階梯式方案的推進則是主動消除噪聲的影響，提升成功率。兩者的結合有效提高了相關能量分析的成功率，尤其是在噪聲較大、能量跡條數較少的情況下。

傳統相關能量分析的基本思想是“分而治之”，但在分治的過程中，任何一次分析的錯誤都將導致最終完整輪密鑰恢復的失敗。本文提出的階梯式相關能量分析，其基本思想是“步步為營”。相較于傳統相關能量分析，只要有一次分析成功，就可以繼續分析下去。而且隨著階梯式流程的推進，一些本可能發生錯誤的分析也將在接下來的分析中因噪聲的減少而被進一步修正。

2.3 階梯式相關能量分析的構造

階梯式相關能量分析包含以下主要步驟：確定分析目標、相關能量分析、篩選分析結果、狀態更新。

相關數據定義如下：

1）m表示完整輪密鑰包含的數據字的個數（以SM4 密碼算法為例，m=4）；

2）數組key存儲所有已恢復的部分密鑰；

3）數組state存儲密鑰恢復的狀態（具體是一個長度為m的布爾數組，true表示當前下標對應的S盒對應的部分密鑰已被恢復，反之則為false）；

4）數組target存儲本次分析的目標（具體是一個長度為m的布爾數組，true表示當前下標對應的S盒對應的部分密鑰被包含在本次分析的目標之內，反之則為false）；

5）數組data存儲相關能量分析的結果和相應的精確系數；

6）數組result存儲本次分析保留的恢復的部分密鑰及其在完整輪密鑰中的位置。

相關函數定義及其基本功能如下：

1）函數target（）根據密鑰恢復的狀態返回本次分析的目標。若還沒有任何部分密鑰被恢復，則分析目標為分別為所有部分密鑰；否則分析目標為所有未被恢復的部分密鑰分別與已恢復的密鑰合并。

2）函數cpa（）根據分析目標、明文、S 盒函數及能量跡返回相關能量分析的結果和相應的c指標。

3）函數select（）根據相關能量分析的結果和相應的c 指標返回本次分析保留的恢復的部分密鑰及其在完整密鑰中的位置。

4）函數update（）根據本次分析結果更新數組key和數組state，以存儲本輪恢復的部分密鑰和當前密鑰恢復的情況。

上述函數均為作者在C語言環境下編寫而得。下面給出階梯式相關能量分析的偽代碼：

算法1 階梯式相關能量分析。

輸入：能量跡W、明文P、S盒函數S；

輸出：輪密鑰。

3 實驗與結果分析

3.1 模擬實驗

在模擬實驗中，在C 語言仿真平臺上對SM4 算法的S 盒操作進行了模擬，并分別添加兩種不同程度的噪聲，其標準差分別為σ=3.0 和σ=5.0。在這兩組數據上分別執行了傳統相關能量分析和本文提出的階梯式相關能量分析。實驗按照不同的給定能量跡條數分組進行，從100 到1 000，間隔為10，每組實驗取1 000 次實驗結果的平均值。圖5 給出了這兩種方案的成功率。表2總結了在成功率達到50%和90%的前提下，兩種方案對能量跡條數的需求和相應的計算量。由于計算量主要取決于相關系數的計算次數，所以這里忽略了排序操作的計算量，只記錄恢復完整輪密鑰所需計算相關系數的次數。

圖5 不同噪聲下能量跡條數與成功率的關系Fig.5 Relationship between the number of power traces and success rate under different noises

表2 階梯式相關能量分析與傳統相關能量分析對比Tab.2 Comparison of stepwise CPA and classic CPA

實驗結果表明，在能量跡條數相同的前提下，本文提出的階梯式相關能量分析的成功率明顯優于傳統相關能量分析。當σ=3.0時，階梯式相關能量分析只需要420 條能量跡就可以達到90%的成功率，而傳統相關能量分析需要560條，減少了25%的能量跡條數需求。當σ=5.0時，階梯式相關能量分析只需要630 條能量跡就可以達到90%的成功率，而傳統相關能量分析需要760 條，減少了17%的能量跡條數需求。值得一提的是，階梯式相關能量分析的計算量為2 560 次，是傳統相關能量分析的2.5 倍。相較于計算量達到幾萬甚至幾十萬的基于遺傳算法的相關能量分析（Correlation Power Analysis based on Simple Genetic Algorithm，SGA-CPA）［16］和基于多種群遺傳算法的相關能量分析（Correlation Power Analysis based on genetic algorithm and Multiple Sieve method，MS-CPA）［17］，階梯式相關能量分析的計算量非常小，可以認為是與傳統相關能量分析的計算量處于同一數量級上。

3.2 FPGA上的實驗

在實際實驗中，使用SAKURA-G 自主搭建實驗平臺。SAKURA-G是一款專門為硬件安全方面的研究和開發而設計的FPGA 板。它由兩塊Spartan-6 FPGA 集成而來：主FPGA 用于密碼算法的實現；控制FPGA 用于相應控制邏輯的實現。超低噪聲的設計使能量分析變得更加容易。

在具體的相關能量分析實驗中，把SM4 硬件電路下載到SAKURA-G 開發板上，然后將其觸發輸出和信號輸出分別與示波器相連，并將主控制口通過USB 連接線與電腦相連。對固定的密鑰和已知的隨機明文執行SM4 密碼算法，并通過使用LeCroy WaveRunner 610Zi 示波器與旁路分析軟件SCAnalyzer 完成5 000 條能量跡的采集。實際采集到的每一條能量跡為一個長度為30 000 的數組，記錄了電壓隨時間變化的曲線。為了降低噪聲和減少計算量，需要對能量跡進行重采樣，即數組中的每10個點取平均數，記為一個點。

首先，對這5 000 條能量跡進行傳統相關能量分析，計算單字節部分密鑰的所有可能值對應的中間值與能量跡的相關系數。圖6 給出了實驗結果：虛線表示正確密鑰，不同灰度的實線表示其他錯誤密鑰。用于計算相關系數的能量跡條數為10～5 000，間隔為10。當能量跡條數大于3 430 條時，正確密鑰對應的相關系數始終大于錯誤密鑰對應的相關系數，這意味著本次實驗中使用傳統相關能量分析恢復密鑰至少需要3 430條能量跡。

圖6 相關系數與能量跡條數的關系（傳統相關能量分析）Fig.6 Relationship between the number of power traces and correlation coefficient（classic CPA）

其次，對同樣的5 000條能量跡計算其與完整密鑰對應的中間值的相關系數，旨在找出同等實驗環境下通過相關能量分析恢復完整輪密鑰所需能量跡的最小數量。由于完整輪密鑰長度為32 比特，窮盡所有可能的計算量較大且沒有必要，所以只選擇部分最具“競爭力”的錯誤密鑰與正確密鑰進行對比。文獻［17］已給出相關結論，即候選密鑰中正確的字節數越多，其對應的相關系數越大。故本次實驗中只選擇28×4個只含有3 個正確字節的候選密鑰與正確密鑰做對比。經過實驗結果的分析與對比發現，在本實驗中，當第2 個S 盒對應的部分密鑰錯誤、其他部分密鑰正確時，錯誤密鑰對應的相關系數與正確密鑰對應的相關系數最接近。所以為了精簡圖表數據，圖7 將只給出這部分實驗結果的數據：其中虛線表示正確密鑰，不同灰度的實線表示其他錯誤密鑰。用于計算相關系數的能量跡條數為10～5 000，間隔為10。當能量跡條數大于3 100條時，正確密鑰對應的相關系數始終大于錯誤密鑰對應的相關系數，這意味著本次實驗中以相關能量分析為基本思想恢復完整密鑰最少需要3 100 條能量跡。當然這是建立在將相關能量分析的搜索空間擴大到232的前提下的。這是通過巨大計算量換取分析精度的一種方式。

最后，同樣是這5 000 條能量跡，對其進行階梯式相關能量分析，記錄每一次分析的結果對應的相關系數，并與正確密鑰對應的相關系數進行對比。圖8 給出了實驗結果：其中虛線表示正確密鑰，4種灰度的實線由淺至深分別表示4次分析的結果。用于計算相關系數的能量跡條數為10～5 000，間隔為10。當能量跡條數達到2 370條時，最后一次分析的結果對應的相關系數已基本與正確密鑰對應的相關系數重合。當能量跡條數大于3 100條時，兩者完全重合。這說明階梯式相關能量分析恢復正確密鑰的能力已經非常接近將搜索空間擴展到最大時的極限。

圖7 相關系數與能量跡條數的關系（完整輪密鑰）Fig.7 Relationship between the number of power traces and the correlation coefficient（whole round key）

圖8 相關系數與能量跡條數的關系（階梯式相關能量分析）Fig.8 Relationship between the number of power traces and correlation coefficient（stepwise CPA）

本次實驗中，使用傳統相關能量分析恢復密鑰至少需要3 430 條能量跡，而將搜索空間擴大到232時，對能量跡條數需求的極限是3 100 條。階梯式相關能量分析的結果在能量跡條數達到2 370 條時基本與正確密鑰吻合，在達到3 100 條時完全吻合。不同實驗中的數據存在細微的差別，但數據間的關系和比例大致不變。由此可以看出階梯式相關能量分析相對于傳統相關能量分析有明顯的優越性。

4 結語

本文討論了相關能量分析在并行實現下分析效率低下的原因，提出了階梯式方案，并通過引入confidence 指標，基于SM4 密碼算法的結構，構造了階梯式相關能量分析。實驗結果表明階梯式相關能量分析以較小的計算量有效降低了傳統相關能量分析對能量跡條數的需求，是一種精確、快捷的分析方案。接下來進一步的研究可以考慮對能量跡進行分析和篩選，以減少計算量、提高分析效率。