基于隨機故障注入的GOST差分故障攻擊方法

蔡承伯, 杜之波, 吳 震, 李圣泉, 江 楠

(1.成都信息工程大學網絡空間安全學院,四川 成都 610225;2.國電南京自動化股份有限公司 南京華盾電力信息安全測評有限公司,江蘇 南京 211106)

0 引言

1977年美國將DES算法確立為數據加密標準(data encryption standard),此后在其他國家和地區出現了一系列DES替代算法,1989年蘇聯發布在GOST 28147-89標準中[1]的GOST分組加密算法就是其中之一。2015年俄羅斯聯邦制定了GOST34.12-2015加密標準,并于2016年1月1日起生效,該標準包含了兩種對稱加密算法,其中之一就是GOST,在新標準中又被稱為Magma[2]。針對GOST的密碼分析工作主要有線性分析[3]、差分分析[3-4]和滑動攻擊[5],但這些關于GOST的數學安全性分析都脫離不了“降低代數復雜度”的特定框架,這意味著在現實條件下很難對其構成真正的威脅。

差分故障攻擊(differential fault attack,DFA)是一種常見的側信道攻擊技術,在1997年由兩位以色列的密碼學家Biham和Shamir提出[6]。其核心思想是通過在密碼設備運行過程中導入故障值,然后結合正確和錯誤密文計算出差分值,最后利用密文差分值和相關密鑰之間的關系進行密鑰破解。利用該方法能夠恢復出多種密碼算法的密鑰,例如 AES[7]、SM4[8-10]、FeW[11]、PRESENT[12]等。在GOST的差分故障攻擊研究中,文獻[13]首次給出GOST的差分故障攻擊方法,研究人員選擇在倒數第二輪的右半部分導入半字節的隨機故障來攻擊最后兩輪子密鑰,注入64次就能成功恢復主密鑰。文獻[14]提供了兩種GOST的差分故障攻擊方法,共同點是都采用單字節隨機故障模型,其主要區別是攻擊最后一輪子密鑰時,方法1誘導的故障位置在最后一輪的右半部分,方法2則將故障位置擴展至最后的兩輪。仿真實驗結果表明在兩種模型下恢復主密鑰分別需要72和36個故障。上述攻擊方法均有兩個共同的現實問題:(1)攻擊要能成功執行,攻擊者必須將故障導入特定的位置,在實際攻擊中嚴格的前提條件導致該方法很難實施,因此針對GOST的差分故障攻擊目前尚沒有公開發表的實測結果。(2)故障數據都是特定的仿真數據,對錯誤密文篩選的過程進行回避。實際上,故障注入產生的錯誤數據并不是全部有效,攻擊者需要根據單次攻擊的具體情況對錯誤密文進行篩選。

針對GOST算法的研究現狀,提出一種更符合實際攻擊的GOST差分故障攻擊方法。首先故障誘導時不再局限于某個位置,而是擴大至算法的最后八輪,這不僅極大地降低了故障誘導的難度,還擴大了故障誘導的范圍。其次密鑰篩選方法讓攻擊者篩選錯誤密文時不再需要特定的錯誤密文,只需在故障分析時簡單篩選錯誤密文即可成功攻擊主密鑰。

1 GOST算法介紹

1.1 GOST加密算法

GOST分組加密算法是對稱加密算法,屬于Feistel網絡結構,明文分組采用的是64比特,密鑰長度采用的是256比特,總共迭代32輪。在每一輪中,F函數的輸出與輪輸入的左半部分進行異或運算成為新的左半部分,然后左右交換成為下一輪的輸入,最后一輪左右不交換。整體輪結構如圖1所示。

1.2 GOST的F函數

F函數如圖2所示,由3個部分組成。首先右半部分數據與該輪子密鑰進行模232加操作,然后將32比特結果分為8個4比特分組,依次進入8個S盒。最后將8個S盒的輸出重組成32比特字,循環左移11比特得到輸出結果[15]。

圖2 GOST的F函數

GOST在GOST 28147-89標準中沒有特定的S盒,但是在最新標準GOST 34.12-2015中填補了對S盒的定義,并且是固定唯一的。具體見表1。

表1 GOST 34.12-2015提供的S盒

1.3 密鑰編排

將256比特的主密鑰K分為8組32比特的子密鑰 K0、K1、K2、K3、K4、K5、K6、K7,第 i輪使用的子密鑰如表2所示。

表2 密鑰編排

2 GOST算法的DFA研究進展

2.1 DFA

一般情況下,故障攻擊分為以下4個步驟:選擇合適的故障模型;針對故障模型選擇合適的注入手段進行故障注入;對獲得的錯誤密文樣本進行選擇性篩選;對篩選后的錯誤密文樣本進行故障分析。在進行故障分析時,如果采用了差分分析法,那么這種故障攻擊就稱為差分故障攻擊。

