白盒SM4的分析與改進

張躍宇 徐 東 陳 杰

①(西安電子科技大學網絡與信息安全學院 西安 710071)

②(桂林電子科技大學廣西密碼學與信息安全重點實驗室 桂林 541004)

③(西安電子科技大學ISN國家重點實驗室 西安 710071)

1 引言

傳統(tǒng)的密碼安全性分析環(huán)境被稱為黑盒攻擊環(huán)境，攻擊者只能訪問密碼系統(tǒng)的輸入與輸出，但隨著密碼系統(tǒng)部署環(huán)境的多樣化，該分析模型已經不能夠反映實際應用中攻擊者的能力。2002年，Chow等人[1]提出了白盒攻擊環(huán)境的概念，該攻擊環(huán)境中的攻擊者對算法運行環(huán)境具備完全的控制權，并且完全掌握算法的設計細節(jié)。白盒攻擊環(huán)境中攻擊者的能力包括但不限于：動態(tài)觀測算法程序運行過程、修改算法程序運行過程中的中間值、對算法程序進行調試分析等。

為了保證在白盒攻擊環(huán)境下運行的密碼算法的密鑰安全性，需要對密碼算法進行白盒化處理，處理后的算法稱為密碼算法的白盒實現。密碼算法的白盒化方法由Chow等人[1]首次提出，并在其白盒高級加密標準(Advanced Encryption Standard，AES)、白盒數據加密標準(Data Encryption Standard， DES)[2]方案中應用，后續(xù)提出的大部分密碼算法的白盒實現方案都采用了該白盒化方法。對于白盒實現的安全性分析工作，主要分為兩類：一類以Billet等人[3]提出的 BGE分析，Michiels等人[4]提出的 MGH分析為代表。這一類的分析充分地利用了攻擊者在白盒攻擊環(huán)境中所掌握的能力，通過對算法細節(jié)的分析找出算法的安全性缺陷，選擇特定的查找表并采用仿射等價、線性等價等代數手段剝離算法內部的混淆手段，對混淆剝離后的查找表進行分析提取密鑰。這一類的分析方法要求攻擊者對白盒實現的設計細節(jié)完全掌握，并且需要利用大量的代數方法進行分析，整體的分析難度較高，在實際應用環(huán)境中較難進行部署。另一類白盒實現的安全性分析工作以Bos等人[5]于2016年提出的差分計算分析(Differential Computational Analysis， DCA)為代表。DCA是差分功耗分析[6]的軟件版本，DCA不需要攻擊者掌握算法的設計細節(jié)，只需要采集算法程序在運行過程的中間狀態(tài)，通過相應的統(tǒng)計分析方法提取密鑰。相較于BGE，GH等分析手段，DCA分析只需要掌握白盒實現的底層算法，能夠監(jiān)測白盒實現程序的運行過程即可進行分析，極大地降低了分析的部署難度。

DCA的提出將白盒實現的安全性分析工作自動化、簡單化。由于其便捷性與高效性，DCA自提出之后便獲得了廣泛關注。Bos等人[5]只是提出了DCA，并利用該方法對幾個白盒AES實現進行了成功分析，并未在理論層面對DCA進行解釋說明，文獻[7，8]對DCA進行了詳細的解釋與介紹，并分別給出了該分析能夠成功進行的理論原因。文獻[9]又提出了改進DCA分析效率的方法。2019年，Rivain等人[10]討論了內部編碼對于DCA的影響，并提出了一種與差分計算分析類似的分析手段。同年，Bogdanov等人[11]又提出了高階的差分計算分析方法，用以分析包含軟件補償對策的白盒實現。

在差分計算分析的理論不斷改進與發(fā)展的同時，研究人員也在尋找針對該分析的軟件補償措施，用以減輕甚至消除差分計算分析對白盒實現安全性的影響。Biryukov等人[7]中提出了名為掩蔽(masking)的補償手段，掩蔽可用于計算過程中的中間值也可用于算法的結構。Lee等人[12]于2017年提出了基于Chow白盒AES改進的白盒AES實現方案，該方案在查找表輸出中添加隨機掩碼用以抵抗差分計算分析。同年，Banik等人[13]提出了控制流混淆、查找表位置隨機化、虛擬操作等軟件補償措施以對抗DCA。2020年，Lee等人[14]再次提出了一種改進型的白盒實現方案，該方案主要針對高階差分計算分析而改進。在不斷地對抗與改進中，差分計算分析已成為檢驗白盒實現方案安全性的重要工具。

