一種NoisyRounds 保護(hù)的白盒AES 實(shí)現(xiàn)及其差分故障分析*

孫 濤, 唐國(guó)俊, 吳昕鍇, 毛振寧, 龔 征

華南師范大學(xué)計(jì)算機(jī)學(xué)院, 廣州510631

1 研究背景

在移動(dòng)互聯(lián)網(wǎng)與物聯(lián)網(wǎng)終端及其軟硬件技術(shù)交替演進(jìn)當(dāng)中, 可信計(jì)算、身份認(rèn)證、密碼算法等網(wǎng)絡(luò)與信息安全關(guān)鍵要素已得到充分重視. 絕大多數(shù)產(chǎn)品在理論上遵照密碼學(xué)廣泛采用的Kerckhoffs 原則(即一個(gè)密碼系統(tǒng)的安全性?xún)H依賴(lài)于密鑰的安全性). 因此工業(yè)界也陸續(xù)制定了TPM、Trustzone、SGX、TEE、SE 等一系列技術(shù)用于保護(hù)密鑰存儲(chǔ)與運(yùn)算中的完整性與機(jī)密性. 在保護(hù)密鑰安全的基礎(chǔ)上, 通過(guò)各種標(biāo)準(zhǔn)密碼算法或安全協(xié)議對(duì)數(shù)據(jù)、身份和隱私信息進(jìn)行安全加固. 在實(shí)際中, 由于移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)硬件資源往往受到限制, 在軟件上又需要考慮設(shè)備兼容性等問(wèn)題, 采取基于硬件安全(TEE、SE) 保護(hù)密鑰的應(yīng)用解決方案在總體上還僅占很小比例, 絕大多數(shù)應(yīng)用仍然通過(guò)傳統(tǒng)軟件加固的方式(代碼混淆、程序加殼、內(nèi)存防dump) 來(lái)保護(hù)應(yīng)用安全方案中的密鑰. 但相關(guān)軟件加固技術(shù)往往依賴(lài)于廠家自身的設(shè)計(jì)與分析, 缺乏理論安全性驗(yàn)證. 在CCS 2018 會(huì)議上, 李卷儒等人通過(guò)分析密碼算法與密鑰在二進(jìn)制代碼存儲(chǔ)與運(yùn)算中的特征, 設(shè)計(jì)并實(shí)現(xiàn)了一種通用的二進(jìn)制代碼密鑰恢復(fù)工具(K-HUNT)[1]. 針對(duì)OpenSSL、mbedTLS 等著名開(kāi)源密碼算法庫(kù)及一些私有密碼算法相關(guān)軟件的實(shí)驗(yàn)結(jié)果表明K-HUNT 均能對(duì)二進(jìn)制代碼中的密鑰進(jìn)行恢復(fù)攻擊. 上述攻擊案例表明傳統(tǒng)軟件加固方式作為密鑰保護(hù)技術(shù)還遠(yuǎn)遠(yuǎn)不夠, 攻擊者往往能通過(guò)靜態(tài)代碼逆向分析、動(dòng)態(tài)程序跟蹤等方式直接獲取密鑰. 在物聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)等資源受限應(yīng)用場(chǎng)景下, 由于分組密碼算法(block cipher) 在性能與效率上的優(yōu)勢(shì), 因此在數(shù)據(jù)加解密、消息認(rèn)證碼與數(shù)字版權(quán)管理方案的構(gòu)造中往往起著重要作用. 在此背景下, 越來(lái)越多的廠商在應(yīng)用中引入了白盒分組密碼算法(white-box block cipher) 來(lái)構(gòu)建軟件環(huán)境下的密鑰安全保護(hù)機(jī)制, 由此也進(jìn)一步提高了學(xué)術(shù)界與工業(yè)界對(duì)白盒分組密碼算法的研究與關(guān)注度.

白盒密碼學(xué)(white-box cryptography) 由Chow 等人[2]在SAC 2002 年會(huì)上首次提出, 其核心思想是通過(guò)白盒密碼實(shí)現(xiàn)技術(shù), 使得密碼算法的軟件實(shí)現(xiàn)與運(yùn)行環(huán)境在對(duì)攻擊者完全開(kāi)放的前提下, 密碼算法所使用的用戶(hù)密鑰仍然不能被攻擊者所獲取. 在提出白盒密碼學(xué)概念的同時(shí), Chow 等人也針對(duì)國(guó)際分組密碼算法標(biāo)準(zhǔn)AES 和DES 給出了相應(yīng)的白盒實(shí)現(xiàn)方案[2,3]. 由于白盒分組密碼算法僅依賴(lài)于軟件實(shí)現(xiàn),具有良好的兼容性和可維護(hù)性, 目前已得到了密碼學(xué)界和工業(yè)界的廣泛研究與關(guān)注. 在防火墻、無(wú)人機(jī)、APP 等應(yīng)用中, 白盒分組密碼算法已作為軟件完整性保護(hù)、身份認(rèn)證、密鑰管理與分發(fā)等功能的關(guān)鍵信息安全保護(hù)技術(shù)加以實(shí)際應(yīng)用.

