一種DEFAULT 密碼算法抵抗差分故障攻擊新方法

顏林洋 ,郝 婕 ,李靈琛

(1.桂林電子科技大學 計算機與信息安全學院,廣西 桂林 541004;2.北京市經濟管理學校,北京 100142)

1997年,Boneh等[1]針對RSA 密碼算法首次提出故障攻擊。隨后,Biham 等[2]成功將差分故障攻擊運用于DES算法的破譯。2017年,李浪等[3]通過在DBLOCK密碼算法的第17輪多次隨機注入故障,平均只需4 次故障就可以恢復其主密鑰;2019 年,Khairallah等[4]通過在非線性層注入非均勻分布故障,提出了一種針對SPN 密碼結構的差分故障攻擊方法,并有效減少了密鑰的搜索空間;2020年,Karmakar等[5]針對NIST 候選算法SIV-Rijndael 256提出一種基于經典策略與密鑰編排相結合的差分故障攻擊方法,且僅使用一個隨機字節故障就可以恢復密鑰。

另一方面,2010年,李瑋[6]通過大量的故障攻擊實驗,證明了包括DES、AES在內的國際主流密碼算法,在不加防護的情況下往往不足以抵抗差分故障攻擊。實際上,故障注入攻擊的防護技術也不斷涌現,主要包括實現級的防護和算法級的防護2種。實現級的防護包括冗余實現、編碼校驗及感染等實現方式;2015年,張海峰等[7]利用同一輸入加密算法的不同級,獲取相應的計算結果,驗證輸出的結果是否一致,判斷是否被注入故障,以抵御差分故障攻擊;2018年,Patranabis等[8]提出了確定性和隨機性2種感染技術來保護AES密碼算法,以抵抗差分故障攻擊;2019年,Benhadjyoussef等[9]提出了一種基于奇偶校驗的錯誤檢測方案,其核心思想是基于奇偶校驗對AES 算法進行防護;同年,Lasheras等[10]提出一種通過模糊輸出值來應對故障攻擊的輕量級防御對策;隨后,Aghaie等[11]利用錯誤檢測限制了故障的傳播;2020 年,Lasheras等[12]提出一種通過少量冗余檢測故障并感染中間狀態的輕量級防御對策;同年,Potestad-Ordonez等[13]利用漢明碼來檢測密碼算法中被注入的故障,并將其應用于AES算法,有效保護了AES算法抵御差分故障攻擊;隨后,Bauer等[14]利用奇偶校驗碼并發檢錯基于ARX 的算法;2021年,Rasoolzadeh等[15]同時引入糾錯和檢錯結構,實現對故障攻擊的防護。另一方面,算法級的防護方法研究也有一些新進展:2019年,Beierle等[16]提出一種可調分組密碼算法CRAFT,并用可調模型來保護其免受差分故障攻擊;2021年,Baski等[17]在亞密會上提出了DEFAULT算法,該算法利用具有線性結構的S盒來抵抗差分故障攻擊(而無需額外的冗余措施),該密鑰長為128 bit的算法版本可以抵抗差分故障攻擊,其計算復雜度代價為264次運算;隨后,Nageler等[18]分析了DEFAULT算法S盒的線性結構的相關性質,構建等價密鑰,用少于100個故障和極低計算代價就可以恢復主密鑰。目前DEFAULT 算法仍無法直接抵抗差分故障攻擊。如何設計新的防護方案確保DEFAULT 密碼算法能有效抵抗故障攻擊亟待進一步解決。

基于DEFAULT算法的結構特點,結合冗余實現橫向混淆(或縱向隱藏)及線性碼提出了一種新的防護方案。該方案使用橫向混淆來對冗余部分進行實現,保證算法抵抗非比特級別的故障注入的能力;將具有1 bit糾錯能力和4 bit檢錯能力的[10,4,6]線性碼引入防護方案,對每個S盒進行保護。

1 理論知識

1.1 差分故障攻擊

1997年,Biham 等[2]提出了差分故障攻擊。該方法利用錯誤密文與正確密文之間的差分,分析密鑰信息,其具有攻擊點多變、分析復雜度低等特點。該攻擊的核心思想是攻擊算法的最后幾輪,其分析對象是密碼的非線性部件S盒:首先構建S盒的擴展差分分布表,其中分布表的輸入為〈差分輸入,差分輸出〉對,輸出為S盒可能輸入;其次,利用算法結構,每次的故障注入都可以確定相應的〈差分輸入,差分輸出〉對,查詢構建出來的擴展差分分布表,并縮小S盒輸入值的可能范圍。利用差分故障傳播可以捕獲輪子密鑰,并有效降低主密鑰的搜索復雜度。