SM4算法(原SMS4算法)是我國商用密碼標準算法[15]。肖-來白盒SM4是SM4算法的第1個白盒實現方案[16]，該方案采用了Chow等人的白盒化思想。2013年，肖-來白盒SM4方案被林婷婷等人攻破[17]。2015年，Shi等人[18]提出了一種新的白盒SM4方案，該方案將SM4步驟結合到查找表中，并采用隨機混淆對查找表進行保護。同年，Bai等人[19]提出了白-武白盒SM4實現方案，該方案在肖-來白盒SM4的基礎上將線性編碼復雜化，希望以此提高方案安全性。2018年，潘文倫等人[20]對肖-來白盒SM4與白-武白盒SM4方案進行了成功分析，分別給出了兩個方案的密鑰空間大小，同時證明了復雜化的線性編碼對方案安全性的貢獻是有限的。2020年，姚思等人[21]結合混淆密鑰與查找表技術提出了一種內部狀態(tài)擴充的白盒SM4實現方案 (White-box implementation of SM4 algorithm with Internal State Expansion， WSISE)算法，該方案顯著提高了攻擊者提取密鑰的復雜度。

本文在差分計算分析的基礎上提出了中間值平均差分分析(Intermediate-Values Mean Difference Analysis， IVMDA)，本分析以白盒SM4實現加密過程中的所有查表結果為輸入，分析以腳本程序的形式部署，分析過程自動化進行。攻擊者只需控制白盒實現的運行環(huán)境即可進行分析。利用IVMDA成功對肖-來白盒SM4進行了密鑰提取工作。為了保證白盒SM4方案的安全性，在肖-來白盒SM4方案中增加軟件對策以抵抗IVMDA。經實驗驗證，改進后的白盒SM4方案可以有效抵抗IVMDA。

2 白盒SM4方案

肖-來白盒SM4實現方案在保持標準SM4算法整體結構不變的同時，將每一輪中密鑰相關的步驟用查找表的形式表示。采用線性編碼對查找表的輸入輸出進行混淆，并且上一個變換的輸出部分引入的混淆會在下一個變換的輸入部分被抵消，以保證白盒SM4方案與標準SM4的輸入輸出一致。方案中的線性編碼均采用仿射的形式。肖-來白盒SM4方案的一輪的計算過程如圖1所示。肖-來白盒SM4方案的一輪加密過程包含5個復合仿射變換，4個8～32 bit的查找表，6個異或操作。

圖1 肖-來白盒SM4的一輪計算過程

3 白盒SM4的中間值平均差分分析

差分計算分析是差分功耗分析在白盒攻擊環(huán)境下的軟件版本，該分析以算法程序運行過程中的軟件執(zhí)行軌跡(software execution trace)為分析對象，而根據軟件執(zhí)行軌跡的具體種類以及進行統(tǒng)計分析時所采用的方法的不同，差分計算分析也可被分為不同種類，差分數據分析[22](Differential Data Analysis， DDA)便是其中一種。本文在差分計算分析的基礎上提出了一種針對白盒SM4方案的分析方法，稱為中間值平均差分分析。

3.1 中間值平均差分分析

為了提高分析效率，選擇白盒實現程序的所有查表結果為分析對象，采用均值差分作為密鑰與軟件執(zhí)行軌跡的相關性指標，由于白盒實現中查找表部分采用了線性編碼對結果進行混淆，因此在分析過程中添加線性組合步驟來抵消編碼影響，分析步驟與DCA基本一致。將該分析方式命名為中間值平均差分分析(IVMDA)。IVMDA的目標是能夠在實際的應用環(huán)境下對白盒SM4實現進行密鑰提取，因此攻擊者的能力需要符合實際的應用場景?；谝陨峡紤]，攻擊者被定義為一個具有惡意目的的合法用戶，該用戶以提取嵌入白盒實現程序中的密鑰為目標，掌握白盒實現程序及其部署環(huán)境，同時具備一定的逆向工程能力、代碼調試能力等黑客技能。攻擊者不掌握白盒實現算法的設計細節(jié)，只了解白盒實現算法的底層算法。對于包含外部編碼的白盒實現程序，攻擊者不掌握外部編碼，但可以以合法用戶身份向外部編碼發(fā)起問詢，并獲得編碼后的明文。

