金雨璇, 楊宏志, 王相賓, 袁慶軍

1. 戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州450000

2. 河南省網(wǎng)絡(luò)密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室, 鄭州450000

3. 深圳網(wǎng)安計(jì)算機(jī)安全檢測(cè)技術(shù)有限公司, 深圳518028

1 引言

為配合我國(guó)WAPI (WLAN Authentication and Privacy Infrastructure) 無(wú)線局域網(wǎng)標(biāo)準(zhǔn)的推廣應(yīng)用, 2006 年1 月我國(guó)自主設(shè)計(jì)的對(duì)稱分組密碼算法SM4 分組密碼算法就此應(yīng)運(yùn)而生. 由于該算法加解密速度快、硬件實(shí)現(xiàn)簡(jiǎn)單以及具備一定的安全性, 多適用于制作密碼芯片, 現(xiàn)已大量運(yùn)用于對(duì)金融領(lǐng)域、政府部門等的重要數(shù)據(jù)的保護(hù). 因此單純通過(guò)研究密碼算法的數(shù)學(xué)結(jié)構(gòu)而判斷密碼算法的安全性已經(jīng)遠(yuǎn)遠(yuǎn)不夠, 我們還必須從密碼算法的實(shí)現(xiàn)角度來(lái)考慮更為現(xiàn)實(shí)的安全問(wèn)題. 如果硬件實(shí)現(xiàn)上出現(xiàn)了問(wèn)題, 算法理論安全性再高也無(wú)法保證數(shù)據(jù)的安全性. 如果SM4 算法硬件實(shí)現(xiàn)被攻破, 則意味著這些產(chǎn)品不再安全.

針對(duì)商用密碼算法的硬件實(shí)現(xiàn), 差分故障攻擊是一種實(shí)際有效的攻擊方法, 對(duì)密碼體制實(shí)際安全性造成極大威脅. 隨著密碼學(xué)家們的不斷深入研究并改進(jìn), 差分故障攻擊方法已被運(yùn)用于對(duì)DES[1]、ECC[2]、AES[3]、RC4[4]等眾多密碼算法的分析中, 并且取得了不俗的成果, 展示了差分故障攻擊在密碼分析上具有相當(dāng)強(qiáng)大的可行性. 在不斷地應(yīng)用發(fā)展中, 差分故障攻擊的實(shí)現(xiàn)途徑愈加多樣、攻擊代價(jià)逐步降低, 可以非常有效的對(duì)密碼硬件進(jìn)行攻擊, 成為了對(duì)密碼體制不容忽視的現(xiàn)實(shí)威脅.

如果可以更加快速的完成差分故障攻擊, 利用更少的故障注入即恢復(fù)出SM4 算法的輪密鑰及初始密鑰, 或者能夠更有效的從可能的密鑰中分辨出正確密鑰, 就能指導(dǎo)相關(guān)芯片的使用者、設(shè)計(jì)者對(duì)加密設(shè)備進(jìn)行保護(hù), 避免這類攻擊, 阻止攻擊者對(duì)其進(jìn)行故障誘導(dǎo), 有利于國(guó)產(chǎn)密碼的研究發(fā)展與使用.

本文在前輩工作的基礎(chǔ)上做出適當(dāng)?shù)母倪M(jìn)[5],給出SM4 單比特差分故障攻擊模型以及具體攻擊步驟,理論上只需要一次故障注入, 隨后對(duì)平均15.3526 比特窮舉搜索, 最終可以恢復(fù)128 比特的初始密鑰. 通過(guò)計(jì)算機(jī)實(shí)驗(yàn)對(duì)攻擊過(guò)程進(jìn)行仿真模擬, 根據(jù)實(shí)驗(yàn)結(jié)果佐證本文中提出的新方案攻擊復(fù)雜度與理論結(jié)果一致, 改進(jìn)后的攻擊方法在一定程度上提高了攻擊效率.

