對(duì)HIGHT密碼改進(jìn)的代數(shù)故障攻擊

陳 浩,王 韜,周 平,周 林,馬云飛,王曉晗

1(解放軍軍械工程學(xué)院 信息工程系,石家莊 050003) 2(車船軍代局駐長(zhǎng)沙地區(qū)軍代室,長(zhǎng)沙 410101)

1 引 言

故障攻擊是一種利用密碼實(shí)現(xiàn)所依附的物理設(shè)備平臺(tái)在外界強(qiáng)電流、高電壓、強(qiáng)輻射等手段干擾下可能出現(xiàn)的寄存器故障或運(yùn)算錯(cuò)誤來(lái)恢復(fù)密鑰的攻擊方法,最早由Boneh等[1]于1996年提出,并成功用于基于CRT實(shí)現(xiàn)的RSA簽名算法.隨后,Biham和Shamir[2]將故障攻擊和差分分析的思想相結(jié)合,提出差分故障分析,并成功地攻擊了DES算法.此后研究者將攻擊對(duì)象擴(kuò)展至ECC等[3]其他公鑰密碼,LED[4],PRESENT[5]等分組密碼,MICKEY[6],Trivium[7]等序列密碼.然而,傳統(tǒng)的差分故障分析方法在某些攻擊場(chǎng)景下存在一些不足,當(dāng)故障傳播特征復(fù)雜、故障差分不易確定、分析的密碼算法采用復(fù)雜非線性部件時(shí),傳統(tǒng)的差分故障分析依賴手工故障傳播分析,難度較大.如果能將分析過(guò)程轉(zhuǎn)化為某類問(wèn)題并將其自動(dòng)化實(shí)現(xiàn),則有望彌補(bǔ)傳統(tǒng)差分故障分析的不足[8].

在eSmart 2010會(huì)議上,N.Courtois等首次將代數(shù)攻擊和故障攻擊相結(jié)合起來(lái),提出了代數(shù)故障分析方法,將分析過(guò)程轉(zhuǎn)化為代數(shù)方程組的自動(dòng)構(gòu)建和求解問(wèn)題,并成功用于DES,僅需窮舉24位密鑰并在加密13輪注入1bit故障即可恢復(fù)全部密鑰信息.此后攻擊對(duì)象趨于多樣化,已擴(kuò)展至LED[9],PRESENT[10],Piccolo[11]等分組密碼,Trivium[12]等序列密碼.同傳統(tǒng)差分故障分析相比,代數(shù)故障攻擊能夠充分利用故障攻擊中泄露出來(lái)的故障信息,具有攻擊通用性強(qiáng)、方程可自動(dòng)化求解的優(yōu)點(diǎn),為密碼分析提供了一種新的自動(dòng)化、通用化分析手段.

HIGHT算法[13]是一種典型的輕量級(jí)分組密碼,設(shè)計(jì)時(shí)采用ARX結(jié)構(gòu)(是一種由模2n加運(yùn)算、循環(huán)移位運(yùn)算、異或運(yùn)算按照一定順序組成的密碼結(jié)構(gòu)),執(zhí)行效率高,非常適合在微型設(shè)備中使用,其安全性研究具有重要意義,自2006年提出以來(lái)密碼界對(duì)其安全性開(kāi)展了一系列研究.

文獻(xiàn)[14]采用面向字節(jié)的故障模型,對(duì)HIGHT密碼提出一種差分故障攻擊方法,通過(guò)窮舉4字節(jié)白化密鑰,并分別在密碼倒數(shù)第3輪和倒數(shù)第4輪共注入約32個(gè)故障可恢復(fù)HIGHT 全部128 bit 密鑰信息.但由于文獻(xiàn)[14]采用的是傳統(tǒng)故障分析方法,分析過(guò)程繁瑣,故障信息利用率低,所需故障樣本量較大,導(dǎo)致攻擊方法有效性和通用性不強(qiáng).文獻(xiàn)[15]對(duì)HIGHT密碼提出一種代數(shù)故障分析方法,將文獻(xiàn)[14]的手工分析方法轉(zhuǎn)化代數(shù)方程組自動(dòng)構(gòu)建和求解問(wèn)題,成功將攻擊擴(kuò)展至加密倒數(shù)第6輪,將攻擊所需故障次數(shù)由32次減小為15次(最好情況下僅需9次).利用不同變量注入故障所產(chǎn)生的故障密文不同來(lái)確定故障位置，但當(dāng)故障注入深度大于6時(shí)，注入到中間變量xr,2m的故障均會(huì)使所有的密文輸出產(chǎn)生錯(cuò)誤,此時(shí)文獻(xiàn)[15]確定故障具體位置的方法失效.

