基于查找表的白盒AES 加密算法優(yōu)化*

陶慎亮 朱 濤

（江蘇警官學(xué)院計(jì)算機(jī)信息與網(wǎng)絡(luò)安全系 南京 210031）

1 引言

在密碼學(xué)中，通常都會(huì)提出一個(gè)前提：即該密碼算法的執(zhí)行環(huán)境（終端）是可信任的，因此密鑰的安全性就成為最先關(guān)注的問題。然而在現(xiàn)實(shí)生活中，這個(gè)前提往往得不到滿足，這就使得密鑰的安全性受到了極大的威脅。例如，當(dāng)用戶打開一個(gè)視頻播放器，該視頻播放器可以自行對加密的視頻信號進(jìn)行解密，此時(shí)該視頻播放器的運(yùn)行環(huán)境可以看作是不安全的，那么該軟件的整個(gè)解密過程對于此用戶（或攻擊者）而言是可見的，這樣可以輕而易舉得到密鑰信息。

針對以上所描述的問題，Chow 等在2002 年提出了一個(gè)概念：白盒攻擊環(huán)境［1］。所謂的白盒攻擊環(huán)境就是指攻擊者對軟件執(zhí)行過程完全可見的環(huán)境。依照上文所述，用戶（或攻擊者）通過運(yùn)行密碼軟件或者直接觀察便能輕而易舉地獲取到密鑰信息。在這種狀況下，如果依舊對密鑰進(jìn)行保護(hù)無異于“亡羊補(bǔ)牢，為時(shí)晚矣”，此時(shí)就迫切地需要對于密鑰的特殊保護(hù)，需要用密碼算法的實(shí)現(xiàn)來對密鑰信息進(jìn)行隱藏，由此，白盒密碼應(yīng)運(yùn)而生。它的目的和作用很明確，即將密鑰信息隱藏于白盒攻擊環(huán)境之中，避免密鑰在密碼軟件執(zhí)行過程中被攻擊者強(qiáng)行獲取。

Chow 等對白盒密碼的設(shè)計(jì)思想［2］就是混淆—打亂明文到密文之間的映射關(guān)系即將密碼算法的輸入和輸出進(jìn)行置亂，使得密碼算法被混淆，從而避免攻擊者強(qiáng)行得出密鑰信息。根據(jù)此思路，白盒DES 算法［1］便被設(shè)計(jì)出來用于避免攻擊者強(qiáng)行得出密鑰信息；在2003年，Chow等又提出白盒AES算法［3］，用查找表的形式來代替密碼算法的執(zhí)行全程，而密鑰信息就隱藏在查找表中，攻擊者從查找表中偵聽到密鑰信息將很困難。2005年Billet等提出了針對該白盒AES 算法的攻擊方法［4］，通過對查找表的分析，在230的時(shí)間復(fù)雜度內(nèi)可以恢復(fù)查找表所混淆的信息，從而獲取密鑰信息。在2010 年，肖雅瑩和來學(xué)嘉提出一種能夠抵抗BGE 攻擊的白盒AES 的可靠實(shí)現(xiàn)［5］，將密碼算法的實(shí)現(xiàn)由查找表和矩陣乘法共同完成，此算法可以得到更高的復(fù)雜度和安全性，但也需要耗費(fèi)更大的內(nèi)存空間，在PC上需要幾秒鐘的運(yùn)行時(shí)間。另外還有其他一些相關(guān)工作［8～17］，性能均有待提高。

為了驗(yàn)證與改善Chow等提出的白盒AES算法的性能，本文設(shè)計(jì)并實(shí)現(xiàn)了Chow白盒AES算法，并且針對算法的不同功能模塊建立了相應(yīng)的加速查找表，選擇合理有效的數(shù)據(jù)結(jié)構(gòu)，改進(jìn)了白盒AES算法各主要功能模塊的性能。實(shí)驗(yàn)證明本文設(shè)計(jì)的白盒AES 算法優(yōu)化方案可在白盒攻擊環(huán)境下對字符進(jìn)行高效地加密和解密操作，同時(shí)能夠有效地保護(hù)密鑰信息。

2 算法設(shè)計(jì)

Chow 等提出的白盒AES 算法的主要實(shí)現(xiàn)難度在于對于有限域GF運(yùn)算的實(shí)現(xiàn)以及各查找表的構(gòu)建與相關(guān)數(shù)據(jù)結(jié)構(gòu)和函數(shù)的設(shè)計(jì)；本文設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)建立算法中相應(yīng)的各類查找表，實(shí)現(xiàn)白盒AES 算法中的各主要功能模塊，能夠提高白盒AES算法的性能，總體設(shè)計(jì)流程圖如圖1所示。

