針對帶DFA防護(hù)SM4的SIFA攻擊

譚子欣 胡永波 龔彥昊 胡春雅 張 琪 朱文鋒 龔子超

(深圳市匯頂科技股份有限公司上海分公司脆弱性分析實驗室 上海 201210)

自1997年Boneh等人[1]在RSA算法上成功實現(xiàn)了故障注入攻擊并破解密鑰之后,故障注入攻擊在密碼學(xué)領(lǐng)域以勢如破竹之勢迅猛發(fā)展.故障注入后的輸出分為2種類型:一種是有效錯誤,攻擊者可利用這種錯誤計算結(jié)果進(jìn)行差分故障分析[2]、碰撞故障分析(collision fault analysis, CFA)[3]、統(tǒng)計故障攻擊(statistical fault attack, SFA)[4]、故障敏感性分析(fault sensitivity analysis, FSA)[5]以及差分錯誤強(qiáng)度分析(differential fault intensity analysis, DFIA)[6]等一系列分析手段.另一種是故障未能影響輸出結(jié)果,攻擊者無法直接利用,通常稱之為無效錯誤.

針對有效錯誤的故障注入防護(hù)方案通常有冗余防護(hù)[7]以及傳染防護(hù)[8].冗余防護(hù)主要用于對稱算法和非對稱算法,傳染防護(hù)主要用于對稱算法.冗余防護(hù)即重復(fù)進(jìn)行1次或多次密碼計算,再將每次計算結(jié)果進(jìn)行比對,僅當(dāng)比對正確才將運(yùn)算結(jié)果輸出.傳染防護(hù)即利用偽計算和冗余計算混淆至真實的輪運(yùn)算中,當(dāng)有故障注入到密碼算法的計算中時,產(chǎn)生的錯誤將會逐輪次地傳遞下去,以保證密碼算法無法輸出對攻擊者有效的錯誤輸出,即有效錯誤.雖然傳染防護(hù)可以避開單次輸出檢查防護(hù)所遇到的跳過檢查的問題,但也需要通過檢查輸出保證密碼算法正常的功能,以供用戶使用.在以硬件實現(xiàn)密碼算法的實際安全產(chǎn)品中,由于傳染防護(hù)方案相對于輸出檢查防護(hù)方案增加了更多的邏輯布線,出于對算法實現(xiàn)開銷的權(quán)衡,多采用冗余防護(hù)方案.

目前對于冗余防護(hù)方案的有效攻擊方式有IFA和SIFA.IFA在2007年由Clavier[9]首次提出,該方案的創(chuàng)造性主要在于可以無需有效錯誤即可還原DES的密鑰,同時還可以避開輸出檢查防護(hù),但I(xiàn)FA需要故障注入精準(zhǔn)到指令級別,使最后輪次的中間值產(chǎn)生固定錯誤,此類攻擊方案對于故障注入的技術(shù)要求較高,依賴于特定的故障模型(如置0模型等),不易于實現(xiàn).2018年,Dobraunig等人[10]提出了比IFA方案更加便于實現(xiàn)的SIFA方案,其不需要指定的故障模型,只要求輸出結(jié)果與注入故障的中間值之間存在依賴關(guān)系,該方案分別對帶冗余防護(hù)方案的AES算法和帶傳染防護(hù)的AES算法成功實現(xiàn)了SIFA攻擊.SIFA方案除了無效錯誤相關(guān)的密文或明文,無需攻擊者更多信息,因此在現(xiàn)實攻擊中具有較強(qiáng)的實用性.

對于SM4算法[11],由于其本身是抗差分分析和線性分析的,所以目前比較有效的攻擊手段主要是差分故障分析.如2006年Zhang等人[12]首次提出的對SM4的差分故障分析,僅通過約47條錯誤密文就能恢復(fù)128b種子密鑰;2011年Li等人[13]提出了一種基于單字節(jié)錯誤模型的DFA方案,其恢復(fù)出128b種子密鑰的平均計算復(fù)雜度只需要222.11;2019年,朱仁杰[14]針對SM4算法提出了一種擴(kuò)大故障注入范圍DFA方案,其破解出128b種子密鑰的計算復(fù)雜度甚至可以降低至210;2020年金雨旋等人[15]提出了一種基于單比特故障模型的DFA方案,其恢復(fù)128b種子密鑰的平均計算復(fù)雜度為215.3526.以上攻擊方案都是針對沒有防護(hù)的SM4算法,一旦帶有冗余防護(hù)等DFA防護(hù)(即有效錯誤防護(hù))之后,DFA分析便難以開展,所以為了對抗DFA防護(hù),本文基于文獻(xiàn)[10]的SIFA思想,對帶DFA防護(hù)方案的SM4算法展開研究.本文的主要貢獻(xiàn)為:首次針對SM4提出了一套抵抗DFA防護(hù)的隨機(jī)明文SIFA方案,并以234的計算復(fù)雜度完成了對128b種子密鑰的破解,同時給出了另外一套選擇明文SIFA方案,該方案能夠?qū)⒐テ品N子密鑰的計算復(fù)雜度降低至212,從計算效率上優(yōu)于大部分針對無防護(hù)SM4的DFA方案.