本文對(duì)HIGHT密碼提出一種改進(jìn)的代數(shù)故障分析方法,將攻擊成功擴(kuò)展至密碼加密第25輪,并從理論角度分析且給出了攻擊所需故障注入次數(shù)和成功率.在密碼第25輪加密注入單字節(jié)隨機(jī)故障下,5次故障注入可在143.70s內(nèi)恢復(fù)全部主密鑰信息,最好情況下僅需4次即能以成功率90%,在551.26s內(nèi)恢復(fù)全部主密鑰信息.此外,本文還對(duì)密碼加密26輪、27輪和加密進(jìn)行了攻擊,恢復(fù)全部主密鑰信息的故障注入次數(shù)分別為7次、11次和23次,實(shí)際成功率分別為90.86%,89.83%和87.48%,與理論分析基本一致.與現(xiàn)有HIGHT故障攻擊相比,文中所需的故障注入次數(shù)是最小的.

2 HIGHT算法

2.1 符號(hào)說(shuō)明

-⊕,A<<

-′:注入故障之后密碼的內(nèi)部狀態(tài)或輸出;

-#S:有限集合S的勢(shì);

-P,C:64比特明文和密文;

-MK=MK15‖…MK1‖MK0:16字節(jié)主密鑰;

-WKi:白化密鑰WKi,0≤i≤7;

-SKk:輪子密鑰,0≤k≤127;

-Xr=xr,7‖…xr,1‖xr,0:密碼第r加密的80比特輸入變量,1≤r≤32;

2.2 HIGHT加密過(guò)程

本節(jié)對(duì)HIGHT算法進(jìn)行簡(jiǎn)單介紹,其完整描述可參見(jiàn)文獻(xiàn)[13].HIGHT是一個(gè)32輪迭代輕量級(jí)分組密碼算法,其分組長(zhǎng)度和密鑰長(zhǎng)度分別為64 和128 位,設(shè)計(jì)時(shí)采用廣義Feistel結(jié)構(gòu),輪函數(shù)沒(méi)有使用S盒,只采用ARX操作.HIGHT密碼算法由密鑰擴(kuò)展、初始變換、輪加密、末輪變換4個(gè)子過(guò)程構(gòu)成:

密鑰擴(kuò)展.密鑰擴(kuò)展算法使用主密鑰MK按照式(1)和式(2)生成初始變換和末變換使用的8字節(jié)的白化密鑰WKi(0≤i≤7)和每輪加密使用的4字節(jié)子密鑰SKi(0≤i≤127):

WKi=MKi+12(i= 0,1,2,3)

(1)

WKi=MKi-4(i= 4,5,6,7)

(2)

(3)

(4)

初始變換.明文P根據(jù)式(5)(6),經(jīng)初始變換成加密首輪的輸入X0:

X0,4=P4?WK2;X0,5=P5;

(5)

X0,6=P6⊕WK3;X0,7=P7

(6)

輪加密函數(shù).算法執(zhí)行32輪加密運(yùn)算,將第i(0≤i≤31)輪輸出Xi按照式(7)～(14)轉(zhuǎn)換成第i+1輪輸入Xi+1.

(7)

Xi+1,1=Xi,0

(8)

(9)

Xi+1,3=Xi,2

(10)

(11)

Xi+1,5=Xi,4

(12)

(13)

Xi+1,7=Xi,6

(14)

每輪加密使用兩個(gè)線性函數(shù)F0和F1,如式(15)(16)所示:

F0(x)=x<<<1⊕x<<<2⊕x<<<7

(15)

F1(x)=x<<<3⊕x<<<4⊕x<<<6

(16)

末輪變換.算法在執(zhí)行完32輪加密運(yùn)算后,將X32根據(jù)式(17)經(jīng)末變換轉(zhuǎn)換成密文C:

(17)

3 HIGHT改進(jìn)代數(shù)故障分析

3.1 故障模型設(shè)定

本節(jié)采用面向單字節(jié)的隨機(jī)故障模型,如圖1所示,其基本假設(shè)如下:

攻擊者能夠借助低成本故障注入技術(shù)(如,時(shí)鐘毛刺,虧電效應(yīng)、電壓峰值等[16])向HIGHT算法加密r(0≤r≤32)輪加密注入單字節(jié)隨機(jī)故障,但故障的具體值和具體位置均未知.此外,攻擊者能夠選擇被加密的明文,并且獲取同一個(gè)密鑰作用下的正確密文和錯(cuò)誤密文.由下頁(yè)圖1可知,當(dāng)攻擊者向HIGHT第25輪加密注入單字節(jié)隨機(jī)故障時(shí),故障傳播特征非常復(fù)雜,很難應(yīng)用傳統(tǒng)差分分析方法進(jìn)行密鑰分析.同時(shí),由于產(chǎn)生的密文輸出全部發(fā)生錯(cuò)誤,很難利用文獻(xiàn)[15]中的方法對(duì)故障位置和差分信息進(jìn)行確定和表示.

3.2 故障傳播特性分析

性質(zhì)1.假設(shè)攻擊者向密碼r輪第α個(gè)中間變量注入隨機(jī)單字節(jié)故障,定義集合:

為故障傳播過(guò)程中第n輪受影響的中間變量,則有下列結(jié)論成立,其中0≤m≤3:

1)#Φ(r,α)r=1;

圖1 故障模型Fig.1 Fault model

證明:對(duì)于結(jié)論①,由圖1可知,顯然成立.

對(duì)于結(jié)論②,不失一般性,假設(shè)攻擊者向密碼r輪xr,α注入一個(gè)單字節(jié)故障,則有:

i)當(dāng)α=2m時(shí),如圖2所示,可知下一輪故障將向xr+1,2(m+1)和xr+1,2m+1兩個(gè)中間狀態(tài)變量擴(kuò)散,所以有#Φ(r,2m)r+1=#Φ(r,2m)r+1.

圖2 故障位置為xr，2mFig．2 Faultwasinjectedinxr，2m圖3 故障位置為xr，2m+1Fig．3 Faultwasinjectedinxr，2m+1

ii)當(dāng)α=2m+1時(shí),如圖3所示,可知下一輪故障將僅向xr,2(m+1)一個(gè)中間狀態(tài)變量擴(kuò)散,所以有#Φ(r,2m+1)r+1=#Φ(r,2m+1)r.

對(duì)于結(jié)論③,由結(jié)論②證明過(guò)程可知,故障位置為xr,2m的故障在下一輪傳播過(guò)程中會(huì)擴(kuò)散到xr+1,2(m+1)和xr+1,2m+1,故障位置為xr,2m+1的故障在下一輪擴(kuò)散中會(huì)擴(kuò)散到xr+1,2(m+1),因此當(dāng)故障沒(méi)有影響第n輪全部8字節(jié)中間變量時(shí),如圖1所示,顯然有#Φ(r,α)n+1=#Φ(r,α)n+1,n>r.反之,則有#Φ(r,α)n+1=#Φ(r,α)n=8,所以結(jié)論③成立.證畢.

3.3 HIGHT改進(jìn)代數(shù)故障分析思想

由性質(zhì)1證明過(guò)程可知,當(dāng)故障注入輪r=25時(shí),注入到xr,2m的故障會(huì)導(dǎo)致所有的密文輸出產(chǎn)生錯(cuò)誤,注入到xr,2m+1的故障會(huì)使8字節(jié)密文輸出中的7個(gè)字節(jié)密文輸出產(chǎn)生錯(cuò)誤,此時(shí)如果按照文獻(xiàn)[15]的方法很難確定故障的具體位置,但根據(jù)錯(cuò)誤密文輸出個(gè)數(shù)顯然可以區(qū)分故障是注入在xr,2m還是xr,2m+1,根據(jù)這個(gè)特點(diǎn)利用性質(zhì)1,可以將故障信息表示成代數(shù)方程組(構(gòu)造方法和詳細(xì)過(guò)程見(jiàn)4.3節(jié)),并且在構(gòu)造代數(shù)方程組時(shí)僅需知道故障是注入在xr,2m還是xr,2m+1,而無(wú)需知道故障的具體位置,因此與文獻(xiàn)[15]相比較,改進(jìn)之后的新方法可將攻擊輪擴(kuò)展至r=25.

此外,由于改進(jìn)之后的新方法在故障信息表示過(guò)程中,不依賴于故障具體傳播路徑,因此改進(jìn)之后的新方法具有更強(qiáng)的通用性.

3.4 攻擊基本過(guò)程

HIGHT改進(jìn)的代數(shù)故障攻擊步驟如下:

1)密碼算法等效代數(shù)方程組構(gòu)建.首先選擇明文P和初始密鑰K,運(yùn)行HIGHT密碼算法得到正確的密文輸出C,并構(gòu)建密碼等效代數(shù)方程組;

2)故障注入及利用.保持(P,K)不變,運(yùn)行實(shí)現(xiàn)密碼算法的密碼芯片并設(shè)定故障注入樣本,利用低成本故障注入技術(shù)向密碼芯片注入故障,產(chǎn)生錯(cuò)誤的密文輸出C,并將故障和錯(cuò)誤密文表示成代數(shù)方程組;

3)代數(shù)方程組求解.使用解析器CryptoMinisat解析器對(duì)上面兩步構(gòu)建代數(shù)方程組進(jìn)行求解恢復(fù)密鑰信息;

4 HIGHT改進(jìn)代數(shù)故障攻擊過(guò)程詳述

4.1 密碼等效代數(shù)方程組構(gòu)建

HIGHT密碼等效代數(shù)方程組構(gòu)建過(guò)程中,關(guān)鍵是構(gòu)造ARX、F0(·)、F1(·)、密鑰擴(kuò)散、輪函數(shù)、末變換等線性和非線性組件在比特層面的等效代數(shù)方程組,下面具體給出構(gòu)建方法.

4.1.1 模2n加運(yùn)算代數(shù)方程組構(gòu)建

定義X,Y,Z∈GF(2n),X=(xn-1,xn-2,…,x0),Y=(yn-1,yn-2,…,y0),Z=(zn-1,zn-2,…,z0),x0,y0,z0分別表示X,Y,Z的最低位,則GF(2n)上的模2n加運(yùn)算可表示為:

(18)

4.1.2F0(·)和F1(·)運(yùn)算代數(shù)方程組構(gòu)建

定義X=(x7,x6,…,x0),Y=(y7,y6,…,y0) 分別為函數(shù)F0(·) 和F1(·)的輸入及輸出,則F0(·) 和F1(·) 分別可表示成GF(2)域上的代數(shù)方程數(shù)(*) and (*′):

(19)

4.1.3 密鑰擴(kuò)展方案代數(shù)方程組構(gòu)建

HIGHT密鑰擴(kuò)展方案可以表示成如下代數(shù)方程組,其中Cj和Dj,0≤j≤8,均為8比特變量.

for(i=0;i<7;i++)

for(j=0;j<7;j++)

for(k=0;k<8;k++)

end

end

for(j=0;j<7;j++)

(20)

for(k=0;k<8;k++)

end

end

end

4.1.4 輪函數(shù)代數(shù)方程組構(gòu)建

HIGHT算法 32 輪加密可以表示成如下GF(2)域上的代數(shù)方程組,其中Ei,Fi,Gi,Hi,0≤i≤8,均為8比特變量:

for(i=0;i<31;i++)

for(k=0;k<8;k++)

end

end

for(i=31;i<32;i++)

for(k=0;k<8;k++)

end

end

(21)

4.1.5 末輪變化代數(shù)方程組構(gòu)建

for(k=0;k<8;k++)

end

(22)

4.2 故障信息表示

本節(jié)將提出一種新的故障信息表示方法,該方法適用于故障具體位置未知場(chǎng)景,并能夠?qū)⒐舴椒〝U(kuò)展至密碼第25輪加密.

Zr=Zr,7‖…Zr,1‖Zr,0,1≤r≤32

(23)

(24)

其中μk=0 表示Zi,k為故障注入字節(jié).

此外,使用HW(μ),0≤HW(μ)≤8,來(lái)表示變量μ的漢明重.為將故障差分信息表示為代數(shù)方程組,引入一個(gè)四比特變量Y=(y3…y0)來(lái)表征HW(μ),計(jì)算關(guān)系式如下:

(25)

由上述分析,假設(shè)攻擊者向密碼r輪第α個(gè)中間變量注入一個(gè)隨機(jī)故障,由2.3節(jié)故障傳播特性性質(zhì)1可知:

i)當(dāng)注入故障索引α=2m時(shí),有下列等式成立:

HW(μ)n=n-r+1,r≤n≤32

(26)

ii)當(dāng)故障索引α=2m+1時(shí),有下列等式成立:

(27)

因此在這種情況下,可以使用n-r個(gè)代數(shù)方程組來(lái)表示故障信息.

4.3 代數(shù)方程組求解