IVMDA整體分為兩部分，數據采集部分與分析部分。

改變攻擊點，對第1輪中剩余3個包含輪密鑰加的S盒運算執(zhí)行以上分析步驟，即可提取出一輪的輪密鑰。整個的分析流程可以自動化進行。后續(xù)輪次的密鑰值的計算可在已提取密鑰值的參與下采用IVMDA對每一輪中包含輪密鑰信息的S盒進行分析而得到。

綜上，IVMDA采用查表結果作為分析對象，相較于DCA省略了對軟件執(zhí)行蹤跡進行序列化處理的步驟，分析過程更加精簡，并且分析對象的采集方式會更多樣，所需采集的數據量也更小。采用均值差分作為密鑰與軟件執(zhí)行蹤跡之間的相關性指標，相較于DDA所采用的皮爾遜系數，分析步驟的復雜度更低。采用線性組合的方式抵消白盒方案中的線性編碼混淆作用，保證了分析的正確性與改進后的DCA相當。

3.2 對肖-來白盒SM4的中間值平均差分分析實驗

圖2 肖-來白盒SM4的中間值平均差分分析結果

(1) 對當前的可能密鑰計算60次中間函數，包含60次S盒運算，3×60=180次8 bit向量的異或運算；

(2) 計算60個中間函數結果的所有線性組合值，即執(zhí)行60×255次8 bit向量乘法，每一個中間函數結果對應255個線性組合值，記作B；

(3) 根據B中相同位置上的元素值，將B對應的中間函數結果所對應的中間數據流進行分組，共進行255×60次分組；

(4) 每一次分組之后，計算不同分組之間的均值差分，該過程中執(zhí)行包含128個元素的集合的異或255×58次，除法運算255×2×128次，128個元素的集合對應元素差分運算255次；

(5) 進行完(4)中的運算后，得到255個包含128個元素的差分值集合，選擇其中最大差分值作為ΔKey。

執(zhí)行以上5部分運算256次即可計算出所有可能密鑰的ΔKey值，取最大ΔKey對應的假設密鑰值作為最佳密鑰猜測。第1輪中4個8 bit密鑰的計算均采取相同的辦法。

綜合實驗結果來看，中間值平均差分分析能夠成功地對肖-來白盒SM4進行密鑰提取工作，只需掌握白盒實現程序及其部署環(huán)境，分析過程被封裝為一個腳本程序，在實際的應用環(huán)境中很容易進行部署。相較于傳統(tǒng)分析方法中所常用的求解矩陣方程、差分分析法等計算方法，IVMDA在分析時所采用的計算均為常見的簡單運算如異或、除法、差分等，計算的復雜度大大降低。綜上，IVMDA是一種非常高效的白盒SM4方案分析方法，其對于白盒SM4安全性具備實際性的威脅。

4 非線性混淆的白盒SM4方案

為了抵抗IVMDA，在肖-來白盒SM4實現方案中添加軟件對策，利用非線性編碼對查找表的輸出進行混淆，消除查表結果與密鑰之間的相關性，本節(jié)提出非線性混淆的白盒SM4實現(White-Box SM4 with Nonlinear Confusion， WBSM4-NC)方案。

4.1 非線性混淆的白盒SM4實現方案

IVMDA能夠成功提取密鑰的原因在于查找表的輸出值與密鑰之間存在相關性，并且線性編碼的混淆作用可以通過計算線性組合的方式進行抵消。本節(jié)所提非線性混淆的白盒SM4實現方案在查找表的輸出處添加非線性編碼，對查找表結果進行混淆。添加混淆之后的查找表結構如圖3所示。