在Chow 等人提出基于查找表的AES 標(biāo)準(zhǔn)分組加密算法的白盒實(shí)現(xiàn)后[2], 從矩陣、仿射變換分析入手進(jìn)行白盒方案破解的工作也伴隨而來(lái). Billet 等人于2004 年提出了基于矩陣求逆方法的白盒密鑰恢復(fù)攻擊技術(shù)(簡(jiǎn)稱(chēng)BGE 攻擊)[4], 該技術(shù)能以232左右的計(jì)算復(fù)雜度對(duì)Chow 等人所提出的AES 白盒實(shí)現(xiàn)及其類(lèi)似構(gòu)造的白盒分組密碼算法進(jìn)行密鑰恢復(fù). 針對(duì)Chow 等人提出的DES 白盒實(shí)現(xiàn), Wyseur 等人也提出了類(lèi)似破解方法[5]. 在BGE 攻擊方法提出后, 陸續(xù)也有新的白盒AES 實(shí)現(xiàn)方案提出, 在此基礎(chǔ)上, 針對(duì)Chow 類(lèi)型的白盒AES 實(shí)現(xiàn)的分析方法也不斷改進(jìn). Bringer 等人在2006 年提出了一種白盒AES 實(shí)現(xiàn)方案[6], 但在2010 年De Mulder 等人給出了相應(yīng)的攻擊方法[7]. 2009 年肖雅瑩和來(lái)學(xué)嘉提出了一種改進(jìn)內(nèi)部編碼方式的AES 白盒實(shí)現(xiàn)方案[8], 該實(shí)現(xiàn)在2012 年被De Mulder 等人以232的計(jì)算復(fù)雜度破解[9]. 在2010 年, Karroumi 基于dual cipher 的思想提出了一種新的白盒AES 實(shí)現(xiàn)方案[10], 但2013 年Lepoint 和Rivain 提出的新分析方法, 將攻擊Chow 等人和Karroumi 提出的白盒AES 方案及其類(lèi)似變種的計(jì)算復(fù)雜度均降低至222[11]. 2016 年Baek 等人提出內(nèi)部狀態(tài)(internal state) 的大小決定了白盒實(shí)現(xiàn)的安全強(qiáng)度, 并基于此理念, 通過(guò)編碼連接兩個(gè)AES 實(shí)例的方式提高內(nèi)部狀態(tài)的大小, 給出了一個(gè)新的白盒AES 實(shí)現(xiàn)方案[12]. 在Eurocrypt 2018 上, Dinur 通過(guò)改進(jìn)的仿射變換等價(jià)變換方法, 將m 比特S 盒的仿射查找表變換的最優(yōu)攻擊復(fù)雜度提高到O(m32m)[13]. 隨后在CHES 2018 上, Derbez等人[14]指出Dinur 算法[13]的不足之處, 給出了針對(duì)SPN 結(jié)構(gòu)+ 仿射變換的白盒分組密碼算法的高效通用分析方法. 針對(duì)Baek 等人提出的白盒AES 實(shí)現(xiàn)方案[11], Derbez 等人在該高效通用分析方法的基礎(chǔ)上給出了計(jì)算復(fù)雜度為231的破解方案[14]. 在上述分析方法的影響下, CHES 2016/2017 連續(xù)兩年舉辦的AES 白盒實(shí)現(xiàn)競(jìng)賽均無(wú)方案能抵抗密鑰恢復(fù)攻擊[15].

在理論上, 白盒安全模型在算法運(yùn)行狀態(tài)下對(duì)攻擊者并無(wú)秘密可言, 但在實(shí)際中, 存在一類(lèi)研究方向, 即對(duì)白盒算法設(shè)計(jì)與實(shí)現(xiàn)提出秘密組件(secret components) 的前提條件, 其中具有代表性的就是Biryukov 等人提出的ASASA 框架[16]. 該類(lèi)工作往往假設(shè)分組加密算法的S 盒或擴(kuò)散層采用了秘密參數(shù)加以實(shí)現(xiàn), 該秘密參數(shù)對(duì)攻擊者并不公開(kāi). 由于該秘密參數(shù)的存在, 使得白盒模型下的攻擊者進(jìn)行密鑰恢復(fù)攻擊的難度大大增加. Chow 等人所提出的白盒分組密碼實(shí)現(xiàn)中, 外部編碼(external encoding) 由于也是對(duì)攻擊者保密, 因此也可以看作是算法白盒實(shí)現(xiàn)的秘密組件. 針對(duì)上述設(shè)計(jì)方案, Bos 等人提出了基于差分計(jì)算分析(differential computation analysis, 以下簡(jiǎn)稱(chēng)DCA) 和差分故障分析(differential fault analysis, 以下簡(jiǎn)稱(chēng)DFA) 的側(cè)信道分析方法[17], 能將設(shè)計(jì)方案中的隱藏S 盒或其他組件加以恢復(fù), 從而最終實(shí)現(xiàn)白盒算法的密鑰恢復(fù)攻擊. 上述側(cè)信道分析方法一經(jīng)提出, 在AES 白盒實(shí)現(xiàn)的破解上也取得了很好的實(shí)際破解效果. 在分析CHES 2017 AES 白盒實(shí)現(xiàn)競(jìng)賽中各種參賽方案的基礎(chǔ)上, Goubin 等人歸納出linear decoding analysis (LDA) 方法, 該方法能有效解決代碼混淆后的白盒分組密碼的秘密組件分析問(wèn)題[18]. Lee 等人提出在輪函數(shù)線性變換到非線性變換之間增加隨機(jī)掩碼的方式, 能有效提升白盒實(shí)現(xiàn)抵抗DCA 攻擊的安全性[19]. 在2019 年Journal of Cryptology 上, Bock 等人在Bos 等人DCA 和DFA 工作的基礎(chǔ)上, 提出了dynamic binary instrumentation (DBI) 安全框架用于白盒模型下密碼算法的側(cè)信道分析[20]. 在SAC 2019 上, Amadori 等人通過(guò)結(jié)合BGE 攻擊技術(shù), 使得DFA 攻擊能對(duì)增加了8 比特輸出外部編碼的白盒AES 方案進(jìn)行攻擊, 該方法的密鑰恢復(fù)攻擊復(fù)雜度為O(232)[21].