1.2 差分故障攻擊的防護方法

根據防護結果的不同,可以分為基于檢測的防護方案和基于感染的防護方案,其中基于檢測的防護方案在時間或空間上對算法實現進行復制,并在每個算法部件運行中比較兩次實現的結果是否一致,若不一致,判斷為故障注入,并結束算法的運行,輸出空密文。而基于感染的防護方案會在算法實現時引入一個檢測模塊,該模塊會存儲在算法部件實現前后中間狀態值,并計算2次保存中間狀態值的差分值。對于0輸入,感染函數會輸出0,對于非0輸入,感染函數會輸出一個非0的隨機值。

算法級的防護方案在近幾年也備受關注。這類算法通常不需要額外的冗余實現即可實現對故障注入的防護,比如DEFAULT算法的設計。

1.3 線性碼

線性碼常被用來錯誤檢測和錯誤糾錯,并被用于故障攻擊的檢測。以下介紹線性碼的相關概念[15]。

定義1一個長為n的碼c∈,其中:k是有效信息,n-k為冗余信息,將這個碼c稱為[n,k]線性碼C。

定義2對于一個[n,k]線性碼C,一個k×n的矩陣G可以讓長為k的原始信息x通過轉換C(x)=x·G,轉換成一個長為n的對應碼字,將矩陣G稱為該線性碼的生成矩陣。

校驗矩陣用于檢測一個的元素是否為可能的碼字。當收到一個長度為n的碼字x∈,判斷該碼是否為有效碼,通常需要使用校驗矩陣進行檢驗。若存在一個n×(n-k)的矩陣H,對于任何c∈(其中0(n-k)表示一個n-k的零向量),則稱H為線性碼的校驗矩陣。

定義3最小距離[n,k]線性碼C的最小距離,其中hw(x)表示x的漢明重量。將一個最小距離為d的[n,k]線性碼C表示為[n,k,d]碼。

引理1[15]對于一個[n,k]線性碼C,d=。

引理2[15]對于一個[n,k,d]線性碼C,其可以糾正錯誤碼c'=c⊕ec,同時檢測錯誤碼c'=c⊕ed,其中e需要滿足hw(ed)+hw(ec)＜d,且hw(ed)＜d/2。

1.4 DEFAULT算法

2021年,Baski等[17]提出DEFAULT 分組密碼算法。該算法專為抵抗差分故障攻擊而設計,其算法整體結構采用SPN 類型,分組長度和密鑰長度均為128 bit,輪數為80輪,具體如圖1所示,包括DEFAULT-LAYER 層、DEFAULT-CORE 層 及DEFAULT-LAYER層。其中LAYER 層用來抵抗差分故障攻擊,而CORE層用來抵抗傳統的數學分析。

圖1 DEFAULT算法結構

算法輪函數結構如圖2所示(https://www.iacr.org/authors/tikz/),包括S盒層、比特變換層、輪常量及輪子密鑰加4個模塊,具體如下。

圖2 DEFAULT兩輪輪函數結構

1)S盒層。LAYER 層與CORE層的不同在于S 盒選取的不同:LAYER 選取的S 盒是037ED4A9CF18B265(具有線性結構,且能有效抵抗差分故 障攻擊)。CORE 選取的 S 盒是196F7C82AED043B5(能抵抗傳統數學分析)。

2)比特變換層。如圖2所示,上一輪的4個S盒會影響對應下一輪特定的4個S盒,且一個S盒內的比特位映射后的相對位置是不變的,即若第i個比特位映射到第j個比特位,則i≡jmod 4。

3)輪常量加。每輪會有一個6 bit的常量被分別異或在第23、19、15、11、7和3比特位置,而第127比特總是保持翻轉。

4)輪密鑰加。輪子密鑰異或到分組中間狀態。

具體的密鑰編排方案及解密過程可參見文獻[17]。

2 橫向混淆和縱向隱藏

根據故障攻擊原理可知,實現故障攻擊的前提是中間狀態發生改變。以往基于檢測思想的防護方案,通常使用一個復制冗余實現(復制原來相同的算法實現)來檢測另一實現是否被注入故障。但由于原始實現和冗余實現的狀態相同,雙重故障仍可能成功(如圖3所示)。

圖3 復制冗余的故障攻擊方法

為了有效抵抗非比特級故障攻擊,在引入冗余的基礎上,讓冗余與原始實現的中間狀態產生差異。這種差異的產生可以通過打亂中間狀態或隱藏中間狀態來實現,即橫向混淆和縱向隱藏。