本文選取CryptoMinisat解析器對(duì)構(gòu)建的代數(shù)方程組進(jìn)行求解.該解析器采用基于可滿足性問(wèn)題SAT的代數(shù)方程組求解策略,具有高效、不受方程組次數(shù)約束的特點(diǎn),能夠較好的解決代數(shù)方程組構(gòu)建過(guò)程中的布爾切割問(wèn)題.在實(shí)際攻擊中需首先將HIGHT密碼和故障信息表示成布爾代數(shù)方程組并將代數(shù)方程組線性化,然后將線性化的代數(shù)方程組轉(zhuǎn)化為符合CryptoMinisat輸入格式的文本文件,以命令行方式調(diào)用crypt.exe進(jìn)行自動(dòng)求解,有關(guān)CryptoMinisat解析器的使用方法可見(jiàn)參看文獻(xiàn)[15].

4.4 攻擊復(fù)雜度分析

由于本文提出的改進(jìn)代數(shù)故障攻擊的復(fù)雜度主要由故障注入次數(shù)構(gòu)成,因此本節(jié)主要從理論角度對(duì)故障注入次數(shù)N進(jìn)行評(píng)估.

本質(zhì)上,故障分析方法主要利用密碼算法正確/錯(cuò)誤密文輸出同故障傳播過(guò)程中涉及到的相關(guān)密鑰關(guān)系進(jìn)行密鑰破解[8].因此,當(dāng)且僅當(dāng)注入的故障在傳播過(guò)程中涉及到全部的主密鑰信息MK時(shí),攻擊者才能恢復(fù)所有主密鑰信息MK.

為了敘述方便,使用下列表達(dá)式

(28)

表示由A通過(guò)關(guān)系式(*)推導(dǎo)出B.定義集合Ωr,i表示中間變量xr,i能夠推導(dǎo)出的主密鑰集合:

Ωr,i={MKω|xr,i→MKω,1≤r≤32,0≤ω≤15,0≤i≤7}

顯然,由HIGHT密碼末變換可知,有下列推斷成立:

(29)

由密碼密鑰擴(kuò)展方案可知,有下列推斷成立:

(30)

(31)

(32)

由式(29)～式(32)可得:

(33)

此外,由輪加密函數(shù)可知,對(duì)每個(gè)64比特的中間變量

Xr=xr,7‖…xr,1‖xr,0,1≤r≤31,有:

(34)

由式(34)可推斷得到:

Ω25,2m=MK,0≤m≤3

Ω25,2m+1MK,0≤m≤3

所以攻擊者對(duì)HIGHT密碼第25輪加密進(jìn)行攻擊時(shí),注入的隨機(jī)故障中只要有一個(gè)位于xr,2m,故障在傳播中將會(huì)涉及全部主密鑰信息.由于故障注入過(guò)程是完全隨機(jī)的,故障注入到xr,2m和xr,2m+1的概率Pr(α=2m)= Pr(α=2m+1)=1/2,因此注入的故障在傳播過(guò)程中覆蓋所有密鑰信息的概率Pr(Ω=MK)可計(jì)算為:

所以理論上,當(dāng)故障注入總數(shù)N=5時(shí),Pr(Ω=MK)→1攻擊者可以恢復(fù)全部主密鑰信息MK.此外,當(dāng)攻擊者對(duì)加密第26輪,27輪和28輪進(jìn)行攻擊時(shí),由文獻(xiàn)[15]可知,恢復(fù)全部密鑰信息MK故障所需的故障注入總數(shù)分別為N=7，N=11和N=23時(shí)(如表1所示).

4.5 攻擊成功率分析

本節(jié)首先給出故障碰撞的定義.

定義1.如圖4所示,假設(shè)攻擊者同時(shí)向中間變量xr,2m和xr,2m+2注入單字節(jié)隨機(jī)故障β1和β2.當(dāng)故障傳播至加密第r+2輪時(shí),故障值Δ3和Δ2同時(shí)作用于中間變量xr+2,2m+3,且有HW(Δxr+2,2m+3)=φ,則將故障傳播過(guò)程中多個(gè)故障值同時(shí)作用于某個(gè)中間變量的現(xiàn)象稱為故障碰撞.

圖4 故障碰撞示意圖Fig.4 Schematic diagram of fault collision

由故障碰撞定義可知,當(dāng)φ=0時(shí),Δxr+2,2m+3=0,故障值Δ3和Δ2相互抵消,產(chǎn)生的概率為:

當(dāng)故障相互抵消時(shí),會(huì)導(dǎo)致HW(μ)n的值發(fā)生變化,從而導(dǎo)致表示故障信息的代數(shù)方程組在構(gòu)建過(guò)程中出現(xiàn)錯(cuò)誤,最終導(dǎo)致攻擊失敗.

假設(shè)攻擊者向密碼r輪中間變量注入單字節(jié)隨機(jī)故障,故障注入位置為α,攻擊設(shè)定的故障樣本為N,其中發(fā)生在奇數(shù)索引(α=2m+1,0≤m≤3)和偶數(shù)索引(α=2m)的故障在傳播過(guò)程中發(fā)生故障碰撞的次數(shù)分別為s和w,則注入一個(gè)故障時(shí)攻擊的成功率為:

Pr[n=1]=Pr[α=2m](1-Pr(φ=0))s+Pr[α=2m+1]

(35)

因?yàn)楣粼O(shè)定的故障樣本為N,則攻擊的成功率為:

Pr[n=N]=(Pr[n=1])N

(36)

此外,分析圖2可知,當(dāng)攻擊者對(duì)密碼第25輪加密進(jìn)行攻擊,且故障注入位置為x25,2m(0≤m≤3)時(shí),故障碰撞次數(shù)為9次,當(dāng){①,②,③,④,⑤,⑥,⑦,⑧,⑨},但由于①和②，②和③，③和⑥，⑤和⑦，⑥和⑧均不同發(fā)生，因此故障碰撞之后相互抵消的可能項(xiàng)數(shù)為5次.同理，當(dāng)故障注入位置為x25,2m+1時(shí)，故障碰撞點(diǎn)為6個(gè)，故障碰撞之后相互抵消的可能次數(shù)為4次，因此根據(jù)公式(36)可得攻擊成功率為Pr(N=5)=91.6%,同理可分析對(duì)26輪，27輪和28輪攻擊的成功率如表1所示.

表1 攻擊所需故障注入總數(shù)和成功率
Table 1 #fault injections and success rate of the attack

攻擊輪理論故障注入個(gè)數(shù)理論攻擊成功率25591．6%26790．86%271189．83%282387．48%

5 攻擊實(shí)驗(yàn)及分析比較

在普通PC上(CPU為Intel(R),Core(TM) i7-4790 3.20GHz,內(nèi)存4G,Windows 7 32位操作系統(tǒng)),使用C++編程語(yǔ)言軟件模擬實(shí)現(xiàn)隨機(jī)單字節(jié)故障注入過(guò)程,使用CryptoMinisat 4.4解析器進(jìn)行求解(詳細(xì)使用方法見(jiàn)文獻(xiàn)[15]).為規(guī)范攻擊成功率,當(dāng)解析器求解方程時(shí)間大于3600s、輸出多個(gè)解或“UNSATISFIABLE”,視為攻擊失敗.

5.1 HIGHT改進(jìn)的代數(shù)故障攻擊實(shí)例

下面以攻擊加密第25輪攻擊為例,給出HIGHT改進(jìn)代數(shù)故障攻擊實(shí)例:

1)隨機(jī)產(chǎn)生明文P=0x0F1416050A00070C,并使用主密鑰MK=0x00112233445566778899AABBCCDDEEFF對(duì)明文進(jìn)行加密,產(chǎn)生密文C=0x00F418AED94F03F2,并使用4.1節(jié)的方法構(gòu)建正確加密時(shí)密碼完整的等效代數(shù)方程組;

2)向HIGHT密碼第25輪加密任意位置注入單字節(jié)的隨機(jī)故障,并設(shè)定故障樣本數(shù)N=5.在分析故障傳播特征的基礎(chǔ)上,利用4.2節(jié)方法將故障信息用代數(shù)方程組表示出來(lái);

3)將構(gòu)建密碼和故障信息的代數(shù)方程組并轉(zhuǎn)化SAT字句,使用CryptoMinisat 4.4解析器對(duì)構(gòu)建的代數(shù)方程組進(jìn)行求解,求解結(jié)果為K=(1111111111101110110111011100110 010111011101010101001100110001000011101110110011001010 1010100010000110011001000100001000100000000)2,轉(zhuǎn)化為16進(jìn)制與MK相同,攻擊成功,耗時(shí)25.14 s.