由于在資源受限環(huán)境下, 在分組密碼算法設(shè)計(jì)上增加側(cè)信道保護(hù)還需要考慮其實(shí)現(xiàn)代價(jià). Zhou 等人的探索性工作表明, 輕量級(jí)分組密碼算法也可以采用查找表或仿射變換的形式進(jìn)行白盒實(shí)現(xiàn)[22]. Xu 等人提出增加輪函數(shù)冗余和查找表變換的方式來(lái)模糊輪函數(shù)邊界, 進(jìn)而達(dá)到增大AES、SM4 等基于S 盒-線性擴(kuò)散類(lèi)型分組密碼白盒實(shí)現(xiàn)的分析難度[23]. 如何在實(shí)現(xiàn)分組密碼算法白盒安全性的基礎(chǔ)上, 能夠抵御各種側(cè)信道分析方式對(duì)算法實(shí)現(xiàn)秘密參數(shù)或組件的恢復(fù)攻擊, 并不是簡(jiǎn)單的技術(shù)疊加. 同時(shí), 算法增加側(cè)信道保護(hù)技術(shù)后能否與白盒實(shí)現(xiàn)有機(jī)整合, 盡可能地降低白盒實(shí)現(xiàn)的性能與資源開(kāi)銷(xiāo), 這也是決定白盒分組密碼算法能否具有實(shí)用性的關(guān)鍵問(wèn)題之一.

在LATINCRYPT 2012 年會(huì)上, Gierlichs 等人提出了DummyRounds 技術(shù)[24]. 該技術(shù)通過(guò)巧妙利用分組密碼輪函數(shù)存在不動(dòng)點(diǎn)的特性, 通過(guò)增加隨機(jī)等效輪的方式來(lái)實(shí)現(xiàn)密碼算法硬件實(shí)現(xiàn)的抗故障攻擊. 在CRYPTO 2016 年會(huì)上, Schneider 等人提出將奇偶校驗(yàn)碼(parity code) 和門(mén)限化實(shí)現(xiàn)(threshold implementation) 的ParTI 方案, 并針對(duì)PRESENT 分組密碼算法實(shí)現(xiàn)了抗差分能量攻擊和故障攻擊的一體化保護(hù)[25]. 雖然DummyRounds 技術(shù)和ParTI 方案均有效地抵抗了故障注入攻擊, 但DummyRounds 技術(shù)要求算法密鑰不能預(yù)先固定, 這與白盒分組密碼算法的密鑰由白盒密鑰表預(yù)計(jì)算完成并分配的實(shí)用方式不符. 同時(shí)DummyRounds 技術(shù)和ParTI 方案僅適用于硬件實(shí)現(xiàn)下的側(cè)信道防護(hù),如果在白盒實(shí)現(xiàn)中直接采用上述技術(shù), 攻擊者可以簡(jiǎn)單的旁路掉DummyRounds 或ParTI 方法中的保護(hù)測(cè)試部分, 使得故障注入還是能取得預(yù)期效果. 與DummyRounds 技術(shù)類(lèi)似的是, 韓國(guó)KAIST 的學(xué)者Lee 和Kim 也提出了基于Table Redundancy 的方式來(lái)抵抗DFA 分析[26]. Table redundancy 方法主要原理是通過(guò)并行MixColumns 步驟, 將計(jì)算結(jié)果進(jìn)行對(duì)比, 如果白盒實(shí)現(xiàn)遭受到DFA 攻擊, 那么并行MixColumns 步驟會(huì)導(dǎo)致輸出結(jié)果無(wú)法用于進(jìn)一步的DFA 分析.

在上述工作的基礎(chǔ)上, 本文針對(duì)一類(lèi)添加了內(nèi)/外部掩碼的隨機(jī)冗余輪函數(shù)保護(hù)的白盒AES[15](由于此類(lèi)保護(hù)方式與DummyRounds 具有相似性, 我們將該方法命名為NoisyRounds), 給出了在各種內(nèi)、外部編碼與冗余輪函數(shù)條件下的DFA 分析. 從我們基于Deadpool 工具[27]改進(jìn)后的自動(dòng)化DFA 分析結(jié)果來(lái)看, 如果僅僅在AES 輪函數(shù)中增加n 輪DummyRounds, 那么DFA 攻擊者只需線性增大獲取錯(cuò)誤密文數(shù)量即可成功恢復(fù)密鑰. 在添加n 組NoisyRounds 保護(hù)后, 密鑰恢復(fù)難度為NoisyRounds 組數(shù)n的(n+1)4計(jì)算復(fù)雜度. 在帶外部編碼的情況下, NoisyRounds 與現(xiàn)有保護(hù)方案一樣能抵抗DFA 工具的分析. 雖然外部編碼能夠抵抗DFA 分析, 但算法加解密結(jié)果也將帶上相應(yīng)的編碼, 與標(biāo)準(zhǔn)加解密結(jié)果不能一致, 將失去在不同系統(tǒng)間的兼容性. 因此實(shí)際白盒AES 應(yīng)用中，如何在不添加外部編碼的前提下抵抗DFA 攻擊也非常重要. 上述分析結(jié)果對(duì)于研究灰盒模型下常用的隨機(jī)冗余輪技術(shù)在白盒模型下的安全性具有參考意義.

2 背景知識(shí)

2.1 Chow 等人的白盒AES 實(shí)現(xiàn)