橫向混淆的方法如圖4(a)所示,在冗余實現橫向打亂中間狀態,圖中中間狀態內的數字表示其對應在中間狀態中的序號。根據新的序列狀態實現新的S盒和線性變換,可以在保證算法正確實現的情況下只改變中間狀態的排序。如果攻擊者利用非比特級別的攻擊,其無法攻擊到與原始實現相對應的比特,比如攻擊者攻擊了中間狀態第4至7個比特,以雙重攻擊的方法,其會將故障注入中間狀態第4、9、6、1個比特位,這樣在經過輪函數后,輸出的結果并不相同,檢測到故障的注入。類似于Adomnicai等[19]提出的GIFT切片實現,是一個典型的橫向混淆方法。

圖4 基于橫向混淆和縱向隱藏的冗余實現

縱向隱藏的方法如圖4(b)所示,將算法實現的非線性部件與線性部件結合,形成一個T 實現,如AES的T-BOX實現和白盒實現可以被用來當做一個非常典型的T實現[20,21];該方法隱藏算法運行的中間狀態,可以讓攻擊者無法找到原始實現與冗余實現對應的中間狀態。

3 DEFAULT算法的防護方案

DEFAULT的防護方案分為兩步:第一步利用橫向混淆對DEFAULT 進行冗余實現;第二步利用線性碼對每個S盒進行故障的糾錯和檢錯。

3.1 DEFAULT基于橫向混淆的實現

整體實現結構如圖5所示,輪函數在進入LAYER層后,進行2次運算,分別是原始實現和橫向混淆實現,其中進入橫向混淆實現前,需先進行初始化。原始實現不改變中間狀態的算法實現。橫向混淆實現可以借鑒Alexandre等[19]提出的針對GIFT的比特切片方法。橫向混淆實現將算法的每個部件單獨實現,包括S盒層、比特置換層、輪密鑰加和輪常量加4個部件。

圖5 DEFAULT基于橫向混淆的實現

在輪函數結束(即完成原始實現和橫向混淆實現)時,將橫向混淆實現的中間狀態逆初始化,比較原始實現的結果和解包后的結果是否一致,若一致,則認為無故障注入,繼續進行接下來的輪函數,否則表示有故障注入。

初始化及橫向混淆的具體實現如下:

1) 初始化。

如式(1)所示,將明文與輪密鑰的所有比特位按4個S盒為一組將比特位的狀態按列分別存入4個分組S4i、S4i+1、S4i+2和S4i+3中,0≤i＜8,Sj表示第j個半字節分片,bj表示第j個比特位。

2) S盒層實現。

防護方案只針對算法運行中的第2 個DEFAULT-LAYER進行冗余實現,所以對于橫向混淆也只有DEFAULT-LAYER層的S盒。DEFAULTLAYER的4 bit S盒可用式(2)來表達。

其中:Si、S'i分別表示S盒輸入和輸出的第i比特;⊕表示XOR;·表示AND。

3) 比特置換層實現。

根據原來DEFAULT算法的比特置換和方案分片后的對應比特位置,逐一遍歷各比特位,找出新的中間狀態對應的比特置換位置,得到具體的置換,如表1所示。

表1 橫向混淆后的比特置換

4) 輪常量加實現。

對于輪常量C=c6c5c4c3c2c1c0,算法選擇了127、23、19、15、11、7、3這7個比特位,除第127個比特位,其余比特位于新的中間狀態的第3 和7 個S中,

其中:XY=00c5c4c3c2c1c0;Sa|Sb表示2個中間狀態的拼接,第127 個比特位直接與S31的最高位異或。

3.2 引入線性碼對S盒進行糾錯檢錯

3.2.1 線性碼的選擇與生成

在實現具體的糾錯檢錯方案前,需要先確定糾錯碼的防護能力及實現方式。

考慮2種攻擊模型,即基于原始實現單個半字節的攻擊和基于原始實現多個半字節的攻擊。

1)基于原始實現單個半字節的攻擊。攻擊者對原始的1個S盒和對應冗余的4個比特位進行攻擊。這些比特位分別位于不同的半字節中,因此,為冗余實現的各個4比特碼字添加單比特糾錯機制,實現半字節以下攻擊的自動糾錯能力。此時,線性碼需要具備1 bit的糾錯能力。

2)基于原始實現多個半字節的攻擊。攻擊者同時攻擊左邊2個或以上的半字節,并對冗余實現對應每個半字節中的多個比特攻擊。若通過糾錯實現安全性,會增加大量的冗余位,極大增加實現消耗。因此,對于需要糾錯大于單比特的防護,根據引理2,防護方案采用檢錯與糾錯并行的方式來降低過大的實現代價,選擇的線性碼需具備4 bit的檢錯能力。