本文第2 節(jié)詳細(xì)介紹了SM4 算法的加密流程以及輪密鑰擴(kuò)展方案, 隨后整理總結(jié)了算法的相關(guān)性質(zhì)與定理; 第3 節(jié)具體闡述了差分故障攻擊的基本假設(shè)以及在該假設(shè)下的攻擊原理和攻擊流程; 第4 節(jié)總結(jié)了自SM4 算法發(fā)布以來(lái), 密碼學(xué)工作者對(duì)其已經(jīng)進(jìn)行過(guò)的差分故障攻擊方法, 并對(duì)各方案間的不同進(jìn)行了對(duì)比描述, 指明了各方案的優(yōu)劣; 第5 節(jié)提出對(duì)SM4 算法的單比特DFA 方案, 理論推導(dǎo)出攻擊復(fù)雜度,并通過(guò)仿真實(shí)驗(yàn)方案及實(shí)驗(yàn)結(jié)果數(shù)據(jù)對(duì)其加以佐證; 第6 節(jié)是對(duì)全文工作總結(jié).

2 SM4 算法

2.1 算法簡(jiǎn)述

SM4 算法由呂述望、李大為、張超等人設(shè)計(jì)并完成相關(guān)標(biāo)準(zhǔn)[6]的起草, 其分組長(zhǎng)度和密鑰長(zhǎng)度均為128 比特, 算法采用非平衡Feistel 結(jié)構(gòu). SM4 通過(guò)32 輪非線性迭代后加上一個(gè)反序變換, 方便于解密,解密輪密鑰只需要是加密輪密鑰的逆序, 而解密算法與加密算法保持一致.

(1) 系統(tǒng)設(shè)置

SM4 的加密密鑰為MK = (MK0,MK1,MK2,MK3), 其中MKi∈Z322,i = 0,1,2,3. 輪密鑰表示為(rk0,rk1,··· ,rk31), 其中rki(i=0,1,··· ,31) 為加密密鑰經(jīng)由密鑰擴(kuò)展方案生成的32 比特第i 輪輪密鑰.

FK=(FK0,FK1,FK2,FK3) 為系統(tǒng)參數(shù), CK=(CK0,CK1,··· ,CK31) 為固定參數(shù), 用于密鑰擴(kuò)展算法, 其中FKi(i=0,1,2,3),CKi(i=0,1,··· ,31) 均為32 比特.

設(shè)T : Z322→Z322為一個(gè)可逆變換, 由非線性變換τ 和線性變換L 復(fù)合而成, 即T (·) = L(τ(·)).其中非線性變換τ 由4 個(gè)并行的S 盒構(gòu)成. 設(shè)A,B ∈(Z82)4, 非線性變換τ 輸入為A=(a0,a1,a2,a3),輸出為B =(b0,b1,b2,b3), 即(b0,b1,b2,b3)=τ(A)=(S(a0),S(a1),S(a2),S(a3)).

L 為線性變換, 其輸入為非線性變換τ 的輸出. 設(shè)輸入為B ∈Z322, 輸出為C ∈Z322, 則C =L(B)=B ⊕(B ?2)⊕(B ?10)⊕(B ?18)⊕(B ?24). 其中?表示循環(huán)左移.

(2) 加密算法

首先執(zhí)行32 次迭代運(yùn)算, 即圖1 中所示的輪函數(shù)運(yùn)算, 即計(jì)算Xi+4=F (Xi,Xi+1,Xi+2,Xi+3,rki)=Xi⊕T (Xi+1⊕Xi+2⊕Xi+3⊕rki),i=0,1,··· ,31

圖1 SM4 算法輪函數(shù)示意圖Figure 1 Schematic diagram of SM4 algorithm round function

然后對(duì)最后一輪輸出數(shù)據(jù)進(jìn)行反序變換得到密文輸出,即(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32).

(3) 密鑰擴(kuò)展算法

設(shè)加密密鑰為MK = (MK0,MK1,MK2,MK3) ∈(Z322)4, 輪密鑰生成方法為rki= Ki+4= Ki⊕T′(Ki+1⊕Ki+2⊕Ki+3⊕CKi)(i=0,1,··· ,31), 其中K0= MK0⊕FK0, K1= MK1⊕FK1, K2=MK2⊕FK2, K3= MK3⊕FK3. 系統(tǒng)參數(shù)FK 的取值為FK0= (A3B1BAC6), FK1= (56AA3350),FK2=(677D9197), FK3=(B27022DC).

T′變換與T 變換類似, 將T 變換中的線性變換L 替換成L′(B) = B ⊕(B ?13)⊕(B ?23) 即可得到.

