相關(guān)能量分析中的后向檢錯(cuò)方案*

司恩澤, 王 安, 祝烈煌, 丁瑤玲, 陳財(cái)森, 丁詩軍

1. 北京理工大學(xué) 計(jì)算機(jī)學(xué)院, 北京100081

2. 密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 北京100878

3. 陸軍裝甲兵學(xué)院演訓(xùn)中心, 北京100072

1 引言

自1996 年Kocher 提出計(jì)時(shí)分析方法[1]以來, 側(cè)信道分析這一不同于經(jīng)典密碼分析的獨(dú)特密碼分析方式, 經(jīng)過20 多年的發(fā)展, 憑借其強(qiáng)大的分析能力及廣闊的應(yīng)用范圍, 業(yè)已成為密碼學(xué)界研究的熱點(diǎn). 側(cè)信道分析的開展方式多種多樣, 應(yīng)用范圍各有不同, 主要包括計(jì)時(shí)分析[1]、能量分析[2–4]、模板分析[5]、電磁分析[6,7]、碰撞攻擊[8,9]、故障分析[10–12]、人工智能側(cè)信道分析[13–15]等多種方式. 其中, 相關(guān)能量分析(Correation Power Analysis, CPA)[3]技術(shù)是側(cè)信道分析領(lǐng)域最常用也是最有效的分析方式.

相關(guān)能量分析是Brier 等人[3]于2004 年提出的, 基本思想是利用密碼設(shè)備運(yùn)行時(shí)的能量消耗與其中間值之間的線性相關(guān)性, 通過猜測密鑰, 計(jì)算中間值, 然后與采集到的能量波形求相關(guān)系數(shù)來判定此密鑰猜測的正確性. 此法不僅效率遠(yuǎn)高于差分能量分析等傳統(tǒng)方法, 而且實(shí)施簡便、應(yīng)用范圍廣, 不論是硬件密碼芯片, 還是在CPU 中執(zhí)行的密碼算法程序, 都無法在無掩碼等防護(hù)措施的情況下免疫此方法. 此法一經(jīng)提出, 很快就取代了差分能量分析等第一代側(cè)信道分析方法, 成為了側(cè)信道分析領(lǐng)域應(yīng)用最廣泛的分析方法.

但是, 傳統(tǒng)的CPA 方法也有其局限性, 由于其只使用一列點(diǎn)與猜測密鑰生成的中間值的漢明重量/漢明距離求相關(guān)系數(shù), 這就導(dǎo)致能量波形中大量其他的事實(shí)上也與密鑰相關(guān)的點(diǎn)的信息被浪費(fèi)了. 如果我們可以妥善利用這些信息, 則必然能夠進(jìn)一步提高分析效率, 降低對能量波形條數(shù)的要求. Oswald 等人[16]提出可以利用對應(yīng)同一中間值的多個(gè)泄露點(diǎn)的信息, 按一定權(quán)重與中間值計(jì)算相關(guān)度, 以此提高效率, 減少恢復(fù)密鑰所需的波形條數(shù); Wang 等人[17]則更進(jìn)一步, 提出利用AES 算法中S 盒輸出值y 與列混合中會(huì)產(chǎn)生的2y、3y 中間值與其對應(yīng)的波形共同求相關(guān)系數(shù), 可以進(jìn)一步提高CPA 的效率, 將所需的能量波形數(shù)減少80% 以上. 但是, 上述方案雖然利用了更多波形點(diǎn)的信息量, 然而其面對的共同問題是, 要想驗(yàn)證密鑰猜測的正確性, 就必須恢復(fù)完整的密鑰才行. 這時(shí), 即使單個(gè)字節(jié)的密鑰猜測準(zhǔn)確率達(dá)到95%,完整恢復(fù)密鑰的概率仍然只有44% 左右, 即使只錯(cuò)了一字節(jié), 也只能否定整個(gè)密鑰. 雖然有密鑰枚舉算法[18–20]可以利用CPA 產(chǎn)生的相關(guān)度序列對密鑰空間進(jìn)行有序遍歷, 但是其搜索空間仍是整個(gè)密鑰的范圍. 如果能利用能量波形本身的特征來縮小搜索范圍, 乃至判斷某個(gè)子密鑰猜測是否正確, 就可以極大地減小搜索空間, 甚至協(xié)助恢復(fù)密鑰.