分組密碼算法AES-128 共10 輪[28],輪函數(shù)包括SubBytes、ShiftRows、MixColumns 和AddRound-Key 四個(gè)組成部分. 首輪之前, 先做一次AddRoundKey, 末輪沒(méi)有MixColumns. Chow 等人針對(duì)AES-128 設(shè)計(jì)的白盒密碼方案[2](以下簡(jiǎn)稱(chēng): Chow-WBAES) 的思路是調(diào)整加密順序, 改變算法每一輪的邊界,構(gòu)成輪函數(shù)加密依次如下順序: ShiftRows, AddRoundKey, SubBytes 和MixColumns 的輪結(jié)構(gòu), 如再將AddRoundKey 與SubBytes 組合成查表操作, 即建立8 比特輸入到8 比特輸出的查找表, 稱(chēng)為T(mén)-box,從而將密鑰隱藏在查找表中. 需要指出的是, 由于AES 的輪狀態(tài)可用4×4 單元表示, 除ShiftRows 以外, 其余操作均在當(dāng)列操作, 所以在AES 的白盒實(shí)現(xiàn)中可以列單位進(jìn)行白盒查找表的建立與加密運(yùn)算. 本文在部分描述中, 將以第1 列為例介紹Chow-WBAES.

對(duì)于一個(gè)字節(jié)的輸入x , T-box 如下表示:

其中i = 0,··· ,15,r = 1,··· ,9, kr為第r 輪輪密鑰, k0為第一輪之前的AddRoundKey 密鑰. ?kr[i] 表示kr經(jīng)過(guò)ShiftRows 變換后的第i 個(gè)字節(jié), i=0,1,··· ,15,r =0,1,··· ,10.

因MixColumns 每次作用在一列, 可由32×32 的矩陣MC 乘32 比特的列向量表示, 在白盒實(shí)現(xiàn)中加密時(shí)的MixColumns 與解密時(shí)的MixColumns 逆操作都可通過(guò)四個(gè)較小規(guī)模的8 比特輸入到32 比特輸出的查找表操作后再通過(guò)異或的方式完成. 加密時(shí)的查找表稱(chēng)為T(mén)yi, 解密時(shí)的查找表稱(chēng)為invTyi,i=0,1,2,3. 構(gòu)造如下表示:

32 比特的列向量(x0,x1,x2,x3) 進(jìn)行MixColumns 或MixColumns 逆操作可表示為4 次查表和3 次異或:

其中, i=0,··· ,3, r =2,··· ,9. 因此需要額外的查找表操作來(lái)抵消MB 的影響以及添加r+1 輪的輸入置換, 所以構(gòu)造8 比特輸入到32 比特輸出的查找表BijBox. 對(duì)于一個(gè)字節(jié)的輸入x, 第1 列的BijBox有如下表示:

結(jié)合查找表, 原AES-128 算法加密操作便可轉(zhuǎn)換為查表操作, 對(duì)于128 比特的明文plaintext, 其AES-128 加密有如下表示:

考慮到code lifting 攻擊, 需要對(duì)白盒解密程序的輸入密文和輸出明文做編碼來(lái)改變加密算法的明文與密文的映射關(guān)系, 防止攻擊者在不還原密鑰的情況下直接通過(guò)白盒解密裝置解密密文, 得到原始的明文,而對(duì)加解密程序的輸入輸出添加的編碼稱(chēng)為外部編碼(external encodings). 用Dk表示AES-128 解密,F 表示外部輸入編碼, G 表示外部輸出編碼, 增加外部編碼的解密程序如下表示:

外部編碼實(shí)現(xiàn)目前主要有線性和非線性編碼, Chow 等人建議的是選擇128 比特到128 比特的置換編碼,并且將該置換轉(zhuǎn)換成16 個(gè)8 比特到128 比特的查找表結(jié)合異或?qū)崿F(xiàn), 即在首輪之前, 添加額外的16 個(gè)8比特到128 比特的查找表和對(duì)應(yīng)的480 個(gè)異或表來(lái)實(shí)現(xiàn), 同樣的在第10 輪之后, 也需要額外的查找表和異或表來(lái)實(shí)現(xiàn)G (也可與第10 輪的T-boxes 結(jié)合, 構(gòu)成新的8 比特到128 比特的查找表). 再通過(guò)查異或表的形式合并. 如圖1 的Type I 所示. 而在Muir[29]等人提出一種非線性編碼方式, 使用16 個(gè)隨機(jī)的8 比特的級(jí)聯(lián)編碼組成128 比特的非線性編碼, 其構(gòu)成如下:

這種編碼方式可無(wú)需額外的查找表, F?1與第1 輪的T-box 輸入結(jié)合, G 與最后一輪T-box 輸出結(jié)合.

圖1 Chow-WBAES 的四類(lèi)查找表Figure 1 Four types of lookup tables of Chow-WBAES

2.2 針對(duì)Chow-WBAES 的差分故障分析

在本小節(jié), 我們首先簡(jiǎn)要概述AES 差分故障攻擊方法, 隨后對(duì)Chow-WBAES 的差分故障攻擊的基本原理與方法進(jìn)行說(shuō)明.

2.2.1 差分故障分析

