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

張躍宇，徐 東，蔡志強(qiáng)，陳 杰

(1.西安電子科技大學(xué) 網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071；2.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；3.中國(guó)人民解放軍66061部隊(duì)，山西 陽(yáng)泉 100141；4.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

2002年，CHOW等[1]首次提出白盒安全模型，該模型下的攻擊者對(duì)算法運(yùn)行環(huán)境具備完全的控制權(quán)。算法細(xì)節(jié)以及運(yùn)行過(guò)程完全暴露在攻擊者的視野中，攻擊者的能力包括動(dòng)態(tài)觀測(cè)算法程序運(yùn)行過(guò)程、修改算法運(yùn)行過(guò)程的中間值、對(duì)算法程序進(jìn)行調(diào)試分析等。為了保證在白盒安全模型下密碼算法的密鑰安全性，需要對(duì)密碼算法進(jìn)行白盒化處理，處理后的算法稱為白盒實(shí)現(xiàn)。一般的白盒化方法是用嵌入密鑰的查找表網(wǎng)絡(luò)來(lái)代替原計(jì)算過(guò)程，采用混淆手段對(duì)查找表進(jìn)行保護(hù)，同時(shí)使用外部編碼對(duì)整個(gè)實(shí)現(xiàn)進(jìn)行保護(hù)。白盒化方法由CHOW等在其白盒AES[1]、白盒DES[2]方案中首次提出并使用，后續(xù)提出的大多數(shù)白盒實(shí)現(xiàn)也是基于該方法實(shí)現(xiàn)的。

白盒安全性模型中密碼算法的運(yùn)行過(guò)程與設(shè)計(jì)細(xì)節(jié)完全被攻擊者所掌握，因此攻擊者可以依據(jù)算法設(shè)計(jì)的缺陷，采用仿射等價(jià)、線性等價(jià)等手段對(duì)算法內(nèi)部的混淆進(jìn)行剝離，對(duì)混淆剝離后的查找表進(jìn)行分析，進(jìn)而提取出密鑰信息。典型攻擊方法的代表有BGE(olivier Billet-henri Gilbert-charaf Ech-chatbi)攻擊[3]、MGH (MICHIELS w-GORISSEN p-HOLLMANN h d)攻擊[4]等分析手段。

2016年，BOS等[5]將差分功耗分析應(yīng)用于白盒實(shí)現(xiàn)的軟件分析中，首次提出差分計(jì)算分析(Differential Computational Analysis，DCA)。差分計(jì)算分析不需要攻擊者全面掌握算法細(xì)節(jié)，只需采集白盒實(shí)現(xiàn)程序運(yùn)行過(guò)程中的相關(guān)變量，通過(guò)相應(yīng)的統(tǒng)計(jì)分析方法即可提取出密鑰信息。差分計(jì)算分析的效率更高，部署更加簡(jiǎn)便。由于差分計(jì)算分析的便捷性與高效性，差分計(jì)算分析從首次提出便取得了廣泛關(guān)注。文獻(xiàn)[6-7]對(duì)差分計(jì)算分析進(jìn)行了解釋與介紹，給出了該分析方法成功進(jìn)行的理論原因。文獻(xiàn)[8]中又提出了改進(jìn)差分計(jì)算分析效率的方法。2019年，RIVAIN等[9]研究了內(nèi)部編碼對(duì)差分計(jì)算分析的影響，并提出了類似的分析手段；同年，BOGDANOV等[10]又提出了高階的差分計(jì)算分析方法，用以分析含有軟件補(bǔ)償對(duì)策的白盒實(shí)現(xiàn)。

SM 4算法是我國(guó)商用密碼標(biāo)準(zhǔn)算法[11]。2009年，肖雅瑩等[12]提出了第一個(gè)SM 4算法的白盒實(shí)現(xiàn)方案(肖-來(lái)白盒SM 4)，該方案利用CHOW等的白盒化思想，將SM 4算法流程轉(zhuǎn)換為查找表網(wǎng)絡(luò)，并采用線性編碼對(duì)查找表進(jìn)行保護(hù)。2013年，林婷婷等[13]結(jié)合BGE攻擊、差分分析等方法，成功對(duì)肖-來(lái)白盒SM 4進(jìn)行了分析。2015年，SHI等[14]提出一種新的白盒SM 4方案，將SM 4算法步驟結(jié)合到查找表中，并利用線性編碼對(duì)查找表進(jìn)行保護(hù)。同年，BAI等[15]又在肖-來(lái)SM 4方案的基礎(chǔ)上，將查找表的編碼復(fù)雜化，提出了一種新的白盒SM 4實(shí)現(xiàn)BAI-WU(白-武)白盒SM 4。2018年，潘文倫等[16]對(duì)肖-來(lái)白盒SM 4以及BAI-WU(白-武)白盒SM 4的安全性進(jìn)行了分析，給出了密鑰空間。2020年，姚思等[17]結(jié)合混淆密鑰與查找表技術(shù)，提出了一種新型白盒SM 4實(shí)現(xiàn)。作為首個(gè)提出的白盒SM 4方案，肖-來(lái)白盒SM 4的白盒化方法與查找表混淆手段在后續(xù)提出的白盒SM 4方案中都得到了借鑒與應(yīng)用。

筆者在對(duì)差分計(jì)算分析進(jìn)行研究的基礎(chǔ)上，首次將差分計(jì)算分析用于白盒SM 4的安全性分析，提出了一種針對(duì)白盒SM 4的分析方法。該分析方法利用加密過(guò)程中所產(chǎn)生的所有中間查表結(jié)果，采用均值差分的方法，使用線性組合抵消白盒SM 4中的混淆，稱該分析方法為中間值平均差分分析(Intermediate-Values Mean Difference Analysis，IVMDA)。并利用IVMDA實(shí)現(xiàn)了肖-來(lái)白盒SM 4的密鑰提取。

1 SM 4白盒實(shí)現(xiàn)方案

肖-來(lái)白盒SM 4算法的基本結(jié)構(gòu)與標(biāo)準(zhǔn)SM 4算法結(jié)構(gòu)大致相同：分組長(zhǎng)度為128 bit，采用32輪非線性迭代結(jié)構(gòu)；密鑰長(zhǎng)度為128 bit，通過(guò)密鑰拓展算法生成32個(gè)32 bit輪密鑰。肖-來(lái)白盒SM 4做出的改進(jìn)是在每一輪的加密過(guò)程中添加線性編碼，對(duì)每一輪的輸入輸出進(jìn)行混淆，在下一輪的輸入處對(duì)上一輪輸出中所添加的混淆進(jìn)行抵消。白盒SM 4的密鑰被提前確定好，每一輪中與密鑰相關(guān)的計(jì)算過(guò)程以查找表的形式呈現(xiàn)，查找表同時(shí)包含了密鑰相關(guān)的計(jì)算過(guò)程以及對(duì)輸入輸出的混淆方法。肖-來(lái)白盒SM 4一輪的計(jì)算過(guò)程如圖1所示。

圖1 肖-來(lái)白盒SM 4一輪過(guò)程

X→Y過(guò)程以查找表的形式體現(xiàn)，且密鑰嵌入查找表中，同時(shí)考慮到X→Y的變換是32入32出的變換。直接生成查找表會(huì)耗費(fèi)巨大的存儲(chǔ)空間，因此需要進(jìn)行分割，用4個(gè)8入32出的變換以及3個(gè)異或操作進(jìn)行代替，將X=(xi，0，xi，1，xi，2，xi，3)經(jīng)過(guò)Ei，j與S盒及密鑰加操作后的值記為(zi，0，zi，1，zi，2，zi，3)，改進(jìn)后的第二部分表達(dá)式如式(1)。

(Ri，0zi，0)⊕(Ri，1zi，1)⊕(Ri，2zi，2)⊕(Ri，3·zi，3⊕c[Qi]) 。

(1)

l[Qi]與c[Qi]分別表示Qi變換的線性變換與常數(shù)部分，Ri，j(j=0，1，2，3)表示32×8的矩陣。由式(1)可以看出，原來(lái)32入32出的查找表被替換成了4個(gè)8入32出的查找表以及3個(gè)異或操作。一輪加密函數(shù)中的F函數(shù)可以用5個(gè)仿射變換、4個(gè)查找表、6個(gè)異或操作完成。

2 差分計(jì)算分析

差分計(jì)算分析是灰盒模型下的差分功耗分析在白盒安全模型下的對(duì)應(yīng)軟件版本。該分析使用程序運(yùn)行過(guò)程中的軟件執(zhí)行軌跡來(lái)提取密鑰信息，軟件執(zhí)行軌跡包括但不限于程序執(zhí)行期間訪問(wèn)的內(nèi)存地址、內(nèi)存數(shù)據(jù)等變量。差分功耗分析所依據(jù)的原理是執(zhí)行加密操作時(shí)所產(chǎn)生的功耗軌跡信息與密鑰密切相關(guān)[18]，差分計(jì)算分析則認(rèn)為軟件執(zhí)行軌跡與密鑰同樣密切相關(guān)。

差分計(jì)算分析可分為以下四步進(jìn)行。

步驟1 攻擊者首先執(zhí)行一次白盒實(shí)現(xiàn)程序，采集其軟件執(zhí)行軌跡，利用可視化工具對(duì)其進(jìn)行處理。

步驟2 攻擊者使用隨機(jī)明文獲取軟件執(zhí)行軌跡，每一條明文會(huì)對(duì)應(yīng)一個(gè)軟件執(zhí)行軌跡。

步驟3 對(duì)采集到的軟件執(zhí)行軌跡進(jìn)行格式化，轉(zhuǎn)換成適當(dāng)?shù)母袷?，以適應(yīng)接下來(lái)的分析。

