基于ESF密碼算法改進的差分故障攻擊①

孔 曼,譚 林,王云麗,龍 敏

1(湖南天河國云科技有限公司,長沙 410100)

2(長沙理工大學 計算機與通信工程學院,長沙 410114)

20世紀70年代中期,分組密碼的研究開始興起,至今信息安全領(lǐng)域的學者們已經(jīng)取得了許多豐碩的研究成果.近年來,隨著物聯(lián)網(wǎng)的發(fā)展,無線傳感器網(wǎng)絡[1]和無線射頻技術(shù)[2]的應用愈來愈廣泛.輕量級分組密碼的出現(xiàn)解決了微型計算設(shè)備計算能力有限、低功耗的問題,且其加密速度快、易于硬件實現(xiàn)、能夠應用于資源受限的環(huán)境中,還具有較高的安全性,所以自問世以來就一直是密碼學界關(guān)注的焦點.然而,隨著信息技術(shù)的高速發(fā)展,人們對于信息的價值流通具有高要求,雖然這些技術(shù)通過開放性的計算機網(wǎng)絡實現(xiàn)信息交換和共享,同時也帶來了交互效率低、安全保障低等問題.

此外,區(qū)塊鏈+物聯(lián)網(wǎng)[3]是未來的發(fā)展方向,區(qū)塊鏈技術(shù)可以為物聯(lián)網(wǎng)提供點對點直接互聯(lián)的方式來傳輸數(shù)據(jù),并且,區(qū)塊鏈的密碼機制[4]能夠為物聯(lián)網(wǎng)中的信息傳輸創(chuàng)造安全的環(huán)境.尤其在資源受限的物聯(lián)網(wǎng)節(jié)點中需要對數(shù)據(jù)進行加密時,不可避免地引入具有占用資源少、功耗低、效率高、易于實現(xiàn)等優(yōu)勢的輕量級密碼算法,同時對密碼算法的安全性提出了更高的要求.

現(xiàn)在的輕量級分組密碼算法大都受到DES[5]和AES[6]設(shè)計原理的影響,目前已有許多的輕量級密碼算法陸續(xù)提出,有非常經(jīng)典的輕量級分組加密算法LBlock[7]、LED[8]、MIBS[9]、KLEIN[10]等,還有近兩年的新秀,如Midori[11]、HBcipher[12]、Surge[13]等.然而這些實際用于物聯(lián)網(wǎng)設(shè)備中的輕量級分組密碼算法日益凸顯出安全漏洞,所以需要對該類算法進行分析研究,不斷完善攻擊過程與方法,以實現(xiàn)密碼算法的更新?lián)Q代,提升輕量級分組密碼算法的防御能力,進一步提升區(qū)塊鏈中密碼技術(shù)的安全性.

故障攻擊是一種側(cè)信道攻擊方法,于1997年被Boneh 等人[14]提出,并用此方法攻擊了基于CRT 算法實現(xiàn)的RSA 簽名密鑰,意味著首次將密碼故障應用于密碼分析.同年,Biham 等人首次提出了差分故障攻擊[15]并且成功分析了DES 算法.此后,差分故障攻擊被廣泛應用于公鑰密碼算法、分組密碼算法等等.完成差分故障攻擊最重要的一點就是在加密設(shè)備中引進故障,如電壓瞬變、外部時鐘驟變、激光束、X-射線等.差分故障攻擊已經(jīng)應用到了許多的輕量級密碼算法分析中.文獻[16]以比特為單位進行故障注入,有效地攻擊GIFT 算法; 文獻[17]針對SKINNY 密碼算法提出了恢復主密鑰平均需要10 個半字節(jié)故障,且通過了大量的模擬驗證; 文獻[18]利用S 盒的差分不均勻性,在最后一輪注入兩次8 個半字節(jié)型的故障,快速恢復了最后一輪密鑰的信息; 文獻[19]提出了隨機注入2 字節(jié)故障的模型,兩對正誤密文就可以在不窮舉搜索的情況下檢索整個128 位AES 密鑰; 文獻[20]提出了在密鑰調(diào)度過程中注入一個字節(jié)型故障,僅需4 個錯誤的密文確定整個密鑰.