在1997 年Crypto 會(huì)議上,Biham 和Shamir 提出了差分故障分析(differential fault analysis,DFA)這一概念, 并將其用于攻擊DES 算法[30]. DFA 攻擊的核心思想是通過(guò)對(duì)分組密碼算法運(yùn)行過(guò)程的中間值注入錯(cuò)誤, 從而誘導(dǎo)出錯(cuò)誤密文并加以收集, 將錯(cuò)誤密文與正確的密文進(jìn)行分析, 最終恢復(fù)出相應(yīng)的輪密鑰. 由于分組密碼算法的密鑰擴(kuò)展函數(shù)大多具有可逆性, 因此在通過(guò)DFA 攻擊方式獲取分組密碼算法的輪密鑰后, 可以根據(jù)對(duì)應(yīng)算法的密鑰擴(kuò)展函數(shù)逆推出相應(yīng)的主密鑰. 例如在AES-128 中, 攻擊者獲取最后一輪的輪密鑰即可恢復(fù)主密鑰, AES-192 和AES-256 則需要最后兩輪的輪密鑰才能恢復(fù)主密鑰.

圖2 Dusart 等人對(duì)第九輪AES 的差分故障攻擊示意圖Figure 2 Illustration of Dusart et al.’s DFA from 9th round AES

將公式(2)中的3○4○式相加可得:

2.2.2 對(duì)Chow 等人的白盒AES 實(shí)現(xiàn)的差分錯(cuò)誤分析實(shí)例

本小節(jié)將介紹針對(duì)Chow-WBAES 的DFA 攻擊實(shí)例. 一般情況下, 攻擊者在對(duì)白盒實(shí)現(xiàn)實(shí)施差分故障攻擊時(shí), 首先運(yùn)行正常的加密程序得到正確的密文并記錄, 然后在加密程序的二進(jìn)制流或白盒查找表中注入錯(cuò)誤, 最終篩選合適的錯(cuò)誤密文用于計(jì)算可能的輪密鑰候選值. 在Bos 等人開(kāi)創(chuàng)性的白盒分組密碼DFA 攻擊方法[17]后, 陸續(xù)有基于DFA 自動(dòng)化分析工具[27]破解白盒AES 的實(shí)際案例[32]. 此外,Teuwen 等人[33]也提出了使用Deadpool[27]工具成功分析Karroumi[10]和SECCON 2016[34]中的白盒AES 實(shí)現(xiàn)方案. 2019 年Bock 等人[20]詳細(xì)提出了若干種能在軟件環(huán)境下對(duì)密碼算法進(jìn)行注入錯(cuò)誤的方法, 有以下5 種:

(1) 通過(guò)code lifting 將白盒加密程序轉(zhuǎn)換成高級(jí)語(yǔ)言(例如C/C++), 這樣就可以將注入錯(cuò)誤的代碼插入到白盒加密的過(guò)程當(dāng)中.

(2) 將白盒程序運(yùn)行在二進(jìn)制動(dòng)態(tài)插樁分析(dynamic binary instrumentation, DBI) 的框架下(例如intel PIN[35]或Valgrind[36]) 并插入誘導(dǎo)錯(cuò)誤的代碼.

(3) 使用支持腳本的程序調(diào)試器(例如gdb) 對(duì)白盒程序進(jìn)行調(diào)試, 通過(guò)腳本自動(dòng)化地去對(duì)注入錯(cuò)誤以及收集對(duì)應(yīng)的密文.

(4) 將程序運(yùn)行在Unicorn Engine[37]或PANDA[38]等模擬器當(dāng)中, 則可以隨時(shí)改變數(shù)據(jù)的值或插入代碼, 從而達(dá)到對(duì)密碼程序注入錯(cuò)誤的目的.

(5) 在某些特定的情況下(例如白盒查找表或程序缺乏完整性檢測(cè)機(jī)制) 向白盒查找表或程序注入錯(cuò)誤, 使其輸出錯(cuò)誤的密文并對(duì)錯(cuò)誤密文進(jìn)行篩選.

當(dāng)加密或解密程序進(jìn)行安全加固后, 前4 種方法將難以實(shí)現(xiàn), 本文所使用的分析工具Deadpool[27]采用了上述的方法(5) 的策略, 將錯(cuò)誤注入到白盒程序中. Teuwen 和Hubain 中對(duì)Deadpool 的工作原理進(jìn)行了闡述[33], 首先提出了兩個(gè)基本的要求:

(1) 白盒加密程序所產(chǎn)生的密文不應(yīng)該帶有外部輸出編碼(external encoding), 因?yàn)槭褂猛獠枯敵鼍幋a時(shí)攻擊者無(wú)法直接地分析出注入錯(cuò)誤對(duì)密文的影響.

(2) 加密程序能多次運(yùn)行, 確保能獲得多對(duì)錯(cuò)誤密文.接下來(lái)對(duì)Deadpool 平臺(tái)的DFA 攻擊進(jìn)行描述:

(1) Deadpool 首先導(dǎo)入白盒查找表T 并運(yùn)行加密程序E 得到正確密文C 并記錄.

(2) Deadpool 嘗試遍歷T(使用優(yōu)化算法降低遍歷空間) 和并產(chǎn)生隨機(jī)錯(cuò)誤注入到T (通過(guò)對(duì)二進(jìn)制中的某段地址異或一串隨機(jī)值), 得到錯(cuò)誤密文, 對(duì)比錯(cuò)誤密文與正確密文, 符合要求的錯(cuò)誤密文將被分類(lèi)記錄, 按列分為4 類(lèi).

(3) 遍歷完成后,運(yùn)用第2.2.1 節(jié)的方法,針對(duì)獲取到的錯(cuò)誤密文分別破解第10 輪輪密鑰K10,0,K10,7,K10,10,K10,13.

(4) 根據(jù)K10逆推回主密鑰.