固定參數(shù)CK 取值方法為: 設(shè)cki,j為CKi的第j 字節(jié)(i=0,1,··· ,31,j =0,1,2,3), 即CKi=(cki,0,cki,1,cki,2,cki,3)∈(Z82)4, 而cki,j=(4i+j)×7(mod256). 其值請(qǐng)參見(jiàn)相關(guān)標(biāo)準(zhǔn)文獻(xiàn)[6].

(4) 解密算法

解密變換與加密變換類似, 不同的僅是輪密鑰的使用順序, 解密時(shí)使用輪密鑰序(rk31,rk30,··· ,rk0)即可.

2.2 算法性質(zhì)

SM4 算法擁有相當(dāng)優(yōu)良的抗差分性質(zhì), 在文獻(xiàn)[7–12] 中分別證明并介紹了此算法多個(gè)性質(zhì), 以及相關(guān)定理推論. 本文主要從S 盒以及線性變換介紹算法的如下5 個(gè)性質(zhì)及3 個(gè)定理.

(1) S 盒變換

S 盒的抗差分能力主要從其差分均勻度以及差分分布表兩方面刻畫, 且具有較小的差分均勻度是S 盒抗差分攻擊的必要條件, 以下兩條性質(zhì)說(shuō)明了SM4 的S 盒具有良好的抗差分性質(zhì).

性質(zhì)1 SM4 的S 盒對(duì)于任何非零的輸入差分, 存在127 個(gè)可能的輸出差分. 其中有一個(gè)輸出差分出現(xiàn)的概率為2?6, 其余輸出差分出現(xiàn)的概率為2?7[8].

設(shè)a,b ∈Z82, 則利用差分分布表求解給定輸入差分a、輸出差分b 的差分方程S(x)⊕S(x ⊕a)=b的復(fù)雜度由28降至1, 且其解至多有4 個(gè), 也即下述性質(zhì)2.

性質(zhì)2 SM4 算法S 盒的差分均勻度僅為4[7].

基于性質(zhì)1 以及差分分布表, 并給定三元組(x,x?,y), 對(duì)于差分方程S(x ⊕k)⊕S(x?⊕k) = y, 性質(zhì)3 描述了其可求解情況的性質(zhì).

性質(zhì)3 以S(·) 表示SM4 的S 盒變換, (x,x?,y) 為Z82中的隨機(jī)三元組, 則有下述事實(shí)成立:

①差分方程S(x ⊕k)⊕S(x?⊕k)=y 有解概率為0.4942;

②如果上述方程有解, 則解的個(gè)數(shù)平均值為2.0236[12].

(2) 線性變換

SM4 算法的線性變換L 由4 個(gè)異或操作與5 個(gè)移位操作組成(包括移0 位), 以下從SM4 的線性變換表明該算法抗差分性質(zhì)優(yōu)良.

分支數(shù)概念由J. Daemen 提出, 可以用于評(píng)測(cè)一個(gè)變換, 尤其是線性變換的差分?jǐn)U散效率, 下面給出其定義:

根據(jù)定義1 可知, 線性變換F 分支數(shù)最大可以達(dá)到5. 一般來(lái)說(shuō), 分支數(shù)越大, 線性變換的擴(kuò)散性質(zhì)越好. 當(dāng)F 分支數(shù)達(dá)到最大時(shí), 我們稱F 是最佳擴(kuò)散的. 而通過(guò)實(shí)驗(yàn)可證明, 對(duì)SM4 的線性變換有以下性質(zhì):

性質(zhì)4 SM4 中線性變換L 的分支數(shù)為5[8].

定理1 如果F (X,k,r1,··· ,rk) 是最佳擴(kuò)散的, 那么必然有k ≥5[9].

由定理1 可知, SM4 算法若想達(dá)到最佳擴(kuò)散性, 則移位操作必須達(dá)到 5 個(gè), 也即 L(B) =F (B,5,r1,··· ,r5). 又由鴿籠原理可知r1到r5中必有兩個(gè)落入同一字節(jié)內(nèi). 不失一般性的, 可設(shè)r1,r2都落入第一字節(jié), 即0 ≤r1

定理2 在r1,··· ,r5的14 336 種取值中, 只有兩種可以使得L 達(dá)到最佳擴(kuò)散性, 分別是SM4 的線性變換L 取值, 以及L 循環(huán)左移24 比特, 其本質(zhì)上是一致的.