在文獻(xiàn)[17] 的末尾, 作者提出了一種利用列混合處波形與對應(yīng)中間值的相關(guān)系數(shù)判斷密鑰猜測是否正確的思想, 但未說明判斷方法, 也未進(jìn)行嚴(yán)謹(jǐn)?shù)赜懻? 受此啟發(fā), 我們提出了在進(jìn)行標(biāo)準(zhǔn)CPA 之后, 利用列混合完成后的中間值與其對應(yīng)的波形點(diǎn)求相關(guān)系數(shù), 檢驗(yàn)其對應(yīng)的四字節(jié)密鑰恢復(fù)是否正確的后向檢錯(cuò)方案, 并依托此方案提出了一種基于閾值的四字節(jié)子密鑰猜測正確性判別方案, 以此構(gòu)建了一種能夠?qū)⑺膫€(gè)列混合分而治之, 四組子密鑰分別恢復(fù)的密鑰搜索方案. 經(jīng)實(shí)驗(yàn)驗(yàn)證, 即使在單字節(jié)密鑰猜測準(zhǔn)確度不佳的情況下, 也可以將成功恢復(fù)密鑰的概率提升至原先的兩倍以上, 且能與各種對CPA 的優(yōu)化方案無縫銜接.

本文余下部分的構(gòu)造如下: 第2 節(jié)是預(yù)備知識(shí), 主要介紹相關(guān)能量分析方法以及本文的分析對象: 世界上使用范圍最廣泛的分組密碼算法—AES; 第3 節(jié)分兩部分, 分別介紹了后向檢錯(cuò)的基本原理以及基于此實(shí)現(xiàn)的基于枚舉的后向檢錯(cuò)算法; 第4 節(jié)為實(shí)驗(yàn)部分, 驗(yàn)證了閾值的存在以及算法的有效性; 第5 節(jié)總結(jié)全文, 并對下一步工作進(jìn)行了一些展望.

2 預(yù)備知識(shí)

2.1 符號說明

lk密鑰長度(字節(jié))

lp明/密文長度(字節(jié))

np明/密文數(shù)量

nt能量波形條數(shù)

lt各波形采樣點(diǎn)數(shù)

k lk維行向量, 保存密鑰

P np×lp矩陣, 按行向量形式保存明文

C np×lp矩陣, 按行向量形式保存密文

T nt×lt矩陣, 按行向量形式保存采集到的能量波形

Y np×lp矩陣, 按行向量形式保存明文通過白化密鑰和字節(jié)代換之后的中間值

Z np×lp矩陣, 按行向量形式保存明文通過白化密鑰、字節(jié)代換、行移位和列混合之后的中間值

ps單個(gè)字節(jié)密鑰猜測準(zhǔn)確率

ρS矩陣Y 中列向量與T 中列向量求得的相關(guān)系數(shù)

ρMC矩陣Z 中列向量與T 中列向量求得的相關(guān)系數(shù)

KeyCand 256×lp矩陣, 保存相關(guān)能量分析得到的按相關(guān)系數(shù)降序排列的候選密鑰序列

Corr 256×lp矩陣, 保存與上述候選密鑰一一對應(yīng)的相關(guān)系數(shù)序列

2.2 高級加密標(biāo)準(zhǔn)

高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard, AES)[21,22], 是一種由Joan Daemen 和Vincent Rijmen 設(shè)計(jì)的分組密碼算法, 分組長度固定為128 比特, 密鑰長度則可以是128, 192 或256 比特. 自2001 年被美國國家標(biāo)準(zhǔn)技術(shù)研究院選定, 接替超期服役十?dāng)?shù)年的DES 算法成為新一代標(biāo)準(zhǔn)算法以來, 經(jīng)過近20 年的發(fā)展, AES 已然成為世界上使用范圍最廣的分組密碼算法. 小到智能卡中的密碼芯片, 大到國際互聯(lián)網(wǎng)中的安全套接字層協(xié)議, 只要是需要保護(hù)數(shù)據(jù)安全的地方, 就有AES 的身影.

AES 算法主要由密鑰擴(kuò)展和輪函數(shù)兩部分組成. 其中密鑰擴(kuò)展部分與本文工作關(guān)系不大, 以下主要介紹輪函數(shù)部分. 輪函數(shù)包含四個(gè)模塊:

字節(jié)代換(SubByte) 利用GF(28) 域上的求逆和仿射變換實(shí)現(xiàn)的非線性字節(jié)替換操作, 又名S 盒;行移位(ShiftRow) 將16 字節(jié)輸入視為4×4 矩陣, 對第i (0 ≤i<4) 行循環(huán)左移i 字節(jié);

列混合(MixColumn) 將16 字節(jié)輸入視為4×4 矩陣, 將各列左乘一個(gè)變換矩陣, 其中各元素的乘法和加法均在GF(28) 域上進(jìn)行;

異或輪密鑰(AddRoundKey) 將輸入與密鑰擴(kuò)展所產(chǎn)生的輪密鑰進(jìn)行異或.