1 預(yù)備知識

1.1 帶冗余防護(hù)的SM4方案

SM4是一種分組為128b長度、密鑰為128b長度的分組密碼,由于SM4是對稱結(jié)構(gòu),其加密過程和解密流程共用一個結(jié)構(gòu).在安全產(chǎn)品的實際應(yīng)用中,為了有效防止SM4遭受DFA攻擊,最常見的做法是通過冗余保護(hù)阻止有效錯誤結(jié)果的輸出,本文所使用的帶冗余防護(hù)的SM4算法如下所示:

算法1.帶冗余防護(hù)的SM4算法.

輸入:P,K;

輸出:C=SM4ENC(P,K).

① 計算C←SM4ENC(P,K);

② 計算P′←SM4DEC(C,K);

③ 如果P=P′,則輸出C,否則生成隨機(jī)數(shù)r并輸出r.

1.2 帶統(tǒng)計無效錯誤分析

SIFA的主要思想是通過故障注入,使得原本分布均勻的中間值變得不均勻,然后利用分布不均勻的中間值變量對真實輪密鑰的偏向性,即受影響的中間值狀態(tài)位對輪密鑰位具有非線性依賴關(guān)系,同時其他錯誤密鑰推導(dǎo)出的錯誤中間值會呈現(xiàn)出均勻的分布,再利用SEI或者CHI計算出非均勻分布與均勻分布之間的距離,從而區(qū)分出真實的密鑰.

本文采用SEI來區(qū)分非均勻分布與均勻分布的偏差,當(dāng)X={xi}i∈[0,n-1],X的SEI計算公式如下所示:

SEI(X)=

其中#{i|xi=δ,i∈[0,n-1]}表示集合X中xi=δ的個數(shù).

2 針對帶冗余防護(hù)SM4算法的SIFA

本節(jié)將詳細(xì)介紹對帶冗余防護(hù)SM4算法的SIFA實現(xiàn),首先介紹基于隨機(jī)明文的SIFA方案,然后再介紹為了降低攻擊復(fù)雜度而設(shè)計的選擇明文SIFA方案.

2.1 基于隨機(jī)明文的SIFA

2.1.1 算法原理

在本文的攻擊方案設(shè)計中,選擇帶冗余防護(hù)SM4算法(算法1)的步驟①(詳見1.1節(jié))作為攻擊目標(biāo),對其第2輪中S非線性變換注入故障,圖1展示了本文進(jìn)行故障注入的具體位置.

圖1 SM4前2輪算法框圖

算法2.攻擊算法A.

輸入:明文集合Pgot={Pi}{i∈[0,3]},其中Pi表示Pgot中的第i字節(jié)組成的數(shù)據(jù)集;

輸出:seimax,rsk.

① 初始化seimax=0,rsk=0,kguess=0;

② 計算temp=P2⊕P3⊕L(S(P1⊕P2⊕P3⊕kguess));

③ 計算seii=SEI(temp[j]),其中j∈[0,3],temp[j]表示temp中的第j字節(jié)組成的數(shù)據(jù)集;

④ 若{seii}i∈[0,3]中存在seik>seimax,則seimax=seik,rsk=kguess;

⑤ 計算kguess=kguess+1;

⑥ 當(dāng)kguess∈[0,232-1],返回步驟②,否則進(jìn)入步驟⑦;

⑦ 輸出seimax和rsk.

在獲得rsk0之后,采用同樣的方式分別對第3～5輪的S變換進(jìn)行故障注入,然后相繼將rsk1,rsk2,rsk3解析出來,最后根據(jù)密鑰擴(kuò)展算法的流程,逆向推導(dǎo)出種子密鑰K,故基于隨機(jī)明文的SIFA方案的計算復(fù)雜度為234.