綜上所述, SM4 算法的線性變換是最佳擴(kuò)散的，且是移位操作最少情況下唯一的.

最后給出SM4 算法加密算法線性變換的逆變換, 其證明可參看文獻(xiàn)[12]:

3 差分故障攻擊

3.1 DFA 原理

以分組密碼算法為例, 圖2 給出了差分故障攻擊的原理, 具體可描述如下: 現(xiàn)代分組密碼的非線性度大都由S 盒查表操作提供, 而對(duì)于某一輪S 盒的未知輸入值, 可根據(jù)分組密碼的結(jié)構(gòu)以及輪函數(shù)特性, 通過(guò)對(duì)密碼芯片進(jìn)行攻擊, 導(dǎo)入隨機(jī)故障值, 使其運(yùn)行過(guò)程的某中間狀態(tài)產(chǎn)生變化, 導(dǎo)致密碼設(shè)備給出錯(cuò)誤輸出. 于是根據(jù)得到正確密文與錯(cuò)誤密文的差分值, 滿足差分方程, 通過(guò)差分分析結(jié)合輪函數(shù)細(xì)節(jié)求解差分方程, 可以獲取該輪輸入值以及正確輸出值. 再利用運(yùn)算過(guò)程中輸入輸出值與涉及的相關(guān)密鑰之間的關(guān)系, 得到輪密鑰可能值集合, 然后通過(guò)多次攻擊不斷地縮小可能密鑰范圍, 最終實(shí)現(xiàn)輪密鑰以及初始密鑰的恢復(fù).

3.2 基本假設(shè)及攻擊流程

為更好地進(jìn)行差分故障攻擊, 通常攻擊者遵循的基本假設(shè)均為:

(1) 攻擊者完全掌握密碼設(shè)備, 可以在加密過(guò)程中任意時(shí)刻任意位置注入故障, 但故障具體值未知;

(2) 攻擊者可以獲得同一個(gè)明文在密鑰作用下正確加密得到的密文, 以及誘發(fā)故障后產(chǎn)生的錯(cuò)誤密文.

(3) 攻擊者可以多次重啟密碼設(shè)備, 以得到多個(gè)不同的錯(cuò)誤密文.

在以上的攻擊假設(shè)下, 差分故障攻擊的攻擊流程通常由四個(gè)步驟構(gòu)成: 確定故障模型、完成故障注入、進(jìn)行故障分析、實(shí)現(xiàn)密鑰恢復(fù). 圖3 展示了分組密碼算法的差分故障攻擊流程.

圖2 分組密碼算法DFA 原理Figure 2 DFA principle of block cipher algorithm

圖3 分組密碼算法DFA 流程Figure 3 DFA process of block cipher algorithm

4 SM4 算法DFA 研究進(jìn)展

在差分故障攻擊方向, 張蕾等人[13]于2006 年首先給出了SM4 算法的差分故障攻擊, 該模型采用了面向字節(jié)的隨機(jī)故障模型, 是最基礎(chǔ)的DFA 模型. 該模型故障注入位置為各輪的后三個(gè)存儲(chǔ)器, 理論上完成一輪子密鑰的恢復(fù)需要8 個(gè)錯(cuò)誤密文, 僅需要32 個(gè)錯(cuò)誤密文再結(jié)合密鑰擴(kuò)展方案, 就可以完全恢復(fù)出SM4 的128 比特種子密鑰. 因?yàn)閷?shí)際中故障發(fā)生的字節(jié)位置是不可能完全平均的, 所以實(shí)際攻擊所需錯(cuò)誤密文數(shù)將略大于理論值; 文中的實(shí)驗(yàn)結(jié)果也驗(yàn)證了這一事實(shí), 恢復(fù)SM4 的128 比特種子密鑰平均大約需要47 個(gè)錯(cuò)誤密文.