綜上,本方案需要實現一個單比特的糾錯和4 bit的檢錯能力,根據1.3節可知線性碼的最小距離為6,即需要找到一個[10,4,6]線性碼。采用隨機的方式獲取線性碼,隨機生成一個矩陣4×10的矩陣G,遍歷所有可能的信息碼對應的線性碼的漢明重量是否小于等于6(引理1),若有一個大于,則重新生成矩陣G并驗證,否則表示生成成功。實驗方案最終選擇式(4)所表示的生成矩陣G。

根據生成矩陣G和定義2,容易獲得校驗矩陣H,如式(5)所示。

3.2.2 線性碼糾錯檢錯具體實現步驟

引入線性碼為S盒提供糾錯檢錯能力的具體步驟如下。

1)橫向混淆實現進入S盒前,采用以下操作:

(a)為32個S盒的輸入值Mi,計算冗余值Ri=Mi·G;

(b)保存所有的冗余值Ri。

2)S盒計算完成后,采用以下操作:

(a)將此時的S盒輸入值與對應冗余值Ri組合生成一個10 bits待檢測向量Di=|Ri;

(b)計算校驗值Ci=H·Di;

(c)判斷Ci是否等于0;

(d)若Ci等于0,表示無故障注入,結束檢測模塊,繼續執行算法;

(e)若Ci不等于0,表示故障被注入,執行(f);

(f)比較Ci與校驗矩陣H的第j列(1≤j≤4)Hj是否相等;

(g)若Ci=Hj,表示輸入值Mi'第j個比特被注入故障,翻轉第j比特進行糾錯,重新執行當前輪函數;

(h)若均不相等,表示注入的故障大于單比特,無法糾錯,輸出空密文。

4 實驗結果

對上述防護方案進行安全性測試。具體實驗環境為:一臺PC 機(Intel(R) Core(TM)i5-4200U CPU@1.6 GHz,8 GiB內存,Windows 7旗艦版);Microsoft Visual Studio 2019編譯;故障的誘導采用半字節隨機生成和固定比特位的隨機生成2種方式進行模擬仿真。

4.1 抵抗差分故障攻擊的有效性

攻擊方法是在原始實現的中間狀態找到一個或多個半字節進行注入錯誤,并對冗余實現對應的比特位進行攻擊。

設定選擇的明文為0x0102030405060708090a0b0c0d0e0f,主密鑰為0x00000000000000000000000000000000。如表2所示,測試實驗在不同輪數注入了不同的故障,共進行了100萬次的隨機故障注入測試,發現對于原始實現小于半字節的故障均可糾錯,而對于原始實現大于半字節的故障也可以糾錯,證明了防護方案的有效性。

表2 部分模擬攻擊實驗數據

4.2 方案性能(分析與比較)

對防護方案所需的軟件消耗進行測試,發現新防護方案僅需額外25.08%的實現消耗。

本防護方案與現有技術對比如表3所示。

表3 差分故障攻擊的防護性能對比

本研究和文獻[15]由于利用了糾錯碼,相較其他防護方案增加了自動糾錯的功能;文獻[22]需要根據算法的輪函數特點,將各種操作合并成一張表,不具有可移植性。文獻[12]減少了不必要的冗余信息,但自動糾錯能力差。由于DEFAULT其輪數相對其他輕量級算法有所增加(DEFAULT有80輪),移植本防護方案到其他分組密碼需要額外約25.08%×(80/40)×(40/28)≈72%的實現消耗。相較文獻[22]的防護方案,本方案有顯著的性能提升,并能提供半字節的自動糾錯能力和全部比特位的檢錯能力。

5 結束語

在構造抵抗差分故障攻擊的防護方案時,如何做到方案有效且額外消耗少是設計中的難點?；贒EFAULT密碼的算法結構,利用橫向混淆和線性碼提出了一種新的防護方法:對DEFAULT 的第2個LAYER層使用橫向混淆完成冗余部分的實現;此外,為了對每個比特位提供故障注入的檢測能力,將具有1 bit糾錯能力和4 bit檢錯能力的[10,4,6]線性碼引入防護中。實驗結果表明,新的防護方法在僅需要25.08%的額外軟件性能消耗下,實現了抵抗多重故障注入攻擊的能力。與已有防護方法相比,新的防護方法除了能有效地提供糾錯及檢錯能力外,需要的實現代價更少。