步驟4 使用差分功耗分析工具對(duì)處理后的軟件執(zhí)行軌跡進(jìn)行分析，提取出密鑰信息。

進(jìn)行步驟1的主要目的是定位出與密鑰相關(guān)的計(jì)算部分，以便縮小采集范圍，節(jié)省分析所需的內(nèi)存空間，在內(nèi)存空間充足時(shí)可跳過(guò)該步驟。軟件執(zhí)行軌跡的采集可以利用PIN[19]或者Valgrind[20]等動(dòng)態(tài)二進(jìn)制分析軟件以及相關(guān)的插件來(lái)完成。而對(duì)于軟件執(zhí)行軌跡的格式化只是將采集的信息限制到單一的種類中，比如只采集寫入內(nèi)存的數(shù)據(jù)或只采集從內(nèi)存中讀出的數(shù)據(jù)。前幾個(gè)步驟的目的是對(duì)采集到的數(shù)據(jù)進(jìn)行處理，使其盡可能地適應(yīng)差分功耗分析，而在分析步驟中只是將差分功耗分析的對(duì)象從電路功耗換成了二進(jìn)制形式的軟件執(zhí)行軌跡，同時(shí)由于軟件執(zhí)行軌跡中不會(huì)存在噪聲，所以往往分析的結(jié)果更加精確。

