楊昌盛,嚴(yán)迎建
(解放軍信息工程大學(xué),河南 鄭州450004)
能量分析(power analysis,PA)攻擊自Paul C.Kocher于1998年提出以來(lái),被廣泛地應(yīng)用于分組密碼和公鑰密碼的分析,但針對(duì)流密碼的研究相對(duì)較少[1-3]。文獻(xiàn)[4]基于LFSR(linear feedback shift register)相鄰時(shí)刻能量消耗差異建立方程組,通過(guò)代數(shù)方法求解內(nèi)部狀態(tài)。文獻(xiàn) [5]通過(guò)選擇初始向量IV 來(lái)消除算法噪聲,用較少的能量跡恢復(fù)密鑰。文獻(xiàn)[6]利用C 語(yǔ)言模擬能量消耗過(guò)程,對(duì)MICKEY流密碼進(jìn)行了仿真攻擊。文獻(xiàn)[7]對(duì)K2流密碼進(jìn)行了包括PA 攻擊在內(nèi)的多種側(cè)信道攻擊。
盡管國(guó)內(nèi)外在流密碼的能量分析攻擊方面已有一定的研究,但大多停留在理論層面,或僅基于簡(jiǎn)單的仿真模型進(jìn)行分析,且部分文獻(xiàn)提出的方法沒(méi)有考慮實(shí)際的可操作性。本文根據(jù)流密碼算法的共性特征,提出了面向同步流密碼PA 攻擊點(diǎn)選取策略,并以eSTREAM[8]項(xiàng)目中獲勝的MICKEY 和Trivium 算法為例進(jìn)行了攻擊演示,最后在ASIC(application specific integrated circuit)開(kāi)發(fā)環(huán)境下進(jìn)行了仿真實(shí)驗(yàn),驗(yàn)證了上述策略的合理性。
與分組密碼中通過(guò)加/解密大量明/密文來(lái)獲取密碼算法能量跡進(jìn)行PA 攻擊的原理類似,同步流密碼的PA 攻擊利用了同步流密碼需要反復(fù)初始化并更換IV 這一特性,使得獲取大量已知IV 對(duì)應(yīng)的能量跡成為可能[5],其主要包括3個(gè)關(guān)鍵點(diǎn):①攻擊點(diǎn)的選取;②能量消耗模型;③假設(shè)能量消耗與實(shí)測(cè)能量跡的匹配。其中攻擊點(diǎn)的選取最為關(guān)鍵,而能量消耗模型的研究已經(jīng)很充分,采用漢明距離作為CMOS器件的能量消耗模型被證明是有效的[9]。
在分組密碼的PA 攻擊中,攻擊點(diǎn)必須是一個(gè)與局部密鑰Kpartial和IV 有關(guān)的中間值f(IV,Kpartial)。在密碼芯片中函數(shù)f 對(duì)應(yīng)于局部電路,局部電路狀態(tài)的變化將反映到局部功耗上。PA 攻擊正是通過(guò)猜測(cè)局部密鑰并根據(jù)能量消耗模型計(jì)算局部電路假設(shè)能量消耗,最后與采樣到的密碼算法總功耗進(jìn)行匹配,匹配效果最好的猜測(cè)密鑰被認(rèn)為是正確的局部密鑰。
同步流密碼的PA 攻擊點(diǎn)選取原則與分組密碼中的類似,但僅滿足上述條件并不足以保證攻擊的可行性。記密碼算法總功耗為Ptotal,攻擊點(diǎn)對(duì)應(yīng)的局部電路功耗為Pattack,與密碼算法有關(guān)的其它功耗為Pnoise.algorithm,密碼設(shè)備運(yùn)行時(shí)引入的隨機(jī)噪聲為Pnoise.electronic,密碼設(shè)備功耗中的常量成分為Pconstant,則密碼算法總功耗可表示如下
其中,Pnoise.electronic與Pattack相互獨(dú)立,而Pconstant對(duì)于功耗匹配沒(méi)有影響,則PA 攻擊最終轉(zhuǎn)換為分析攻擊點(diǎn)假設(shè)能量消耗與Pattack+Pnoise.algorithm的匹配情況。在針對(duì)分組密碼PA攻擊的文獻(xiàn) [10]中,作者假設(shè)Pnoise.algorithm與Pattack相互獨(dú)立,并取得了理想的攻擊結(jié)果。分析發(fā)現(xiàn),由于分組密碼中普遍使用了混亂和擴(kuò)散部件,使得Kpartial在參與密碼算法中的其它運(yùn)算時(shí),經(jīng)過(guò)混亂和擴(kuò)散的作用,其在Pnoise.algorithm中的功耗分量表現(xiàn)出很強(qiáng)的隨機(jī)性。而流密碼的構(gòu)造相對(duì)簡(jiǎn)單,且存在大量線性部件,Pattack與Pnoise.algorithm相互獨(dú)立的假設(shè)不再適用,而Pattack與Pnoise.algorithm的相關(guān)性可能導(dǎo)致PA 攻擊無(wú)法實(shí)現(xiàn)。
據(jù)此,本文提出在選取同步流密碼的PA 攻擊點(diǎn)時(shí),必須嚴(yán)格保證所攻擊的Kpartial在Pnoise.algorithm中引起的分量與Pattack不相關(guān)或弱相關(guān)。
根據(jù)以上分析,本文就同步流密碼PA 攻擊點(diǎn)的選取提出以下策略。
(1)適用于逐比特攻擊的情形
對(duì)于密鑰逐比特注入的密碼算法(如MICKEY、A5/1),以與密鑰注入端直接相關(guān)的中間狀態(tài)為攻擊點(diǎn)進(jìn)行逐比特攻擊是最為有效的方法;如果密鑰與IV 并行注入,但密碼算法中存在密鑰與IV 單比特結(jié)合的部件(如Trivium),如圖1所示,則該部件也可能成為有效的攻擊點(diǎn),由于這種攻擊點(diǎn)僅以1比特寄存器的能量消耗差異值為區(qū)分函數(shù),因此在選取IV時(shí)應(yīng)特別考慮,以免Pattack被Pnoise.algorithm掩蓋。
(2)適用于多比特攻擊的情形
圖1 密鑰與IV 單比特結(jié)合
流密碼算法的前饋模型中普遍采用濾波函數(shù),一般是將FSR 的抽頭代入布爾函數(shù)進(jìn)行運(yùn)算,如圖2所示。如果布爾函數(shù)f2是非線性的(如Grain、DECIM),則其可能成為有效的攻擊點(diǎn)。但若f2是線性的,則抽頭位置所對(duì)應(yīng)的局部密鑰可能存在多種組合,例如f2為4輸入異或邏輯,當(dāng)通過(guò)PA 攻擊猜測(cè)出某一時(shí)刻h 的值為0 時(shí),則該時(shí)刻t1t2t3t4可能取值0000、1111、1100、0011等情況,對(duì)于抽頭數(shù)量較多的部件,這種組合的數(shù)量是非??捎^的,這種情況下的f2不適合作為攻擊點(diǎn)。
圖2 前饋模型中的濾波函數(shù)
密鑰K =(k1,…,k80),長(zhǎng)度為80比特,初始向量IV=(iv1,…,ivL),長(zhǎng)度L 可變,0≤L≤80,由寄存器R和S組成,每個(gè)寄存器100級(jí),其中R 為線性,S為非線性。其密鑰加載和初始化過(guò)程包括4 個(gè)階段:①寄存器R和S置0;②IV 逐比特注入;③密鑰逐比特注入;④空轉(zhuǎn)(preclock)。圖3給出了MICKEY 算法的硬件原理圖,IV和密鑰從input_bit端口逐比特注入,經(jīng)過(guò)組合邏輯后分別由input_bit_r和input_bit_s注入寄存器R 和寄存器S。其中,寄存器R 中有50個(gè)狀態(tài)位與input_bit_r有關(guān),寄存器S中所有狀態(tài)位均與input_bit_s相關(guān),具體參見(jiàn)文獻(xiàn)[11]。
圖3 MICKEY 算法硬件原理
(1)攻擊點(diǎn)選取
根據(jù)1.3中的分析,MICKEY 算法與 “適用于逐比特攻擊”中的前一種情形相符,故采取逐比特攻擊方案。選取IV 加載完畢后,密鑰加載階段寄存器R 和寄存器S中所有與密鑰注入端相關(guān)的狀態(tài)位為攻擊點(diǎn),即ft(IV,K)=(Rt‖St)IV,K,t=0,…,80,其中,t表示已經(jīng)加載的密鑰比特?cái)?shù);“‖”表示拼接操作,ft表示第t個(gè)密鑰比特注入后,寄存器R 和S所有狀態(tài)位,共150比特。
(2)獲取密碼算法能量消耗
準(zhǔn)備N 組隨機(jī)初始向量IV1,IV2,…,IVN和待攻擊密鑰K’=(k’1,…k’80),測(cè)量MICKEY 算法在加載上述IV和密鑰時(shí)的能量消耗,記為P=(P1,P2,…,PN)T,其中Pi=(Pi,1,Pi,2,…,Pi,M)對(duì)應(yīng)于IVi參與運(yùn)算時(shí)的能量跡,M 為能量跡中采樣點(diǎn)個(gè)數(shù),即P的規(guī)模為N×M。
(3)計(jì)算攻擊點(diǎn)假設(shè)能量消耗值
(4)假設(shè)能量消耗值與能量跡匹配
最后比較P 中各列P*,i(1≤i≤M)與Hk(1≤K≤80,對(duì)應(yīng)于第k比特密鑰)中各列(1≤j≤2)的匹配程度。本文使用相關(guān)系數(shù)反映Hk中各列與P 中各列的匹配程度,計(jì)算公式如下
上述攻擊方案與攻擊平臺(tái)無(wú)關(guān),在實(shí)測(cè)環(huán)境和仿真環(huán)境中均適用,兩者僅在IV 的樣本數(shù)量和獲取密碼算法能量消耗的方式上有所區(qū)別。為了初步驗(yàn)證攻擊方案的有效性,本文采用芯片設(shè)計(jì)流程中的EDA 工具獲取密碼算法能量消耗,其流程如圖4所示。
圖4 基于ASIC開(kāi)發(fā)環(huán)境的功耗仿真流程
采用SMIC 0.18μm 工藝庫(kù),用Design Compiler 對(duì)Verilog HDL實(shí)現(xiàn)的MICKEY 算法進(jìn)行綜合,得到門級(jí)網(wǎng)表,并以 “攻擊方案第2步”中準(zhǔn)備的IV 和密鑰為測(cè)試激勵(lì)在VCS下進(jìn)行仿真,得到包含網(wǎng)表中所有門的翻轉(zhuǎn)信息的VCD 文件,最后利用PrimeTimePX 獲取密碼算法的能量消耗信息,具體可參考文獻(xiàn)[12]。
實(shí)驗(yàn)采用隨機(jī)初始向量2000 組,待攻擊密鑰K’ =0x5a5b5c5d5e5fa5a6a7a8(k1在最左端)。按照上述攻擊方案,逐比特恢復(fù)出了完整的80比特密鑰。圖5給出了攻擊第1、2和80比特時(shí),假設(shè)能量消耗與算法總功耗(仿真功耗)的匹配情況,圖中縱軸為相關(guān)系數(shù),橫軸為功耗采樣點(diǎn)。
圖5 仿真攻擊第1、2和80比特時(shí)的相關(guān)系數(shù)
表1列出了攻擊第1、2、3、79和80比特時(shí),ρk兩列中的最大值。
表1 擊第1、2、3、79和80比特時(shí)ρk 峰值
密鑰K=(k1,…,k80),初始向量IV=(iv1,…,iv80),長(zhǎng)度均為80比特,由3 個(gè)NFSR(nonlinear feedback shift register)組成,級(jí)數(shù)分別為93,84和111,共288比特。其密鑰安裝與初始化過(guò)程包括2個(gè)階段:
(1)密鑰和IV 安裝,過(guò)程如下:
(s1,s2,…,s93)←(k1,…,k80,0,…,0)
(s94,s95,…,s177)←(iv1,…,iv80,0,…,0)
(s178,s179,…,s288)←(0,…,0,1,1,1)
(2)空轉(zhuǎn)4×288個(gè)時(shí)鐘周期,過(guò)程如下:
for i=1 to 4·288 do
t1←s66+s91·s92+s93+s171
t2←s162+s175·s176+s177+s264
t3←s243+s286·s287+s288+s69
(s1,s2,…,s93)←(t3,s1,…,s92)
(s94,s95,…,s177)←(t1,s94,…,s176)
(s178,s179,…,s288)←(t2,s178,…,s287)
end
(1)攻擊點(diǎn)選取
Trivium 算法符合 “適用于逐比特攻擊”中的后一種情形。記Trivium 空轉(zhuǎn)t 個(gè)時(shí)鐘周期后第i 個(gè)狀態(tài)比特為(1≤i≤288)=,則中間值t1可記為=+·++。由于,,…,全為0,因此當(dāng)0≤t≤10時(shí),,,為0,=+,而=k66-t,=iv78-t,根據(jù)前文分析,以t1為攻擊點(diǎn)可以逐比特恢復(fù)k66,k65,…,k56。由于=ki(1≤i≤80),故當(dāng)完成前述11比特密鑰的攻擊后,,,…,即為已知,進(jìn)而當(dāng)27≤t≤35時(shí),,,已知,以t1為攻擊點(diǎn)可以逐比特恢復(fù)出k39,k38,…,k31。依此類推,反復(fù)地以前面攻擊出的密鑰比特為后續(xù)攻擊的條件,最終可恢復(fù)出絕大部分密鑰,其中當(dāng)t≥66時(shí)用到式(1)
1)IV 選擇方案1
表2 第1種IV 選擇方案下的漢明距離情況
在具體攻擊時(shí),P_HD 是基于猜測(cè)密鑰比特計(jì)算出來(lái)的假設(shè)值,而T_HD 是實(shí)際情況下的固有值。當(dāng)密鑰猜測(cè)正確時(shí),P_HD 與T_HD 的相關(guān)系數(shù)為1。但當(dāng)密鑰猜測(cè)錯(cuò)誤時(shí),如猜測(cè)密鑰比特為0,而實(shí)際密鑰比特為1時(shí),P_HD= (0,3),T_HD=(1,2),兩者的相關(guān)系數(shù)仍為1,故該IV 選擇方案是不可行的。
2)IV 選擇方案2
方案1的主要問(wèn)題在于IV 空間過(guò)小,但是IV 空間過(guò)大又會(huì)造成寄存器s94的漢明距離被其它寄存器掩蓋的問(wèn)題。本文最初采用大量隨機(jī)IV 進(jìn)行攻擊試驗(yàn),其攻擊結(jié)果與方案1類似。因此,方案2在方案1的基礎(chǔ)上僅增加了iv77-t)1個(gè)可變IV 比特,即iv77-t‖iv78-t取00、01、10或11,IV 其它比特全為0。類似的,表3給出了不同密鑰比特下,4個(gè)IV 參與運(yùn)算時(shí)所有寄存器的漢明距離(T_HD)和s94‖s170‖s171‖s172的漢明距離(P_HD)。
表3 第2種IV 選擇方案下的漢明距離情況
方案2中,當(dāng)密鑰猜測(cè)正確時(shí),P_HD 與T_HD 的相關(guān)系數(shù)為1。當(dāng)密鑰猜測(cè)錯(cuò)誤時(shí),如猜測(cè)密鑰比特為0,而實(shí)際密鑰比特為1時(shí),P_HD=(0,3,2,3),T_HD=(1,2,3,2),兩者的相關(guān)系數(shù)為0.5,即密鑰猜測(cè)正確與否是可區(qū)分的,故該IV 選擇方案具備可行性。據(jù)此,攻擊點(diǎn)確定為ft(IV,K)=(‖‖‖)IV,K(0≤t≤10)。
(2)測(cè)量密碼算法能量消耗
根據(jù)上述方案準(zhǔn)備IV,攻擊每1個(gè)密鑰比特需要4個(gè)IV,測(cè)量Trivium 算法在加載上述IV 和待攻擊密鑰時(shí)的能量消耗,記為P =(P1,P2,…,P4)T,其中Pi=(Pi,1,Pi,2,…,Pi,Y)對(duì)應(yīng)于IVi參與運(yùn)算時(shí)的能量跡,Y 為能量跡中采樣點(diǎn)個(gè)數(shù),即P 的規(guī)模為4×Y。
(3)計(jì)算攻擊點(diǎn)假設(shè)能量消耗值
當(dāng)攻擊k66-t(0≤t≤10)時(shí),對(duì)于每一種猜測(cè)值,分別計(jì)算t+1時(shí)刻的攻擊點(diǎn)狀態(tài)ft+1(IV,K),由于是逐比特攻擊,根據(jù)前面攻擊出的密鑰比特可以確定=0),故t時(shí)刻的攻擊點(diǎn)狀態(tài)ft(IV,K)已知,采用漢明距離模型計(jì)算攻擊點(diǎn)處的假設(shè)能量消耗值,記為=HW(ft⊕ft+1),1≤i≤4,0≤t≤10,其中=(,),分別對(duì)應(yīng)猜測(cè)密鑰比特為0和1,即Ht的規(guī)模為4×2。
(4)假設(shè)能量消耗值與能量跡匹配
與MICKEY 類似,針對(duì)Trivium 的能量攻擊也采用相關(guān)系數(shù)來(lái)確定假設(shè)能量消耗值與算法總體功耗的匹配程度。所不同的是,MICKEY 的能量攻擊中是根據(jù)整個(gè)相關(guān)系數(shù)矩陣中最大值確定猜測(cè)密鑰比特。在Trivium 的能量攻擊中,由于假設(shè)能量消耗矩陣H 每列僅含4個(gè)量,而密碼算法能量跡采樣點(diǎn)數(shù)(即P 列數(shù))遠(yuǎn)大于24,故從整條能量跡來(lái)看,無(wú)論密鑰猜測(cè)正確與否,Trivium 的相關(guān)系數(shù)矩陣ρ中都可能出現(xiàn)相關(guān)系數(shù)值很高的采樣點(diǎn),因此在分析不同猜測(cè)密鑰比特與能量跡的匹配情況時(shí),必須在該密鑰比特參與攻擊點(diǎn)運(yùn)算的時(shí)刻進(jìn)行。具體來(lái)說(shuō)就是,在攻擊k66-t(0≤t≤10)時(shí),比較t+1時(shí)刻能量跡采樣點(diǎn)與假設(shè)能量消耗值的相關(guān)系數(shù),下文將這一時(shí)刻稱為攻擊時(shí)刻。
與MICKEY 的仿真實(shí)驗(yàn)類似,在SMIC 0.18μm工藝庫(kù)下利用PTPX 獲取Trivium 算法運(yùn)算時(shí)的功耗,待攻擊密鑰K’=0x5a5b5c5d5e5fa5a6a7a8。圖6給出了攻擊k66,k65,k64和k63時(shí),攻擊點(diǎn)的假設(shè)能量消耗與算法總功耗的匹配情況,圖中縱軸為相關(guān)系數(shù),橫軸為功耗采樣點(diǎn),虛線框?qū)?yīng)于攻擊時(shí)刻。
圖6 仿真攻擊k66,k65,k64和k63時(shí)的相關(guān)系數(shù)
表4列出了攻擊k66,k65,k64,k63和k62時(shí),不同猜測(cè)密鑰比特在攻擊時(shí)刻的假設(shè)能量消耗值與能量跡的相關(guān)系數(shù)??梢钥吹?,當(dāng)密鑰猜測(cè)正確時(shí),假設(shè)能量消耗值與能量跡的相關(guān)系數(shù)幾乎為1,而當(dāng)猜測(cè)錯(cuò)誤時(shí),相關(guān)系數(shù)近似為0.5,與前文的分析高度吻合,驗(yàn)證了攻擊方案的有效性。
表4 攻擊k66,k65,k64,k63和k62時(shí)在攻擊時(shí)刻的相關(guān)系數(shù)
本文提出了同步流密碼PA 攻擊點(diǎn)選取策略,并以面向硬件的同步流密碼算法MICKEY 和Trivium 為例進(jìn)行了攻擊演示,給出了具體的攻擊方案及基于PrimeTimePX 等EDA 工具的仿真攻擊結(jié)果,證明了攻擊的有效性,進(jìn)而驗(yàn)證了攻擊點(diǎn)選取策略的合理性,為同步流密碼PA 攻擊的后續(xù)研究奠定了基礎(chǔ)。
最后,結(jié)合攻擊點(diǎn)選取策略,從抗能量攻擊的角度,對(duì)流密碼設(shè)計(jì)人員提出兩點(diǎn)安全性建議:①密鑰盡量并行加載,避免逐比特注入;②前饋函數(shù)中與密鑰有關(guān)抽頭數(shù)量盡可能多,避免一到一映射。
[1]ZANG Yuliang,HAN Wenbao.Differential power attack on linear feedback shift register[J].Journal of Electronic &Information Technology,2009,31 (10):2406-2410 (in Chinese).[臧玉亮,韓文報(bào).線性反饋移位寄存器的差分能量攻擊 [J].電子與信息學(xué)報(bào),2009,31 (10):2406-2410.]
[2]JIA Yanyan,HU Yupu,ZHAO Yongbin,et al.Correlation power analysis of DECIM v2 [J].The Journal of China Universities of Posts and Telecommunications,2011,18 (5):118-123.
[3]TANG Ming,CHENG Pingpan,QIU Zhenlong.Differential power analysis on ZUC algorithm[EB/OL].http://eprint.iacr.org/,Report 2012/299,2012.
[4]Sanjay Burman,Debdeep Mukhopadhyay,Kamakoti Veezhinathan.LFSR based stream cipher are vulnerable to power attacks[G].LNCS 4859:Berlin Heiderberg:Springer-Verlag,2007:384-392.
[5]Fischer W,Gammel BM,Kniffler O.Differential power analysis of stream ciphers [G].LNCS 4377:Berlin Heider-berg:Springer-Verlag,2007:257-270.
[6]ZANG Yuliang,ZENG Guang,HAN Wenbao,et al.Power attack on stream cipher MICKEY 2.0[J].Journal of PLA University of Science and Technology (Natural Science Edition),2009,10 (4):334-338 (in Chinese). [臧玉亮,曾光,韓文報(bào),等.MICKEY 流密碼算法的能量攻擊 [J].解放軍理工大學(xué)學(xué)報(bào) (自然科學(xué)版),2009,10 (4):334-338.]
[7]Matt Henricksen,Wun She Yap,Chee Hoo Yian,et al.Sidechannel analysis of the K2stream cipheR [G].LNCS 6168:Berlin Heiderberg:Springer-Verlag,2010:53-73.
[8]ECRYPT.ECRYPT stream cipher project[EB/OL].http://www.ecrypt.eu.org/stream/,2008.
[9]Tim Guneysu,Amir Moradi.Generic side-channel countermeasures for reconfigurable devices [G].LNCS 6917:Berlin Heidelberg:Springer-Verlag,2011:33-48.
[10]Stefan Mangard,Elisabeth Oswald,Thomas Popp.Power analysis attack [M].FENG Dengguo,ZHOU Yongbin,LIU Jiye,et al transl.Beijing:Science Press,2010:56-58 (in Chinese). [Stefan Mangard,Elisabeth Oswald,Thomas Popp.能量分析攻擊 [M].馮登國(guó),周永斌,劉繼業(yè),等譯.北京:科學(xué)出版社,2010:56-58.]
[11]Steve Babbage,Matthew Dodd.The stream cipher MICKEY 2.0[EB/OL].http://www.ecrypt.eu.org/stream/p3ciphers/mikcey-p3.pdf,2008.
[12]FAN Haifeng,YAN Yingjian,XU Jinfu,et al.Simulation of correlation power analysis against AES cryptographic chip[J].Computer Engineering and Design,2010,31 (2):260-262 (in Chinese). [樊海鋒,嚴(yán)迎建,徐金甫,等.AES密碼芯片的相關(guān)性功耗分析仿真 [J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31 (2):260-262.]