2.1.2 仿真實驗

本文設(shè)計仿真實驗如下:先設(shè)置密鑰K=0x676F6F6469787661747261696E696E67,其首輪輪密鑰為0x8A443F8C,然后隨機(jī)生成1萬條仿真明文數(shù)據(jù)M,再計算這些明文對應(yīng)的中間值temp.為了構(gòu)造出非均勻分布的temp集合,選擇所有temp[0,:]∈(50,200)(即temp的第0字節(jié)的數(shù)值在50～200之間)對應(yīng)的明文組成新的明文集M′,M′所對應(yīng)的中間值為temp′,經(jīng)過篩選后M′剩余5500條明文.圖2展示了temp第0字節(jié)分布與temp′第0字節(jié)分布的對比圖,其中圖2(a)對應(yīng)temp的第0字節(jié)分布,圖2(b)對應(yīng)temp′的第0字節(jié)分布.

圖2 第0字節(jié)分布對比圖

然后將M′輸入到算法2中,計算出所有候選密鑰所對應(yīng)的SEI值,由于候選密鑰的范圍較大,不宜在圖中完整展示,故而本文選擇了候選密鑰范圍為0x8A430000～0x8A46FFFF,橫坐標(biāo)共計196603個候選值,具體如圖3所示,發(fā)現(xiàn)輪密鑰0x8A443F8C所對應(yīng)的SEI值高于其他錯誤輪密鑰對應(yīng)的SEI值,因此得出真實的輪密鑰為0x8A443F8C.

圖3 部分SEI-候選密鑰對應(yīng)圖

2.1.3 基于STM32F103CT6的實際攻擊

為了檢驗實際攻擊的有效性,本文首先按照1.1節(jié)中的設(shè)計,將帶冗余防護(hù)的SM4在keil軟件通過C語言實現(xiàn)后,將其下載至單片機(jī)STM32F103CT6中,然后基于電壓毛刺故障注入平臺搭建環(huán)境,平臺連接示意如圖4所示:

圖4 電壓毛刺故障注入平臺連接示意圖

正常工作電壓為3.3V,毛刺電壓配置為0V,隨機(jī)毛刺脈寬配置為500～550ns,電壓毛刺的觸發(fā)信號設(shè)在SM4第2輪輪計算開始位置.為了能讓故障發(fā)生在S變換時間區(qū)域,配置毛刺延遲約為630ns,通過電壓毛刺造成的瞬時掉電使得S變換功能紊亂,從而引入故障.

首先將SM4的密鑰配置成固定形式,如K=0x676F6F6469787661747261696E696E67,然后傳入2000條隨機(jī)明文數(shù)據(jù),在電壓毛刺的故障注入下,有1799條數(shù)據(jù)由于觸發(fā)冗余防護(hù)而輸出隨機(jī)數(shù),剩余201條由于未觸發(fā)冗余防護(hù)或者故障注入未成功而返回正常密文.將這201條明文輸入到算法2,可以計算出所有候選密鑰對應(yīng)的SEI值,圖5展示了候選密鑰范圍在0x8A430000～0x8A46FFFF的SEI值.其中0x8A443F8C所對應(yīng)的SEI值最大,故而得到候選輪密鑰0x8A443F8C為真實輪密鑰.

圖5 在實際攻擊中部分SEI-候選密鑰對應(yīng)圖

隨后用真實輪密鑰和這201條明文計算出中間值temp′,發(fā)現(xiàn)temp′呈現(xiàn)出單字節(jié)分布不均勻的特征,其中圖6(a)中展示的第0字節(jié)分布表現(xiàn)出的不均勻特性尤為明顯.

圖6 實際攻擊后temp′的字節(jié)分布圖

2.2 基于選擇明文的SIFA

2.1節(jié)所介紹的攻擊需要對rsk0猜測232次,因此實現(xiàn)攻擊的計算量非常大,本節(jié)提出一種選擇明文攻擊方式能夠降低攻擊的運(yùn)算量,由于K0是一個固定值,而且X1⊕X2⊕X3⊕rsk0是一個32b的中間值,因此要計算出L(S(X1⊕X2⊕X3⊕rsk0)),需要猜測32b的密鑰,當(dāng)把X1⊕X2⊕X3⊕rsk0表示為4個獨(dú)立的字節(jié){t0,t1,t2,t3},有