兩年后, 李瑋等人[14]對(duì)攻擊方案進(jìn)行了改進(jìn), 針對(duì)密鑰擴(kuò)展方案進(jìn)行故障注入. 在生成各輪子密鑰前注入故障與密鑰數(shù)據(jù)存儲(chǔ)器中, 最佳情況下可以影響到該輪的全部S 盒. 最高效率的情況下, 一次故障注入就可以對(duì)4 個(gè)S 盒都進(jìn)行有效攻擊, 兩次注入即可以恢復(fù)一輪子密鑰, 僅需要8 個(gè)錯(cuò)誤密文就可以恢復(fù)原始密鑰. 同時(shí)文中給出了判斷故障注入處的方法, 便于在攻擊過(guò)程中對(duì)于低效的故障注入直接舍棄,提高了故障誘導(dǎo)的攻擊成功率, 減少了錯(cuò)誤密文數(shù).

2011 年, Li R L 等人[12]一改之前傳統(tǒng)DFA 方案逐輪攻擊的方法, 利用SM4 算法獨(dú)特的差分路徑直接對(duì)第28 輪進(jìn)行故障注入, 對(duì)后五輪進(jìn)行統(tǒng)一的攻擊. 在攻擊者保證發(fā)生故障為單字節(jié)故障的前提下,這種新式的攻擊方法在第28 輪的后三個(gè)數(shù)據(jù)存儲(chǔ)器之一誘發(fā)故障, 僅需要一次故障注入, 即可恢復(fù)初始密鑰的大部分信息. 再經(jīng)過(guò)平均次窮舉搜索, 最終可恢復(fù)SM4 算法的初始密鑰.

以上DFA 方案皆是在仿真實(shí)驗(yàn)中實(shí)現(xiàn)的, 具有較苛刻的理論條件, 2016 年榮雪芳團(tuán)隊(duì)[15]提出符合實(shí)際攻擊狀況的方案, 不再要求在固定已知位置注入唯一單字節(jié)故障, 而只需要在算法后4 輪隨機(jī)進(jìn)行故障注入, 將理論引入了實(shí)踐. 通過(guò)對(duì)無(wú)防護(hù)SM4 算法的智能卡實(shí)施該攻擊的結(jié)果表明, 與其他攻擊方法相比, 該方法可擴(kuò)大故障注入的范圍, 提高故障攻擊的實(shí)用性.

5 改進(jìn)的SM4 算法差分故障攻擊

5.1 故障模型

目前針對(duì)SM4 算法的DFA 故障注入模型均基于字節(jié)注入, 而早在2010 年, Agoyan 等人就已經(jīng)利用激光的手段實(shí)現(xiàn)了對(duì)微控制器的單比特故障注入[16]. 更高精度的故障注入可以對(duì)算法硬件實(shí)現(xiàn)進(jìn)行更高效的攻擊, 因此現(xiàn)有故障模型無(wú)法準(zhǔn)確分析評(píng)估算法差分故障安全性. 并且, 由于單比特故障注入模型的故障值集合較小, 理論上針對(duì)各算法的差分故障攻擊均能有不同程度的效率提高. 針對(duì)激光注入等高精度故障注入技術(shù), 本文在文獻(xiàn)[12] 的基礎(chǔ)上進(jìn)行改進(jìn), 提出了一種針對(duì)SM4 算法的單比特的差分故障攻擊模型. 本模型基于以下的基礎(chǔ)假設(shè):

(1) 攻擊者可以獲得同一密鑰作用下的正誤密文對(duì), 且密鑰未知.

(2) 攻擊者可以誘發(fā)單比特的隨機(jī)故障.

5.2 基本過(guò)程

本文采用的攻擊模型為單比特的隨機(jī)故障模型, 攻擊的基本過(guò)程為

(1) 選擇明文攻擊, 獲取明文在密鑰作用下的正確密文;

(2) 重新加密明文, 加密進(jìn)行至第28 輪時(shí), 在第四個(gè)存儲(chǔ)器中注入故障, 隨后完成后續(xù)加密得到錯(cuò)誤密文;

(3) 通過(guò)差分分析推測(cè)最后一輪輪密鑰可能值;

(4) 在得到最后一輪輪密鑰可能值集合的基礎(chǔ)上, 推測(cè)得到倒數(shù)后四輪輪密鑰可能值集合;

(5) 利用第四步得到的所有輪密鑰逆推得到初始密鑰可能值集合;

(6) 通過(guò)暴力攻擊, 從初始密鑰可能值中得到正確密鑰.

6 SM4 算法的單比特DFA 攻擊

6.1 基本攻擊方法

