陳 浩,王 韜,劉會英,周 平,馮曉云(.軍械工程學院 信息工程系,河北 石家莊050003;.南京理工大學 計算機科學與技術學院,江蘇 南京0094)
模加運算[1]廣泛地應用在流密碼,輕型分組密碼,哈希函數(shù)等設計中,對采用模加運算的密碼算法安全性分析近年來已成為密碼分析學的研究熱點。Helix作為一種典型模加運算結構的流密碼,采用輪函數(shù)迭代,交叉使用逐位異或,模232加和循環(huán)移位3種運算來提供復雜的非線性,增強算法安全性,對其安全性的研究對其他具有模加運算結構的密碼有很大的借鑒意義。
代數(shù)故障攻擊[2]由Courtois在eSmart 2010會議上首次提出,它用代數(shù)分析方法建立密碼算法代數(shù)方程組,利用注入故障獲取錯誤密文,將故障差分轉(zhuǎn)化為等效方程組,然后通過求解方程組進行密鑰恢復。目前代數(shù)故障攻擊處于起步階段,相關研究較少,主要有Mohamed等于2011年對流密碼Trivium 提出的代數(shù)故障攻擊[3],攻擊僅需2個故障和420個密鑰流比特即可恢復Trivium 全部的內(nèi)部狀態(tài),顯著的提高了故障信息的利用率。由于該方法僅針對Trivium 算法結構,對具有模加運算結構的流密碼并不適用。
本文對Helix首次提出一種代數(shù)故障攻擊。針對算法中模232加運算,提出一種通用的代數(shù)故障攻擊模型,并通過選擇明文和故障注入,建立Helix在該模型下的代數(shù)方程組,使用CryptoMiniSAT 解析器求解方程組恢復密鑰信息。實驗結果表明,580次故障注入即可恢復Helix工作密鑰除最高位外的248比特信息,剩余8比特密鑰信息可以通過窮舉得到。
Helix面向軟件實現(xiàn),支持可變的密鑰長度 (最長256比特),使用長度為128 比特初始向量,以字為單位進行運算。
為論述方便起見,基本符號見表1。
表1 基本符號及說明
Helix算法輪函數(shù)如圖1所示,由圖1可知輪函數(shù)交叉使用異或,模232加,循環(huán)移位運算操作。
圖1 Helix輪函數(shù)結構
Helix使用工作密鑰(K0,…,K7),初始向量(N0,…,N3),輪編號i和用戶密鑰U 的長度(U) (0≤(U)≤32)來進行密鑰擴展。整個密鑰擴展分為兩步,第一步將用戶密鑰U 轉(zhuǎn)換為工作密鑰;第二步將工作密鑰轉(zhuǎn)換成輪子密鑰。
其中,i=7,…,0。在第二步中,首先將初始向量擴展成8個字Nk:=(k mod 4)-Nk-4(mod 232),其中K=4,…,7,則輪子密鑰由式(2)-式(4)產(chǎn)生
Helix在加密第一個明文P0前,從i=-8開始運行8輪輪函數(shù),運行到i=-1時,完成初始化。初始值的設定是依照式 (5)-式 (7)來設定的
分析流密碼Helix算法結構可知,Helix的安全性主要依賴模加運算,因此對Helix的代數(shù)故障攻擊實質(zhì)就是對模加運算的代數(shù)故障攻擊。本節(jié)對模加運算提出了一種通用的代數(shù)故障攻擊模型,并給出了該模型下代數(shù)方程組的構建。
如圖2所示,對流密碼代數(shù)故障攻擊主要可分為3步:第一步,利用流密碼加密算法結構建立關于內(nèi)部狀態(tài)或者密鑰的代數(shù)方程組;第二步,向流密碼加密算法引入隨機故障使中間狀態(tài)產(chǎn)生差分以獲取有關內(nèi)部狀態(tài)或者密鑰的額外信息,利用這些額外信息構建新的關于內(nèi)部狀態(tài)或者密鑰的代數(shù)方程組;第三步,利用基于可滿足性問題[4],基于偽隨機化問題[5],基于Grbner[6]基等方法求解第一步和第二步構建的方程組,進而恢復內(nèi)部狀態(tài)或者初始密鑰信息。本文使用CryptoMiniSAT 解析器進行密鑰求解,使用方法見文獻 [7]。
圖2 代數(shù)故障攻擊一般過程
本文采用隨機單比特翻轉(zhuǎn)故障模型,即假設攻擊者具有下列能力:
(1)能夠正確運行密碼算法,對明文信息P 進行加密得到正確的密文C;
(2)能夠向密碼任意位置注入隨機單比特故障使密碼內(nèi)部狀態(tài)某個比特發(fā)生翻轉(zhuǎn) (0→1或1→0),并對明文信息P 加密得到錯誤密文C′;
(3)能夠反復多次向密碼注入故障,并且能夠重啟密碼設備恢復初始狀態(tài)。
由2.1節(jié)可知,對模加運算的代數(shù)故障攻擊方程組構建可分為兩步:根據(jù)模加運算特點構造代數(shù)方程組;注入隨機單比特故障,利用故障信息建立額外代數(shù)方程組;為了更好的說明代數(shù)方程組的構建,首先給出模加運算的定義。
定義 設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)上的模加運算可表示為
(1)利用模加運算特點構造代數(shù)方程組;
根據(jù)文獻 [8],可以將式 (8)等價轉(zhuǎn)換成GF(2)上的如式 (9)、式 (10)所示的方程組
其中,ci表示進位,且有c0=0,所以根據(jù)式 (9)、式(10)可以將GF(2n)上的模加運算轉(zhuǎn)換成GF(2)上的代數(shù)方程組。
(2)利用故障信息構建代數(shù)方程組;
一般而言,由于模加運算在密碼算法結構中的位置不同,向模2n加運算結構注入隨機單比特故障α∈GF(2n),α= (εn-1,εn-2,…,ε0),存在下列兩種情況:
1)已知注入的隨機故障α,正確輸出Z 和錯誤輸出Z′;
圖3 第一種情況
如圖3所示,故障值α和正確和錯誤輸出Z 和Z′均已知,則根據(jù)故障信息可以得到如式 (11)所示的方成組
同式 (8),我們可以將式 (11)轉(zhuǎn)化成GF(2)上的代數(shù)方程組,如式 (12)所示
2)已知注入的隨機故障α,正確輸出和錯誤輸出差分ΔZ;
設ΔZ=β,β= (δn-1,δn-2,…,δ0),如圖4 所示,已知正確輸出和錯誤輸出的差分β則可以得到如式 (13)
圖4 第二種情況
同式 (8),將式 (14)等價轉(zhuǎn)化成GF(2)上的代數(shù)方程組,得到如下式 (15)-式 (17)
綜合上述兩種情況可以構建模加運算在GF(2)上的代數(shù)方程組,通過多次故障注入,可以構建足夠多的代數(shù)方程組,對方程組進行求解可以恢復X,Y 的值。值得指出的是,由文獻 [9]知,雖然式 (11)所對應的方程組系統(tǒng)包含了全部X,Y 的比特信息,但由于方程中的最高位不提供任何解的信息,因此通過求解式 (11)可以恢復X,Y全部的前n-1比特信息,式 (13)所對應的方程組系統(tǒng)只包含了X,Y 的前n-1比特信息,因此同樣只能恢復X,Y 的前n-1比特信息。
對Helix的代數(shù)故障攻擊可分為3步,第一步在Helix第i(i>8)輪,選擇不同明文Pi的值得到不同的密鑰流,使用本文2.3節(jié)提出的方法構建代數(shù)方程組求解出C 值;第二步通過在指定位置注入隨機故障求取D 的值,進而求出密鑰Xi,1的值;第三步,根據(jù)密鑰擴展算法,重復第一步第二步恢復出全部的密鑰信息;下面將詳細論述上面的攻擊過程。
步驟1 隨機選擇明文Pi,運行密碼設備得到相應的密鑰流,則有式 (18)成立
步驟2 重啟密碼設備,改變明文Pi使新的明文滿足P′i=PiΔ得到新的密鑰流 ()′,則有式 (19)成立
對式 (18)和式 (19)求差分可以得到式 (20)
在式 (20)中令φ=PiA 則可將式 (20)轉(zhuǎn)換為式(21)
顯然式 (21)與2.3節(jié)中的式 (9)對應,采用2.3節(jié)中的方法將式 (21)轉(zhuǎn)換成二元域上的方程組。
步驟3 改變步驟2中的Δ值并重新執(zhí)行步驟2,構建足夠多的代數(shù)方程組;
步驟4 對步驟1~步驟3構建的代數(shù)方程系統(tǒng)進行求解,恢復φ,B,C;
步驟1 使用3.1節(jié)明文Pi,運行密碼設備得到密鑰流Zi+10,則有
步驟2 如圖5 所示,保持明文不變,在E 處注入隨機比特故障m,得到新的密鑰流 ()′,則有
因為Z,Z′和C 均已知,且根據(jù)文獻 [10]可以得到定理:
定理[10]對于本文2.3節(jié)中式 (8),若在X 上發(fā)生的單比特故障α,則α=2l成立的充要條件為
由定理1可以得到故障值m,顯然式 (22)、式 (23)對應2.3節(jié)中的第一種情況,采用2.3節(jié)中的方法將其傳換成二元域上代數(shù)方程組;
步驟3 重啟密碼設備,并保持明文不變,重新執(zhí)行步驟1和步驟2,構建足夠多的代數(shù)方程組;
圖5 對Helix的代數(shù)故障攻擊
步驟4 對步驟1~步驟3構建的代數(shù)方程系統(tǒng)進行求解,恢復Xi,1;
步驟1 使用3.1節(jié)明文Pi,運行密碼設備得到相應的密鑰流Zi+10
步驟2 如圖5 所示,保持明文不變,在G 處注入隨機比特故障n,得到新的密鑰流 ()′
因為由式 (19)可以計算出B 和B′,根據(jù)定理可以計算得到故障n,所以式 (24)和式 (25)同樣對應于2.3節(jié)中的第一種情況,將其轉(zhuǎn)換成二元域上的方程組。
步驟3 重啟密碼設備,并保持明文不變,重新執(zhí)行步驟1和步驟2,構建足夠多的代數(shù)方程組;
步驟4 對步驟1~步驟3 構建的代數(shù)方程組進行求解,恢復Xi,0;
由本文1.3節(jié)Helix密鑰擴展算法可知,可以對連續(xù)八輪i,i+1,i+2,i+3,i+4,i+5,i+6,i+7 (其中i滿足i mod8=0)輪加密進行攻擊,由于用戶密鑰長度(U)未知,因此由3.1節(jié)方法只能恢復工作密鑰K0,K2,K3,K4,K6,K7共6個密鑰,采用3.2節(jié)方法可以恢復剩下兩個工作密鑰K1,K5,至此恢復了Helix的全部工作密鑰K0,K1,K2,K3,K4,K6,K5,K7。
在普通PC 機 (CPU 為AMD Athlon (tm)64Processor 3000+,內(nèi)存為1G)上,使用C++語言、CryptoMin-iSAT 軟件實現(xiàn)了Helix的代數(shù)故障攻擊仿真實驗,其中故障誘導得到錯誤密文采用計算機軟件模擬完成。下面給出某次Helix代數(shù)故障攻擊過程:
(1)產(chǎn)生一個隨機明文P=21646C726F77202C6F6C6C6 54816,初始向量N=6665646362613938373635343332313016,用戶密鑰U=78696C654816,則正常運行密碼設備生成的正確密文C=0DF2232C80C5A0827AB9274C6C16;生成的工作密鑰K=39113251F5857A359FB69B734A2803F4DA15F16D20 D61C8FD2A1A3CB7AD71E6C16。
(2)根據(jù)3.1節(jié)中方法,通過選擇明文P 恢復C 值;
(3)根據(jù)3.2節(jié)中方法,注入隨機故障恢復Xi,1;
(4)根據(jù)3.3節(jié)中方法,注入隨機故障恢復密鑰Xi,0
(5)根據(jù)密鑰擴展算法恢復其余密鑰信息,結果見表2。
表2 Helix代數(shù)故障攻擊結果
如表2所示,攻擊可以恢復工作密鑰K0~K7除最高1位的所有248比特,且實驗結果同真實密鑰一致,攻擊成功,剩下的8比特密鑰信息可以通過窮舉得到。
圖6表示恢復C 值,Xi,1,Xi,0所需選擇明文次數(shù)和故障注入次數(shù)。結果表明,攻擊恢復密鑰Xi,1所需的故障注入次數(shù)較多約為260次,恢復Xi,1所需的故障注入次數(shù)較少僅需10次,而恢復C 值所需明文選擇次數(shù)為100次,所以總的故障注入總數(shù)為580 (10×6+260×2)次。
圖6 實驗恢復C 值,Xi,1,Xi,0結果
本文首次將代數(shù)故障攻擊應用在Helix流密碼上,提出了一種對模加運算通用的代數(shù)故障攻擊模型,詳細介紹了該模型下代數(shù)方程組的構建,給出了整個攻擊過程。
實驗結果表明,580次故障注入可以恢復Helix工作密鑰除最高位的248比特信息,剩余8比特信息可以通過窮舉得到。本文所提出的對模加方程的代數(shù)故障攻擊模型具有通用性強,求解方便等優(yōu)點,可以為其他具有模加運算結構的流密碼和分組密碼的代數(shù)故障攻擊提供一定的參考。
[1]ZHENG B,GUAN J.Differential characteristic probability of added Key on modulo 2noperation [J].Journal of Electronics&Information Technology,2009,31 (11):2708-2712 (in Chinese).[鄭斌,關杰.“與密鑰模2n加運算”的差分性質(zhì)研究 [J].電子信息學報,2009,26 (2):132-136.]
[2]Courtois N,Ware D,Jackson K.Fault-algebraic attacks on inner rounds of DES [C]//eSmart,2010:22-24.
[3]Mohamed M,Bulygin S.Using SAT solving to improve differential fault analysis of trivium[J].International Journal Security and Its Applications,2012,6 (1):29-37.
[4]Faure G,Nieuwenhuis R,Oliveras A,et al.SAT modulo the theory of linear arithmetic:Extract,inexact and commercial solvers[G].LNCS 4996:SAT,2008:77-90.
[5]Yossed O,Mario K,Thomas P,et al.Side-channel analysis in the presence of errors[C]//CHES.USA:California,2010:428-442.
[6]Sugita M,Kawazoe M,Imai H.Relation between XL algorithm and Grbner basis algorithms [EB/OL].http://eprint.iacr.org/112,2010.
[7]LI Junru,GU Dawu.Differential fault analysis on PRESENT[C]//China Crypt,2009:3-13 (in Chinese).[李卷孺,谷大武.PRESENT 算法的差分故障攻擊 [C]//中國密碼學會,2009:3-13.]
[8]Courtois N,Debraize B.Algebraic description and simultaneous linear approximations of addition in snow 2.0 [C]//ICICS,2008:328-344.
[9]LI Shenhua.Cryptanalysis of two symmetric encryption algorithms ARIA and Salsa20 [D].Jinan:Shandong University Doctoral Dissertation,2008:42-50 (in Chinese).[李 申 華.對稱密碼算法ARIA 和Salsa20的安全性分析 [D].濟南:山東大學博士學位論文,2008:42-50.]
[10]ZHANG Zhongya.Security analysis on block-like type stream ciphers[D].Zhengzhou:PLA Information Engineering University Master Dissertation,2011:47-49 (in Chinese).[張中亞.類分組型序列密碼算法的安全性分析 [D].鄭州:解放軍信息工程大學碩士論文,2011:47-49.]