本文通過分析ESF[21]的算法結(jié)構(gòu),提出了一種差分故障攻擊方法.此方法針對結(jié)構(gòu)中按位進行運算的算法具有通用性.此攻擊方法的主要思想是,在S 盒運算前注入錯誤故障,結(jié)合差分方程與S 盒在不同故障條件下輸出差分不均勻性,進而獲取內(nèi)部狀態(tài)信息,最后分析得出初始密鑰.共需要約10 個故障密文,可將計算復雜度降為222.

1 ESF 算法介紹

1.1 加密流程

ESF 算法是一個基于變種的Feistel 結(jié)構(gòu)的加密算法,輪函數(shù)采用的是SPN 代換置換網(wǎng)絡形式,其整體結(jié)構(gòu)借鑒于LBlock 算法,其中的置換層是仿照了PRESENT 算法的按位置換形式.

算法流程包含了輪密鑰異或、非線性變換、線性擴散、中間狀態(tài)異或與移位操作.ESF 算法的分組長度為64 比特,初始密鑰80 比特,迭代輪數(shù)為32 輪.加密流程如圖1,數(shù)據(jù)輸入分成左右兩個部分,令P=L0||R0表示64 位明文,C=L32||R32表示64 位密文.Ki(i=1,2,…,32)是每一輪迭代加密的輪密鑰.輪函數(shù)F中包含S 盒非線性變換和P 盒按位置換.

圖1 ESF 算法的加密流程

1.2 輪密鑰生成

ESF 算法的初始密鑰是80 位,記為K=k79k78…k0,初始密鑰的左邊32 位作為第一輪輪密鑰K1,Ki(i=1,2,…,32)是80 位的密鑰中間狀態(tài),輪密鑰生成算法如算法1 所示.

算法1.ESF 算法的密鑰擴展方案輸入: 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].⊕

2 ESF 算法結(jié)構(gòu)分析

2.1 ESF 算法置換層結(jié)構(gòu)分析

ESF 共有8 個S 盒,前4 個S 盒(S7-S4)的輸出去往奇數(shù)號的S 盒(S7、S5、S3、S1),后4 個S 盒(S3-S0)的輸出去往偶數(shù)號的S 盒(S6、S4、S2、S0).具體傳播位置置換如圖2 所示,其中粗線表示有故障的傳播,Ii(i=0,1,…,7)是右半明文中間狀態(tài)的半字節(jié)表示形式.

圖2 ESF 的置換圖

2.2 ESF 算法S 盒差分分布情況

假設(shè)a是一個半字節(jié)作為某個S 盒的輸入.在S 盒輸入前,導入隨機故障f,即為S 盒的輸入差分.f*表示為S 盒的輸出差分,則滿足差分公式:

已知每一個輸入差分都有一個相應的輸出差分,且輸入差分有24= 16 種可能,對應的輸出差分有4-8 種可能,并且每一對(f,f*)能夠得到輸入值a的集合,集合內(nèi)元素的個數(shù)為2 或者4.正是由于分布的不均勻性,成為了差分故障攻擊的突破口.由于篇幅限制,文中只列出S7盒的差分分布表.ESF 算法S7盒的差分性如表1 所示(ID表示輸入差分,OD表示輸出差分).

表1 ESF 中S7 盒的差分分布表

2.3 ESF 算法差分擴散規(guī)律

已經(jīng)知道ESF 算法的置換層的基本運算單位是比特.在S 盒運算前隨機注入1 比特故障,那么無論在哪個S 盒,輸入差分只可能為0001、0010、0100、1 000這4 個中的任何一個,由這4 個輸入差分,可列出每個S 盒對應的輸出差分,以S7盒為例,表2 列出了S7盒的輸入所對應的所有可能出現(xiàn)的輸出差分(OD表示輸出差分).