差分計(jì)算分析需要攻擊者能夠在受控環(huán)境下重復(fù)多次執(zhí)行二進(jìn)制白盒實(shí)現(xiàn)程序，并且攻擊者掌握白盒實(shí)現(xiàn)外部編碼的輸入編碼或者輸出編碼任一部分。這兩點(diǎn)是能夠進(jìn)行差分計(jì)算分析的基本定義，只有滿足以上兩點(diǎn)，才能夠完整地運(yùn)行差分計(jì)算分析的全部步驟。

文獻(xiàn)[5]中的差分計(jì)算分析所需要的軟件執(zhí)行軌跡為白盒程序運(yùn)行時(shí)的內(nèi)存讀寫記錄，采用均值差分對(duì)其進(jìn)行統(tǒng)計(jì)分析。文獻(xiàn)[21]在差分計(jì)算分析的基礎(chǔ)上提出了差分?jǐn)?shù)據(jù)分析(Differential Data Analysis，DDA)。該分析與差分計(jì)算分析基本類似，不同之處在于需要的軟件執(zhí)行軌跡為加密過(guò)程中所有查表結(jié)果，利用相關(guān)系數(shù)(如皮爾遜相關(guān)系數(shù))進(jìn)行統(tǒng)計(jì)分析。差分?jǐn)?shù)據(jù)分析所需的分析對(duì)象為查表結(jié)果，該數(shù)據(jù)較差分計(jì)算分析所需的內(nèi)存訪問(wèn)記錄更易于采集，但差分?jǐn)?shù)據(jù)分析需要計(jì)算數(shù)據(jù)的皮爾遜相關(guān)系數(shù)來(lái)進(jìn)行統(tǒng)計(jì)分析，該步驟卻比差分計(jì)算分析中計(jì)算均值差分來(lái)進(jìn)行統(tǒng)計(jì)分析的方法更復(fù)雜。文獻(xiàn)[5，21]中實(shí)驗(yàn)顯示，差分計(jì)算分析所需要的軟件執(zhí)行軌跡數(shù)目通常為數(shù)千條，而差分?jǐn)?shù)據(jù)分析所需要的軟件執(zhí)行軌跡數(shù)量為數(shù)百條。綜合以上兩種分析的優(yōu)點(diǎn)，采用更易于采集的查表結(jié)果為分析對(duì)象，并以復(fù)雜度更低的計(jì)算均值差分作為統(tǒng)計(jì)分析的方法，筆者提出了用于白盒SM 4密鑰提取的新型分析方法，名為中間值平均差分分析(Intermediate-Values Mean Difference Analysis，IVMDA)。

