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

陶慎亮 朱 濤

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

1 引言

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

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

圖2 普通AES加密流程

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

圖3 白盒AES加密流程

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 白盒AES查找表流程

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

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

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

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

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

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

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

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

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

1）對解密密鑰進行賦值；

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

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

4）對解密后的密文進行拼接；

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

6）釋放資源。

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

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

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

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

3）else

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

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

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

3 算法測試

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

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

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

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

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

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

同樣，實驗驗證了解密的中間過程?？梢钥吹浇饷苓^程也是先對128bits 的密文進行操作，完成10 輪變換之后得到一組明文，然后再對下一個128bits 的密文進行解密操作，得到一組明文，將這兩組明文拼接起來，再進行去PKCS5Padding 填充操作，去掉16×16 之后，得到正確的明文“0123456789abcde”。

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

00112233445566778899aabbcce

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

4 結(jié)語

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