表2 ESF 中S7 盒每一個輸出差分可能的輸入

觀察表2 的輸出差分,可知,當輸入差分僅為0001、0010、0100、1 000 時,經(jīng)過S 盒后,至少能發(fā)生2 比特的故障錯誤.再分析每個S 盒的可能的輸入,可以發(fā)現(xiàn)經(jīng)過S 盒后,發(fā)生2 比特和3 比特故障錯誤的概率較大,且發(fā)生2 比特故障錯誤的概率大于發(fā)生3 比特故障錯誤的概率,發(fā)生4 比特故障錯誤的概率最大也才1/8,因此,在S 盒運算前注入1 比特故障,至少將導致2 個半字節(jié)出現(xiàn)錯誤.本文將以2 比特故障錯誤進行保守分析.

在S 盒運算前注入1 比特故障,經(jīng)過3 輪迭代運算后,只導致兩個S 盒的輸出半字節(jié)出現(xiàn)故障錯誤的平均概率僅為0.019 5,所以在分析過程中可以忽略此種情況.本文將以最后一輪S 盒輸出半字節(jié)出現(xiàn)故障的個數(shù)為3 的情況進行保守分析.

3 ESF 的差分故障攻擊

3.1 攻擊條件

(1)攻擊者有能力選擇一個明文進行加密,并獲得相應的正確故障密文;

(2)攻擊者能夠誘導1 比特故障輸入到加密的第30 輪寄存器中;

(3)故障位置和值均未知.

3.2 攻擊過程及分析

3.2.1 攻擊流程

(1)選擇明文P進行加密,獲得正確密文C.

(2)恢復最后一輪輪密鑰,步驟如下:

1)對同樣的明文P進行加密,在第30 輪輪函數(shù)運行前注入1 比特隨機故障到寄存器B30Nj(1≤j≤8,表示在第30 輪、第j個S 盒位置)中,獲得錯誤密文D1.將正確密文C與錯誤密文D1 進行異或,得到密文差分ΔD1 (此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察最后一輪右邊32 比特密文差分,得到準確的進入逆運算的密文差分),密文差分經(jīng)過逆P 盒置換,得到最后一輪S 盒的輸出差分.

2)查找表2,由最后一輪S 盒的輸出差分列出相應S 盒正確輸入的候選值.

3)在第30 輪輪函數(shù)運算前,多次注入1 比特的隨機故障,并重復步驟1)和步驟2),不斷縮小S 盒正確輸入的候選值的個數(shù),直到剩下唯一一個.此時得到的就是S 盒的正確輸入值.

4)最后將正確S 盒的輸入值與正確密文的左邊32 比特異或,即可得到最后一輪輪密鑰.

(3)恢復第31 輪輪密鑰,步驟如下:

1)結(jié)合最后一輪輪密鑰和最后一輪輸出,可逆推得到第31 輪正確輸出.此時,在第29 輪注入1 比特的隨機故障到位置B29Nj(1≤j≤8)中,獲得錯誤密文D2,結(jié)合最后一輪輪密鑰,可逆推得到第31 輪故障輸出.將第31 輪的正確輸出與故障輸出異或,得到中間狀態(tài)密文差分(此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察第31 輪的輸出的右32 比特密文差分,得到準確的進入逆運算的密文差分).密文差分經(jīng)過逆P 盒置換,得到第31 輪S 盒的輸出差分.

2)查找表2,由第31 輪S 盒的輸出差分列出相應S 盒正確輸入的候選值.

3)在第29 輪輪函數(shù)運算前,多次注入1 比特的隨機故障,并重復步驟1)和步驟2),不斷縮小S 盒正確輸入的候選值的個數(shù),直到剩下唯一一個.此時得到的就是S 盒的正確輸入值.

4)最后將正確S 盒的輸入值與正確密文的左邊32 比特異或,即可得到第31 輪輪密鑰.

(4)恢復第30 輪輪密鑰,步驟如下:

1)結(jié)合第31 輪輪密鑰和第31 輪輸出,可逆推得到第30 輪正確輸出.此時,在第28 輪注入1 比特的隨機故障到寄存器B28Nj(1≤j≤8)中,獲得錯誤密文D3,結(jié)合第31 輪輪密鑰,可逆推得到第30 輪故障輸出.將第30 輪的正確輸出與故障輸出異或,得到中間狀態(tài)密文差分(此外,密文差分還受上一輪輸出的左邊32 比特的差分影響,但可直接觀察第30 輪的輸出的右邊32 比特密文差分,得到準確的進入逆運算的密文差分).密文差分經(jīng)過逆P 盒置換,得到第30 輪S 盒的輸出差分.

2)通過與(3)類似的方法分析出第30 輪輪密鑰.

3.2.2 差分故障攻擊方法分析

由第3.2.1 節(jié)已經(jīng)知道,在第30 輪S 盒運算前隨機注入1 比特故障,在第32 輪至少能得到3 個錯誤的S 盒輸出,在這樣的情況下,恢復第32 輪的輪密鑰所需要的錯誤密文則減少到6 個(平均每兩對S 盒的輸入輸出差分所對應的可能輸入值的集合能確定唯一的S 盒半字節(jié)輸入值).

由于是在第30 輪的S 盒運算前注入的故障錯誤,因此,在恢復最后一輪輪密鑰的同時,也可以得到第31 輪中至少12 個錯誤的S 盒輸出,那么只需要在第29 輪的S 盒運算前再注入2 比特的故障錯誤,得到2 個錯誤密文就可以恢復第31 輪輪密鑰; 在恢復最后一輪輪密鑰時,已經(jīng)得到第30 輪的6 個錯誤的S 盒輸出,在恢復第31 輪輪密鑰時,已經(jīng)得到第30 輪的至少4 個錯誤的S 盒輸出,那么只需在第28 輪S 盒運算前注入2 比特故障,即可恢復第30 輪輪密鑰.綜上所述,理論上只需要約10 個錯誤密文就可以恢復最后3 輪輪密鑰K32、K31、K30.

3.2.3 密鑰推斷過程

以下步驟通過恢復出的最后3 輪輪密鑰K32、K31、K30,來推斷80 比特的完整子密鑰,其中“||”表示連接符.

(1)根據(jù)密鑰的擴展方案,K30是K30的左32 位,K30=K30[0:31] ||K30[47:0];

(2)移位之后:

K30=K30[13:31] ||K30[47:0] ||K30[0:12];

(3)過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)過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 位未知, 可以通過窮舉的方式獲得初始密鑰, 即初始密鑰搜索空間降至222.

4 實驗結(jié)果與分析

4.1 實驗配置

本文使用一臺普通的筆記本電腦進行實驗,處理器為AMD A4-Series A4-5 000 四核,操作系統(tǒng)為64 位Windows 7 旗艦版SP1,內(nèi)存為4 GB.采用使用DVEC++ 5.1 軟件編程.

4.2 攻擊實驗結(jié)果

本文ESF 算法中的故障注入,是通過編程修改相關(guān)語句來實現(xiàn)的.實驗過程中的由于樣本選取的隨機性及樣本空間有限,在恢復最后一輪輪密鑰的過程中,實際需要的故障密文數(shù)量會在理論值周圍波動.我們進行了多組實驗,現(xiàn)僅列出其中10 組如表3 所示,表4列舉了序號1 的實驗結(jié)果.

表3 差分故障攻擊ESF 算法的實驗數(shù)據(jù)

表4 恢復輪密鑰的一組實驗數(shù)據(jù)

固定明文和密鑰,明文取0123456789ABCDEF,密鑰取0123456789ABCDEFFEDC,加密后,獲得的正確密文為9F68B9406A42D352.采用本文方法,計算出第32 輪的子密鑰504CAFDC、 第31 輪子密鑰76236A65 以及第30 輪子密鑰F61629EB.這與未注入故障前,正確運行密碼算法程序時得出的最后3 輪子密鑰一致,驗證了本方法的正確性.