以AES-128, 即密鑰長度128 字節(jié)的AES 算法為例, 其流程如圖1 所示, 可見整個(gè)算法由白化密鑰及十個(gè)依次執(zhí)行的輪函數(shù)組成, 其中第10 輪不包括列混合部分. 圖2 展示了隸屬于同一列混合的四個(gè)字節(jié)的明文在第1 輪輪函數(shù)中經(jīng)歷的各項(xiàng)操作. 圖中可見由于行移位操作的影響, 進(jìn)入列混合的四個(gè)S 盒輸出字節(jié)分別是y0、y5、y10和y15. 這四個(gè)字節(jié)經(jīng)歷了列混合之后, 將成為下一輪輸入的前四個(gè)字節(jié), 所以稱它們?yōu)閦0–z3. 中間值Y 和Z 將在后向檢錯(cuò)方案中扮演十分重要的作用.

圖1 AES-128 總體結(jié)構(gòu)Figure 1 AES-128 structure

圖2 第一輪細(xì)節(jié)Figure 2 Detail of first round

2.3 相關(guān)能量分析

相關(guān)能量分析[3]是側(cè)信道分析領(lǐng)域廣泛使用的經(jīng)典算法,自2004 年提出至今始終是業(yè)界公認(rèn)最為有效的側(cè)信道分析方法. 此法是一種特殊的選擇明文攻擊, 目標(biāo)一般是內(nèi)部正在執(zhí)行密碼算法程序的CPU,即由軟件實(shí)現(xiàn)的密碼算法, 或是由數(shù)字電路硬件實(shí)現(xiàn)密碼算法的集成電路芯片. 攻擊者一方面需要擁有目標(biāo)設(shè)備的訪問權(quán)限, 可構(gòu)造任意明文所對應(yīng)的密文, 另外還需要知曉目標(biāo)設(shè)備內(nèi)部使用的密碼算法類型,并需要能控制目標(biāo)設(shè)備的外圍電路, 以便采集其能量消耗. 基本思想是利用密碼算法執(zhí)行過程中產(chǎn)生的中間值與產(chǎn)生該值時(shí)的能量消耗的相關(guān)性來判斷密鑰猜測是否正確. 以下將以軟件實(shí)現(xiàn)的AES-128 算法為例進(jìn)行介紹, 此時(shí)lp= lk= 16, 中間值與能量消耗之間滿足漢明重量(Hamming Weight, HW) 模型, 即其能量消耗與中間值的漢明重量線性相關(guān).

2.4 密鑰枚舉方法

為了解決相關(guān)能量分析對側(cè)信息利用率較低, 一旦密鑰恢復(fù)失敗便無能為力的問題, 提高密鑰恢復(fù)的成功率,學(xué)界提出了多種方法[18–20],其中Veyrat-Charvillon 等人[18]提出的最優(yōu)密鑰枚舉算法(Optimal Key Enumeration Algorithm) 最為典型. 此法是一種基于分治思想的確定性算法, 利用相關(guān)能量分析產(chǎn)生的256×16 個(gè)密鑰的相關(guān)度序列, 將每字節(jié)對應(yīng)的256 個(gè)相關(guān)度值分別歸一化并降序排列之后, 分為八組, 組內(nèi)按照各密鑰候選值的相關(guān)度歸一化值, 將面積1×1 的正方形切分成256×256 份, 從面積最大的矩形開始, 按照同行、列有方格在邊界集中時(shí)，其他方格在此方格被搜索出隊(duì)前不重復(fù)入隊(duì)的原則構(gòu)建邊界集, 以此作為搜索序列. 再使用樹狀遞歸的方法, 依托兩個(gè)字節(jié)的邊界集, 依次構(gòu)建四字節(jié)、八字節(jié)和十六字節(jié)的邊界集以及搜索序列. 此方法巧妙地利用了相關(guān)能量分析的輸出值信息, 將各候選字節(jié)的相關(guān)度值轉(zhuǎn)化其恰為正確密鑰的概率, 并給出了科學(xué)的枚舉方案, 可有效降低找到密鑰所需的搜索空間.

3 后向檢錯(cuò)方案