3 中間值平均差分分析

介紹中間值平均差分分析，應(yīng)用該分析對(duì)肖-來(lái)白盒SM 4進(jìn)行密鑰提取工作，給出了實(shí)際分析結(jié)果，并根據(jù)結(jié)果對(duì)分析做出相應(yīng)改進(jìn)。

3.1 攻擊模型與原理說(shuō)明

中間值平均差分分析的目標(biāo)是能夠在實(shí)際應(yīng)用環(huán)境下對(duì)白盒SM 4進(jìn)行密鑰提取。傳統(tǒng)的白盒安全模型中，攻擊者對(duì)算法的細(xì)節(jié)以及運(yùn)行環(huán)境都具備完全的了解以及控制能力，但在實(shí)際應(yīng)用環(huán)境中的攻擊者往往不具備該攻擊條件。根據(jù)實(shí)際應(yīng)用環(huán)境中白盒實(shí)現(xiàn)面臨的現(xiàn)實(shí)性威脅對(duì)攻擊者的能力進(jìn)行定義。白盒實(shí)現(xiàn)的攻擊者是一個(gè)帶有惡意目的的合法用戶，掌握白盒實(shí)現(xiàn)的二進(jìn)制程序，并具備一定的逆向、代碼調(diào)試等能力。攻擊者不直接掌握外部編碼，但可以向外部編碼組件發(fā)送明文并獲得編碼后的明文。攻擊者不掌握白盒實(shí)現(xiàn)方案的算法細(xì)節(jié)，只了解白盒方案的底層算法種類。攻擊者的分析對(duì)象是白盒實(shí)現(xiàn)的所有查表結(jié)果。

中間值平均差分分析也可以認(rèn)為是一種差分功耗分析在軟件層面的變體分析方式，差分功耗分析是利用加密芯片運(yùn)行過(guò)程中產(chǎn)生的功耗信息與密鑰的相關(guān)性來(lái)進(jìn)行統(tǒng)計(jì)分析[18]，從而提取出密鑰信息。中間值平均差分分析的分析對(duì)象是加密過(guò)程中的查表結(jié)果，每一個(gè)表中都嵌入了密鑰信息，查表結(jié)果與密鑰之間必然存在相關(guān)性，因此可以利用統(tǒng)計(jì)分析的方法對(duì)大量樣本進(jìn)行分析，提取密鑰。中間值平均差分分析基于以上原理進(jìn)行密鑰的提取工作。

3.2 中間值平均差分分析

中間值平均差分分析整體分為兩部分：數(shù)據(jù)采集部分與數(shù)據(jù)分析部分。

第1部分?jǐn)?shù)據(jù)采集。用SM 4白盒實(shí)現(xiàn)對(duì)n條隨機(jī)明文{p0，p1，…，pn}進(jìn)行加密，順序采集加密過(guò)程中產(chǎn)生的128個(gè)查表結(jié)果，以列表的形式組織數(shù)據(jù)，稱該列表為一條中間數(shù)據(jù)流。每一個(gè)隨機(jī)明文進(jìn)行加密的過(guò)程都對(duì)應(yīng)一條中間數(shù)據(jù)流ti。最終采集到n條明文及其對(duì)應(yīng)的n條中間數(shù)據(jù)流{t0，t1，…，tn}，并以鍵值對(duì)的形式將明文與中間數(shù)據(jù)流對(duì)應(yīng)組織起來(lái)。其中明文作為鍵，中間數(shù)據(jù)流作為值。

