張 鵬,胡予濮,張 濤
(1.西安電子科技大學(xué)通信工程學(xué)院,陜西西安 710071;2.中國人民解放軍69220部隊司令部,新疆阿克蘇 842000)
旁道攻擊[1]不同于傳統(tǒng)的密碼分析,它是利用密碼體制在具體實現(xiàn)過程中所表現(xiàn)出來的物理特性來分析密碼參數(shù)的。威脅最大的旁道攻擊手段有錯誤插入攻擊(Fault Induction Attack),能量攻擊(Power Attack),時間攻擊(Timeing Attack)。本文介紹了一種Mickey流密碼的錯誤引入攻擊方法。
錯誤引入攻擊是假設(shè)攻擊者控制了密碼設(shè)備,正確使用密碼設(shè)備加密,同時在加密過程中可以引入錯誤,使加密過程受到影響,輸出錯誤的加密結(jié)果。攻擊者不知道密碼設(shè)備中的信息,其目的是通過把引入錯誤后的輸出結(jié)果與沒有錯誤的結(jié)果進(jìn)行對比,從而得到密碼設(shè)備中的信息。
向設(shè)備中引入錯誤的類型可以分為以下幾類。按照錯誤影響的時間可以分為永久錯誤與暫時錯誤。按照錯誤發(fā)生位置的不同,有的精確到某一比特引入錯誤,有的對一定的范圍內(nèi)引入錯誤。按照錯誤發(fā)生的時間不同,有的精確到某一時刻引入錯誤,有的在一定時間范圍內(nèi)引入錯誤。不同的錯誤類型在實現(xiàn)時會有不同的難易程度。
Mickey[2]流密碼是一種基于硬件的流密碼,由Steve Babbage和 Matthew Dodd設(shè)計,后發(fā)展為Mickey2.0[3]和 Mickey - 128[4], 本 文 主 要 研 究Mickey-128。Mickey是在ECRYPT(European Network of Excellence for Cryptology)[5]計劃中最終的勝出密鑰之一,它具有設(shè)計簡單、硬件容易實現(xiàn)等優(yōu)勢。
密碼算法包括一個128位的密鑰種子K以及一個初始化變量iv,iv的長度是0~128中的任意值,iv的長度記做ivlength,2個160位的寄存器記做R和S。
PRAPS={0,4,5,8,10,11,14,16,20,25,30,32,35,36,38,42,43,46,50,51,55,56,57,60,61,62,63,65,66,69,73,74,76,79,80,81,82,85,86,90,91,92,95,97, 100, 101, 105, 106, 107, 108, 109,111,112,113,115,116,117,127,128,129,130,131,133,135,136,137,140,142,148,150,152,153,154,156,157}
函數(shù)定義 CLOCK_R(R,INPUT_BIT_R,CONTROL_BIT_R)
r0,r1,…,r159表示前一時刻寄存器中的狀態(tài)。r0',r1',…,r159'表示后一時刻寄存器中的狀態(tài)。式中,“⊕”表示異或運算,“·”表示與運算。
先定義 4個序列:COMP01,…,COMP0158、COMP11,…,COMP1158、FB00,…,F(xiàn)B0159、FB10,…,F(xiàn)B1159。
COMP0i={0,1,1,1,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0};
1≤i≤158
COMP1i={0,0,0,0,1,1,0,0,1,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,1,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,0,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0};
1≤i≤158
FB0i={1,1,1,1,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1};
0≤i≤159
FB1i={1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,0,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0};
0≤i≤159
函數(shù)定義 CLOCK_S(R,INPUT_BIT_S,CONTROL_BIT_S)
s0,s1,…,s159表示前一時刻寄存器中的狀態(tài)。,…,159表示寄存器的中間狀態(tài)。s0',s1',…,s159'表示后一時刻寄if存器中的狀態(tài)。
混合函數(shù)定義為 CLOCK_KG(R,S,INPUT_BIT)
CONTROL_BIT_R=s54⊕r106
CONTROL_BIT_S=s106⊕r53
If MIXING=TRUE,
CLOCK_R(R,INPUT_BIT_R=INPUT_BIT⊕s80,CONTROL_BIT_R=CONTROL_BIT)
CLOCK_S(S,INPUT_BIT_S=INPUT_BIT,CONTROL_BIT_S=CONTROL_BIT)
If MIXING=FALSE,
CLOCK_R(R,INPUT_BIT_R=INPUT_BIT,CONTROL_BIT_R=CONTROL_BIT)
CLOCK_S(S,INPUT_BIT_S=INPUT_BIT,CONTROL_BIT_S=CONTROL_BIT)
先將寄存器R和S置全0。輸入iv
For 0≤i≤ivlength -1
CLOCK_KG(R,S,MIXING=TRUE,INPUT_BIT=ivi)
輸入k
For 0≤i≤127
CLOCK_KG(R,S,MIXING=TRUE,INPUT_BIT=ki)
輸入全0
For 0≤i≤159
CLOCK_KG(R,S,MIXING=TRUE',INPUT_BIT=0)
For 0≤i≤L -1
zi=r0⊕s0
CLOCK_KG(R,S,MIXING=FALSE,INPUT_BIT=0)
根據(jù)文獻(xiàn)[6]提出的錯誤攻擊模型,假設(shè)攻擊者能在生成密鑰流階段和初始化階段中在特定的時刻向某些特定位置上引入一個到兩個錯誤。此外,攻擊者可以多次重啟密鑰生成機(jī),其目的是通過比較錯誤引入前后密鑰流的變化,從而確定寄存器內(nèi)部初始狀態(tài)的信息。
第1步 在產(chǎn)生密鑰流的過程引入錯誤。從而求解出初始化完成之后寄存器R和S的狀態(tài)。
z0,z1,…表示第0,1,…時刻的輸出密鑰。
用同樣的方法,反復(fù)多次,解出每一時刻的r159,cr,s158,s159,cs。從而計算出初始化完成之后寄存器R和S的所有準(zhǔn)確的狀態(tài)。
第2步 在已知初始化結(jié)束后寄存器R和S的所有準(zhǔn)確狀態(tài)的情況下。在初始化過程中向寄存器R和S引入錯誤求解出密鑰種子。
在初始化過程中,有3個階段,輸入iv,輸入K,輸入全0。
在輸入全0的過程中,如果已知后一時刻的全部狀態(tài)和前一時刻的控制位 CONTROL_BIT_R、CONTROL_BIT_S就能計算出前一時刻的狀態(tài)。已知初始化結(jié)束后的寄存器狀態(tài),現(xiàn)在可以假設(shè)控制位,即CONTROL_BIT_R和CONTROL_BIT_S分別為00、01、10、11,從而計算出前一時刻的狀態(tài),再來驗證之前假設(shè)的控制位是否正確。在驗證過程中,有兩種情況:一種是只有一個假設(shè)成立;另一種是有兩個或多個假設(shè)成立。如果是第一種情況,就直接計算出前一時刻狀態(tài)。若是第二種情況,在該時刻向寄存器R和S同時引入錯誤,然后記錄其輸出結(jié)果。另外計算出多種假設(shè)成立時的前一時刻狀態(tài),在同樣的位置引入錯誤,計算其輸出密鑰流,與實際引入錯誤后的輸出密鑰流比較,排除不同的。從而得到正確的前一時刻狀態(tài)。通過160輪計算可以計算出在輸入密鑰種子之后的寄存器狀態(tài)。
用同樣的方法作用于輸入K的過程,在這個過程中不只要假設(shè)控制位,還要假設(shè)ki,再用排除法計算出ki和前一時刻狀態(tài)。在這個過程中,只有一種假設(shè)成立的情況很少,所以每輪都要引入錯誤。再通過128輪計算,解得密鑰種子和輸入密鑰種子之前寄存器的狀態(tài)。
計算iv方法不變,只是計算完成1輪后要監(jiān)測計算出的寄存器狀態(tài),直到檢測到狀態(tài)為全0。計算的輪數(shù)為ivlength。同時解出iv。
用C++語言編寫程序,模擬實現(xiàn)了攻擊算法。并且每次隨機(jī)選取密鑰種子,都能準(zhǔn)確地計算出密鑰種子。在密鑰流生成階段插入640次錯誤,需要960個密鑰就可以計算出寄存器R和S在密鑰流生成階段的初始狀態(tài),恢復(fù)整個密鑰流。在得出寄存器R和S在密鑰流生成階段的初始狀態(tài)的前提下,在初始化階段最壞的情況下插入416次錯誤,需要12480個密鑰就可以計算出密鑰種子K和初始值iv。
給出了一種對Mickey流密碼的引入錯誤攻擊方法,要求攻擊者能夠在任意時刻向寄存器的任意位置引入錯誤,實驗證明了其可行性。
[1] QUISOUATER J J,RIZK M.Side channel attacks[EB/OL].(2008-9-12)[2010-11-2]http://www.ipa.go.jp/se-curity/enc.
[2] BABBAGE S,DODD M W.The stream cipher MICKEY IST-2002-507932,[EB/OL].(2007-09-11)[2010-12 -28]http//www.ecrypt.eu.org/stream.
[3] BABBAGE S,DODD M W.The stream cipher MICKEY 2.0,revised ECRYPT stream cipher submission[EB/OL].(2009-03-12)[2010-12-28]www.ecrypt.com.
[4] BABBAGE S,DODD M W.The stream cipher MICKEY-128 2.0,revised ECRYPT stream cipher submission[EB/OL].(2009-05-03)[2010-12-28]www.ecrypt.com.
[5] Ecrypt.eSTREAM:ECRYPT stream cipher project,IST -2002-507932[EB/OL].(2010-07-18)[2011-01-12]http://www.ecrypt.eu.org/stream.
[6] HOCH J J,SHAMIR A.Fault analysis of stream ciphers[C].Heidelberg:CHES 2004,LNCS,Springer,2004,3156:240-253.