在相關(guān)能量分析方法當(dāng)中, 檢驗(yàn)密鑰猜測是否正確的方案只有一種, 即利用猜測的密鑰對任意明文進(jìn)行一次加密, 或者對任意密文進(jìn)行一次解密, 觀察其結(jié)果是否與正確密/明文相等. 顯然, 此法的最大弊端就是必須在密鑰完全恢復(fù)正確的情況下才能判定其正確性, 而就算密鑰只有一字節(jié)出現(xiàn)錯(cuò)誤, 其加密結(jié)果也必然是錯(cuò)誤的, 而且攻擊者無從確定錯(cuò)誤的字節(jié)是哪一個(gè), 只能對整個(gè)密鑰空間進(jìn)行搜索. 雖然有密鑰枚舉等方式進(jìn)行協(xié)助, 但是如果有方法能推測出錯(cuò)誤密鑰的出現(xiàn)位置, 縮小搜索范圍, 無疑可以大幅提升效率. 后向檢錯(cuò)方案的設(shè)計(jì)目的正是完成這一任務(wù).

3.1 后向檢錯(cuò)方案的基本原理

如圖2 所示, 在通過各個(gè)S 盒之后, 各中間值的下一站是列混合. 圖中可見輸入列混合的四個(gè)字節(jié)都參與到了每個(gè)輸出字節(jié)的運(yùn)算當(dāng)中, 也就意味著只要有一個(gè)字節(jié)的密鑰猜錯(cuò)了, 此處的所有字節(jié)都會(huì)受到影響. 而列混合運(yùn)算也是要消耗能量的, 它的輸出值的漢明重量也會(huì)反映在能量波形上, 也能與波形各列計(jì)算相關(guān)系數(shù). 當(dāng)密鑰猜錯(cuò)時(shí), 此相關(guān)度同樣會(huì)比密鑰猜對時(shí)更低. 以下稱此相關(guān)度為ρMC. 那么, 應(yīng)當(dāng)如何利用此特性來縮小密鑰搜索范圍？探究這一問題之前, 我們可以先對錯(cuò)誤本身的特性進(jìn)行一些分析.

設(shè)單字節(jié)密鑰猜測正確率為ps, 則根據(jù)二項(xiàng)分布原理可求出完整猜中密鑰以及出現(xiàn)錯(cuò)誤字節(jié)的概率.表1 展示了在單字節(jié)正確率為某值時(shí), 出現(xiàn)某數(shù)量錯(cuò)誤字節(jié)的可能性. 表中最后一列包括所有單字節(jié)錯(cuò)誤以及出現(xiàn)兩字節(jié)、三字節(jié)和四字節(jié)錯(cuò)誤時(shí), 錯(cuò)誤字節(jié)落在同一列混合中的情況. 可見就算單字節(jié)恢復(fù)正確率達(dá)到95%, 完整恢復(fù)密鑰的概率也僅有44%. 但是在此情況下, 錯(cuò)誤出現(xiàn)在同一列混合中的概率, 已經(jīng)達(dá)到了40%. 而當(dāng)密鑰恢復(fù)正確率進(jìn)一步提高到97% 時(shí), 可以發(fā)現(xiàn)就算只能恢復(fù)發(fā)生在同一個(gè)列混合中的錯(cuò)誤密鑰, 也能將總的密鑰恢復(fù)成功率提高到61.43%+31.84% = 93.27%, 這無疑是一個(gè)很大的進(jìn)步. 所以, 當(dāng)單字節(jié)密鑰猜測準(zhǔn)確率較高時(shí), 我們可以使用一種簡單方法恢復(fù)大多數(shù)的密鑰. 具體流程如算法1 所示.

表1 密鑰錯(cuò)誤字節(jié)數(shù)及其發(fā)生概率Table 1 Probability of number of wrong bytes

此方案可以確保當(dāng)錯(cuò)誤密鑰確實(shí)只出現(xiàn)在一個(gè)列混合當(dāng)中時(shí), 攻擊者可以準(zhǔn)確找到此列混合, 并利用窮搜的方式恢復(fù)此密鑰. 由于現(xiàn)代電腦計(jì)算能力的增強(qiáng), 窮搜AES 的232密鑰空間已不再是一個(gè)難以完成的任務(wù), 即使在個(gè)人電腦上也只需要不到一小時(shí)即可完成. 但是, 只要錯(cuò)誤字節(jié)分布在不同的列混合中,此法就斷無可能恢復(fù)密鑰. 為了解決此類同樣常見的情況, 光靠現(xiàn)有的判斷密鑰恢復(fù)正確性的手段已經(jīng)無法完成了, 我們需要更好的辦法.

3.2 基于枚舉的后向檢錯(cuò)方案

