相關能量分析中的后向檢錯方案*

司恩澤, 王 安, 祝烈煌, 丁瑤玲, 陳財森, 丁詩軍

1. 北京理工大學 計算機學院, 北京100081

2. 密碼科學技術國家重點實驗室, 北京100878

3. 陸軍裝甲兵學院演訓中心, 北京100072

1 引言

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

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

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

在文獻[17] 的末尾, 作者提出了一種利用列混合處波形與對應中間值的相關系數判斷密鑰猜測是否正確的思想, 但未說明判斷方法, 也未進行嚴謹地討論. 受此啟發, 我們提出了在進行標準CPA 之后, 利用列混合完成后的中間值與其對應的波形點求相關系數, 檢驗其對應的四字節密鑰恢復是否正確的后向檢錯方案, 并依托此方案提出了一種基于閾值的四字節子密鑰猜測正確性判別方案, 以此構建了一種能夠將四個列混合分而治之, 四組子密鑰分別恢復的密鑰搜索方案. 經實驗驗證, 即使在單字節密鑰猜測準確度不佳的情況下, 也可以將成功恢復密鑰的概率提升至原先的兩倍以上, 且能與各種對CPA 的優化方案無縫銜接.

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

2 預備知識

2.1 符號說明

lk密鑰長度(字節)

lp明/密文長度(字節)

np明/密文數量

nt能量波形條數

lt各波形采樣點數

k lk維行向量, 保存密鑰

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

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

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

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

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

ps單個字節密鑰猜測準確率

ρS矩陣Y 中列向量與T 中列向量求得的相關系數

ρMC矩陣Z 中列向量與T 中列向量求得的相關系數

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

Corr 256×lp矩陣, 保存與上述候選密鑰一一對應的相關系數序列

2.2 高級加密標準

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

AES 算法主要由密鑰擴展和輪函數兩部分組成. 其中密鑰擴展部分與本文工作關系不大, 以下主要介紹輪函數部分. 輪函數包含四個模塊:

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

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

異或輪密鑰(AddRoundKey) 將輸入與密鑰擴展所產生的輪密鑰進行異或.

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

圖1 AES-128 總體結構Figure 1 AES-128 structure

圖2 第一輪細節Figure 2 Detail of first round

2.3 相關能量分析

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

2.4 密鑰枚舉方法

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

3 后向檢錯方案

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

3.1 后向檢錯方案的基本原理

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

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

表1 密鑰錯誤字節數及其發生概率Table 1 Probability of number of wrong bytes

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

3.2 基于枚舉的后向檢錯方案

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

3.2.1 錯誤列判別

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

3.2.2 密鑰猜測正確性判別

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

算法2 的基于枚舉的后向檢錯方案Input:波形矩陣T;明文矩陣P;密文矩陣C;候選密鑰矩陣KeyCand;與候選密鑰一一對應的相關系數矩陣Corr;子密鑰枚舉個數上限max_keynum;保存候選子密鑰個數上限max_subkey;相關度閾值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}, 其中每個元素都是最大容量為max_subkey×4 字節的矩陣, 對應四個列混合;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 的對應列, 輸入2.4 節所述的最優密鑰枚舉算法來獲得max_keynum×4 字節的密鑰搜索序列矩陣Ks;10 for Ks 中的任一行向量ks do 9 11 利用此四字節密鑰計算ρ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 將正確的列混合對應的子密鑰填入SubkeyCache 中的相應矩陣;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 節所述, 文獻[18] 中給出的密鑰枚舉算法是自下而上構建搜索序列的, 也就是說此法不僅可以搜索完整的16 字節密鑰, 對4 字節的子密鑰也可使用. 我們只要提供相應字節對應的候選值-相關度序列, 就可以讓算法按正確率從高到低的順序輸出密鑰, 提供給上述正確性判別函數.

3.2.4 基于枚舉的方案

有了以上基礎, 就可以方便地建立起能夠分別恢復各個列混合密鑰的基于枚舉的后向檢錯方案了, 其具體流程如算法2 所示. 需要說明的是, 雖然我們仍然需要對各列混合的候選子密鑰集合進行排列組合,但是經過密鑰正確性判別篩選之后, 我們只需保留10 到20 個候選值, 便可以較高的概率搜索到正確密鑰, 其組合數目上限為105左右, 需要進行的計算量很小. 下文中我們以實驗對算法的有消息進行了驗證.

4 實驗與對比

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

4.1 閾值存在性檢驗

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

圖3 三種設備對應能量波形的ρMC 分析Figure 3 ρMC analysis for power traces of three devices

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

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

4.2 后向檢錯方案的效率對比

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

圖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 單片機波形的成功率對比Figure 6 Comparison of success rate of MCU power traces

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

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

4.3 后向檢錯方案的適用范圍

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

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

5 結論

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