第2部分對(duì)采集到的數(shù)據(jù)進(jìn)行分析。根據(jù)攻擊者的能力，已知白盒實(shí)現(xiàn)的底層算法是SM 4，在該算法中與密鑰相關(guān)的計(jì)算部分是S盒，一輪中有4個(gè)并列的S盒計(jì)算，選取算法第一輪中包含密鑰加運(yùn)算的S盒計(jì)算作為中間函數(shù)φ(m0，j，rk0，j)。

φ(m0，j，rk0，j)=S(m0，j⊕rk0，j)=e，j∈{0，1，2，3} 。

(2)

式中，rk0，j表示8 bit長(zhǎng)的部分輪密鑰，而m0，j表示進(jìn)入S盒的8 bit長(zhǎng)的中間向量m0，中間函數(shù)的計(jì)算結(jié)果為e。根據(jù)SM 4算法流程，該中間向量m0由平均分為4部分的128 bit的明文的后三部分異或得到，由于掌握外部編碼的輸入編碼部分，因此可以直接使用原明文利用式(3)對(duì)中間向量m0進(jìn)行計(jì)算：

m0=pi，1⊕pi，2⊕pi，3。

(3)

采用中間函數(shù)φ，遍歷部分密鑰rk0，j所有可能的值。選取n條明文對(duì)應(yīng)的m0的一部分m0，j計(jì)算中間函數(shù)φ(m0，j，rk0，j)的結(jié)果，rk0，j∈{0，1}8，共有256種可能值，根據(jù)rk0，j值將中間函數(shù)結(jié)果分為256組。對(duì)每一組分別進(jìn)行以下4步的分析。

步驟1 定義一個(gè)選擇函數(shù)φ(e)，對(duì)組內(nèi)每一個(gè)中間函數(shù)結(jié)果e，利用式(4)計(jì)算其選擇函數(shù)的結(jié)果。

φ(e)=Sn(e)=b∈{0，1}，0≤n≤7 。

(4)

式中，Sn(e)是取中間結(jié)果的第n位。每一個(gè)中間結(jié)果e對(duì)應(yīng)8個(gè)選擇函數(shù)結(jié)果b；b是一個(gè)比特位，取值范圍只有0和1；根據(jù)n的不同，總共得到8個(gè)不同的b，用列表將其組織起來(lái)，記作B。

每一組的中間結(jié)果e都對(duì)應(yīng)一條明文，而一條明文對(duì)應(yīng)一條中間值數(shù)據(jù)流，同時(shí)每一個(gè)中間結(jié)果e也對(duì)應(yīng)一個(gè)B。因此，在不同的e所對(duì)應(yīng)的B中選取一個(gè)元素b，可以將其與一個(gè)中間數(shù)據(jù)流ti對(duì)應(yīng)起來(lái)。

步驟2 設(shè)定兩個(gè)集合A0，A1。當(dāng)b為0時(shí)，將對(duì)應(yīng)的中間數(shù)據(jù)流分入集合A0中，當(dāng)b為1時(shí)，將對(duì)應(yīng)的中間數(shù)據(jù)流分入集合A1中。隨后，利用式(5)和式(6)計(jì)算集合A0與集合A1的均值差分。

(5)

(6)

步驟3 對(duì)B中所有順序上的元素執(zhí)行步驟2中的分組以及計(jì)算均值差分，最終得到8個(gè)ΔLC值，選取其中最大的記為Δkey，該值與當(dāng)前組的密鑰猜測(cè)唯一對(duì)應(yīng)。

步驟4 對(duì)于所有的假設(shè)密鑰值對(duì)應(yīng)的組，執(zhí)行步驟1中計(jì)算選擇函數(shù)以及根據(jù)選擇函數(shù)結(jié)果進(jìn)行分組并計(jì)算均值差分等步驟。最終得到與當(dāng)前假設(shè)密鑰值惟一對(duì)應(yīng)的Δkey。比較所有的假設(shè)密鑰對(duì)應(yīng)的Δkey，Δkey值最大的假設(shè)密鑰即為最佳的猜測(cè)密鑰。

