GOST 的差分故障攻擊*

謝 敏, 李嘉琪, 田 峰

1. 西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室, 西安710071

2. 陜西省區塊鏈與安全計算重點實驗室, 西安710071

1 引言

GOST 是前蘇聯時期的標準分組密碼,最開始用于軍事級別保密、政府通訊和蘇聯最大兩家銀行的保密工作, 直到1994 才正式公布, 目前依然是俄羅斯聯邦的加密標準. 早期對GOST 的分析沒有取得特別好的成果,學者們普遍認為GOST 對差分、線性等傳統分析方法有足夠好的安全性. 2010 年, GOST 被提交至國際標準化組織成為全球工業加密標準, 對GOST 的相關研究再次活躍起來. 2011 年, Courtois 等人[1]首次提出了對32 輪GOST 的差分分析方法, 所需時間復雜度約為2226; 同年Isobe[2]結合反射攻擊和中間相遇攻擊對GOST 算法進行了分析, 數據復雜度和時間復雜度為232和2225; 2012 年, Dinur 和Shamir 等人[3]對Isobe 的攻擊做了改進, 所需數據復雜度和時間復雜度為232和2224; 2013 年, Kim[4]受Isobe 中間相遇攻擊的啟發, 找到了GOST 算法中2128組弱密鑰, 針對這些密鑰的攻擊時間復雜度可以降為2125.5, 此外, 他還首次提出了GOST 上的差分故障攻擊方法, 選擇在算法第31 輪右側引入半字節隨機故障, 平均64 次故障注入可恢復GOST 算法的主密鑰. 2019 年, Lu[5]針對GOST 算法提出了一種新的線性攻擊方法, 所用區分器攻擊32 輪GOST 需要的數據復雜度和時間復雜度均為2173.8.

Poschmann 等人[6]在2010 年研究了GOST 算法的物理實現, 指出GOST 算法完全符合輕量級密碼算法的設計準則, 非常適用于低能耗的RFID 標簽, 而該類設備的安全性極易受到旁路攻擊的威脅, 差分故障攻擊[7]作為旁路攻擊中使用最為廣泛的攻擊手段之一, 對主流輕量級算法Lblock 和GIFT 等均有出色的攻擊效果[8,9], 所以在GOST 算法應用于輕量級設備前進行差分故障分析是十分必要的.

2 GOST 分組密碼介紹

2.1 GOST 加密算法

GOST 算法的分組長度為64 比特, 密鑰長度為256 比特, 明文經過32 輪迭代得到密文. 該算法采用了廣義Feistel 結構, 其輪函數如下式:

為方便描述, 我們將8 個S 盒分別記為S7,S6,··· ,S0, 如圖1 所示.

圖1 GOST 單輪結構Figure 1 One round structure of GOST

對于GOST 算法, 其S 盒并不固定, 在不同的應用場景下會采用不同的S 盒, 常用于研究的S 盒為已公布的應用在俄聯邦中央銀行的S 盒, 如表1 所示.

表1 GOST 的S 盒Table 1 S-box of GOST

2.2 GOST 的密鑰擴展算法

GOST 算法的密鑰擴展較為簡單, 256 比特主密鑰直接切分為8 個32 比特的子密鑰, 分別記為K1,K2,··· ,K8, 前24 輪加密的輪密鑰ki將按順序循環使用這8 個子密鑰, 最后8 輪則倒序使用.

3 GOST 的差分故障攻擊

3.1 故障模型

本文用到的符號說明如下:

本文采用的故障模型包括以下兩個基本假設:

(1) 攻擊者擁有加密機的訪問權限, 可以獲得一定數量的明密文對(選擇明文攻擊, CPA).

(2) 攻擊者可以在加密過程中的某一輪導入單字節隨機故障以獲取錯誤密文, 但是故障導入的具體位置和故障值是未知的.

3.2 攻擊原理

對于第i輪右半段的輸入Ri和S 盒的輸入ini有ini=Ri+ki, 根據算法結構, 若Li+1已知, 則Ri可知, 此時一旦確定了S 盒的輸入, 也就確定了輪密鑰ki. 根據S 盒的差分分布特性, 可利用S 盒的輸入輸出差分對來獲得其輸入的信息.

為獲得S 盒的輸入差分, 對模加運算做如下等價轉換: 對于加密過程的某一輪, 如第i輪, S 盒的32

為了獲得S 盒的可能輸入值, 我們研究了GOST 算法8 個S 盒的差分特性, 得到了每個S 盒在固定輸入差分的情況下其輸出差分與輸入的對應關系, 這里僅列出S0的情況為例, 詳見表2. 借助該對應關系,我們就可以從S 盒已知的輸入輸出差分獲得其可能輸入, 再通過故障的引入不斷縮小其可能輸入的范圍,直到確定出S 盒輸入的唯一值, 進而由關系ini=Ri+ki解出輪密鑰, 最終利用密鑰擴展算法, 將最后8輪輪密鑰組合得到主密鑰.

表2 S0 固定輸入差分下輸出差分與輸入的對應關系Table 2 Corresponding relationship between output difference and input under fixed input difference of S0

3.3 GOST 差分故障攻擊過程

3.3.1 模加運算轉化后的差分擴散特性分析

表3 ? = 1 時? 與, 關系表Table 3 Relationship among ?, and when ? = 1

