GOST 的差分故障攻擊*

謝 敏, 李嘉琪, 田 峰

1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 西安710071

2. 陜西省區(qū)塊鏈與安全計(jì)算重點(diǎn)實(shí)驗(yàn)室, 西安710071

1 引言

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

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

2 GOST 分組密碼介紹

2.1 GOST 加密算法

GOST 算法的分組長度為64 比特, 密鑰長度為256 比特, 明文經(jīng)過32 輪迭代得到密文. 該算法采用了廣義Feistel 結(jié)構(gòu), 其輪函數(shù)如下式:

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

圖1 GOST 單輪結(jié)構(gòu)Figure 1 One round structure of GOST

對(duì)于GOST 算法, 其S 盒并不固定, 在不同的應(yīng)用場(chǎng)景下會(huì)采用不同的S 盒, 常用于研究的S 盒為已公布的應(yīng)用在俄聯(lián)邦中央銀行的S 盒, 如表1 所示.

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

2.2 GOST 的密鑰擴(kuò)展算法

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

3 GOST 的差分故障攻擊

3.1 故障模型

本文用到的符號(hào)說明如下:

本文采用的故障模型包括以下兩個(gè)基本假設(shè):

(1) 攻擊者擁有加密機(jī)的訪問權(quán)限, 可以獲得一定數(shù)量的明密文對(duì)(選擇明文攻擊, CPA).

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

3.2 攻擊原理

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

為獲得S 盒的輸入差分, 對(duì)模加運(yùn)算做如下等價(jià)轉(zhuǎn)換: 對(duì)于加密過程的某一輪, 如第i輪, S 盒的32

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

表2 S0 固定輸入差分下輸出差分與輸入的對(duì)應(yīng)關(guān)系Table 2 Corresponding relationship between output difference and input under fixed input difference of S0

3.3 GOST 差分故障攻擊過程

3.3.1 模加運(yùn)算轉(zhuǎn)化后的差分?jǐn)U散特性分析

表3 ? = 1 時(shí)? 與, 關(guān)系表Table 3 Relationship among ?, and when ? = 1

表3 ? = 1 時(shí)? 與, 關(guān)系表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 基于半字節(jié)故障的分析

由3.2 節(jié)的攻擊原理, 研究獲取故障所在半字節(jié)對(duì)應(yīng)S 盒的輸入輸出差分是攻擊實(shí)現(xiàn)的關(guān)鍵, 在任何故障模型下, 都要做基于半字節(jié)故障的分析來獲取S 盒的輸入差分, 為此我們給出基于半字節(jié)故障的一般化分析如下:

表4 映射fTable 4 Mapping f

3.3.3 GOST 算法多輪擴(kuò)散分析

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

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

圖2 GOST 多輪差分?jǐn)U散示意圖Figure 2 Multi-round differential diffusion of GOST

3.3.4 GOST 算法完整攻擊方案

1) 故障模型

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

2) 攻擊步驟

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

步驟1 恢復(fù)k31的第0 個(gè)半字節(jié)

步驟2 恢復(fù)k31的其他半字節(jié)

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

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

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

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

3.4 實(shí)驗(yàn)仿真結(jié)果和分析

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

圖3 GOST 一萬次實(shí)驗(yàn)結(jié)果Figure 3 Result of 10 000 experiments on GOST

4 結(jié)束語

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