圖1 白盒AES算法實(shí)現(xiàn)總體設(shè)計(jì)流程圖

執(zhí)行白盒AES算法的前后需要進(jìn)行有關(guān)PKCS（The Public-Key Cryptography Standards，公鑰密碼標(biāo)準(zhǔn)）5Padding 的操作。在加密之前需要對明文進(jìn)行PKCS 5Padding 填充，明文由UI 傳入之后先分組，每一組大小16bits，如果最后一組剛好是16bits，那么填充一組“16”，如果不滿，則填充缺少的那個(gè)字符。

本文針對白盒AES 的改進(jìn)主要在于對于各種類型查找表的構(gòu)造，首先分析整個(gè)算法的查找表查找流程、各查找表之間的關(guān)系、數(shù)量情況以及占用內(nèi)存情況。

域具備加法和乘法上的封閉性，就是說對域中的元素進(jìn)行加法或乘法運(yùn)算后的結(jié)果仍然是域中的元素；這里所說的加法和乘法分別對應(yīng)與運(yùn)算和異或運(yùn)算。有限域是指元素個(gè)數(shù)為有限個(gè)數(shù)的域。而GF（28）中的元素都為多項(xiàng)式：

這些多項(xiàng)式與256 個(gè)數(shù)一一對應(yīng)，將數(shù)的運(yùn)算變成了多項(xiàng)式的運(yùn)算，而此多項(xiàng)式又對應(yīng)著一個(gè)數(shù)，由此達(dá)到混淆的目的。Galois（伽羅華）域SDK—m4ri 對GF（28）的有關(guān)運(yùn)算提供了支持。以AES-128為例的普通AES算法流程如圖2。

圖2 普通AES加密流程

白盒AES 算法流程如圖3 所示，其改變了每一輪的局限，把AddRoundKeys 和下一輪的SubBytes兩個(gè)步驟聯(lián)合起來作為一個(gè)新的步驟，將這個(gè)新的步驟稱之為T-Box（T盒）。這樣密鑰信息就被隱藏在SubBytes（即S盒中）。

圖3 白盒AES加密流程

其中T 為T 盒，是由AddRoundKey 和SubBytes所組成的；T盒能夠用以下公式表示：

S 為S 盒，是 固 定 的8bits 輸 入8bits 輸 出 的 置換；mbi為線性變換，用于對T 盒進(jìn)行混淆作用；MB為一個(gè)32×32（bits）的雙射，用于對MC 進(jìn)行混淆；mbi 和MB 的混淆作用都需要用額外的計(jì)算來進(jìn)行抵消。

在算法的實(shí)現(xiàn)過程中密鑰是事先選定的，因此T 盒是可以計(jì)算出來的，根據(jù)式（3）和式（4）可以知道T 盒也是由8bits 輸入到8bits 輸出，由于明文為128bits，所以每一輪需要16 個(gè)T 盒來支持變換，總共需要160個(gè)T盒。

白盒密碼的首要目標(biāo)就是保護(hù)密鑰信息，而密鑰信息隱藏在T 盒里面，因此對于T 盒的保護(hù)就變成了首要目標(biāo)，由此避免攻擊者獲取密鑰信息。

在AES 中的每一輪狀態(tài)都可以用一個(gè)4×4（bits）的單元進(jìn)行表示，128bits 的明文在此變?yōu)榱?28×128（bits）的矩陣，為了符合4×4單元，將32×32看作是4×4 矩陣中的一個(gè)元素，而MixColumn 變換操作一次執(zhí)行一列，因此可以看作是一個(gè)32×32（bits）的矩陣MC 乘以一個(gè)32bits 的列向量進(jìn)行表示，需要一次性占用B232×32=16G 的內(nèi)存?？梢詫C按列分為4個(gè)MCi，在這之前還需要左乘一個(gè)32×32（bits）的雙射MB 進(jìn)行混淆，因此整個(gè)過程可以表示為

式（4）的hi是T 盒經(jīng)過混淆之后進(jìn)行的一部分MixColumn 的結(jié)果，可以用一個(gè)8bits 輸入32bits 輸出的查找表進(jìn)行表示，這個(gè)查找表加入置亂編碼后就形成了類型Ⅱ查找表（如圖4）。h0⊕h1⊕h2⊕h3中的三個(gè)異或加入置亂編碼之后則可以用類型Ⅳ查找表來表示（如圖5）。