對(duì)一輪中的四個(gè)S盒分別執(zhí)行以上分析過(guò)程即可完整恢復(fù)一輪的輪密鑰。

3.3 實(shí)驗(yàn)結(jié)果與分析

采用Python語(yǔ)言實(shí)現(xiàn)中間值平均差分分析，對(duì)一個(gè)肖-來(lái)白盒SM 4程序進(jìn)行密鑰提取。在CPU為Intel(R) Core(TM) i5-6300HQ@2.3 GHz，運(yùn)行內(nèi)存大小為8 GB的計(jì)算機(jī)上執(zhí)行該分析。嵌入白盒實(shí)現(xiàn)程序的主密鑰為0123456789abcdeffedcba9876543210(十六進(jìn)制數(shù)串)，將得到的每一個(gè)部分假設(shè)密鑰及其所對(duì)應(yīng)的Δkey以圖片的形式展示在圖2中。

第一輪的輪密鑰為0xf12186f9。圖2中表示了第一輪的4部分猜測(cè)密鑰值及其對(duì)應(yīng)的Δkey的關(guān)系，橫坐標(biāo)key為猜測(cè)密鑰的值，縱坐標(biāo)為Δkey，根據(jù)中間值平均差分分析的描述，最大的Δkey所對(duì)應(yīng)的橫坐標(biāo)key為正確的密鑰猜測(cè)，并且正確的密鑰猜測(cè)對(duì)應(yīng)的Δkey應(yīng)當(dāng)為一個(gè)明顯的峰值。從圖中結(jié)果顯示，并未出現(xiàn)明顯的峰值，波形雜亂無(wú)章，同時(shí)正確密鑰所對(duì)應(yīng)的Δkey也不是最大值，該結(jié)果表明中間值平均差分分析并未成功提取出密鑰信息。重復(fù)多次實(shí)驗(yàn)均得到以上結(jié)果，結(jié)合肖-來(lái)SM 4方案對(duì)該結(jié)果進(jìn)行分析。

在肖-來(lái)白盒SM 4方案中，查找表的輸入、輸出部分存在隨機(jī)的仿射對(duì)輸入與輸出進(jìn)行混淆，而輸入的混淆會(huì)被抵消，因此只有輸出部分的混淆對(duì)查找表的結(jié)果產(chǎn)生影響。根據(jù)中間值平均差分分析的原理，查找表的結(jié)果與密鑰之間必然存在相關(guān)性，而實(shí)驗(yàn)結(jié)果卻并沒(méi)有反映出該相關(guān)性。猜測(cè)是輸出部分的混淆影響了實(shí)驗(yàn)結(jié)果，設(shè)計(jì)對(duì)照實(shí)驗(yàn)對(duì)該猜測(cè)進(jìn)行驗(yàn)證。

圖2 中間值平均差分分析結(jié)果

圖3 查找表無(wú)輸出編碼的白盒SM 4中間值平均差分分析結(jié)果

嵌入查找表主密鑰為0123456789abcdeffedcba9876543210十六進(jìn)制數(shù)串，第一輪的子密鑰為0xf12186f9。圖3(a)～(d)分別表示對(duì)第1輪子密鑰4部分的猜測(cè)結(jié)果，圖3(a)中最高值對(duì)應(yīng)的橫坐標(biāo)key為31，十六進(jìn)制為0x1f；圖3(b)中最高值對(duì)應(yīng)橫坐標(biāo)key為33，對(duì)應(yīng)十六進(jìn)制為0x21；圖3(c)中最高值對(duì)應(yīng)橫坐標(biāo)key為134，十六進(jìn)制為0x86；圖3(d)中最高值對(duì)應(yīng)橫坐標(biāo)key為249，十六進(jìn)制為0xf9。后3部分的分析結(jié)果為正確密鑰值，并且正確密鑰對(duì)應(yīng)的Δkey為明顯的峰值。同時(shí)改變嵌入密鑰重新生成查找表，進(jìn)行多次實(shí)驗(yàn)，結(jié)果均為后3部分的密鑰猜測(cè)值與正確密鑰值相符。