(1) 計(jì)算?Bj=L?1(?Cj);

(2) 以ai表示?Aj的第i 個(gè)字節(jié)(i=0,1,2,3), 記為ai=(?Aj)i, 也即?Aj=a0||a1||a2||a3, 同理bi=(?Bj)i;

(3) 根據(jù)ai,bi, 結(jié)合性質(zhì)1給出的差分分布表可以得到各字節(jié)所有可能輸入值INj(ai,bi).

(4) 推導(dǎo)密鑰與輸入輸出間的關(guān)系(rkj?1)i= (Aj)i⊕INj(ai,bi), 可以得到密鑰rkj?1的第i 個(gè)字節(jié)可能值集合ki;

根據(jù)上述攻擊過(guò)程以及性質(zhì)3, 給定二元組(?A,?C), 可以得到如下結(jié)論:

6.2 攻擊過(guò)程詳述

本節(jié)對(duì)具體的攻擊過(guò)程進(jìn)行詳述.

(1) 獲取正誤密文對(duì)

隨機(jī)選擇一個(gè)明文X = (X0,X1,X2,X3), 并對(duì)其正確加密獲得正確密文Y = (Y0,Y1,Y2,Y3). 在同樣的密鑰作用下對(duì)明文再次加密, 在加密過(guò)程中對(duì)第28 輪注入1 比特的故障

(2) 猜測(cè)后四輪密鑰值

由于明文以及正誤密文對(duì)已知, 而加密算法的最后進(jìn)行的逆序變換易于求逆, 因此可利用上文提到的基本攻擊方法對(duì)后四輪逐輪進(jìn)行差分攻擊, 分別推導(dǎo)出第32 輪到第29 輪的輪密鑰.

計(jì)算A32=X32⊕X33⊕X34⊕rk31,A?32=X?32⊕X?33⊕X?34⊕rk31, 則對(duì)于第32 輪T 變換, 其輸入差分和輸出差分分別為

此時(shí)利用前述基本攻擊方法可得rk31可能值集合rk31

利用①步中得到的所有輪密鑰可能值, 對(duì)正誤密文進(jìn)行一輪的解密可以得到

對(duì)得到的所有二元組(?A31,?C31) 進(jìn)行基本攻擊, 得到可能密鑰集合rk31,rk30.

用②步中得到的所有(rk31,rk30)∈rk31,rk30, 對(duì)正誤密文進(jìn)行兩輪的解密可以得到

考慮第30 輪的輪函數(shù), 計(jì)算所有可能的

利用其對(duì)第30 輪進(jìn)行基本攻擊, 由每組(?A30,?C30) 求得后三輪密鑰候選值集合rk31,rk30,rk29.

與上節(jié)同理, 首先用③步中得到的所有(rk31,rk30,rk29) ∈rk31,rk30,rk29, 對(duì)正誤密文進(jìn)行三輪的解密可以得到

考慮第29 輪的輪函數(shù), 計(jì)算?A29,?C29所有候選值, 其中

對(duì)第29 輪進(jìn)行基本攻擊, 由每組(?A29,?C29) 求得后四輪密鑰候選值集合rk31,rk30,rk29,rk28.

(3) 恢復(fù)初始密鑰

利用密鑰擴(kuò)展方案的逆, 對(duì)步驟2 中得到的所有密鑰可能值求逆, 得到初始密鑰候選值集合MK.用MK中所有初始密鑰候選值對(duì)正確密文解密, 并判斷是否與明文相同. 由于密鑰固定時(shí), 密碼算法都是明文集合到密文集合的雙射, 所以最終僅可能有一個(gè)密鑰通過(guò)判斷.

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

根據(jù)上一節(jié)提出的攻擊方法可知, 最終恢復(fù)出的密鑰個(gè)數(shù)不止一個(gè). 因此本節(jié)從理論上給出各輪輪密鑰可能值個(gè)數(shù)的期望, 用以描述攻擊復(fù)雜度.

(1) rk31個(gè)數(shù)期望值

在完成第32 輪的基本攻擊時(shí), 由差分路徑以及輪函數(shù)運(yùn)算規(guī)則可以得到?X31= L(?B28), 那么可

得

若記L?1(?X35)?=(d0,d1,d2,d3), 則可知?B32有四類可能取值