圖4 TypeⅡ查找表結(jié)構(gòu)

圖5 TypeⅣ查找表結(jié)構(gòu)

圖6 TypeⅢ查找表結(jié)構(gòu)

而對于所有的輸入輸出是用了兩個(gè)128bits 到128bits 的雙射，此雙射包含了抵消混淆效果的mbi-1，對此雙射的置亂編碼可以用類型Ⅰ查找表（如圖7）進(jìn)行表示。

圖7 TypeⅠ查找表結(jié)構(gòu)

總結(jié)一下四個(gè)類型的查找表：類型Ⅰ表具有2個(gè)4位的輸入編碼，一個(gè)128×8的矩陣，和32個(gè)4位的輸出編碼；類型Ⅱ表具有2個(gè)4位輸入編碼，一個(gè)8×8 混合雙射，一個(gè)T 盒，一個(gè)32×8 的代表（MB·MCi-1）的矩陣，8個(gè)4位的輸出編碼；類型Ⅲ表具有2 個(gè)4 位的輸入編碼，一個(gè)32×8 的矩陣，和8 個(gè)4 位的輸出編碼。類型Ⅳ表具有2 個(gè)4 位輸入編碼，已知的異或操作和一個(gè)4位輸出編碼

總體的查找表訪問流程如圖8。

圖8 白盒AES查找表流程

由此可以計(jì)算出總共的查找表的數(shù)量和總共所需的占用內(nèi)存：

TypeⅡ和TypeⅢ：9×2×4×2＝288 個(gè)表，每個(gè)表大小為28×32＝8192bytes；

用于支持TypeⅡ和TypeⅢ的TypeⅣ：9×2×4×8 × 3＝1728 個(gè) 表，每 個(gè) 表 的 大 小 為28× 4＝1024bytes；

TypeⅠ：2×4＝32個(gè)表，每個(gè)表的大小為28×4＝1024bytes；

用于支持TypeⅠ的TypeⅣ：2×32×15＝960 個(gè)表，每個(gè)表的大小為8192bytes。

因此總的查找表大小為770048B（752KB）。

Type II and III：288 次查找訪問；支持II，III 的Type IV：1728次查找訪問；

Type I：32×4＝128 次查找訪問；支持I 的Type IV：960次查找訪問。

在此白盒AES加密算法函數(shù)實(shí)現(xiàn)基礎(chǔ)上，由于相關(guān)的各類型查找表的構(gòu)造、訪問，都已實(shí)現(xiàn)好，因此增加了相應(yīng)的白盒AES解密功能，解密步驟如下：

1）對解密密鑰進(jìn)行賦值；

2）白盒AES解密算法的初始化；

3）循環(huán)對每一段密文進(jìn)行解密；

4）對解密后的密文進(jìn)行拼接；

5）刪除填充字符并計(jì)算明文長度；

6）釋放資源。

解密所得到的明文將返回給UI 界面顯示出來，并與普通AES算法得出的明文進(jìn)行比對。

在加密操作的第三步和解密操作的第四步中，都有一個(gè)對字符填充的操作。在加密的時(shí)候，需要對明文進(jìn)行PKCS 5Padding填充。填充過程偽代碼如下：

1）if（明文字長為16的整數(shù)倍）

2）｛填充一組（一組16 字節(jié)）全為‘16’的字符串｝

3）else

4）｛最后一組的末尾填充字符，字符為需要填充的個(gè)數(shù)｝

如此進(jìn)行填充完之后才可執(zhí)行之后的加密操作。

同理，在解密操作時(shí)，需要對解密操作之后的字符串進(jìn)行刪除填充操作才能得到相應(yīng)的明文，而刪除操作實(shí)際上只要得出真正明文的長度來即可。于是只需減掉最后一個(gè)字符個(gè)數(shù)，即可得出真實(shí)明文長度。根據(jù)此長度循環(huán)獲取明文字符即可。

3 算法測試

為了判別算法實(shí)現(xiàn)的準(zhǔn)確性，設(shè)計(jì)了算法演示UI，在UI 中加入了AES 對照組用于檢驗(yàn)加解密結(jié)果是否正確。實(shí)驗(yàn)中，采用Java編寫，在配置為Xeon2.3GHz*24*6 核，64GB 內(nèi)存，512GB 硬盤的服務(wù)器上運(yùn)行。