由于可以固定得到第一輪子密鑰的后3部分，因此可以認(rèn)為在不含輸出編碼的情況下，中間值均值差分分析可以通過(guò)對(duì)查找表值的分析得出正確密鑰。對(duì)比兩次實(shí)驗(yàn)的結(jié)果，可以得出結(jié)論：肖-來(lái)白盒SM 4實(shí)現(xiàn)中查找表的輸出編碼部分對(duì)中間值平均差分分析造成了干擾，導(dǎo)致分析失敗。

3.4 對(duì)中間值平均差分分析的改進(jìn)

節(jié)3.3的研究與分析表明，查找表輸出編碼是影響分析的關(guān)鍵因素。肖-來(lái)白盒SM 4實(shí)現(xiàn)的混淆手段只有線性編碼，該編碼是對(duì)查找表原始輸出進(jìn)行線性組合得到新的結(jié)果，使得假設(shè)中間函數(shù)結(jié)果與實(shí)際查找表結(jié)果不匹配。因此，分析步驟中直接利用中間函數(shù)結(jié)果進(jìn)行分組并不能反映密鑰與查表值的關(guān)系，需要添加相關(guān)操作抵消編碼影響。筆者采用計(jì)算中間函數(shù)結(jié)果的線性組合的方式來(lái)抵消線性編碼的混淆作用。

對(duì)于中間值平均差分分析的改進(jìn)只在選擇函數(shù)的形式上做出了改變，其余部分保持不變。選擇函數(shù)形式如下：

φ(e)=LCe=b∈{0，1}，1≤LC≤255 。

(7)

式中，LC∈{0，1}8取值范圍從1至255，該表達(dá)式計(jì)算出中間函數(shù)結(jié)果的所有線性組合結(jié)果，目的是為了消除白盒實(shí)現(xiàn)中的線性編碼手段對(duì)結(jié)果的影響。每一個(gè)中間結(jié)果e對(duì)應(yīng)255個(gè)線性組合結(jié)果b；b是一個(gè)比特位，取值范圍只有0和1。根據(jù)LC的不同，總共得到255個(gè)不同的b，以列表的形式將其組織起來(lái)，記作B。

對(duì)于一組的中間結(jié)果e，每一個(gè)都對(duì)應(yīng)一條明文，而一條明文對(duì)應(yīng)一條中間值數(shù)據(jù)流，同時(shí)每一個(gè)中間結(jié)果e也對(duì)應(yīng)一個(gè)B。因此，在不同的e所對(duì)應(yīng)的B中選取一個(gè)元素b，可以將其與一個(gè)中間數(shù)據(jù)流ti對(duì)應(yīng)起來(lái)。設(shè)定兩個(gè)集合A0，A1，當(dāng)b為0時(shí)，將對(duì)應(yīng)的中間數(shù)據(jù)流分入集合A0中，當(dāng)b為1時(shí)，將對(duì)應(yīng)的中間數(shù)據(jù)流分入集合A1中。隨后，計(jì)算集合A0與集合A1的均值差分，計(jì)算步驟如式(5)和式(6)。對(duì)B中所有順序上的元素執(zhí)行以上分組以及計(jì)算均值差分的步驟，最終得到255個(gè)ΔLC值，選取其中最大的記為Δkey；該值與當(dāng)前組的密鑰猜測(cè)惟一對(duì)應(yīng)。

對(duì)于所有的假設(shè)密鑰值對(duì)應(yīng)的組，執(zhí)行以上計(jì)算選擇函數(shù)以及根據(jù)選擇函數(shù)結(jié)果進(jìn)行分組并計(jì)算均值差分等步驟。最終得到與當(dāng)前假設(shè)密鑰值惟一對(duì)應(yīng)的Δkey。比較所有的假設(shè)密鑰對(duì)應(yīng)的Δkey，Δkey值最大的假設(shè)密鑰即為最佳的猜測(cè)密鑰。

3.5 改進(jìn)后中間值平均差分分析的實(shí)驗(yàn)結(jié)果

改進(jìn)后的中間值平均差分分析采用Python進(jìn)行實(shí)現(xiàn)，對(duì)肖-來(lái)白盒SM 4的二進(jìn)制程序進(jìn)行分析。在CPU為Intel(R) Core(TM) i5-6300HQ@2.3 GHz，運(yùn)行內(nèi)存大小為8 GB的計(jì)算機(jī)上執(zhí)行該分析。嵌入白盒實(shí)現(xiàn)程序的主密鑰為0123456789abcdeffedcba9876543210(十六進(jìn)制數(shù)串)。實(shí)驗(yàn)結(jié)果如圖4所示。