如上所述, 簡單后向檢錯(cuò)方案僅能在ps≥95% 的情況下使用. 即使是ps的一點(diǎn)微小下降也會(huì)導(dǎo)致其成功率的暴跌. 其主要原因是此法仍然使用了利用加/解密結(jié)果正確性判斷密鑰猜測正確性的判別方式, 僅僅只是把容許的錯(cuò)誤比特?cái)?shù)量從零擴(kuò)展到了同一列混合內(nèi)的四字節(jié)而已. 如果有一種手段能夠?qū)⒄_和錯(cuò)誤的列區(qū)分開的話, 就可以將標(biāo)準(zhǔn)CPA 中的分而治之思維運(yùn)用到此處, 將四個(gè)列混合對應(yīng)的密鑰分別進(jìn)行恢復(fù). 實(shí)驗(yàn)發(fā)現(xiàn), 可以采用閾值作為區(qū)分二者的標(biāo)準(zhǔn). 另外, 為了提高搜索的效率, 我們利用文獻(xiàn)[18] 中的密鑰枚舉算法, 對各列混合對應(yīng)的四字節(jié)密鑰進(jìn)行枚舉. 以下將分別介紹以上方法, 并將其組合成能對分散在多個(gè)列混合中的錯(cuò)誤字節(jié)進(jìn)行恢復(fù)的基于枚舉的后向檢錯(cuò)方案.

3.2.1 錯(cuò)誤列判別

為了確定哪些列包含錯(cuò)誤的字節(jié), 攻擊者需要確定一個(gè)閾值以區(qū)分正確和錯(cuò)誤的密鑰. 閾值可以通過觀察簡單算法中獲得的各ρMC值進(jìn)行估計(jì). 在ps較高時(shí), 出現(xiàn)四個(gè)列混合全有錯(cuò)的情況是極少的, 所以多數(shù)時(shí)候可以通過觀察其最大值和最小值之間的差距來估計(jì)閾值的位置, 并且可以在恢復(fù)密鑰過程中靈活調(diào)節(jié). 如果四個(gè)列混合中只有一個(gè)列的ρMC值低于閾值, 則可以認(rèn)為錯(cuò)誤的密鑰位于與該列混合相對應(yīng)的四個(gè)字節(jié)中, 并且可以通過算法1 來恢復(fù)該密鑰. 如果大于兩個(gè), 則通過加密結(jié)果判斷密鑰是否正確的方法將不再有效, 這時(shí)才需要利用基于枚舉的方案.

3.2.2 密鑰猜測正確性判別

如圖2 所示, 列混合的計(jì)算僅與其對應(yīng)的四字節(jié)密鑰有關(guān). 所以攻擊者只需要猜測這幾個(gè)密鑰字節(jié),就能獲得列混合的中間結(jié)果, 而與其他密鑰字節(jié)無關(guān). 基于此種獨(dú)立性, 上述閾值可用于估計(jì)猜測值的正確性, 即如果相應(yīng)的ρMC高于閾值, 則此組密鑰字節(jié)很可能是完全正確的. 但是, 以上思路有兩點(diǎn)不足.首先, 一一計(jì)算所有232個(gè)ρMC顯然是不可行的, 因?yàn)椴ㄐ螚l數(shù)較多時(shí), 相關(guān)系數(shù)的計(jì)算遠(yuǎn)比AES 算法本身更耗時(shí); 第二, 既然恢復(fù)單個(gè)字節(jié)密鑰時(shí)存在錯(cuò)誤密鑰的相關(guān)度高于正確密鑰的情況, 那么類似的錯(cuò)誤在此同樣可能出現(xiàn). 為解決上述兩點(diǎn)不足, 我們采取了以下方法: 1、合理地安排候選密鑰的順序, 將具有較高正確概率的密鑰字節(jié)先行猜測, 以提高搜索效率, 這即是密鑰枚舉算法的任務(wù); 2、在枚舉子密鑰時(shí),保存一些使列混合相關(guān)度超過閾值的子密鑰, 形成候選子密鑰集合, 枚舉完畢后將各列混合對應(yīng)的候選子密鑰進(jìn)行排列組合, 以此來提高找到正確密鑰的概率.