根據(jù)表3 所列的實驗數(shù)據(jù),當恢復第32、31、30 輪子密鑰時,分別需要進行多次不等的故障注入,但最終的總計結(jié)果體現(xiàn)了計算攻擊時所需故障密文數(shù)量為10.3 個,就能夠恢復最后3 輪子密鑰.接近理論所需的故障密文數(shù)量.

4.3 對比分析

本文針對密碼算法ESF 改進的差分故障攻擊,其明密文對數(shù)量約為10 個,時間復雜度為222,表5 描述了其他針對ESF 算法的攻擊方法以供對比.

表5 針對ESF 算法的攻擊方法對比表

高紅杰等人[22]研究了ESF 算法抵抗不可能差分攻擊的能力,基于一條8 輪不可能差分路徑,根據(jù)輪密鑰之間的關(guān)系,對12 輪ESF 算法進行了攻擊,攻擊12 輪ESF 算法所需的數(shù)據(jù)復雜度為253,時間復雜度為260.23.尹軍等人[23]通過建立相關(guān)密鑰下的MILP 模型,利用搜索到的11 輪相關(guān)密鑰差分特征,提出了13 輪的相關(guān)密鑰差分攻擊,攻擊的數(shù)據(jù)復雜度為247,時間復雜度為266.李明明等人[24]利用密鑰編排算法部分子密鑰間存在的依賴關(guān)系,給出了ESF 算法的13 不可能差分分析,其時間復雜度為277.39,數(shù)據(jù)復雜度為261.99個選擇明文.徐朋[25]通過在28 到32 輪右半部分導入共約24 次故障,將密鑰搜索空間降至222,此方法故障注入要求難度大,需要在輪函數(shù)輸入前的8 個半字節(jié)狀態(tài)上同時發(fā)生故障.

本文方法相較于前3 種方法,有故障注入操作這一技術(shù)要求,但是時間復雜度和數(shù)據(jù)復雜度相對來說降低不少,這得益于差分故障攻擊自身的優(yōu)勢; 相較于第4 種同樣的差分故障攻擊,本文不需要有高要求的故障注入手段,例如,本文不需要限定在一輪的某個位置或者某一部分注入故障,而是可以任意在一輪中隨機注入故障,然后充分完整地分析其故障擴散的規(guī)律,找到此攻擊方法.而文獻[25]中,恢復最后3 輪密鑰時,將注入故障限定在右半部分密文的每個半字節(jié)上,極大地增大了實現(xiàn)難度.因此本文針對ESF 的攻擊方法,是目前存在的研究中最優(yōu)的方法.

5 結(jié)束語

本文提出了一種針對置換層為拉線型的密碼算法ESF 的改進的差分故障攻擊.通過選定最后3 輪,分析故障擴散的程度,分別注入6 次、2 次、2 次故障,共10 次故障,并結(jié)合差分表能夠分析出最后3 輪輪密鑰.結(jié)合最后3 輪輪密鑰和密鑰編排,可將恢復主密鑰的計算復雜度降至222.在本章的差分故障分析中,為了保證方法的通用性,且避免最優(yōu)情況的偶然性,分析過程都是利用概率較大的情況進行分析,例如本文分析中,如果故障影響的比特數(shù)越多,密鑰分析難度越低,但由于故障傳播路徑中至少產(chǎn)生2 個比特故障,且產(chǎn)生2 比特故障的概率較大,所以會優(yōu)先利用實驗中產(chǎn)生2 比特故障的情況進行保守分析.這種辦法通用性強,還可以用于其他具有類似置換層的密碼算法中,分析置換層故障的傳播特性和S 盒的差分分布,可得到全部或部分密鑰.另外,由于S 盒的一些抗差分性質(zhì),導致分析出來的某處S 盒的輸入值不唯一的現(xiàn)象.所以,下一步,將針對S 盒的差分分布和其差分均勻度進行研究并改善,加強抵抗此類差分故障分析.