其中0 ?= γ ∈F82為?B28中故障發(fā)生字節(jié)的對(duì)應(yīng)值. 對(duì)于單比特故障的情況, γ 可能值經(jīng)實(shí)驗(yàn)知有254個(gè), γ 不會(huì)取值0x7F.

記?A32?= (a0,a1,a2,a3), 對(duì)照差分分布表, 對(duì)所有i = 0,1,2,3 比對(duì)是否存在輸入差分為ai, 輸出差分為di.

若存在某0 ≤i ≤3, 使得S(x)⊕S(x ⊕ai) = di無(wú)解, 則說(shuō)明該字節(jié)為故障發(fā)生字節(jié). 不失一般性的, 可以假設(shè)i = 3 時(shí)方程無(wú)解. 若為此情況, 前三字節(jié)密鑰可以通過(guò)差分分布表得到可能取值,第四字節(jié)密鑰則需要遍歷得知. 在這種情況下, 得到的第32 輪輪密鑰的可能值集合rk31中, 平均有(2.0236)3×254×0.4942×2.0236 ≈211.0395個(gè)元素.

若不存在, 也即對(duì)?i,0 ≤i ≤3,S(x)⊕S(x ⊕ai)=di都有解, 此時(shí)無(wú)法判斷故障發(fā)生的字節(jié). 由于注入的故障可能發(fā)生在任一字節(jié), 故?B28可能有1016 個(gè)可能值. 此時(shí)得到的第32 輪輪密鑰的可能值集合中平均有(2.0236)3×1016×0.4942×2.0236=213.0395個(gè)元素.

由于?i,0 ≤i ≤3,S(x)⊕S(x ⊕ai) = di有解的可能性為0.4942, 故第32 輪子密鑰可能值集合的元素個(gè)數(shù)平均為(1 ?0.4942)×211.0395+0.4942×213.0395≈212.3514.

(2) (rk31,rk30) 個(gè)數(shù)期望值

如果在上一步已知故障發(fā)生字節(jié), 則?X30= E 有8 種可能取值, 而?X34是固定已知的, 因此相應(yīng)的可知?C31= ?X30⊕?X34= E ⊕?X34有8 種取值. 此時(shí)可以推知RK31,RK30中元素個(gè)數(shù)期望值約為211.0395×8×2?4.0673×24.0677= 214.0399; 否則?X30有32 種可能取值, 進(jìn)而可知cardRK31,RK30=213.0395×32×2?4.0673×24.0677=214.0399=216.0399.

(3) (rk31,rk30,rk29) 個(gè)數(shù)期望值

在本輪攻擊中, 由于?C30= ?X33是確定的值, 可由密文直接得到, 因此rk29求取情況取決于得到的本輪差分方程組的個(gè)數(shù), 以及其是否可解.

(4) (rk31,rk30,rk29,rk28) 個(gè)數(shù)期望值

與上節(jié)同理, ?C29=?X32可由密文直接得到. 此時(shí)如果已知故障發(fā)生位置, 則可知

7 攻擊實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文中攻擊方法的攻擊復(fù)雜度理論值的正確性, 在普通PC 機(jī)器(CPU 為Intel(R)Core(TM)i5-6200U @ 2.30 GHz 2.40 GHz, 內(nèi)存8 GB) 上使用C 語(yǔ)言(Visual C++ 6.0) 編程實(shí)現(xiàn)本文提出的攻擊方法的仿真實(shí)驗(yàn). 每次實(shí)驗(yàn)的明文以及密鑰數(shù)據(jù)皆由計(jì)算機(jī)隨機(jī)生成, 不含任何特殊要求, 利用計(jì)算機(jī)模擬故障注入過(guò)程, 得到正誤密文.

編號(hào) rk31 (rk31,rk30) (rk31,rk30,rk29) (rk31,rk30,rk29,rk28) 故障位置 遍歷復(fù)雜度(bit)1 2064 18 432 26 624 65 024 第2 字節(jié) 15.9887 2 2032 18 432 20 480 65 152 第4 字節(jié) 15.9915 3 8128 257 536 221 184 130 048 未知 16.9887 4 8128 243 456 276 480 203 264 未知 17.6330 5 8136 242 688 243 712 204 800 未知 17.6439 6 2064 17 792 40 960 65 152 第3 字節(jié) 15.9915 7 8128 263 680 245 760 199 168 未知 17.6036 8 2048 16 896 28 672 65 152 第1 字節(jié) 15.9915 9 2048 16 128 8192 65 024 第2 字節(jié) 15.9887 10 8128 263 936 278 528 132 480 未知 17.0154