Deadpool 系列攻擊工具的開(kāi)源, 引起了白盒密碼界的廣泛關(guān)注, 其對(duì)目前多個(gè)公開(kāi)發(fā)表的白盒實(shí)現(xiàn)進(jìn)行了DFA 攻擊, 表1 展示了部分白盒AES 實(shí)現(xiàn)在DFA 攻擊下的實(shí)際抵抗效果.

表1 部分白盒AES 實(shí)現(xiàn)在DFA 攻擊下的實(shí)際抵抗效果Table 1 Actual status of partial AES white-box implementations against DFA attack

3 一種NoisyRounds 保護(hù)的AES 白盒實(shí)現(xiàn)

在本節(jié)中, 我們將提出一種可有效抵抗DFA 攻擊的AES 白盒實(shí)現(xiàn)方案NoisyRounds-WBAES. 首先介紹NoisyRounds-WBAES 的原理及其實(shí)現(xiàn), 然后通過(guò)Deadpool 平臺(tái)的DFA 分析工具[27]的攻擊實(shí)驗(yàn), 我們給出在NoisyRounds 保護(hù)下的白盒AES 實(shí)現(xiàn)抵抗DFA 攻擊的有效性.

3.1 NoisyRounds-WBAES 原理說(shuō)明與分析

雖然Tao Xu 等人的輪邊界混淆工作[23]被Yeom 等人采用積分攻擊和BGE 攻擊相結(jié)合的方式破解[39], 但特定結(jié)構(gòu)的隨機(jī)冗余輪函數(shù)(DummyRounds) 是否能抵抗側(cè)信道攻擊, 特別是DFA 攻擊仍然有待詳細(xì)研究. 因此本文基于Chow-WBAES 方案, 提出了一種針對(duì)白盒AES 實(shí)現(xiàn)的NoisyRounds 保護(hù)方案, 該方案結(jié)合了在灰盒模型中證明有效的DummyRounds 技術(shù), 同時(shí)根據(jù)DFA 攻擊的特點(diǎn)來(lái)設(shè)計(jì)冗余輪函數(shù)的結(jié)構(gòu). 以下將該方案簡(jiǎn)稱(chēng)為NoisyRounds-WBAES.

在CHES 2016 上, Bos 等人[17]提出了針對(duì)AES 白盒應(yīng)用DFA 攻擊的方案, 該方案選擇AES白盒實(shí)現(xiàn)的最后兩輪進(jìn)行攻擊, 該方案主要有以下兩個(gè)特點(diǎn): (1) 無(wú)需知道注入故障的具體值; (2) 無(wú)需跟蹤寄存器和內(nèi)存信息, 錯(cuò)誤密文可直接輸出. 該方案將單個(gè)字節(jié)的錯(cuò)誤注入到MixColumns8th與MixColumns9th之間, 經(jīng)過(guò)MixColumns9th以及第10 輪運(yùn)算后, 最終得到與正確密文相比存在4 個(gè)錯(cuò)誤字節(jié)的錯(cuò)誤密文(該4 個(gè)錯(cuò)誤字節(jié)分布符合ShiftRows 規(guī)律). 我們將MixColumns9th及第10 輪整輪稱(chēng)為“DFA 分析輪組”. 本文在Chow-WBAES 的基礎(chǔ)上, 通過(guò)在實(shí)際的第10 輪后添加與DFA 分析輪組的結(jié)構(gòu)一致的輪組來(lái)混淆DFA 攻擊, 這樣的輪組稱(chēng)為“NoisyRounds”, 而相對(duì)應(yīng)的, 需要增加能夠抵消新增的NoisyRounds 的輪結(jié)構(gòu)已保證白盒實(shí)現(xiàn)的正確性. 在應(yīng)用上述Deadpool 平臺(tái)的DFA 分析工具攻擊NoisyRounds-WBAES 時(shí), NoisyRounds 與DFA 分析輪組都有可能被注入錯(cuò)誤并輸出錯(cuò)誤密文,并且根據(jù)密文無(wú)法區(qū)分其來(lái)自二者中的哪一個(gè). 又因?yàn)镹oisyRounds 的查找表T-box 所使用的密鑰是隨機(jī)生成的, 與實(shí)際密鑰沒(méi)有任何關(guān)聯(lián), 如此DFA 分析工具提取出的密鑰為實(shí)際密鑰與NoisyRounds 的密鑰的集合, 若要區(qū)分, 攻擊者需將集合內(nèi)密鑰遍歷, 而遍歷空間與添加的NoisyRounds 組數(shù)n 成正相關(guān).

3.2 NoisyRounds-WBAES 的設(shè)計(jì)與實(shí)現(xiàn)

NoisyRounds-WBAES 在Chow-WBAES 方案的基礎(chǔ)上, 改變?cè)?0 輪, 并添加若干組的Noisy-Rounds. 每組NoisyRounds 包含3 輪, 其中第2-3 輪和Chow-WBAES 的DFA 分析輪組在結(jié)構(gòu)上是一致的, 并且NoisyRounds 使用的輪密鑰是隨機(jī)的. 為更好的描述NoisyRounds-WBAES 實(shí)現(xiàn), 首先假定NoisyRounds 的組數(shù)為n, NoisyRounds-WBAES 的算法描述如算法1 所示. 將NoisyRounds-WBAES分為3 個(gè)階段描述.