圖3中xi，j表示第i輪中第j個查找表的輸入，Ei，0消 除xi，j中的編碼。S*為包含輪密鑰加操作的S盒。Ri，j為8～32 bit的仿射編碼，是原方案中矩陣L與仿射變換Qi的復合編碼Ri的一部分，當j=0，1， 2時Ri，j，以矩陣形式執(zhí)行編碼操作，當j=3時Ri，j以仿射變換形式執(zhí)行編碼操作。out為添加的8 bit非線性編碼，對查找表輸出再次進行混淆。圖3所示的查找表結構是在肖-來白盒SM4方案的查找表結構的輸出部分添加了4個級聯的8 bit非線性編碼，對Ri，j表的32 bit輸出進行混淆。經過混淆的32 bit結果作為該表的輸出，這樣使得輸入xi，j與經過混淆的32 bit結果對應起來，形成了新的帶有非線性混淆的8～32 bit的查找表。

圖3 包含混淆操作的查找表

在使用8 bit非線性編碼對查找表的輸出進行混淆之后，不能直接使用查表結果進行異或。異或過程需要借助異或表完成，異或表結構如圖4(a)所示。異或表以兩個字節(jié)為輸入，表中輸入編碼in消去數據中的非線性編碼。in=out–1，異或后的數據需要再進行編碼保護，確保再次與其他數據進行異或時的正確性。肖-來白盒實現中4個查找表結果的3次異或操作需要用12個異或表來替代，最終結果為一個32 bit的經過4個級聯的8 bit非線性編碼的結果，即該結果為圖1中的Y 進行4個級聯的8 bit非線性編碼操作，記作Y′。

圖4 異或表與編碼過程

4.2 非線性混淆的白盒SM4實現方案的分析與對比

圖5 查找表與部分仿射編碼的組合

在應用潘文倫等人的分析方法對WBSM4-NC的安全性進行分析的過程中，對Qi矩陣部分的恢復也是基于以上原因無法進行，所以同理也可以認為WBSM4-NC方案對于潘文倫等人的分析方法是安全的。

通過以上的分析，WBSM4-NC在已有的針對白盒SM4實現的安全性分析中可以保證安全性，接下來驗證該方案在中間值平均差分分析下的安全性。采用與3.2節(jié)相同的程序執(zhí)行環(huán)境進行中間值平均差分分析實驗，實驗結果如圖6所示。

分析程序的輸出為圖6的雜亂折線圖，說明本文采用的軟件對策可成功抵抗IVMDA。這是由于采用了8 bit的非線性編碼對查找表結果進行混淆之后，查找表結果與原密碼算法中包含輪密鑰加的S盒運算的結果之間的關系相當于執(zhí)行了一次置換操作，同時也可以采用一些被驗證過的S盒來充當該8 bit非線性編碼，由于S盒的性質，混淆后的查找表結果與原查找表結果之間的相關性很難采用相應手段進行恢復，從而在IVMDA中保證了方案的安全性。表1對幾種白盒SM4實現方案的安全性進行對比。

圖6 WBSM4-NC方案的中間值平均差分分析結果

表1 白盒實現方案的安全性對比

從表1的安全性對比可以看出，在安全性方面WBSM4-NC方案相比于其他的白盒SM4方案具備一定的優(yōu)勢。該方案可以抵抗林婷婷等人以及潘文倫等人的分析，在實際的應用環(huán)境中能夠保證密鑰的安全性。下面對WBSM4方案的內存效率進行分析與對比。

為了保證密鑰安全性，抵抗IVMDA， WBSM4-NC方案在內存性能上做出了妥協，犧牲內存空間以換取安全性。在每一輪的加密過程中，總計3種不同類型的查找表：

(1)嵌入輪密鑰的8～32 bit查找表，每張表占用空間28×32 bit=1 kB；

(2)16～8 bit的異或表，每張表占用空間216×8 bit=64 kB；

(3)8～32 bit的 TDi，j表，每張表占用空間28×32 bit=1 kB。