密鑰的設(shè)置由文件輸入傳入，將帶有密鑰的。txt 文本輸入即可（在實(shí)際應(yīng)用過程中可由加密者自己設(shè)置，寫入實(shí)現(xiàn)代碼中以防止被攻擊者通過其他方式），通過加密這個(gè)動(dòng)作將密鑰和明文這兩個(gè)信息傳給后端程序執(zhí)行加密操作，得出的密文返回至UI 上進(jìn)行顯示。另外，由于AES 算法的密鑰分別有128bits，192bits和256bits，因此UI應(yīng)能夠選擇哪一種密鑰，利用UI界面執(zhí)行下述實(shí)驗(yàn)測試。

執(zhí)行白盒AES加解密算法的程序，首先需要提供存儲(chǔ)密鑰的文本文件，輸入明文，執(zhí)行加密操作，可以看到普通AES密文和白盒AES密文，再將密文復(fù)制到解密組的密文輸入框中，執(zhí)行解密操作，可以得到普通AES明文和白盒AES明文。

通過UI 可以看到白盒AES 加解密的中間步驟，可以看到明文經(jīng)過PKCS5Padding 填充之后的字符。明文“0123456789abcde”為16 位，因此需要在后面再填充16×16，本文實(shí)驗(yàn)將它們作2 位16 進(jìn)制輸出。

而后可以看見，白盒AES 加密先對前16 個(gè)字符進(jìn)行了加密，因?yàn)槭?28bits 的白盒AES 加密。先進(jìn)行類型Ⅰ查找表的訪問和類型Ⅳ查找表的訪問；根據(jù)實(shí)驗(yàn)結(jié)果所示，訪問之后變?yōu)榱薳0e83946 5340009e 4e007a3e f2d185b6，UI 界面顯示了該明文在10輪過程中的變化情況。

之后便是對下一組16 個(gè)字符的加密操作，經(jīng)過10 輪的變換后所得出的字符與之前所得到的字符進(jìn)行拼接，得出密文。

同樣，實(shí)驗(yàn)驗(yàn)證了解密的中間過程。可以看到解密過程也是先對128bits 的密文進(jìn)行操作，完成10 輪變換之后得到一組明文，然后再對下一個(gè)128bits 的密文進(jìn)行解密操作，得到一組明文，將這兩組明文拼接起來，再進(jìn)行去PKCS5Padding 填充操作，去掉16×16 之后，得到正確的明文“0123456789abcde”。

當(dāng)明文的位數(shù)不是16 的整數(shù)倍的時(shí)候，PKCS5Padding填充將會(huì)把此明文填充至16 的整數(shù)倍，填充的字符為缺少個(gè)數(shù)的數(shù)字。明文為

00112233445566778899aabbcce

實(shí)驗(yàn)中有關(guān)查找表的構(gòu)建需要用到GF（28）的運(yùn)算，而有關(guān)GF 運(yùn)算的編程實(shí)現(xiàn)有伽羅華域SDK m4ri 來提供支持，改進(jìn)的白盒AES 算法將原有的AES算法改成關(guān)于查找表的查找操作，對所需查找表的個(gè)數(shù)以及所要占用的內(nèi)存進(jìn)行詳細(xì)的分析與計(jì)算：總共需要查找表3008 個(gè)，所需要訪問次數(shù)為3104次，查找表占用內(nèi)存752KB，算法運(yùn)算加、解密時(shí)間均在0.1s內(nèi)，獲得了良好的性能。

4 結(jié)語

本文分析普通AES 算法在白盒攻擊環(huán)境下存在的安全隱患，考慮到伽羅瓦域運(yùn)算［6］的需求，選用了合適的SDK，構(gòu)造相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來支持建立白盒AES算法所需的各類型查找表；設(shè)計(jì)各種查找表的訪問改進(jìn)了白盒AES算法的主要功能模塊，如ByteRotation，MixColumn和ByteSubstitution等；選用多個(gè)測試用例，根據(jù)所實(shí)現(xiàn)的白盒AES算法對加解密結(jié)果做出相應(yīng)的測試和分析，并和普通AES的結(jié)果進(jìn)行了對比。實(shí)驗(yàn)證明改進(jìn)的白盒AES 算法具有良好的準(zhǔn)確性和效率，對于不同類型的復(fù)雜字符都能實(shí)現(xiàn)白盒AES算法。