L(S(X1⊕X2⊕X3⊕rsk0))=
L(S({t0,t1,t2,t3}))=L(S[t0]<<24)⊕
L(S[t1]<<16)⊕L(S[t2]<<8)⊕L(S[t3]).

假設(shè)能使t1～t3固定成任意常數(shù),即固定明文X1⊕X2⊕X3的第1～3字節(jié)為常數(shù),則L(S[t1]<<16)⊕L(S[t2]<<8)⊕L(S[t3])=α,α為常數(shù),故而

L(S(X1⊕X2⊕X3⊕rsk0))=L(S(t0))⊕α,

然后可以得到

Y1⊕Y2⊕L(S(X1⊕X2⊕X3⊕rsk0))=
Y1⊕Y2⊕L(S(t0)<<24)⊕α.

此時要得到中間值temp=Y1⊕Y2⊕L(S(t0)<<24)⊕α,只需計算L(S(t0)<<24),而計算t0只需要遍歷rsk0的高8b即可,即遍歷rsk0[0].

算法3.攻擊算法B.

輸出:seimax,rsk_bytenum.

① 初始化seimax=0,rsk_bytenum=0,t=0;

② 若bytenum=0,令e=S(t)<<24;

③ 若bytenum=1,令e=S(t)<<16;

④ 若bytenum=2,令e=S(t)<<8;

⑤ 若bytenum=3,令e=S(t);

⑧ 若{seii}i∈[0,3]中存在seii>seimax,則seimax=seii,rsk_bytenum=t;

⑨ 計算t=t+1;

⑩ 若t∈[0,28-1],返回步驟②,否則進(jìn)入下一步;

同理,用同樣的方法分別攻擊第3～5輪的S變換,直到破解出rsk1,rsk2,rsk3,最后再通過密鑰擴(kuò)展的逆運(yùn)算獲取種子私鑰K.因此,本節(jié)方法可以將計算復(fù)雜度降低至212.

本文提出的SIFA攻擊方案不僅可以抵御DFA防護(hù),選擇明文SIFA方案在效率上甚至優(yōu)于現(xiàn)有大部分針對無防護(hù)SM4的攻擊方案,具體如表1所示:

表1 本文方案與現(xiàn)有方案對比情況

3 結(jié) 語

本文首次提出了一套針對帶DFA防護(hù)SM4的SIFA方案,并通過仿真進(jìn)行了實驗驗證.同時,本文針對帶冗余防護(hù)的SM4算法,在單片機(jī)STM32F103CT6上成功破解了密鑰,計算復(fù)雜度為234.實驗證明,只需要少量的帶有無效錯誤的密文所對應(yīng)的明文,便可實施攻擊.另外還提出了一套基于選擇明文的SIFA方案,能夠?qū)⒂嬎銖?fù)雜度降低至212,從計算效率上優(yōu)于目前大多數(shù)針對無防護(hù)SM4的DFA方案.

本文提出的針對SM4的SIFA攻擊方案同樣可以應(yīng)用于帶掩碼防護(hù)的SM4方案以及帶傳染防護(hù)的SM4方案.對于帶掩碼防護(hù)的方案,攻擊者需要對第2輪S變換進(jìn)行注錯,導(dǎo)致sout1的2條掩碼數(shù)據(jù)發(fā)生無效錯誤,使得正確密文所對應(yīng)的真實sout1依舊呈現(xiàn)出不均勻分布,攻擊者通過重復(fù)加密過濾出正確的密文,再將正確密文帶入本文提出的隨機(jī)明文SIFA方案,破解出首輪的輪密鑰,直至破解出SM4的完整密鑰.而對于帶傳染防護(hù)的SM4方案,只需要通過重復(fù)加密過濾出帶有無效錯誤的正確密文即可.

通過驗證,也更加證實了SIFA策略對于帶DFA防護(hù)的對稱算法方案存在較大威脅,但從文獻(xiàn)[10]的結(jié)果與本文的實踐不難看出,SIFA策略對于攻擊的時間位置依舊存在較大的依賴性,因為隨著無效錯誤在正常密文中的比重減少,目標(biāo)中間值的分布也將趨近于均勻分布,故給密碼算法增加隨機(jī)延遲防護(hù)或添加偽計算防護(hù)可以很好地提高SIFA攻擊難度,從攻擊復(fù)雜度上削弱SIFA的效率.