算法2 的基于枚舉的后向檢錯(cuò)方案Input:波形矩陣T;明文矩陣P;密文矩陣C;候選密鑰矩陣KeyCand;與候選密鑰一一對應(yīng)的相關(guān)系數(shù)矩陣Corr;子密鑰枚舉個(gè)數(shù)上限max_keynum;保存候選子密鑰個(gè)數(shù)上限max_subkey;相關(guān)度閾值threshold;Output:新的最佳密鑰kg′best;表示輸出密鑰是否正確的布爾量Succ;1 利用算法1 的步驟5–6 獲取向量ρMC;2 Ind_BelowT = {使ρMC i < threshold的所有i值,0 ≤i < 4};3 if size(Ind_BelowT) ≤1 then 4 使用算法1 來求解kg′best 和Succ;5 else 6 建立列混合候選子密鑰緩存矩陣SubkeyCache = {SubkeyCache0,SubkeyCache1,SubkeyCache2,SubkeyCache3}, 其中每個(gè)元素都是最大容量為max_subkey×4 字節(jié)的矩陣, 對應(yīng)四個(gè)列混合;7 for Ind_BelowT 中的任一元素ind do 8 IndKey = {ind×4,(ind×4+5) mod 16,(ind×4+10) mod 16,(ind×4+15) mod 16};按照IndKey 中的值提取KeyCand 和Corr 的對應(yīng)列, 輸入2.4 節(jié)所述的最優(yōu)密鑰枚舉算法來獲得max_keynum×4 字節(jié)的密鑰搜索序列矩陣Ks;10 for Ks 中的任一行向量ks do 9 11 利用此四字節(jié)密鑰計(jì)算ρMC ks ;12 if SubkeyCacheind.size < max_subkey then 13 if ρMC ks > threshold then 14 將ks 寫入SubkeyCacheind;15 end 16 else 17 break;18 end 19 end 20 end 21 Succ = false;22 將正確的列混合對應(yīng)的子密鑰填入SubkeyCache 中的相應(yīng)矩陣;23 while SubkeyCache 中仍有未嘗試的子密鑰組合&& Succ! = true do 24 取下一組合, 填入kg′best;25 Succ = (AES(p0,kg′best) == c0);26 end 27 end

3.2.3 密鑰枚舉

如2.4 節(jié)所述, 文獻(xiàn)[18] 中給出的密鑰枚舉算法是自下而上構(gòu)建搜索序列的, 也就是說此法不僅可以搜索完整的16 字節(jié)密鑰, 對4 字節(jié)的子密鑰也可使用. 我們只要提供相應(yīng)字節(jié)對應(yīng)的候選值-相關(guān)度序列, 就可以讓算法按正確率從高到低的順序輸出密鑰, 提供給上述正確性判別函數(shù).

3.2.4 基于枚舉的方案

有了以上基礎(chǔ), 就可以方便地建立起能夠分別恢復(fù)各個(gè)列混合密鑰的基于枚舉的后向檢錯(cuò)方案了, 其具體流程如算法2 所示. 需要說明的是, 雖然我們?nèi)匀恍枰獙Ω髁谢旌系暮蜻x子密鑰集合進(jìn)行排列組合,但是經(jīng)過密鑰正確性判別篩選之后, 我們只需保留10 到20 個(gè)候選值, 便可以較高的概率搜索到正確密鑰, 其組合數(shù)目上限為105左右, 需要進(jìn)行的計(jì)算量很小. 下文中我們以實(shí)驗(yàn)對算法的有消息進(jìn)行了驗(yàn)證.

4 實(shí)驗(yàn)與對比

為了驗(yàn)證上述算法的有效性, 我們基于數(shù)緣科技的側(cè)信道分析教學(xué)科研實(shí)驗(yàn)套件中的STC89C52 單片機(jī)、側(cè)信道分析測評套件中的8 位和32 位CPU 智能卡三種場景進(jìn)行了實(shí)驗(yàn). 在以上三種設(shè)備之內(nèi),我們按照其設(shè)備特點(diǎn)分別實(shí)現(xiàn)了AES-128 程序, 主要差別是32 位卡中的列混合操作是利用32 位寄存器按列完成的, 即類似圖2 中表現(xiàn)的那樣, 而8 位卡和8051 單片機(jī)中的類似操作只能按字節(jié)完成. 這也就意味著在32 位卡上, 一個(gè)列混合對應(yīng)的中間值是一個(gè)32 比特整數(shù), 而在8 位卡和單片機(jī)上, 一個(gè)列混合對應(yīng)四個(gè)8 比特整數(shù), 二者不再對等. 考慮到如果密鑰出錯(cuò), 這四個(gè)字節(jié)的相關(guān)度都將下降, 所以我們采取的方法是直接將四個(gè)值的相關(guān)系數(shù)取平均值. 實(shí)驗(yàn)證明此法效果良好. 為確保實(shí)驗(yàn)的準(zhǔn)確性, 我們在三種設(shè)備上均采集了5000 條固定密鑰和隨機(jī)明文, 包括整個(gè)第一輪的能量波形, 每次測試都隨機(jī)從中抽取一定數(shù)量的波形來進(jìn)行實(shí)驗(yàn). 以下所有提到波形數(shù)量之處, 其波形均是如此抽取出來的.

4.1 閾值存在性檢驗(yàn)

