張躍宇 徐 東 陳 杰
①(西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院 西安 710071)
②(桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室 桂林 541004)
③(西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室 西安 710071)
傳統(tǒng)的密碼安全性分析環(huán)境被稱為黑盒攻擊環(huán)境,攻擊者只能訪問密碼系統(tǒng)的輸入與輸出,但隨著密碼系統(tǒng)部署環(huán)境的多樣化,該分析模型已經(jīng)不能夠反映實(shí)際應(yīng)用中攻擊者的能力。2002年,Chow等人[1]提出了白盒攻擊環(huán)境的概念,該攻擊環(huán)境中的攻擊者對算法運(yùn)行環(huán)境具備完全的控制權(quán),并且完全掌握算法的設(shè)計(jì)細(xì)節(jié)。白盒攻擊環(huán)境中攻擊者的能力包括但不限于:動態(tài)觀測算法程序運(yùn)行過程、修改算法程序運(yùn)行過程中的中間值、對算法程序進(jìn)行調(diào)試分析等。
為了保證在白盒攻擊環(huán)境下運(yùn)行的密碼算法的密鑰安全性,需要對密碼算法進(jìn)行白盒化處理,處理后的算法稱為密碼算法的白盒實(shí)現(xiàn)。密碼算法的白盒化方法由Chow等人[1]首次提出,并在其白盒高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES)、白盒數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard, DES)[2]方案中應(yīng)用,后續(xù)提出的大部分密碼算法的白盒實(shí)現(xiàn)方案都采用了該白盒化方法。對于白盒實(shí)現(xiàn)的安全性分析工作,主要分為兩類:一類以Billet等人[3]提出的 BGE分析,Michiels等人[4]提出的 MGH分析為代表。這一類的分析充分地利用了攻擊者在白盒攻擊環(huán)境中所掌握的能力,通過對算法細(xì)節(jié)的分析找出算法的安全性缺陷,選擇特定的查找表并采用仿射等價(jià)、線性等價(jià)等代數(shù)手段剝離算法內(nèi)部的混淆手段,對混淆剝離后的查找表進(jìn)行分析提取密鑰。這一類的分析方法要求攻擊者對白盒實(shí)現(xiàn)的設(shè)計(jì)細(xì)節(jié)完全掌握,并且需要利用大量的代數(shù)方法進(jìn)行分析,整體的分析難度較高,在實(shí)際應(yīng)用環(huán)境中較難進(jìn)行部署。另一類白盒實(shí)現(xiàn)的安全性分析工作以Bos等人[5]于2016年提出的差分計(jì)算分析(Differential Computational Analysis, DCA)為代表。DCA是差分功耗分析[6]的軟件版本,DCA不需要攻擊者掌握算法的設(shè)計(jì)細(xì)節(jié),只需要采集算法程序在運(yùn)行過程的中間狀態(tài),通過相應(yīng)的統(tǒng)計(jì)分析方法提取密鑰。相較于BGE,GH等分析手段,DCA分析只需要掌握白盒實(shí)現(xiàn)的底層算法,能夠監(jiān)測白盒實(shí)現(xiàn)程序的運(yùn)行過程即可進(jìn)行分析,極大地降低了分析的部署難度。
DCA的提出將白盒實(shí)現(xiàn)的安全性分析工作自動化、簡單化。由于其便捷性與高效性,DCA自提出之后便獲得了廣泛關(guān)注。Bos等人[5]只是提出了DCA,并利用該方法對幾個白盒AES實(shí)現(xiàn)進(jìn)行了成功分析,并未在理論層面對DCA進(jìn)行解釋說明,文獻(xiàn)[7,8]對DCA進(jìn)行了詳細(xì)的解釋與介紹,并分別給出了該分析能夠成功進(jìn)行的理論原因。文獻(xiàn)[9]又提出了改進(jìn)DCA分析效率的方法。2019年,Rivain等人[10]討論了內(nèi)部編碼對于DCA的影響,并提出了一種與差分計(jì)算分析類似的分析手段。同年,Bogdanov等人[11]又提出了高階的差分計(jì)算分析方法,用以分析包含軟件補(bǔ)償對策的白盒實(shí)現(xiàn)。
在差分計(jì)算分析的理論不斷改進(jìn)與發(fā)展的同時(shí),研究人員也在尋找針對該分析的軟件補(bǔ)償措施,用以減輕甚至消除差分計(jì)算分析對白盒實(shí)現(xiàn)安全性的影響。Biryukov等人[7]中提出了名為掩蔽(masking)的補(bǔ)償手段,掩蔽可用于計(jì)算過程中的中間值也可用于算法的結(jié)構(gòu)。Lee等人[12]于2017年提出了基于Chow白盒AES改進(jìn)的白盒AES實(shí)現(xiàn)方案,該方案在查找表輸出中添加隨機(jī)掩碼用以抵抗差分計(jì)算分析。同年,Banik等人[13]提出了控制流混淆、查找表位置隨機(jī)化、虛擬操作等軟件補(bǔ)償措施以對抗DCA。2020年,Lee等人[14]再次提出了一種改進(jìn)型的白盒實(shí)現(xiàn)方案,該方案主要針對高階差分計(jì)算分析而改進(jìn)。在不斷地對抗與改進(jìn)中,差分計(jì)算分析已成為檢驗(yàn)白盒實(shí)現(xiàn)方案安全性的重要工具。
SM4算法(原SMS4算法)是我國商用密碼標(biāo)準(zhǔn)算法[15]。肖-來白盒SM4是SM4算法的第1個白盒實(shí)現(xiàn)方案[16],該方案采用了Chow等人的白盒化思想。2013年,肖-來白盒SM4方案被林婷婷等人攻破[17]。2015年,Shi等人[18]提出了一種新的白盒SM4方案,該方案將SM4步驟結(jié)合到查找表中,并采用隨機(jī)混淆對查找表進(jìn)行保護(hù)。同年,Bai等人[19]提出了白-武白盒SM4實(shí)現(xiàn)方案,該方案在肖-來白盒SM4的基礎(chǔ)上將線性編碼復(fù)雜化,希望以此提高方案安全性。2018年,潘文倫等人[20]對肖-來白盒SM4與白-武白盒SM4方案進(jìn)行了成功分析,分別給出了兩個方案的密鑰空間大小,同時(shí)證明了復(fù)雜化的線性編碼對方案安全性的貢獻(xiàn)是有限的。2020年,姚思等人[21]結(jié)合混淆密鑰與查找表技術(shù)提出了一種內(nèi)部狀態(tài)擴(kuò)充的白盒SM4實(shí)現(xiàn)方案 (White-box implementation of SM4 algorithm with Internal State Expansion, WSISE)算法,該方案顯著提高了攻擊者提取密鑰的復(fù)雜度。
本文在差分計(jì)算分析的基礎(chǔ)上提出了中間值平均差分分析(Intermediate-Values Mean Difference Analysis, IVMDA),本分析以白盒SM4實(shí)現(xiàn)加密過程中的所有查表結(jié)果為輸入,分析以腳本程序的形式部署,分析過程自動化進(jìn)行。攻擊者只需控制白盒實(shí)現(xiàn)的運(yùn)行環(huán)境即可進(jìn)行分析。利用IVMDA成功對肖-來白盒SM4進(jìn)行了密鑰提取工作。為了保證白盒SM4方案的安全性,在肖-來白盒SM4方案中增加軟件對策以抵抗IVMDA。經(jīng)實(shí)驗(yàn)驗(yàn)證,改進(jìn)后的白盒SM4方案可以有效抵抗IVMDA。
肖-來白盒SM4實(shí)現(xiàn)方案在保持標(biāo)準(zhǔn)SM4算法整體結(jié)構(gòu)不變的同時(shí),將每一輪中密鑰相關(guān)的步驟用查找表的形式表示。采用線性編碼對查找表的輸入輸出進(jìn)行混淆,并且上一個變換的輸出部分引入的混淆會在下一個變換的輸入部分被抵消,以保證白盒SM4方案與標(biāo)準(zhǔn)SM4的輸入輸出一致。方案中的線性編碼均采用仿射的形式。肖-來白盒SM4方案的一輪的計(jì)算過程如圖1所示。肖-來白盒SM4方案的一輪加密過程包含5個復(fù)合仿射變換,4個8~32 bit的查找表,6個異或操作。
圖1 肖-來白盒SM4的一輪計(jì)算過程
差分計(jì)算分析是差分功耗分析在白盒攻擊環(huán)境下的軟件版本,該分析以算法程序運(yùn)行過程中的軟件執(zhí)行軌跡(software execution trace)為分析對象,而根據(jù)軟件執(zhí)行軌跡的具體種類以及進(jìn)行統(tǒng)計(jì)分析時(shí)所采用的方法的不同,差分計(jì)算分析也可被分為不同種類,差分?jǐn)?shù)據(jù)分析[22](Differential Data Analysis, DDA)便是其中一種。本文在差分計(jì)算分析的基礎(chǔ)上提出了一種針對白盒SM4方案的分析方法,稱為中間值平均差分分析。
為了提高分析效率,選擇白盒實(shí)現(xiàn)程序的所有查表結(jié)果為分析對象,采用均值差分作為密鑰與軟件執(zhí)行軌跡的相關(guān)性指標(biāo),由于白盒實(shí)現(xiàn)中查找表部分采用了線性編碼對結(jié)果進(jìn)行混淆,因此在分析過程中添加線性組合步驟來抵消編碼影響,分析步驟與DCA基本一致。將該分析方式命名為中間值平均差分分析(IVMDA)。IVMDA的目標(biāo)是能夠在實(shí)際的應(yīng)用環(huán)境下對白盒SM4實(shí)現(xiàn)進(jìn)行密鑰提取,因此攻擊者的能力需要符合實(shí)際的應(yīng)用場景?;谝陨峡紤],攻擊者被定義為一個具有惡意目的的合法用戶,該用戶以提取嵌入白盒實(shí)現(xiàn)程序中的密鑰為目標(biāo),掌握白盒實(shí)現(xiàn)程序及其部署環(huán)境,同時(shí)具備一定的逆向工程能力、代碼調(diào)試能力等黑客技能。攻擊者不掌握白盒實(shí)現(xiàn)算法的設(shè)計(jì)細(xì)節(jié),只了解白盒實(shí)現(xiàn)算法的底層算法。對于包含外部編碼的白盒實(shí)現(xiàn)程序,攻擊者不掌握外部編碼,但可以以合法用戶身份向外部編碼發(fā)起問詢,并獲得編碼后的明文。
IVMDA整體分為兩部分,數(shù)據(jù)采集部分與分析部分。
改變攻擊點(diǎn),對第1輪中剩余3個包含輪密鑰加的S盒運(yùn)算執(zhí)行以上分析步驟,即可提取出一輪的輪密鑰。整個的分析流程可以自動化進(jìn)行。后續(xù)輪次的密鑰值的計(jì)算可在已提取密鑰值的參與下采用IVMDA對每一輪中包含輪密鑰信息的S盒進(jìn)行分析而得到。
綜上,IVMDA采用查表結(jié)果作為分析對象,相較于DCA省略了對軟件執(zhí)行蹤跡進(jìn)行序列化處理的步驟,分析過程更加精簡,并且分析對象的采集方式會更多樣,所需采集的數(shù)據(jù)量也更小。采用均值差分作為密鑰與軟件執(zhí)行蹤跡之間的相關(guān)性指標(biāo),相較于DDA所采用的皮爾遜系數(shù),分析步驟的復(fù)雜度更低。采用線性組合的方式抵消白盒方案中的線性編碼混淆作用,保證了分析的正確性與改進(jìn)后的DCA相當(dāng)。
圖2 肖-來白盒SM4的中間值平均差分分析結(jié)果
(1) 對當(dāng)前的可能密鑰計(jì)算60次中間函數(shù),包含60次S盒運(yùn)算,3×60=180次8 bit向量的異或運(yùn)算;
(2) 計(jì)算60個中間函數(shù)結(jié)果的所有線性組合值,即執(zhí)行60×255次8 bit向量乘法,每一個中間函數(shù)結(jié)果對應(yīng)255個線性組合值,記作B;
(3) 根據(jù)B中相同位置上的元素值,將B對應(yīng)的中間函數(shù)結(jié)果所對應(yīng)的中間數(shù)據(jù)流進(jìn)行分組,共進(jìn)行255×60次分組;
(4) 每一次分組之后,計(jì)算不同分組之間的均值差分,該過程中執(zhí)行包含128個元素的集合的異或255×58次,除法運(yùn)算255×2×128次,128個元素的集合對應(yīng)元素差分運(yùn)算255次;
(5) 進(jìn)行完(4)中的運(yùn)算后,得到255個包含128個元素的差分值集合,選擇其中最大差分值作為ΔKey。
執(zhí)行以上5部分運(yùn)算256次即可計(jì)算出所有可能密鑰的ΔKey值,取最大ΔKey對應(yīng)的假設(shè)密鑰值作為最佳密鑰猜測。第1輪中4個8 bit密鑰的計(jì)算均采取相同的辦法。
綜合實(shí)驗(yàn)結(jié)果來看,中間值平均差分分析能夠成功地對肖-來白盒SM4進(jìn)行密鑰提取工作,只需掌握白盒實(shí)現(xiàn)程序及其部署環(huán)境,分析過程被封裝為一個腳本程序,在實(shí)際的應(yīng)用環(huán)境中很容易進(jìn)行部署。相較于傳統(tǒng)分析方法中所常用的求解矩陣方程、差分分析法等計(jì)算方法,IVMDA在分析時(shí)所采用的計(jì)算均為常見的簡單運(yùn)算如異或、除法、差分等,計(jì)算的復(fù)雜度大大降低。綜上,IVMDA是一種非常高效的白盒SM4方案分析方法,其對于白盒SM4安全性具備實(shí)際性的威脅。
為了抵抗IVMDA,在肖-來白盒SM4實(shí)現(xiàn)方案中添加軟件對策,利用非線性編碼對查找表的輸出進(jìn)行混淆,消除查表結(jié)果與密鑰之間的相關(guān)性,本節(jié)提出非線性混淆的白盒SM4實(shí)現(xiàn)(White-Box SM4 with Nonlinear Confusion, WBSM4-NC)方案。
IVMDA能夠成功提取密鑰的原因在于查找表的輸出值與密鑰之間存在相關(guān)性,并且線性編碼的混淆作用可以通過計(jì)算線性組合的方式進(jìn)行抵消。本節(jié)所提非線性混淆的白盒SM4實(shí)現(xiàn)方案在查找表的輸出處添加非線性編碼,對查找表結(jié)果進(jìn)行混淆。添加混淆之后的查找表結(jié)構(gòu)如圖3所示。
圖3中xi,j表示第i輪中第j個查找表的輸入,Ei,0消 除xi,j中的編碼。S*為包含輪密鑰加操作的S盒。Ri,j為8~32 bit的仿射編碼,是原方案中矩陣L與仿射變換Qi的復(fù)合編碼Ri的一部分,當(dāng)j=0,1, 2時(shí)Ri,j,以矩陣形式執(zhí)行編碼操作,當(dāng)j=3時(shí)Ri,j以仿射變換形式執(zhí)行編碼操作。out為添加的8 bit非線性編碼,對查找表輸出再次進(jìn)行混淆。圖3所示的查找表結(jié)構(gòu)是在肖-來白盒SM4方案的查找表結(jié)構(gòu)的輸出部分添加了4個級聯(lián)的8 bit非線性編碼,對Ri,j表的32 bit輸出進(jìn)行混淆。經(jīng)過混淆的32 bit結(jié)果作為該表的輸出,這樣使得輸入xi,j與經(jīng)過混淆的32 bit結(jié)果對應(yīng)起來,形成了新的帶有非線性混淆的8~32 bit的查找表。
圖3 包含混淆操作的查找表
在使用8 bit非線性編碼對查找表的輸出進(jìn)行混淆之后,不能直接使用查表結(jié)果進(jìn)行異或。異或過程需要借助異或表完成,異或表結(jié)構(gòu)如圖4(a)所示。異或表以兩個字節(jié)為輸入,表中輸入編碼in消去數(shù)據(jù)中的非線性編碼。in=out–1,異或后的數(shù)據(jù)需要再進(jìn)行編碼保護(hù),確保再次與其他數(shù)據(jù)進(jìn)行異或時(shí)的正確性。肖-來白盒實(shí)現(xiàn)中4個查找表結(jié)果的3次異或操作需要用12個異或表來替代,最終結(jié)果為一個32 bit的經(jīng)過4個級聯(lián)的8 bit非線性編碼的結(jié)果,即該結(jié)果為圖1中的Y 進(jìn)行4個級聯(lián)的8 bit非線性編碼操作,記作Y′。
圖4 異或表與編碼過程
圖5 查找表與部分仿射編碼的組合
在應(yīng)用潘文倫等人的分析方法對WBSM4-NC的安全性進(jìn)行分析的過程中,對Qi矩陣部分的恢復(fù)也是基于以上原因無法進(jìn)行,所以同理也可以認(rèn)為WBSM4-NC方案對于潘文倫等人的分析方法是安全的。
通過以上的分析,WBSM4-NC在已有的針對白盒SM4實(shí)現(xiàn)的安全性分析中可以保證安全性,接下來驗(yàn)證該方案在中間值平均差分分析下的安全性。采用與3.2節(jié)相同的程序執(zhí)行環(huán)境進(jìn)行中間值平均差分分析實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖6所示。
分析程序的輸出為圖6的雜亂折線圖,說明本文采用的軟件對策可成功抵抗IVMDA。這是由于采用了8 bit的非線性編碼對查找表結(jié)果進(jìn)行混淆之后,查找表結(jié)果與原密碼算法中包含輪密鑰加的S盒運(yùn)算的結(jié)果之間的關(guān)系相當(dāng)于執(zhí)行了一次置換操作,同時(shí)也可以采用一些被驗(yàn)證過的S盒來充當(dāng)該8 bit非線性編碼,由于S盒的性質(zhì),混淆后的查找表結(jié)果與原查找表結(jié)果之間的相關(guān)性很難采用相應(yīng)手段進(jìn)行恢復(fù),從而在IVMDA中保證了方案的安全性。表1對幾種白盒SM4實(shí)現(xiàn)方案的安全性進(jìn)行對比。
圖6 WBSM4-NC方案的中間值平均差分分析結(jié)果
表1 白盒實(shí)現(xiàn)方案的安全性對比
從表1的安全性對比可以看出,在安全性方面WBSM4-NC方案相比于其他的白盒SM4方案具備一定的優(yōu)勢。該方案可以抵抗林婷婷等人以及潘文倫等人的分析,在實(shí)際的應(yīng)用環(huán)境中能夠保證密鑰的安全性。下面對WBSM4方案的內(nèi)存效率進(jìn)行分析與對比。
為了保證密鑰安全性,抵抗IVMDA, WBSM4-NC方案在內(nèi)存性能上做出了妥協(xié),犧牲內(nèi)存空間以換取安全性。在每一輪的加密過程中,總計(jì)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方案的空間耗費(fèi)是巨大的。但是需要注意,肖-來白盒SM4方案本身并不包含非線性混淆部件而只有線性混淆部件,因此該方案的空間耗費(fèi)小于包含非線性部件的方案。表2對幾種白盒方案的效率做了簡單比較。
表2的Luo-Lai-You白盒AES方案[26]的空間大小與WBSM4-NC方案空間大小處在相同數(shù)量級,這是由于這兩個方案中均包含非線性混淆,原有的異或操作需要用異或表實(shí)現(xiàn),因此需要占用大量內(nèi)存空間。同時(shí),Luo-Lai-You白盒AES方案中使用的非線性部件為4 bit,根據(jù)文獻(xiàn)[8]的研究結(jié)論,4 bit的非線性編碼并不能混淆軟件執(zhí)行軌跡(該文獻(xiàn)中選擇內(nèi)存讀取記錄為分析對象)與密鑰之間的相關(guān)性。
表2 白盒實(shí)現(xiàn)方案的內(nèi)存效率對比
為了驗(yàn)證4 bit的非線性部件是否能夠混淆查找表結(jié)果與密鑰之間的相關(guān)性,采用了IVMDA對使用4 bit非線性部件的WBSM4-NC方案進(jìn)行分析,該分析的運(yùn)行環(huán)境與3.2節(jié)中IVMDA的運(yùn)行環(huán)境相同,圖7是本次分析的輸出結(jié)果。相對于8 bit的WBSM4-NC方案,4 bit版本方案在構(gòu)造方法上保持一致,只是由于編碼長度的改變,相應(yīng)的查找表大小與異或次數(shù)發(fā)生了變化,具體的方案不再展開描述。根據(jù)分析結(jié)果顯示,第1輪中所有部分輪密鑰均被揭示。由此可以證明:4 bit長度的非線性編碼并不能混淆查找表結(jié)果與密鑰的相關(guān)性,因此使用8 bit的非線性部件是為了保證安全性而作出的必要妥協(xié)。
圖7 4bit版本的WBSM4-NC方案的中間值平均差分分析結(jié)果
白-武白盒SM4方案占用空間較大的原因在于該方案為了提高安全性,在設(shè)計(jì)編碼時(shí)使得編碼復(fù)雜化,查找表數(shù)量較多。綜上可以看出,白盒方案在確保安全性的同時(shí)就必須舍棄一部分內(nèi)存效率,WBSM4-NC方案的內(nèi)存開銷仍在合理范圍之內(nèi)。WBSM4-NC方案對查找表的輸出進(jìn)行非線性混淆,將部分復(fù)合仿射編碼以查找表的形式存儲,提高了白盒SM4方案的安全性。并且與其他白盒SM4實(shí)現(xiàn)方案相比其內(nèi)存效率也保持在合理范圍之內(nèi)。該方案適合在實(shí)際應(yīng)用環(huán)境中部署,以提高密碼系統(tǒng)的安全性。
本文針對白盒SM4方案,提出了中間值平均差分分析IVMDA,該分析方法是差分能量分析針對白盒SM4方案的軟件改進(jìn)版本。首次提出白盒SM4方案的自動化分析方法,降低了對白盒SM4方案進(jìn)行安全性分析的難度。中間值平均差分分析使白盒密碼分析工作不再專屬于密碼學(xué)者,掌握部分計(jì)算機(jī)技能的黑客也可以對白盒密碼系統(tǒng)進(jìn)行分析,這對于白盒密碼系統(tǒng)的安全性是一種非常實(shí)際的威脅。同時(shí),考慮到IVMDA針對查找表的輸出結(jié)果進(jìn)行分析,利用計(jì)算線性組合的方式抵消線性編碼對查找表結(jié)果與密鑰相關(guān)性的混淆,該分析主要針對的是采用線性編碼保護(hù)查找表的白盒方案。后續(xù)的研究工作可以將中間值差分分析拓展到其他采用線性編碼保護(hù)查找表的白盒實(shí)現(xiàn)方案上,形成一個普適性的分析框架,以更好地評價(jià)白盒方案在實(shí)際應(yīng)用環(huán)境中的安全性。本文提出了利用8 bit非線性編碼對查找表輸出進(jìn)行混淆的軟件對策來抵抗IVMDA,提出非線性混淆的白盒SM4實(shí)現(xiàn)方案WBSM4-NC。通過實(shí)驗(yàn)驗(yàn)證,該軟件對策可以有效抵抗中間值平均差分分析。但為了保證安全性,必須增加白盒實(shí)現(xiàn)方案的內(nèi)存占用,這同時(shí)也相應(yīng)地限制了白盒實(shí)現(xiàn)方案的應(yīng)用范圍。因此,在后續(xù)的研究中需要進(jìn)一步地探究如何在保證安全性的前提下,降低白盒實(shí)現(xiàn)方案的內(nèi)存開銷,這對于白盒密碼的實(shí)際應(yīng)用具有重要意義。