孔 曼,譚 林,王云麗,龍 敏
1(湖南天河國(guó)云科技有限公司,長(zhǎng)沙 410100)
2(長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院,長(zhǎng)沙 410114)
20世紀(jì)70年代中期,分組密碼的研究開(kāi)始興起,至今信息安全領(lǐng)域的學(xué)者們已經(jīng)取得了許多豐碩的研究成果.近年來(lái),隨著物聯(lián)網(wǎng)的發(fā)展,無(wú)線傳感器網(wǎng)絡(luò)[1]和無(wú)線射頻技術(shù)[2]的應(yīng)用愈來(lái)愈廣泛.輕量級(jí)分組密碼的出現(xiàn)解決了微型計(jì)算設(shè)備計(jì)算能力有限、低功耗的問(wèn)題,且其加密速度快、易于硬件實(shí)現(xiàn)、能夠應(yīng)用于資源受限的環(huán)境中,還具有較高的安全性,所以自問(wèn)世以來(lái)就一直是密碼學(xué)界關(guān)注的焦點(diǎn).然而,隨著信息技術(shù)的高速發(fā)展,人們對(duì)于信息的價(jià)值流通具有高要求,雖然這些技術(shù)通過(guò)開(kāi)放性的計(jì)算機(jī)網(wǎng)絡(luò)實(shí)現(xiàn)信息交換和共享,同時(shí)也帶來(lái)了交互效率低、安全保障低等問(wèn)題.
此外,區(qū)塊鏈+物聯(lián)網(wǎng)[3]是未來(lái)的發(fā)展方向,區(qū)塊鏈技術(shù)可以為物聯(lián)網(wǎng)提供點(diǎn)對(duì)點(diǎn)直接互聯(lián)的方式來(lái)傳輸數(shù)據(jù),并且,區(qū)塊鏈的密碼機(jī)制[4]能夠?yàn)槲锫?lián)網(wǎng)中的信息傳輸創(chuàng)造安全的環(huán)境.尤其在資源受限的物聯(lián)網(wǎng)節(jié)點(diǎn)中需要對(duì)數(shù)據(jù)進(jìn)行加密時(shí),不可避免地引入具有占用資源少、功耗低、效率高、易于實(shí)現(xiàn)等優(yōu)勢(shì)的輕量級(jí)密碼算法,同時(shí)對(duì)密碼算法的安全性提出了更高的要求.
現(xiàn)在的輕量級(jí)分組密碼算法大都受到DES[5]和AES[6]設(shè)計(jì)原理的影響,目前已有許多的輕量級(jí)密碼算法陸續(xù)提出,有非常經(jīng)典的輕量級(jí)分組加密算法LBlock[7]、LED[8]、MIBS[9]、KLEIN[10]等,還有近兩年的新秀,如Midori[11]、HBcipher[12]、Surge[13]等.然而這些實(shí)際用于物聯(lián)網(wǎng)設(shè)備中的輕量級(jí)分組密碼算法日益凸顯出安全漏洞,所以需要對(duì)該類算法進(jìn)行分析研究,不斷完善攻擊過(guò)程與方法,以實(shí)現(xiàn)密碼算法的更新?lián)Q代,提升輕量級(jí)分組密碼算法的防御能力,進(jìn)一步提升區(qū)塊鏈中密碼技術(shù)的安全性.
故障攻擊是一種側(cè)信道攻擊方法,于1997年被Boneh 等人[14]提出,并用此方法攻擊了基于CRT 算法實(shí)現(xiàn)的RSA 簽名密鑰,意味著首次將密碼故障應(yīng)用于密碼分析.同年,Biham 等人首次提出了差分故障攻擊[15]并且成功分析了DES 算法.此后,差分故障攻擊被廣泛應(yīng)用于公鑰密碼算法、分組密碼算法等等.完成差分故障攻擊最重要的一點(diǎn)就是在加密設(shè)備中引進(jìn)故障,如電壓瞬變、外部時(shí)鐘驟變、激光束、X-射線等.差分故障攻擊已經(jīng)應(yīng)用到了許多的輕量級(jí)密碼算法分析中.文獻(xiàn)[16]以比特為單位進(jìn)行故障注入,有效地攻擊GIFT 算法; 文獻(xiàn)[17]針對(duì)SKINNY 密碼算法提出了恢復(fù)主密鑰平均需要10 個(gè)半字節(jié)故障,且通過(guò)了大量的模擬驗(yàn)證; 文獻(xiàn)[18]利用S 盒的差分不均勻性,在最后一輪注入兩次8 個(gè)半字節(jié)型的故障,快速恢復(fù)了最后一輪密鑰的信息; 文獻(xiàn)[19]提出了隨機(jī)注入2 字節(jié)故障的模型,兩對(duì)正誤密文就可以在不窮舉搜索的情況下檢索整個(gè)128 位AES 密鑰; 文獻(xiàn)[20]提出了在密鑰調(diào)度過(guò)程中注入一個(gè)字節(jié)型故障,僅需4 個(gè)錯(cuò)誤的密文確定整個(gè)密鑰.
本文通過(guò)分析ESF[21]的算法結(jié)構(gòu),提出了一種差分故障攻擊方法.此方法針對(duì)結(jié)構(gòu)中按位進(jìn)行運(yùn)算的算法具有通用性.此攻擊方法的主要思想是,在S 盒運(yùn)算前注入錯(cuò)誤故障,結(jié)合差分方程與S 盒在不同故障條件下輸出差分不均勻性,進(jìn)而獲取內(nèi)部狀態(tài)信息,最后分析得出初始密鑰.共需要約10 個(gè)故障密文,可將計(jì)算復(fù)雜度降為222.
ESF 算法是一個(gè)基于變種的Feistel 結(jié)構(gòu)的加密算法,輪函數(shù)采用的是SPN 代換置換網(wǎng)絡(luò)形式,其整體結(jié)構(gòu)借鑒于LBlock 算法,其中的置換層是仿照了PRESENT 算法的按位置換形式.
算法流程包含了輪密鑰異或、非線性變換、線性擴(kuò)散、中間狀態(tài)異或與移位操作.ESF 算法的分組長(zhǎng)度為64 比特,初始密鑰80 比特,迭代輪數(shù)為32 輪.加密流程如圖1,數(shù)據(jù)輸入分成左右兩個(gè)部分,令P=L0||R0表示64 位明文,C=L32||R32表示64 位密文.Ki(i=1,2,…,32)是每一輪迭代加密的輪密鑰.輪函數(shù)F中包含S 盒非線性變換和P 盒按位置換.
圖1 ESF 算法的加密流程
ESF 算法的初始密鑰是80 位,記為K=k79k78…k0,初始密鑰的左邊32 位作為第一輪輪密鑰K1,Ki(i=1,2,…,32)是80 位的密鑰中間狀態(tài),輪密鑰生成算法如算法1 所示.
算法1.ESF 算法的密鑰擴(kuò)展方案輸入: 80 比特初始密鑰.輸出: 輪密鑰.
1)K1←K;2)for i = 2 to 32 do;3)Ki←Ki-1<<<13;4)[k79k78k77k76] = S0([k79k78k77k76]);5)[k75k74k73k72] = S0([k75k74k73k72]);6)[k47k46k45k44k43] = [k47k46k45k44k43] [i]2;7)Ki←[k79k78…k0];8)Ki←[k79k78…k48].⊕
ESF 共有8 個(gè)S 盒,前4 個(gè)S 盒(S7-S4)的輸出去往奇數(shù)號(hào)的S 盒(S7、S5、S3、S1),后4 個(gè)S 盒(S3-S0)的輸出去往偶數(shù)號(hào)的S 盒(S6、S4、S2、S0).具體傳播位置置換如圖2 所示,其中粗線表示有故障的傳播,Ii(i=0,1,…,7)是右半明文中間狀態(tài)的半字節(jié)表示形式.
圖2 ESF 的置換圖
假設(shè)a是一個(gè)半字節(jié)作為某個(gè)S 盒的輸入.在S 盒輸入前,導(dǎo)入隨機(jī)故障f,即為S 盒的輸入差分.f*表示為S 盒的輸出差分,則滿足差分公式:
已知每一個(gè)輸入差分都有一個(gè)相應(yīng)的輸出差分,且輸入差分有24= 16 種可能,對(duì)應(yīng)的輸出差分有4-8 種可能,并且每一對(duì)(f,f*)能夠得到輸入值a的集合,集合內(nèi)元素的個(gè)數(shù)為2 或者4.正是由于分布的不均勻性,成為了差分故障攻擊的突破口.由于篇幅限制,文中只列出S7盒的差分分布表.ESF 算法S7盒的差分性如表1 所示(ID表示輸入差分,OD表示輸出差分).
表1 ESF 中S7 盒的差分分布表
已經(jīng)知道ESF 算法的置換層的基本運(yùn)算單位是比特.在S 盒運(yùn)算前隨機(jī)注入1 比特故障,那么無(wú)論在哪個(gè)S 盒,輸入差分只可能為0001、0010、0100、1 000這4 個(gè)中的任何一個(gè),由這4 個(gè)輸入差分,可列出每個(gè)S 盒對(duì)應(yīng)的輸出差分,以S7盒為例,表2 列出了S7盒的輸入所對(duì)應(yīng)的所有可能出現(xiàn)的輸出差分(OD表示輸出差分).
表2 ESF 中S7 盒每一個(gè)輸出差分可能的輸入
觀察表2 的輸出差分,可知,當(dāng)輸入差分僅為0001、0010、0100、1 000 時(shí),經(jīng)過(guò)S 盒后,至少能發(fā)生2 比特的故障錯(cuò)誤.再分析每個(gè)S 盒的可能的輸入,可以發(fā)現(xiàn)經(jīng)過(guò)S 盒后,發(fā)生2 比特和3 比特故障錯(cuò)誤的概率較大,且發(fā)生2 比特故障錯(cuò)誤的概率大于發(fā)生3 比特故障錯(cuò)誤的概率,發(fā)生4 比特故障錯(cuò)誤的概率最大也才1/8,因此,在S 盒運(yùn)算前注入1 比特故障,至少將導(dǎo)致2 個(gè)半字節(jié)出現(xiàn)錯(cuò)誤.本文將以2 比特故障錯(cuò)誤進(jìn)行保守分析.
在S 盒運(yùn)算前注入1 比特故障,經(jīng)過(guò)3 輪迭代運(yùn)算后,只導(dǎo)致兩個(gè)S 盒的輸出半字節(jié)出現(xiàn)故障錯(cuò)誤的平均概率僅為0.019 5,所以在分析過(guò)程中可以忽略此種情況.本文將以最后一輪S 盒輸出半字節(jié)出現(xiàn)故障的個(gè)數(shù)為3 的情況進(jìn)行保守分析.
(1)攻擊者有能力選擇一個(gè)明文進(jìn)行加密,并獲得相應(yīng)的正確故障密文;
(2)攻擊者能夠誘導(dǎo)1 比特故障輸入到加密的第30 輪寄存器中;
(3)故障位置和值均未知.
3.2.1 攻擊流程
(1)選擇明文P進(jìn)行加密,獲得正確密文C.
(2)恢復(fù)最后一輪輪密鑰,步驟如下:
1)對(duì)同樣的明文P進(jìn)行加密,在第30 輪輪函數(shù)運(yùn)行前注入1 比特隨機(jī)故障到寄存器B30Nj(1≤j≤8,表示在第30 輪、第j個(gè)S 盒位置)中,獲得錯(cuò)誤密文D1.將正確密文C與錯(cuò)誤密文D1 進(jìn)行異或,得到密文差分ΔD1 (此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察最后一輪右邊32 比特密文差分,得到準(zhǔn)確的進(jìn)入逆運(yùn)算的密文差分),密文差分經(jīng)過(guò)逆P 盒置換,得到最后一輪S 盒的輸出差分.
2)查找表2,由最后一輪S 盒的輸出差分列出相應(yīng)S 盒正確輸入的候選值.
3)在第30 輪輪函數(shù)運(yùn)算前,多次注入1 比特的隨機(jī)故障,并重復(fù)步驟1)和步驟2),不斷縮小S 盒正確輸入的候選值的個(gè)數(shù),直到剩下唯一一個(gè).此時(shí)得到的就是S 盒的正確輸入值.
4)最后將正確S 盒的輸入值與正確密文的左邊32 比特異或,即可得到最后一輪輪密鑰.
(3)恢復(fù)第31 輪輪密鑰,步驟如下:
1)結(jié)合最后一輪輪密鑰和最后一輪輸出,可逆推得到第31 輪正確輸出.此時(shí),在第29 輪注入1 比特的隨機(jī)故障到位置B29Nj(1≤j≤8)中,獲得錯(cuò)誤密文D2,結(jié)合最后一輪輪密鑰,可逆推得到第31 輪故障輸出.將第31 輪的正確輸出與故障輸出異或,得到中間狀態(tài)密文差分(此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察第31 輪的輸出的右32 比特密文差分,得到準(zhǔn)確的進(jìn)入逆運(yùn)算的密文差分).密文差分經(jīng)過(guò)逆P 盒置換,得到第31 輪S 盒的輸出差分.
2)查找表2,由第31 輪S 盒的輸出差分列出相應(yīng)S 盒正確輸入的候選值.
3)在第29 輪輪函數(shù)運(yùn)算前,多次注入1 比特的隨機(jī)故障,并重復(fù)步驟1)和步驟2),不斷縮小S 盒正確輸入的候選值的個(gè)數(shù),直到剩下唯一一個(gè).此時(shí)得到的就是S 盒的正確輸入值.
4)最后將正確S 盒的輸入值與正確密文的左邊32 比特異或,即可得到第31 輪輪密鑰.
(4)恢復(fù)第30 輪輪密鑰,步驟如下:
1)結(jié)合第31 輪輪密鑰和第31 輪輸出,可逆推得到第30 輪正確輸出.此時(shí),在第28 輪注入1 比特的隨機(jī)故障到寄存器B28Nj(1≤j≤8)中,獲得錯(cuò)誤密文D3,結(jié)合第31 輪輪密鑰,可逆推得到第30 輪故障輸出.將第30 輪的正確輸出與故障輸出異或,得到中間狀態(tài)密文差分(此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察第30 輪的輸出的右邊32 比特密文差分,得到準(zhǔn)確的進(jìn)入逆運(yùn)算的密文差分).密文差分經(jīng)過(guò)逆P 盒置換,得到第30 輪S 盒的輸出差分.
2)通過(guò)與(3)類似的方法分析出第30 輪輪密鑰.
3.2.2 差分故障攻擊方法分析
由第3.2.1 節(jié)已經(jīng)知道,在第30 輪S 盒運(yùn)算前隨機(jī)注入1 比特故障,在第32 輪至少能得到3 個(gè)錯(cuò)誤的S 盒輸出,在這樣的情況下,恢復(fù)第32 輪的輪密鑰所需要的錯(cuò)誤密文則減少到6 個(gè)(平均每?jī)蓪?duì)S 盒的輸入輸出差分所對(duì)應(yīng)的可能輸入值的集合能確定唯一的S 盒半字節(jié)輸入值).
由于是在第30 輪的S 盒運(yùn)算前注入的故障錯(cuò)誤,因此,在恢復(fù)最后一輪輪密鑰的同時(shí),也可以得到第31 輪中至少12 個(gè)錯(cuò)誤的S 盒輸出,那么只需要在第29 輪的S 盒運(yùn)算前再注入2 比特的故障錯(cuò)誤,得到2 個(gè)錯(cuò)誤密文就可以恢復(fù)第31 輪輪密鑰; 在恢復(fù)最后一輪輪密鑰時(shí),已經(jīng)得到第30 輪的6 個(gè)錯(cuò)誤的S 盒輸出,在恢復(fù)第31 輪輪密鑰時(shí),已經(jīng)得到第30 輪的至少4 個(gè)錯(cuò)誤的S 盒輸出,那么只需在第28 輪S 盒運(yùn)算前注入2 比特故障,即可恢復(fù)第30 輪輪密鑰.綜上所述,理論上只需要約10 個(gè)錯(cuò)誤密文就可以恢復(fù)最后3 輪輪密鑰K32、K31、K30.
3.2.3 密鑰推斷過(guò)程
以下步驟通過(guò)恢復(fù)出的最后3 輪輪密鑰K32、K31、K30,來(lái)推斷80 比特的完整子密鑰,其中“||”表示連接符.
(1)根據(jù)密鑰的擴(kuò)展方案,K30是K30的左32 位,K30=K30[0:31] ||K30[47:0];
(2)移位之后:
K30=K30[13:31] ||K30[47:0] ||K30[0:12];
(3)過(guò)S 盒之后:
K30=S0(K30[13:16])||S0(K30[17:20])||K30[21:31] ||K30[47:0] ||K30[0:12];
(4)加輪常量之后:
K31=S0(K30[13:16])||S0(K30[17:20])||K30[21:31] ||K30[47:34] ||K30[33:29]⊕i||K30[28:0]||K30[0:12].
(5)K31是K31的左32位,移位之后:
K31=K30[26:31] ||K30[47:34] ||K30[33:29]⊕i||K30[28:0] ||K30[0:12] ||S0(K30[13:16])||S0(K30[17:20])||K30[21:25];
(6)過(guò)S 盒之后:
K31=S0(K30[26:29])||S0(K30[30:31] ||K30[47:46])||K30[45:34] ||K30[33:29]⊕i||K30[28:0] ||K30[0:12] ||S0(K30[13:16])||S0(K30[17:20])||K30[21:25];
(7)加輪常量之后:
K32=S0(K30[26:29])||S0(K30[30:31] ||K30[47:46])||K30[45:34] ||K30[33:29]⊕i||K30[28:22] ||K30[21:17]⊕i||K30[16:0] ||K30[0:12] ||S0(K30[13:16])||S0(K30[17:20])||K30[21:25].
K32是K32左32 位, 可以看出K32已知32+13+4+4+5 = 58 位, 剩余22 位未知, 可以通過(guò)窮舉的方式獲得初始密鑰, 即初始密鑰搜索空間降至222.
本文使用一臺(tái)普通的筆記本電腦進(jìn)行實(shí)驗(yàn),處理器為AMD A4-Series A4-5 000 四核,操作系統(tǒng)為64 位Windows 7 旗艦版SP1,內(nèi)存為4 GB.采用使用DVEC++ 5.1 軟件編程.
本文ESF 算法中的故障注入,是通過(guò)編程修改相關(guān)語(yǔ)句來(lái)實(shí)現(xiàn)的.實(shí)驗(yàn)過(guò)程中的由于樣本選取的隨機(jī)性及樣本空間有限,在恢復(fù)最后一輪輪密鑰的過(guò)程中,實(shí)際需要的故障密文數(shù)量會(huì)在理論值周圍波動(dòng).我們進(jìn)行了多組實(shí)驗(yàn),現(xiàn)僅列出其中10 組如表3 所示,表4列舉了序號(hào)1 的實(shí)驗(yàn)結(jié)果.
表3 差分故障攻擊ESF 算法的實(shí)驗(yàn)數(shù)據(jù)
表4 恢復(fù)輪密鑰的一組實(shí)驗(yàn)數(shù)據(jù)
固定明文和密鑰,明文取0123456789ABCDEF,密鑰取0123456789ABCDEFFEDC,加密后,獲得的正確密文為9F68B9406A42D352.采用本文方法,計(jì)算出第32 輪的子密鑰504CAFDC、 第31 輪子密鑰76236A65 以及第30 輪子密鑰F61629EB.這與未注入故障前,正確運(yùn)行密碼算法程序時(shí)得出的最后3 輪子密鑰一致,驗(yàn)證了本方法的正確性.
根據(jù)表3 所列的實(shí)驗(yàn)數(shù)據(jù),當(dāng)恢復(fù)第32、31、30 輪子密鑰時(shí),分別需要進(jìn)行多次不等的故障注入,但最終的總計(jì)結(jié)果體現(xiàn)了計(jì)算攻擊時(shí)所需故障密文數(shù)量為10.3 個(gè),就能夠恢復(fù)最后3 輪子密鑰.接近理論所需的故障密文數(shù)量.
本文針對(duì)密碼算法ESF 改進(jìn)的差分故障攻擊,其明密文對(duì)數(shù)量約為10 個(gè),時(shí)間復(fù)雜度為222,表5 描述了其他針對(duì)ESF 算法的攻擊方法以供對(duì)比.
表5 針對(duì)ESF 算法的攻擊方法對(duì)比表
高紅杰等人[22]研究了ESF 算法抵抗不可能差分攻擊的能力,基于一條8 輪不可能差分路徑,根據(jù)輪密鑰之間的關(guān)系,對(duì)12 輪ESF 算法進(jìn)行了攻擊,攻擊12 輪ESF 算法所需的數(shù)據(jù)復(fù)雜度為253,時(shí)間復(fù)雜度為260.23.尹軍等人[23]通過(guò)建立相關(guān)密鑰下的MILP 模型,利用搜索到的11 輪相關(guān)密鑰差分特征,提出了13 輪的相關(guān)密鑰差分攻擊,攻擊的數(shù)據(jù)復(fù)雜度為247,時(shí)間復(fù)雜度為266.李明明等人[24]利用密鑰編排算法部分子密鑰間存在的依賴關(guān)系,給出了ESF 算法的13 不可能差分分析,其時(shí)間復(fù)雜度為277.39,數(shù)據(jù)復(fù)雜度為261.99個(gè)選擇明文.徐朋[25]通過(guò)在28 到32 輪右半部分導(dǎo)入共約24 次故障,將密鑰搜索空間降至222,此方法故障注入要求難度大,需要在輪函數(shù)輸入前的8 個(gè)半字節(jié)狀態(tài)上同時(shí)發(fā)生故障.
本文方法相較于前3 種方法,有故障注入操作這一技術(shù)要求,但是時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度相對(duì)來(lái)說(shuō)降低不少,這得益于差分故障攻擊自身的優(yōu)勢(shì); 相較于第4 種同樣的差分故障攻擊,本文不需要有高要求的故障注入手段,例如,本文不需要限定在一輪的某個(gè)位置或者某一部分注入故障,而是可以任意在一輪中隨機(jī)注入故障,然后充分完整地分析其故障擴(kuò)散的規(guī)律,找到此攻擊方法.而文獻(xiàn)[25]中,恢復(fù)最后3 輪密鑰時(shí),將注入故障限定在右半部分密文的每個(gè)半字節(jié)上,極大地增大了實(shí)現(xiàn)難度.因此本文針對(duì)ESF 的攻擊方法,是目前存在的研究中最優(yōu)的方法.
本文提出了一種針對(duì)置換層為拉線型的密碼算法ESF 的改進(jìn)的差分故障攻擊.通過(guò)選定最后3 輪,分析故障擴(kuò)散的程度,分別注入6 次、2 次、2 次故障,共10 次故障,并結(jié)合差分表能夠分析出最后3 輪輪密鑰.結(jié)合最后3 輪輪密鑰和密鑰編排,可將恢復(fù)主密鑰的計(jì)算復(fù)雜度降至222.在本章的差分故障分析中,為了保證方法的通用性,且避免最優(yōu)情況的偶然性,分析過(guò)程都是利用概率較大的情況進(jìn)行分析,例如本文分析中,如果故障影響的比特?cái)?shù)越多,密鑰分析難度越低,但由于故障傳播路徑中至少產(chǎn)生2 個(gè)比特故障,且產(chǎn)生2 比特故障的概率較大,所以會(huì)優(yōu)先利用實(shí)驗(yàn)中產(chǎn)生2 比特故障的情況進(jìn)行保守分析.這種辦法通用性強(qiáng),還可以用于其他具有類似置換層的密碼算法中,分析置換層故障的傳播特性和S 盒的差分分布,可得到全部或部分密鑰.另外,由于S 盒的一些抗差分性質(zhì),導(dǎo)致分析出來(lái)的某處S 盒的輸入值不唯一的現(xiàn)象.所以,下一步,將針對(duì)S 盒的差分分布和其差分均勻度進(jìn)行研究并改善,加強(qiáng)抵抗此類差分故障分析.