攻擊中,我們一共進(jìn)行了100組攻擊仿真實(shí)驗(yàn),分別隨機(jī)生成了100組不同的三元組(Pn,MKn,Cn)(1≤n≤100),且均設(shè)定故障樣本量為N=5,攻擊實(shí)驗(yàn)具體結(jié)果如圖5所示.由圖5可知,在100組攻擊樣本中,成功樣本為91個(gè),失敗樣本9個(gè)(其中求解時(shí)間超過(guò)3600s的樣本為0個(gè),解析器輸出“UNSATISFIABLE”的樣本為9個(gè)),所以攻擊實(shí)際成功率為91%,略低于4.5節(jié)理論值.在91個(gè)成功樣本中,解析器平均求解時(shí)間為143.70s.

圖5 攻擊輪為第25輪,故障樣本N=5的攻擊結(jié)果Fig.5 Result of the attack on 25-th round,N=5

本文針對(duì)密碼25輪加密,還在不同故障樣本量下進(jìn)行了仿真實(shí)驗(yàn),對(duì)每個(gè)故障樣本N各進(jìn)行100組仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖6所示.由圖可知,攻擊的實(shí)際成功率始終維持在91%左右,比理論值91.6%略小.當(dāng)故障樣本小于等于3時(shí)，攻擊成功率為0%.當(dāng)故障樣本N小于等于12時(shí),解析器平均價(jià)求解時(shí)間基本趨于穩(wěn)定,其值在4.84s上下浮動(dòng).最好情況下,僅需4個(gè)故障樣本即可恢復(fù)全部主密鑰信息MK,解析器平均求解時(shí)間為551.26s.

圖6 不同故障樣本量下,對(duì)密碼25輪攻擊結(jié)果Fig.6 Result of the attack on 25-th round under differ ent N

此外,本文還對(duì)密碼第26輪、第27輪、28輪加密各進(jìn)行了100次攻擊實(shí)驗(yàn),設(shè)定的故障樣本分別為7、11和23,實(shí)驗(yàn)結(jié)果如表2所示.

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

對(duì)上述實(shí)驗(yàn)結(jié)果進(jìn)行分析可以得出以下3個(gè)結(jié)論:

1)攻擊的實(shí)際成功率始終略小于理論分析值.可能的原因是,在攻擊實(shí)驗(yàn)中的故障注入是通過(guò)軟件模擬實(shí)現(xiàn)的,很難實(shí)現(xiàn)故障位置完全等概率分布,因此在實(shí)際攻擊中故障注入次數(shù)應(yīng)略大于理論注入次數(shù),這就直接導(dǎo)致攻擊實(shí)際成功率略小于理論分析值;

表2 密碼26輪和27輪攻擊成功率
Table 2 Success rate of the attack on round 26 and round 27

攻擊輪成功次數(shù)成功率268989%(≤理論值90．86%)278686%(≤理論值89．83%)288484%(≤理論值87．48%)

2)攻擊針對(duì)密碼同一輪加密進(jìn)行攻擊時(shí),故障樣本越大,解析器求解時(shí)間基本趨向減小.原因是故障樣本越多,構(gòu)建的代數(shù)方程組包含密鑰信息和未知中間變量的信息就越多,解析器求解速度也就相對(duì)越小.由于CryptoMinisat解析器在求解代數(shù)方程組時(shí)的時(shí)間抖動(dòng)性較大,雖然本文在進(jìn)行實(shí)驗(yàn)仿真時(shí),進(jìn)行大量重復(fù)實(shí)驗(yàn),對(duì)求解時(shí)間取平均值,但仍然無(wú)法完全消除求解時(shí)間的抖動(dòng)性,這就解釋了為什么會(huì)出現(xiàn)故障樣本N越大,求解時(shí)間越小的個(gè)別現(xiàn)象.

3)與文獻(xiàn)[15]相比,本文提出的新方法能將攻擊延伸至密碼加密第25輪,且本文提出的方法在構(gòu)建故障信息時(shí)不依賴故障具體的傳播路徑,通用性和有效性較好,與現(xiàn)有故障攻擊相比,所需的故障注入次數(shù)是最小的.

6 結(jié) 語(yǔ)

本文對(duì)HIGHT提出一種改進(jìn)的代數(shù)故障攻擊,與文獻(xiàn)[15]相比,提出的新方法能夠?qū)⒐粞由熘撩艽a加密第25輪,且方法具有較好的通用性.下一步研究的方向主要著眼于提高攻擊方法的有效性和實(shí)用性:一是,針對(duì)故障碰撞開(kāi)展相應(yīng)的容錯(cuò)處理研究;二是,研究更加高效的故障信息表示方法,進(jìn)一步提高攻擊的有效性和實(shí)用性.