每一輪包含4張嵌入輪密鑰的8～32 bit查找表、12張異或表、4張T Di，j表，因此整個的加密過程中查找表占用的空間為32×4×1 kB+32×12×64 kB+32×4×1 kB=24832 kB。相比于肖-來白盒SM4方案中總大小為128 kB的查找表，WBSM4-NC方案的空間耗費是巨大的。但是需要注意，肖-來白盒SM4方案本身并不包含非線性混淆部件而只有線性混淆部件，因此該方案的空間耗費小于包含非線性部件的方案。表2對幾種白盒方案的效率做了簡單比較。

表2的Luo-Lai-You白盒AES方案[26]的空間大小與WBSM4-NC方案空間大小處在相同數量級，這是由于這兩個方案中均包含非線性混淆，原有的異或操作需要用異或表實現，因此需要占用大量內存空間。同時，Luo-Lai-You白盒AES方案中使用的非線性部件為4 bit，根據文獻[8]的研究結論，4 bit的非線性編碼并不能混淆軟件執(zhí)行軌跡(該文獻中選擇內存讀取記錄為分析對象)與密鑰之間的相關性。

表2 白盒實現方案的內存效率對比

為了驗證4 bit的非線性部件是否能夠混淆查找表結果與密鑰之間的相關性，采用了IVMDA對使用4 bit非線性部件的WBSM4-NC方案進行分析，該分析的運行環(huán)境與3.2節(jié)中IVMDA的運行環(huán)境相同，圖7是本次分析的輸出結果。相對于8 bit的WBSM4-NC方案，4 bit版本方案在構造方法上保持一致，只是由于編碼長度的改變，相應的查找表大小與異或次數發(fā)生了變化，具體的方案不再展開描述。根據分析結果顯示，第1輪中所有部分輪密鑰均被揭示。由此可以證明：4 bit長度的非線性編碼并不能混淆查找表結果與密鑰的相關性，因此使用8 bit的非線性部件是為了保證安全性而作出的必要妥協。

圖7 4bit版本的WBSM4-NC方案的中間值平均差分分析結果

白-武白盒SM4方案占用空間較大的原因在于該方案為了提高安全性，在設計編碼時使得編碼復雜化，查找表數量較多。綜上可以看出，白盒方案在確保安全性的同時就必須舍棄一部分內存效率，WBSM4-NC方案的內存開銷仍在合理范圍之內。WBSM4-NC方案對查找表的輸出進行非線性混淆，將部分復合仿射編碼以查找表的形式存儲，提高了白盒SM4方案的安全性。并且與其他白盒SM4實現方案相比其內存效率也保持在合理范圍之內。該方案適合在實際應用環(huán)境中部署，以提高密碼系統(tǒng)的安全性。

5 結束語

本文針對白盒SM4方案，提出了中間值平均差分分析IVMDA，該分析方法是差分能量分析針對白盒SM4方案的軟件改進版本。首次提出白盒SM4方案的自動化分析方法，降低了對白盒SM4方案進行安全性分析的難度。中間值平均差分分析使白盒密碼分析工作不再專屬于密碼學者，掌握部分計算機技能的黑客也可以對白盒密碼系統(tǒng)進行分析，這對于白盒密碼系統(tǒng)的安全性是一種非常實際的威脅。同時，考慮到IVMDA針對查找表的輸出結果進行分析，利用計算線性組合的方式抵消線性編碼對查找表結果與密鑰相關性的混淆，該分析主要針對的是采用線性編碼保護查找表的白盒方案。后續(xù)的研究工作可以將中間值差分分析拓展到其他采用線性編碼保護查找表的白盒實現方案上，形成一個普適性的分析框架，以更好地評價白盒方案在實際應用環(huán)境中的安全性。本文提出了利用8 bit非線性編碼對查找表輸出進行混淆的軟件對策來抵抗IVMDA，提出非線性混淆的白盒SM4實現方案WBSM4-NC。通過實驗驗證，該軟件對策可以有效抵抗中間值平均差分分析。但為了保證安全性，必須增加白盒實現方案的內存占用，這同時也相應地限制了白盒實現方案的應用范圍。因此，在后續(xù)的研究中需要進一步地探究如何在保證安全性的前提下，降低白盒實現方案的內存開銷，這對于白盒密碼的實際應用具有重要意義。