首先需要驗(yàn)證的是閾值是否存在. 此測試需要控制好參數(shù), 使得各設(shè)備上的單個(gè)字節(jié)的猜測準(zhǔn)確率ps基本相等. 在此測試中, 我們選擇的ps值是0.9 左右. 為此, 我們將使用以下參數(shù)進(jìn)行實(shí)驗(yàn): 對于單片機(jī),由于其電路集成度低, 功耗高, 能量泄露十分明顯, 所以我們抽取13 條波即可達(dá)到此正確率; 對8 位卡,需要45 條波; 對32 位卡, 合適的波形數(shù)量則是50. 由于我們知道密鑰, 所以可以在顯示列混合相關(guān)度時(shí)標(biāo)示出正確和錯(cuò)誤的列混合. 測試效果如圖3 所示.

圖3 三種設(shè)備對應(yīng)能量波形的ρMC 分析Figure 3 ρMC analysis for power traces of three devices

“O” 形表示此列混合對應(yīng)的子密鑰完全正確, “X” 形反之, 各點(diǎn)的橫坐標(biāo)表示某一次測試時(shí)該列混合中間值與對應(yīng)波形點(diǎn)的相關(guān)系數(shù), 縱坐標(biāo)為列混合編號, 圖中豎向虛線標(biāo)示了閾值. 根據(jù)之前的分析, 我們應(yīng)當(dāng)觀察到絕大多數(shù)“O” 形點(diǎn)落在閾值右側(cè)而絕大多數(shù)“X” 形點(diǎn)落在其左側(cè), 二者之間存在明顯的分界.

圖中可見, 雖然列混合之間有一定差異, 但是仍然只有極少數(shù)相關(guān)系數(shù)由于噪聲的干擾而越過閾值,絕大多數(shù)相關(guān)系數(shù)值都落在了符合上述假設(shè)的位置上. 由此可見對三種實(shí)驗(yàn)設(shè)備而言, 列混合相關(guān)度的閾值均是存在的.

4.2 后向檢錯(cuò)方案的效率對比

圖4、5、6 展示了標(biāo)準(zhǔn)CPA、簡單后向檢錯(cuò)算法、枚舉個(gè)數(shù)上限為216個(gè)的最優(yōu)密鑰枚舉算法以及子密鑰枚舉個(gè)數(shù)上限為212個(gè)、候選子密鑰上限為20 個(gè)的基于枚舉的后向檢錯(cuò)算法四種方案在各設(shè)備上的密鑰恢復(fù)成功率, 另外列出了各點(diǎn)的單字節(jié)密鑰猜測成功率ps作為參考. 圖中橫坐標(biāo)為波形條數(shù), 縱坐標(biāo)對應(yīng)1000 次實(shí)驗(yàn)的成功率. 其中單片機(jī)由于信噪比較高, 為確保其ps與智能卡大致相當(dāng), 故而使用的波形條數(shù)也相對較少. 值得注意的是, 由于基于枚舉的后向檢錯(cuò)方案存在候選子密鑰排列組合的步驟, 所以我們采用了降低其子密鑰枚舉個(gè)數(shù)上限的方式來盡可能平衡復(fù)雜度差異.

圖4 32 位智能卡波形的成功率對比Figure 4 Comparison of success rate of 32-bit smart card power traces

圖5 8 位智能卡波形的成功率對比Figure 5 Comparison of success rate of 8-bit smart card power traces

圖6 單片機(jī)波形的成功率對比Figure 6 Comparison of success rate of MCU power traces

圖中可見, 不論在什么樣的設(shè)備上, 簡單后向檢錯(cuò)和基于枚舉的后向檢錯(cuò)方案均比標(biāo)準(zhǔn)CPA 在成功率方面有顯著提升, 而基于枚舉的后向檢錯(cuò)方案的成功率又比最優(yōu)密鑰枚舉算法高出許多. 尤其是在ps低于80%的情況下, 此時(shí)就算使用密鑰枚舉算法也很難恢復(fù)密鑰了, 而基于枚舉的后向檢錯(cuò)方案卻仍能保持兩倍以上的成功率, 這使得達(dá)到75% 成功率所需的能量波形減少了30% 到40%. 以上事實(shí)均說明基于枚舉的后向檢錯(cuò)方案確實(shí)起到了成功恢復(fù)多個(gè)列混合內(nèi)的錯(cuò)誤密鑰字節(jié)的作用.