根據(jù)主密鑰可計(jì)算出第一輪的輪密鑰為0xf12186f9。分析程序?qū)Φ谝惠?部分的密鑰進(jìn)行猜測(cè)，圖4(a)～(b)表示了4部分猜測(cè)密鑰值及其對(duì)應(yīng)的Δkey的關(guān)系，橫坐標(biāo)key表示猜測(cè)密鑰的值，縱坐標(biāo)為Δkey。圖4(a)中最高Δkey所對(duì)應(yīng)的橫坐標(biāo)key為241，轉(zhuǎn)為十六進(jìn)制即為0xf1；圖4(b)中最高Δkey所對(duì)應(yīng)的橫坐標(biāo)key為33，轉(zhuǎn)換為十六進(jìn)制即為0x21；圖4(c)中最高Δkey所對(duì)應(yīng)的橫坐標(biāo)key為134，轉(zhuǎn)為十六進(jìn)制為0x86；圖4(d)中最高Δkey對(duì)應(yīng)的橫坐標(biāo)key為249，轉(zhuǎn)換為十六進(jìn)制為0xf9。分析所得結(jié)果與第一輪查找表中實(shí)際嵌入的輪密鑰完全相符，該分析耗時(shí)約為27 min。

圖4 改進(jìn)后中間值平均差分分析對(duì)肖-來(lái)白盒SM 4分析結(jié)果

改變參與分析的明文數(shù)量，重復(fù)進(jìn)行實(shí)驗(yàn)。明文數(shù)量與分析結(jié)果的對(duì)應(yīng)關(guān)系如表1所示。

表1 明文數(shù)量與分析結(jié)果

從表1的結(jié)果可以看出：隨著明文數(shù)目的降低，Δkey的最高值與次高值之間的差距越來(lái)越小，在隨機(jī)明文的數(shù)量低至一定數(shù)目之后，所得到的分析結(jié)果會(huì)出現(xiàn)錯(cuò)誤。實(shí)驗(yàn)結(jié)果表明，明文數(shù)量的下限在50左右波動(dòng)，同時(shí)，隨著明文數(shù)量的降低，分析所需時(shí)間也會(huì)下降，在保證分析正確性的前提下只需要60條明文即可完成密鑰提取工作。

3.6 與其他分析對(duì)比

表2 分析方法的對(duì)比

通過(guò)以上幾方面的對(duì)比，可以看出中間值平均差分分析在分析效率、部署簡(jiǎn)便性以及分析結(jié)果的準(zhǔn)確性方面要優(yōu)于潘、林的分析方法。同時(shí)，本實(shí)驗(yàn)中的中間值平均差分分析采用解釋型編程語(yǔ)言Python進(jìn)行實(shí)現(xiàn)，其效率還可以通過(guò)利用編譯型編程語(yǔ)言重新實(shí)現(xiàn)以及引入并行計(jì)算等方法進(jìn)行優(yōu)化，分析的時(shí)間還能大幅縮短。

4 總結(jié)與展望

筆者在差分計(jì)算分析的基礎(chǔ)上提出了中間值平均差分分析。該分析以白盒實(shí)現(xiàn)加密過(guò)程中的查表結(jié)果為分析對(duì)象，并且利用線性組合的手段抵消了查找表輸出部分的線性編碼。相比于之前的針對(duì)白盒SM 4方案的安全性分析手段，中間值平均差分分析部署簡(jiǎn)單、分析效率高、分析結(jié)果精確，是一種高效的新型分析方法。為了提高白盒方案的內(nèi)存效率，近期提出的白盒實(shí)現(xiàn)方案均采用線性編碼手段對(duì)查找表進(jìn)行保護(hù)，如姚思等人的白盒CLEFIA方案[22]，而中間值平均差分分析的分析對(duì)象即為線性編碼保護(hù)的查找表。因此，在未來(lái)的研究中，可以將中間值平均差分分析推廣到類似的白盒方案的安全性分析工作中來(lái)。