算法1 NoisyRounds-WBAES Input: P,ki,?ki for i ∈0,··· ,10,rki for i ∈0,··· ,n, 其中P 為明文, n 為NoisyRounds 組數(shù), ki 為主密鑰K 的子密鑰, ?ki 為ki 的ShiftRows 以后的結(jié)果, rki 為隨機(jī)生成的輪密鑰.Output: C = AES(P,K).1 State: R ←P; r ←1;2 while r ≤9 do 3 R = ShiftRows(R);4 R = AddRoundKey(R,?kr?1);5 R = SubBytes(R);6 ss R = MixColumns(R)7 end 8 R = ShiftRows(R);9 R = AddRoundKey(R,?k9);10 R = SubBytes(R);11 R = AddRoundKey(R,k10);12 r ←1;13 while r ≤n do 14 R = AddRoundKey(R,rkr?1);15 R = invSubBytes(R);16 R = AddRoundKey(R,rkr);17 R = invShiftRows(R);18 R = invMixColumns(R);19 R = MixColumns(R);20 R = ShiftRows(R);21 R = AddRoundKey(R,rkr);22 R = SubBytes(R);23 R = AddRoundKey(R,rkr?1);24 end 25 return R

· 1-10 輪: NoisyRounds-WBAES 的第1-10 輪和Chow-WBAES 的第1-10 輪的運(yùn)算是一致的, 需要說(shuō)明的是, NoisyRounds-WBAES 第10 輪在Chow-WBAES 的第10 輪基礎(chǔ)上增加了AddRoundKey 和invSubBytes 步驟, 具體在NoisyRounds 抵消部分在描述.

其中i=0,1,··· ,15, invS 為AES-128 中S 盒的逆操作, rkr為隨機(jī)生成的密鑰.

對(duì)于一個(gè)字節(jié)的輸入x, NoisyRounds-WBAES 中每輪的第1 列的TM-table 構(gòu)造如下:

其中i=0,1,2,3. θ 為位擴(kuò)展操作, 將8 位的輸入轉(zhuǎn)換為32 位的輸出, θi(x) 有如下表示:

同樣的, 需要額外的查找表操作來(lái)抵消MB 的影響以及添加r+1 輪的輸入置換, 所以構(gòu)造8 比特輸入到32 比特輸出的查找表BijBox. 對(duì)于一個(gè)字節(jié)的輸入x, BijBox 有如下表示:

最終, NoisyRounds-WBAES 在應(yīng)用了內(nèi)部線性和非線性編碼以后, 在NoisyRounds 組數(shù)為n 時(shí),所需查找表數(shù)量如表2 所示, 共需存儲(chǔ)開(kāi)銷(xiāo)168n+508 KB, 與Chow-WBAES 的存儲(chǔ)開(kāi)銷(xiāo)相比, 每添加一組NoisyRounds, 存儲(chǔ)開(kāi)銷(xiāo)增加30%, 而將故障注入正確位置的概率降低50%. 圖3 展示了錯(cuò)誤注入NoisyRounds 的N2和N3時(shí)的情況, 注入N2和N3時(shí)得到的錯(cuò)誤密文與注入到實(shí)際第8 輪和第9 輪之間的到的錯(cuò)誤密文與正確的密文相比, 都是存在4 個(gè)錯(cuò)誤字節(jié)且這4 個(gè)字節(jié)有同樣的排列規(guī)律, 這對(duì)于攻擊者來(lái)說(shuō)是不可區(qū)分的.

表2 NoisyRounds-WBAES 存儲(chǔ)開(kāi)銷(xiāo)Table 2 Total storage requirement of NoisyRounds-WBAES

3.3 實(shí)驗(yàn)與安全性分析

在系統(tǒng)版本為Ubuntu16.4, GCC 版本為5.4.0, 內(nèi)存大小16 G, CPU 型號(hào)為Intel(R) Core(TM) i7-7700 CPU@3.60 GHz 的實(shí)驗(yàn)環(huán)境中,運(yùn)用Deadpool 工具對(duì)Chow-WBAES 與NoisyRounds-WBAES,包括兩種算法增加非線性/線性的外部編碼的情況進(jìn)行DFA 實(shí)驗(yàn).

圖3 針對(duì)NoisyRounds 的錯(cuò)誤注入示意圖Figure 3 Illustration of DFA attack to NoisyRounds

實(shí)驗(yàn)結(jié)果表3 展示了NoisyRounds 組數(shù)為1 的白盒AES 實(shí)現(xiàn)與Chow-WBAES 的對(duì)比結(jié)果, 結(jié)合表1, 我們發(fā)現(xiàn)有如下現(xiàn)象:

· NoisyRounds-WBAES 在一次遍歷所需次數(shù)上小于Chow-WBAES, 這是因?yàn)镃how-WBAES 的查找表為實(shí)現(xiàn)為724 KB,可注入范圍為bijBox8th和xor_table8th的部分空間,大小為160 Bytes,所以獲得錯(cuò)誤密文的概率為0.22%,而添加1 組NoisyRounds 后,可注入范圍被擴(kuò)大到320 Bytes,而查找表大小擴(kuò)充到964 KB, 所以獲得錯(cuò)誤密文概率增大到0.32%, 從而破壞了Deadpool 分析工具的遍歷優(yōu)化算法. 圖4 展示了在Deadpool 工具下有效錯(cuò)誤密文、混淆錯(cuò)誤密文以及無(wú)效錯(cuò)誤密文隨NoisyRounds 組數(shù)的關(guān)系, 其中無(wú)效錯(cuò)誤密文是錯(cuò)誤注入到了MB 置換造成符合規(guī)律的錯(cuò)誤密文, 混淆錯(cuò)誤密文是錯(cuò)誤注入到NoisyRounds 后得到的錯(cuò)誤密文, 而有效錯(cuò)誤密文才是包含實(shí)際密鑰信息的錯(cuò)誤密文.