表3 ? = 1 時? 與, 關系表Table 3 Relationship among ?, and when ? = 1

Ri j kij Rij|kij ?ci j+1 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0

3.3.2 基于半字節故障的分析

由3.2 節的攻擊原理, 研究獲取故障所在半字節對應S 盒的輸入輸出差分是攻擊實現的關鍵, 在任何故障模型下, 都要做基于半字節故障的分析來獲取S 盒的輸入差分, 為此我們給出基于半字節故障的一般化分析如下:

表4 映射fTable 4 Mapping f

3.3.3 GOST 算法多輪擴散分析

3.3.2 節是基于半字節故障的一般化分析, 建立了活躍S 盒與密鑰恢復之間的聯系, 在已有分析的基礎上, 活躍S 盒的數量將直接影響單次故障引入的恢復效率. 為此我們將故障時刻提前, 并采用擴散速度較快、引入難度較低的單字節隨機故障, 利用GOST 的擴散層以及差分擴散特性實現快速的故障擴散, 經過4 輪可將單字節故障擴散到GOST 右側輸入的全部8 個半字節. 與之相比, Kim[4]對GOST 的差分故障攻擊中采用了列舉所有可能擴散路徑的分析方法, 其故障模型很難從兩輪擴展到多輪, 從而導致最終擴散產生的活躍S 盒數量較少, 大大限制了攻擊的整體效果.

圖2 給出了GOST 多輪差分擴散的示意圖. 如圖所示, 若在GOST 加密的第i輪右側輸入Ri處引入隨機單字節故障, 經過左循環移11 位后, 將影響Ri+1的3 個半字節; 同理, 由于Ri+1和Li+1均有非零差分, 它們將影響Ri+2的5 個半字節, 從而再經過一輪的迭代,Ri處引入的隨機單字節故障將影響Ri+3的全部8 個半字節.

圖2 GOST 多輪差分擴散示意圖Figure 2 Multi-round differential diffusion of GOST

3.3.4 GOST 算法完整攻擊方案

1) 故障模型

由3.3.3 節的分析, 我們選擇在第0 輪至第21 輪之間任意一輪右側輸入處引入單字節隨機故障的模型, 引入難度較小, 且能夠確保故障擴散后的影響覆蓋最后8 輪右側輸入的全部64 個半字節, 該8 輪輪密鑰組合即為GOST 算法256 比特主密鑰.

2) 攻擊步驟

由1) 的分析, 在第T(0≤T ≤21) 輪引入的單字節隨機故障經過多輪擴散, 其影響將覆蓋第24 到31 輪右側輸入的所有半字節, 這樣對其中每個S 盒都能得到一組長為4 比特的輸入輸出差分對, 共計64組. 在第T輪右側輸入引入單字節隨機故障M次, 可獲得M組密文, 并由此計算出M組ΔR31和Δout31對, 密鑰恢復步驟可總結為:

步驟1 恢復k31的第0 個半字節

步驟2 恢復k31的其他半字節

步驟3 恢復k30,k29,k28,k27,k26,k25,k24共7 輪的輪密鑰

利用恢復后的k31向上解密一輪, 得到M組ΔR30和Δout30對, 然后用同樣的方式恢復k30. 設恢復k30所需故障次數為N30.

同理, 我們可依次恢復其他6 輪的輪密鑰k29,k28,k27,k26,k25,k24. 設恢復它們所需故障次數分別為N29,N28,··· ,N24.

令M= max{N30,N29,··· ,N24}, 由GOST 的密鑰編排算法,M即為恢復主密鑰所需故障次數.從以上攻擊步驟可以看出, 每組密文對經過層層解密將參與到最后8 輪全部64 個半字節密鑰的恢復中,恢復GOST 算法256 比特主密鑰所需故障次數實際上為該64 個半字節密鑰恢復所需故障次數的上界.

3.4 實驗仿真結果和分析

通過計算機程序模擬3.3.4 節中的攻擊方案, 設立恢復GOST 算法主密鑰為一次完整實驗, 其中每次實驗的明文、密鑰和故障具體位置均隨機生成. 我們進行了一萬次模擬實驗來探尋該方法的攻擊效果,圖3 展示了GOST 算法單字節故障多輪攻擊一萬次模擬實驗中恢復256 比特主密鑰所需故障次數的分布情況, 結果表明12 次故障內成功恢復主密鑰的實驗占比達98%, 一萬次實驗成功恢復主密鑰所需的平均故障次數為7.46, 相比現有的差分故障攻擊結果有了很大的提升.

圖3 GOST 一萬次實驗結果Figure 3 Result of 10 000 experiments on GOST

4 結束語

本文利用GOST 算法模加運算部件的特點, 采用差分故障對其進行了攻擊. 通過在前22 輪任意一輪右側輸入處引入單字節隨機故障, 較好地完成了GOST 的差分故障攻擊. 實驗結果表明, 完成GOST 的256 比特主密鑰恢復平均所需故障注入次數為7.46, 一萬次實驗中有98% 的實驗在12 次故障注入內即可完成主密鑰恢復. 可見, 差分故障攻擊對GOST 是十分有效的, 為了避免此類攻擊, 需要對加密設備進行特別保護. 此外, 這種針對模加運算部件的攻擊為同類型密碼算法分析提供了新的思路, 也對模加運算相關算法的設計提供了新的參考.