差分故障攻擊主要是在密碼芯片運行的過程中進行故障誘導,利用得到的錯誤密文和正確密文計算出輸入差分和輸出差分,再根據算法結構建立差分方程,求解差分方程得到輪密鑰的候選值集合,通過多次攻擊縮小候選值范圍,最終得到唯一正確的輪密鑰。攻擊原理如圖3所示。

圖3 DFA原理

2.2 GOST已有DFA方法

2012年Jongsung Kim[13]首次提出了一種GOST密碼差分故障攻擊方法,其攻擊原理是利用GOST獨有的故障傳播路徑將隨機的半字節故障分別注入到R30的第7個、第8個、第6個、第5個、第4個、第3個、第2個、第1個半字節中,一次性攻擊最后兩輪的子密鑰。理論上基于此模型恢復K31和K32需要16個錯誤密文,恢復主密鑰需要64個錯誤密文。該方法具有以下特點:(1)攻擊選用的故障模型相對嚴苛,注入半字節隨機故障時,攻擊者雖然不控制故障的取值,但是需要控制故障的位置;(2)在實際攻擊中利用此方法攻擊最后八輪子密鑰時,攻擊K31和K32時需要進行一輪故障注入,攻擊K29和K30時需要重新進行一輪故障注入,換言之恢復主密鑰總共需要四輪故障注入;(3)在單輪的故障注入后還需要對錯誤密文進行篩選,并且至少選出16個符合要求的錯誤密文。

2015年陶智[14]提出了兩種GOST密碼差分故障攻擊方法,攻擊采用的均為單字節隨機故障模型。方法1采用的攻擊策略是將隨機單字節故障注入到最后一輪R31的第1個、第2個、第3個、第4個字節中,通過差分分析來恢復最后一輪子密鑰的某一字節,最后通過重復攻擊來恢復最后一輪子密鑰的所有字節。但是這種方法與文獻[13]提出的方法一樣,存在故障導入精準率太低的問題。因此,方法2在方法1的基礎上提出了一種理論上的改進策略,在攻擊最后一輪子密鑰時將故障注入的范圍擴大為最后兩輪,使用該策略在進行差分分析前,要根據密文差分和故障注入位置的關系來判斷故障注入的輪數和字節位置。如果不符合要求則需要重新進行故障注入,直到獲取的錯誤密文數量滿足攻擊成功所需的錯誤密文數量為止。仿真實驗結果表明,使用這兩種不同的方法進行攻擊分別需要72個和36個錯誤密文。

3 基于隨機故障注入的DFA

3.1 符號說明

本文使用的符號說明如表3所示。

表3 符號說明

3.2 基本過程

基本過程如下:(1)選擇一組初始明文,使用密鑰K進行加密得到正確密文。(2)在主密鑰不變的情況下再次對這組明文進行加密,在后八輪任意位置進行隨機故障注入,完成后獲取一定數量的故障密文,對故障密文進行簡單篩選。隨后通過差分分析,結合密鑰篩選方法依次恢復出后八輪子密鑰 rk31、rk30、rk29、rk28、rk27、rk26、rk25、rk24。 (3)結合密鑰編排的逆方法恢復出256位主密鑰K。

3.3 攻擊過程詳述

步驟1 采集正確密文信息和泄露的能量曲線。

選擇初始明文P(L0,R0)=FE DC BA 98 76 54 32 10,在密鑰為K的GOST算法下進行加密,得到正確密文C(XL,XR)。同時用示波器連接插入智能卡的讀卡器,對泄露的能量曲線進行采集,獲取最后八輪的運行時間,以便確定導入隨機故障的位置,如圖4所示。

圖4 隨機故障注入

步驟2 執行隨機故障注入,獲取一定數量的錯誤密文。

(1)使用密鑰K再次對明文P進行加密,根據步驟1獲取的能量曲線確定最后八輪的運行時間段,對最后八輪執行隨機故障注入,獲取一定數量的錯誤密

(2)對獲取的錯誤密文進行一個簡單篩選。篩選出與正確密文長度一樣,但值不一樣的錯誤密文。

步驟3 攻擊第32輪。

ST為算法正常運行時S盒的正確輸入,SF為故障注入后S盒的錯誤輸入;記ST、SF、Sin從左到右對應的4個字節分別為ST[x],x=0,1,2,3、SF[x],x=0,1,2,3、Sin[x],x=0,1,2,3,則有:

(3)使用密鑰篩選方法,計算出第32輪子密鑰rk31。

步驟4 攻擊剩余七輪的子密鑰,每輪需要的錯誤密文均來自于步驟2。在步驟3的基礎上對GOST最后一輪解密,獲得第31輪正確的和錯誤的輪輸出,重復步驟3的操作,恢復出rk30。以此類推恢復出rk29、rk28、rk27、rk26、rk25、rk24。

步驟5 根據密鑰編排的逆方法,恢復主密鑰K。

3.4 密鑰篩選方法