在時(shí)間方面, 基于枚舉的后向檢錯(cuò)方案由于需要進(jìn)行較多的列混合計(jì)算, 所以必然比傳統(tǒng)的最優(yōu)密鑰枚舉算法要慢得多. 實(shí)驗(yàn)中的表現(xiàn)也確實(shí)如此, 在單字節(jié)正確率較低時(shí), 最優(yōu)密鑰枚舉算法完成搜索的平均時(shí)間約為0.021 秒, 而本方法則需要0.29 到0.95 秒, 視出錯(cuò)列混合數(shù)量而定, 從時(shí)間消耗上看確實(shí)差距較大. 但是側(cè)信道分析主要的瓶頸出現(xiàn)在波形采集一端, 由于目標(biāo)設(shè)備的訪問控制、實(shí)際情況限制等諸多原因, 采集足量能量波形的任務(wù)不一定能夠如期完成, 而只要得到了能量波形, 后續(xù)的分析工作完全可以不受干擾地進(jìn)行, 時(shí)間方面并不存在瓶頸. 所以減少能量波形的使用量一般被視為側(cè)信道分析方法優(yōu)化的主要目標(biāo), 在這一點(diǎn)上本方案完全是合格的.

4.3 后向檢錯(cuò)方案的適用范圍

到目前為止的所有理論分析與實(shí)驗(yàn)均是以AES 算法為目標(biāo)進(jìn)行的, 但是由于現(xiàn)代分組密碼算法結(jié)構(gòu)的相似性, 利用攻擊點(diǎn)之后的能量波形信息對密鑰猜測值的正確性進(jìn)行檢驗(yàn)這一思路完全可以用在其他分組密碼算法上. 以SM4 算法[23]為例, 此算法的輪函數(shù)中同樣具有四個(gè)并列的8 比特S 盒以及以循環(huán)左移和異或組成的線性運(yùn)算L(x)= x ⊕(x ?2)⊕(x ?10)⊕(x ?18)⊕(x ?24), 其中x 為位寬32比特的S 盒輸出值. 此二者的組成恰與AES 中S 盒與列混合相對應(yīng), 所以我們的方法可以直接套用至軟件實(shí)現(xiàn)的SM4 算法的側(cè)信道分析中. 由于S 盒的位寬都是相同的, 所以連最優(yōu)密鑰枚舉算法也可直接使用.

對其他分組密碼算法也可用類似的方式進(jìn)行處理, 只是可能需要調(diào)整密鑰枚舉算法而已. 如軟件實(shí)現(xiàn)的DES 算法[24], 我們利用CPA 恢復(fù)首輪的子密鑰后, 可以在本輪的P 置換、輪函數(shù)輸出與明文的異或運(yùn)算以及第二輪的E 置換等處進(jìn)行后向檢錯(cuò), 由于DES 的位寬窄, 子密鑰僅48 比特, 所以在執(zhí)行后向檢錯(cuò)時(shí)無需分治法也能達(dá)到比較好的效果.

5 結(jié)論

本文通過利用列混合處波形與中間值的線性相關(guān)關(guān)系, 設(shè)計(jì)了一種在相關(guān)能量分析完成后進(jìn)行的后向檢錯(cuò)方案, 能夠在相關(guān)能量分析沒能恢復(fù)密鑰時(shí), 尋找可能出錯(cuò)字節(jié)所對在的列混合, 縮小錯(cuò)誤密鑰字節(jié)的搜索范圍, 最終對錯(cuò)誤密鑰進(jìn)行修正. 方法是通過計(jì)算當(dāng)前密鑰猜測的列混合輸出與能量波形的相關(guān)度,觀察其是否越過閾值, 以此判斷單個(gè)列混合對應(yīng)的四字節(jié)子密鑰猜測正確性, 再分別對各錯(cuò)誤的列混合對應(yīng)的四字節(jié)密鑰分別進(jìn)行搜索, 通過計(jì)算候選密鑰產(chǎn)生的列混合輸出與波形的相關(guān)性是否越過閾值來判斷其正確性, 以此對各個(gè)出錯(cuò)的列混合分別進(jìn)行修正, 而無需在完整恢復(fù)密鑰之后才能得知其正確性. 另外,為了提高密鑰搜索效率, 我們使用文獻(xiàn)[18] 中的最優(yōu)密鑰枚舉方法對單個(gè)列混合對應(yīng)的四字節(jié)子密鑰進(jìn)行搜索, 提高了在232密鑰空間中進(jìn)行密鑰搜索的效率. 上述方法極大地提高了密鑰恢復(fù)成功率, 與最優(yōu)密鑰枚舉方案相比, 在復(fù)雜度近似的情況下達(dá)到相同密鑰恢復(fù)成功率時(shí)的能量波形使用量減小了30% 以上. 且適用于多種分組密碼算法. 未來我們計(jì)劃尋找更準(zhǔn)確的區(qū)分正確與錯(cuò)誤密鑰候選值的方法, 使用能量波形中提供的更多信息, 以期找到更多有效的側(cè)信道分析方法.