我們進(jìn)行了1000 次實(shí)驗(yàn), 本文給出前十次的實(shí)驗(yàn)數(shù)據(jù)如表1所示, 其中2 到4 列表示對(duì)應(yīng)項(xiàng)元素個(gè)數(shù). 由表中數(shù)據(jù)可以看出, 每次攻擊經(jīng)過(guò)較低復(fù)雜度的暴力攻擊即可以成功恢復(fù)128 比特的SM4 初始密鑰. 當(dāng)可推知故障發(fā)生位置時(shí), 最終的遍歷復(fù)雜度約為216; 未知故障發(fā)生位置時(shí), 遍歷復(fù)雜度稍高, 約為217.5.

另外, 實(shí)驗(yàn)數(shù)據(jù)略高于理論推導(dǎo)值, 這是由于在推算暴力攻擊的理論值時(shí), 認(rèn)為SM4 算法的差分方程解平均為2.0236 個(gè), 但是實(shí)際上據(jù)差分分布表可知存在差分方程的解為4 個(gè). 對(duì)每一輪的攻擊需要對(duì)4個(gè)字節(jié)的差分方程進(jìn)行求解, 只要有一個(gè)方程的解為4 個(gè), 最終暴力攻擊的復(fù)雜度就會(huì)增大1 比特. 一次完整的攻擊需要求解16 個(gè)方程, 是完全有可能出現(xiàn)4 解方程的, 因此在實(shí)驗(yàn)中認(rèn)為偏差2 比特都是可以接受的. 圖4 展示了1000 個(gè)實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)圖, 由此可看出, 總體上實(shí)驗(yàn)數(shù)據(jù)是符合理論推導(dǎo)值的.

8 總結(jié)與展望

本文在總結(jié)對(duì)比已有的針對(duì)SM4 算法的差分故障攻擊的基礎(chǔ)上, 面對(duì)現(xiàn)有故障注入能力大幅度提升的現(xiàn)狀, 本文給出了一個(gè)針對(duì)SM4 算法的改進(jìn)的差分故障攻擊方案. 通過(guò)理論推導(dǎo)可知, 本文提出的攻擊模型僅需要通過(guò)在第28 輪的第4 個(gè)數(shù)據(jù)存儲(chǔ)器中誘發(fā)一次單比特故障, 再經(jīng)過(guò)對(duì)平均15.3526 比特的窮舉搜索, 最終可以恢復(fù)128 比特的初始密鑰. 并且, 通過(guò)計(jì)算機(jī)實(shí)驗(yàn)仿真模擬可以佐證本文中提出的新方案攻擊復(fù)雜度與理論結(jié)果一致. 在表2 中, 展示了本文與針對(duì)SM4 算法的已有差分故障攻擊的結(jié)果對(duì)比.結(jié)果顯示, 本文提出的新攻擊方案較以往的方案相比攻擊效率有較為明顯的提升.

下一步的研究方向是考慮多次單比特故障注入的情況, 進(jìn)一步提高攻擊效率優(yōu)化攻擊性能. 另外, 基于單比特故障攻擊模型的假設(shè)較強(qiáng), 下一步工作可以通過(guò)調(diào)整攻擊相關(guān)參數(shù), 在模型假設(shè)條件與攻擊效率之間尋找平衡. 在未來(lái)的研究中, 將擴(kuò)展本文提出的攻擊模型的分析對(duì)象, 繼續(xù)研究針對(duì)其他算法的單比特差分故障攻擊.

文獻(xiàn) 故障模型 故障位置 所需錯(cuò)誤密文數(shù) 故障注入輪數(shù) 遍歷復(fù)雜度文獻(xiàn)[13] 面向字節(jié) 加密算法 32 4 -文獻(xiàn)[14] 面向字節(jié) 密鑰編排方案 8 4 -文獻(xiàn)[12] 面向字節(jié) 加密算法 1 1 22.11本文 面向比特 加密算法 1 1 15.35