步驟3(3)提到的密鑰篩選方法具體如下:

(1)將256個候選字節從小到大放入數組kbyte,同時設置一個全為0的二維數組K[4][256],其中4代表該輪子密鑰從左到右的4個字節,256對應kbyte的256個候選字節。

(2)如果Sout不為0,就將256個 kbyte依次帶入等式(9)和式(10),當式(11)成立時,二維數組對應的位置自增1,不成立則不變。例如分析第一個錯誤密文時,x=0對應的kbyte等于0x00和0x03時使式(11)成立,其余的不成立,則K[0][256]={1,0,0,1,…,0,0},其他3個字節同理。

(3)分析完所有錯誤密文后,找到二維數組K各行最大的值,其對應位置的候選字節即為步驟(4)需要的字節。例如針對第一個字節,K[0][256]={5,18,5,1,…,88,…,0,0},最大值88位于數組元素編號121處,則對應的候選字節為0x7C,其他3個字節同理。

(4)記步驟(3)得到的4個字節依次為 kbyte,0、kbyte,1、kbyte,2、kbyte,3,因為模 232加法運算有可能出現進位的情況,所以這里得到的kbyte,0、kbyte,1、kbyte,2不一定是子密鑰正確的前3個字節,因此需要對這3個字節作二次處理,具體如下:

如果kbyte,3+XR[3]>0xFF,則kbyte,2=(kbyte,2-1)mod 28;如果kbyte,2+XR[2]>0xFF,則kbyte,1=(kbyte,1-1)mod 28;如果 kbyte,1+XR[1]>0xFF,則 kbyte,0=(kbyte,0-1)mod 28。最后將處理后的 4 個字節 kbyte,0、kbyte,1、kbyte,2、kbyte,3重組為32比特的字,得到正確的rk31。

4 實驗與分析

4.1 實驗環境

所需要的實驗環境如表4所示。

表4 實驗環境

4.2 原始信息采集

首先設置初始明文為:FE DC BA 98 76 54 32 10,然后采集GOST算法智能卡正常工作時產生的能量曲線和輸出的正確密文信息,對應3.3小節的步驟1。圖5是示波器采集到的能量曲線,橫軸表示算法的運行時間,縱軸表示運行過程中泄露的功耗。圖6是采集到的正確明文和密文信息:FE DC BA 98 76 54 32 10 4E E9 01 E5 C2 D8 CA 3D。

圖5 能量曲線

圖6 正確明文和密文信息

4.3 故障注入

首先通過觀察圖5能量曲線的運行時間軸,以確定GOST算法的最后八輪運行區間,在實際攻擊中可以選擇最后九輪或者最后十輪進行攻擊,只要包含最后八輪即可。然后對選中的運行區間實施1000次隨機故障注入。圖7是故障注入后Inspector采集到的部分數據信息,綠色數據是故障注入失敗的返回數據;紅色數據是故障注入成功的返回數據;矩形框部分是返回的錯誤密文,一共有240條。最后記錄下這240條數據,用于后續差分分析。

圖7 返回數據信息

4.4 差分分析

使用3.3小節步驟3和步驟4提出的方法對正確密文以及上述獲得的240密文進行攻擊。第32輪攻擊結果如圖8所示,在每4個字節里面,如果單個字節的置信度最高并且明顯高于其他字節,那么這個字節就是正確的候選密鑰字節。最終第32輪子密鑰為:FF EE DD CC。

圖8 第32輪結果

攻擊剩余7輪,每一輪使用的錯誤密文與第32輪一致,攻擊結果見表4。

表4 剩余七輪攻擊結果

4.5 結果驗證

使用攻擊得到的主密鑰FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11 00 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF對同一明文進行加密,得到密文4E E9 01 E5 C2 D8 CA 3D,結果與圖6采集的正確密文信息一致,表明攻擊成功。同時也證明了本文提出的方法在真實實驗環境下能夠恢復出主密鑰,并且相比現有其他方法,擴大了攻擊的故障誘導范圍,提高了攻擊的靈活性和實用性。表5對各方法的故障誘導位置作了比較。

表5 故障誘導位置

5 結束語

進行差分故障分析時常常是在某假設的故障模型的條件下進行,而故障模型的效率不僅取決于需要的錯誤密文數量,還取決于在實際攻擊中的可用性和可行性。針對現有攻擊方法的不足提出基于隨機故障注入的GOST差分故障攻擊方法,將故障誘導的范圍擴大到最后八輪,打破了苛刻的理論條件,提高了攻擊性和實用性。其次,提出的密鑰篩選方法在攻擊每一輪子密鑰時使用的錯誤密文都一樣,降低了錯誤密文樣本篩選的難度,解決了之前需要根據單輪攻擊的具體情況篩選出特定錯誤密文的難題。本文在一定程度上為同類型密碼在實際差分故障攻擊中的應用研究提供了新的思路。