[1] Boneh D,DeMillo R A,Lipton R J.On the importance of checking cryptographic protocols for faults[C].Proceedings of the EUROCRYPT 1997,LNCS,1233,1997:37-51.

[2] Biham E,Shamir A.Differential fault analysis of secret key cryptosystems[C].Proceedings of the CRYPTO 1997,LNCS,1997,1294:513-525.

[3] Biehl I,Mwyer B,Muller V.Differential fault analysis on elliptic curve cryptosystems[C].Proceedings of the CRYPTO 2000,Santa Barbara,California,LNCS 1880,2000:131-146.

[4] Li Wei,Gu Da-wu,Zhao Chen,et al.Security analysis of the LED lightweight cipher in the internet of things[J].Chinese Journal of Computers,2012,35(3):434-445.

[5] Li Jun-ru,Gu Da-wu.Differential fault analysis on PRESENT[C].China CRYPT 2009,2009:3-13.

[6] Banik S,Maitra S.A differential fault attack on MICKEY 2.0[EB/OL].Cryptology ePrint Archive,http://eprint.iacr.org/2013/166,2013.

[7] Hu Yu-pu,Zhang Feng-rong,Zhang Yi-wei.Hard fault analysis of trivium[J].Des.Codes Cryptogr,2012,62(3):289-311.

[8] Guo Shi-ze,Wang Tao,Zhao Xin-jie.Principles and methodologies of side-channel analysis in cryptography [M].Beijing:Science Press,2014.

[9] Zhang Fan,Zhao Xin-jie,Guo Shi-ze,et al.Improved algebraic fault analysis:a case study on piccolo and applications to other lightweight block ciphers[C].Proceedings of COSADE 2013,LNCS,7864:62-79.

[10] Wu Ke-hui,Zhao Xin-jie,Wang Tao,et al.Algebraic fault attack on PRESENT[J].Journal on Communications,2012,33(8):85-92.

[11] Zhao Xin-jie,Guo Shi-ze,Wang Tao,et al.Research of algebraic fault analysis on Piccolo[J].Chinese Journal of Computer,2013,36(4):882-894.

[12] Mohamed M S E,Bulygin S,Bchmann J.Using SAT solving to improve differential fault analysis of trivium[J].International Journal of Security and Its Applications,2012,6(1):29-38.

[13] Hong D,Sung J,Hong S,et al.HIGHT:a new block cipher suitable for low-resource device[C].Proceedings of CHES,LNCS,4249,2006:46-59.

[14] Fan Wei-jie,Wu Wen-ling,Zhang Lei.Differential fault analysis on HIGHT[J].Journal of Graduate University of Chinese Academy of Sciences,2012,29(2):271-276.

[15] Chen Hao,Wang Tao,Zhang Fan,et al.Algebraic fault analysis of HIGHT[J].Journal of Shanghai Jiaotong University,2015,49(12):1817-1825.

[16] Tunstall M.Fault analysis in cryptography[M].Beijing:Science Press,2015:239-253.

附中文參考文獻(xiàn)：

[4] 李 瑋,谷大武,趙 辰,等.物聯(lián)網(wǎng)環(huán)境下LED輕量級(jí)密碼算法的安全性分析[J].計(jì)算機(jī)學(xué)報(bào),2012,35(3):434-445.

[5] 李卷孺,谷大武.PRESENT算法的差分故障攻擊[C].中國(guó)密碼學(xué)會(huì)2009年會(huì),2009:3-13.

[8] 郭世澤,王 韜,趙新杰.密碼旁路分析原理與方法[M].北京:科學(xué)出版社,2014.

[10] 吳克輝,趙新杰,王 韜,等.PRESENT密碼代數(shù)故障攻擊[J].通信學(xué)報(bào),2012,33(8):85-92.

[11] 趙新杰,郭世澤,王 韜,等.Piccolo 密碼代數(shù)故障分析研究[J].計(jì)算機(jī)學(xué)報(bào),2013,36(4):882-894.

[14] 范偉杰,吳文玲,張 蕾.HIGHT算法的差分故障攻擊[J].中國(guó)科學(xué)院研究生院學(xué)報(bào),2012,29(2):271-276.

[15] 陳 浩,王 韜,張 帆,等.HIGHT密碼代數(shù)故障分析[J].上海交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,49(12):1817-1825.

[16] Marc J.密碼故障分析與防護(hù)[M].北京:科學(xué)出版社,2015:239-253.