· 外部編碼對(duì)DFA 攻擊有抵抗作用. 通過(guò)實(shí)驗(yàn)發(fā)現(xiàn), 外部編碼對(duì)DFA 的抵抗作用主要為外部輸出編碼的影響, 因?yàn)橥獠枯敵鼍幋a可看成加密算法的秘密套件, 外部輸出編碼對(duì)于攻擊者是未知的,并且外部輸出編碼不會(huì)在加密算法內(nèi)部抵消, 所以攻擊者無(wú)法繞過(guò)外部編碼的影響. 現(xiàn)對(duì)帶外部編碼的WBAES 進(jìn)行DFA 注入分析:

(1) 非線性外部輸出編碼: 假設(shè)明文Ai通過(guò)密鑰K 加密得到經(jīng)G 編碼的密文, 再通過(guò)在A0注入一個(gè)字節(jié)的錯(cuò)誤, 得到錯(cuò)誤密文, 根據(jù)章節(jié)2.2.1 的推算方法可得:

由于G0,G1,G2,G3未知, 無(wú)法確定Z 的集合, 所以該攻擊平臺(tái)不適用增加外部輸出編碼的白盒實(shí)現(xiàn).

(2) 線性外部輸出編碼: 線性外部輸出編碼可以看作是對(duì)輸出密文的128 比特到128 比特的置換,密文經(jīng)過(guò)置換后一個(gè)錯(cuò)誤的字節(jié)將影響大于等于個(gè)字節(jié), 而四個(gè)字節(jié)將影響大于等于4 個(gè)字節(jié), 被編碼的密文最終不能夠被分析工具當(dāng)作錯(cuò)誤密文收集并且無(wú)法分析, 所以無(wú)法應(yīng)用此類(lèi)方法還原密鑰.

盡管NoisyRounds 使得Deadpool 平臺(tái)的DFA 工具的遍歷優(yōu)化算法失效從而導(dǎo)致不能提取密鑰, 但攻擊者仍可以對(duì)白盒查找表進(jìn)行全遍歷注入, 進(jìn)而獲取所有的錯(cuò)誤密文, 其中所有的無(wú)效錯(cuò)誤密文, 混淆錯(cuò)誤密文以及有效錯(cuò)誤密文. 對(duì)于無(wú)外部編碼的Chow-WBAES, 其查找表大小為508 KB, 逐個(gè)字節(jié)注入錯(cuò)誤僅需2 小時(shí)即可完成. 因此我們假設(shè)攻擊者已經(jīng)通過(guò)全遍歷注入獲取到所有的錯(cuò)誤密文, 由于加密程序和白盒查找表經(jīng)過(guò)混淆以后, DFA 分析輪組對(duì)應(yīng)的查找表在整個(gè)白盒表中的位置是未知的, 攻擊者通過(guò)分析所有錯(cuò)誤密文得到的密鑰為所有NoisyRounds 的隨機(jī)密鑰以及真實(shí)密鑰的集合.

表3 基于Deadpool 工具的DFA 攻擊結(jié)果Table 3 Result of DFA attack against multiple algorithms

圖4 錯(cuò)誤密文對(duì)占比情況與NoisyRounds 組數(shù)關(guān)系圖Figure 4 Distribution of fault ciphertext pairs

(1) 隨機(jī)選擇明文P, 運(yùn)行白盒AES 加密程序E 得到密文C.

不難發(fā)現(xiàn), 此種攻擊模型下, 攻擊者需要遍歷候選密鑰并執(zhí)行加密程序(n+1)4次, 才能夠提取出真實(shí)密鑰, 而白盒查找表的大小隨n 的變化呈正相關(guān). 圖5 展示了提取真實(shí)密鑰所需遍歷次數(shù)和白盒查找表大小隨NoisyRounds 組數(shù)n 的變化關(guān)系.

4 結(jié)束語(yǔ)

雖然Chow 等人的白盒AES 實(shí)現(xiàn)方案存在多種破解手段, 但由于其實(shí)現(xiàn)代價(jià)小, 因此在實(shí)際中通過(guò)增加代碼混淆等軟件加固手段仍然得到廣泛應(yīng)用. 本文提出了一種基于NoisyRounds 保護(hù)的白盒AES實(shí)現(xiàn)方案, 該方案通過(guò)改變Chow 等人的白盒AES 算法的第10 輪結(jié)構(gòu), 并在其后增加能夠混淆DFA 攻擊分析的輪組來(lái)抵抗DFA 攻擊. 實(shí)驗(yàn)與安全性分析表明, 該方案能夠以計(jì)算復(fù)雜度為O(n4) 增大DFA針對(duì)白盒AES 攻擊的難度, 而存儲(chǔ)開(kāi)銷(xiāo)以線性大小增加. 如果在NoisyRounds 保護(hù)的基礎(chǔ)上增加外部編碼保護(hù), 在外部編碼未知的前提下，攻擊者將不能通過(guò)DFA 分析來(lái)進(jìn)行密鑰恢復(fù)攻擊. 本文工作對(duì)于提升Chow 類(lèi)型白盒AES 的抗DFA 分析能力具有參考意義. 未來(lái)我們將嘗試肖雅瑩和來(lái)學(xué)嘉提出的16比特的內(nèi)部編碼的白盒AES 方案的DFA 分析和進(jìn)一步研究NoisyRounds 技術(shù)對(duì)基于仿射變換的白盒SM4 實(shí)現(xiàn)的抗DFA 保護(hù)方案.

圖5 遍歷子密鑰次數(shù)和存儲(chǔ)開(kāi)銷(xiāo)與n 的變化關(guān)系圖Figure 5 Relation between number of exhaustive search and storage cost