分組密碼故障攻擊效率分析方法研究*

朱仁杰，楊 鵬，鄭 輝，陳保亮

（1.海軍工程大學 信息安全系，湖北 武漢 430000；2.中國人民解放軍31677部隊，河北 保定 071000；

3.海軍工程大學 電子工程學院，湖北 武漢 430000）

0 引 言

故障攻擊可以被攻擊者主動實施，根據需要對密碼算法注入故障，獲取故障泄露信息，提高了分析算法密鑰的可能性，降低了計算復雜度，對密碼應用造成了嚴重的安全威脅[1-6]。故障的安全威脅是密碼應用領域需要長期面對的問題[7-10]。文獻[11]主要以信息論的角度對故障攻擊的能力進行研究。本文通過研究分析故障攻擊能力評估方法，進而揭示密碼芯片面臨故障攻擊威脅程度。

本文深入分析了分組密碼算法故障攻擊特點，提出了一種描述故障攻擊的一般方法。確定故障攻擊中的關鍵要素，并通過對比故障攻擊中的關鍵要素實現對故障攻擊的評估。通過分析將不同的故障攻擊納入到統一的框架體系內，實現通用工具分析處理不同的故障攻擊。

1 故障攻擊特點分析

1.1 AES算法簡介

本文以高級加密標準（Advanced Encryption Standard，AES[12]）為對象，研究故障攻擊能力的評估方法。在本文中，明文記為P，密文記為C，密鑰記為K。

AES密碼算法是由美國國家標準與技術研究所（National Institute of Standards and Technology，NIST）制定的分組密碼算法加密標準。本文中以128位密鑰版本的AES算法為研究對象。

Kr是第r輪的輪密鑰。加密操作首先將128位的明文分組轉換為2維的16字節狀態矩陣，與輪密鑰K0進行異或運算后，進行 10輪函數加密操作。每一輪的加密操作包括以下步驟：

字節替換（SubBytes，SB），非線性變換，由16個S盒組成，每一個S盒獨立進行替換操作，記為SB。

行移為（ShiftRows，SR），狀態矩陣每行單獨進行字節移位操作，記為SR。

列混合（MixColums，MC），狀態矩陣每一列進行線性混合操作，記為MC。

輪密鑰加（AddRoundKey，ARK），狀態矩陣與輪密鑰Kr,r∈[0,10]進行按位的⊕操作。

1.2 故障攻擊特點分析

故障攻擊通過干擾電路，改變算法的正確加密操作，使其輸出錯誤的密文。故障的注入方法有很多，例如：激光、時鐘故障、電源尖峰或電磁擾動等。

故障攻擊的目標是密碼算法的密鑰K，通過反推算法中間狀態，與故障模型進行匹配獲取秘密信息。現有的故障攻擊方法主要有差分故障攻擊（Different Fault Attack，DFA[13-16]）、故障敏感度分析（Fault Sensitive Analyze，FSA[17]）、差分故障強度分析（Different Fault Intensity Analyze，DFIA[18]）等。對分組密碼的故障攻擊可描述為以下三步。

第一步：故障泄露信息獲取。

在密碼芯片有未知密鑰K對隨機明文P進行加密操作過程中，進行故障注入，獲取觀測信息O和故障特征T。典型的觀測信息O有：明文、正確密文、故障密文、故障注入強度等。故障特征T則由故障模型所確定。對于不同的故障攻擊方法，需要獲取的觀測信息不同，故障特征也不同。

例如，DFA中觀測信息為

其中，C為任意明文P經未知密鑰K加密得到的正確密文，C′是在明文和密鑰相同的情況下，故障干擾的密文輸出結果。

攻擊者需要找到一條攻擊路徑。攻擊路徑是觀測信息O，故障特征T與算法密鑰K之間的連接關系，記為R。輸入是O和K，輸出是故障特征T。

其中，gi是分組密碼算法中的加密函數。以AES為例，gi∈{SB-1,SR-1,MC-1,ARK-1}。f由攻擊方式確定。

第二步：故障特征推測。

利用第一步中獲取的信息，結合密碼算法結構和故障注入模型，以及候選密鑰，反推中間狀態數據，推測故障特征。

式中，Kg是猜測密鑰，Tp是由觀測信息O、Kg根據攻擊路徑R推測出的故障特征。其中，Kg與R是未知的。為了推測中間故障特征，攻擊者在所有可能密鑰范圍內選取猜測密鑰Kg。攻擊必需采用分而治之的策略，保證攻擊目標K足夠短，確保可以測試所有可能的猜測密鑰。

例如在對AES開展的攻擊中，攻擊目標是輪密鑰Kr的一個字節，則K=[0,255]，可能的猜測密鑰有256個。

第三步：關聯度匹配。

在上一步中，所有的猜測密鑰經過故障特征推測，會得到一個Tp值，只有在猜測密鑰正確，關系R正確的情況下，推測出來的中間故障狀態Tp符合第一步中的故障特征T。

關聯度匹配目的是將正確密鑰和錯誤密鑰區分開，將第一步中獲取的故障模型與第二步中反推得到的中間秘密數據進行比較，區分出正確的密鑰。

以上三步過程是所有故障攻擊所遵循的基本過程。有些故障攻擊首先恢復出部分信息，不能一次直接恢復出全部的密鑰信息，在這種情況下，需要重復進行上述三步過程。在重復的過程中可能需要不同的觀測信息和故障特征等。

2 故障攻擊效率分析研究

目前，已發布的故障攻擊分析方法有很多種，然而絕大部分的故障攻擊方法都是從經典的攻擊方法中衍變而來。在本節的內容中，我們主要介紹并分析差分故障分析（DFA）、故障敏感度分析（FSA）和差分故障強度分析（DFIA）三種故障攻擊分析方法。并分析比較三種故障攻擊分析方法在不同情況下的攻擊效率。

2.1 差分故障分析（DFA）

1997年，Biham和Sharmir首次提出了針對DES分組密碼算法的差分故障攻擊概念。隨后，差分故障分析方法又經過了不斷的發展衍變。

在此例中，攻擊的目標是第十輪密鑰的四個字節，k=k10。k10存在256個可能值。攻擊者在第8輪字節代換（SB）操作之間注入單字節故障，故障特征T為下圖紅色標注狀態矩陣。

第一步：獲取信息是密文對O=(C,C′)。

第二步：反推得到中間狀態。R=R1⊕R2，其中R1=SB-1○SR-1○⊕，R2=SB-1○SR-1○⊕。

則中間故障狀態為Tp=R(O)=R1(C)⊕R2(C′)。

第三步：故障狀態匹配。不滿足式mat(Tp,T)的候選密鑰Kg為錯誤密鑰。

攻擊者探索最后一輪密鑰k1,k8,k11,k14四個字節時，T為：

由Kg反推得到的Tp若不滿足上式T，Kg即為錯誤密鑰。

單次故障的計算復雜度為216，剩余密鑰空間為232。Michael Tunstall提出了利用第9輪密鑰與第10輪密鑰之間的關系，再進行復雜度為216的計算，可將剩余密鑰空間降為212。

已公布的DFA分析方法有很多種，從第6輪到第10輪都存在DFA的故障攻擊方法。各種攻擊方法所需的故障注入數量和計算復雜度各有不同。

2.2 故障敏感度分析（FSA）

故障敏感度分析（FSA）攻擊由Yang Li等人在2010年的Cryptographic Hardware and Embedded Systems上提出。該分析方法主要依賴于密碼芯片故障敏感度的數據依賴性。注入故障能引起密碼狀態產生故障與密碼狀態的漢明重量有關系。

第一步：獲取信息為若干明文和錯誤密文對，O=(P,C)。通過逐漸增強故障注入強度，直到加密出現故障，記錄此時的故障敏感度FC。根據故障敏感度的數據依賴性，得到中間狀態的漢明重量，記為故障特征T。

第二步：反推中間故障狀態。

R=HW○SB-1○SR-1○⊕，Tp=R(O)=HW○SB-1○SR-1○ (C⊕Kg)利用密文C和候選密鑰計算出中間狀態值I的漢明重量Tp=HW(I)。

第 三 步：mat(Tp,T)。Cor(Kg)=ρ(T,Tp)，計 算Tp和T之間的皮爾遜相關系數，相關系數最大的Tp對應的候選密鑰為正確密鑰。

當攻擊者可以在第10輪輸入狀態選取字節進行故障注入時，需要對50組明文進行故障注入可以恢復全部密鑰信息。計算復雜度為212。

2.3 差分故障強度分析（DFIA）

差分故障強度分析是由Ghalaty提出的。當故障注入強度調整較小時，中間故障狀態也會隨之產生較小的改變，DFIA就是根據這種特性對密碼芯片進行攻擊。該攻擊的方法步驟如下：

第一步：在AES第9輪輸出位置注入逐漸增加強度的故障，觀測信息為O=(q,C′q)。q為故障注入強度和C′q為相應的故障密文。

第二步：利用故障密文和候選密鑰反推第9輪輸出狀態矩陣。S′q=SB-1○SR-1○(C′q⊕Kg)

第三步：對所有的猜測密鑰Kg，計算下式結果。

值最小的ρKg對應的密鑰即為正確密鑰。

DFIA攻擊的成功實施，主要依賴于隨著故障強度逐漸增加，中間狀態的故障比特位隨之增加。因此在攻擊開始前，需要掌握故障注入強度與產生故障類型的對應關系。

在最理想的條件下，攻擊者可以精確的故障注入，通過控制故障注入強度，使第10輪的輸入狀態的單字節分別產生1、2、3位比特故障。在這種情況下，48次故障注入可恢復完整的第10輪密鑰，計算復雜度為212。

當攻擊者無法精確控制注入故障位數時，通過逐漸增加故障注入強度，目標狀態在故障強度達到故障敏感點時產生故障。在這種情況下，平均需要對90組明文進行90次故障注入可恢復完整的第10輪密鑰，計算復雜度約為214.5。

當攻擊者不能控制故障注入的字節時，需要進行約2000次故障注入可恢復完整的第10輪密鑰，計算復雜度約為240。

2.4 攻擊效率分析

在本節中，分析對比上述三種故障分析攻擊方法的效率。在所有的故障攻擊方法中，單次故障攻擊計算復雜度相差不大，因此故障攻擊所需的次數決定了攻擊效率。對于每一種類型的故障攻擊，記錄所需明文數量以及每一個明文所需的故障注入數量。在本文中，故障攻擊效率定義為：

其中，E，Pn，Fn分別代表故障攻擊效率、所需明文數量、單個明文所需注入故障數量。

本節主要在三種情況下比較各故障分析攻擊的效率。第一種情況，攻擊者可以精確的故障注入，可以使狀態矩陣的單一字節分別產生1、2、3字節比特故障。第二種情況，攻擊者可以在狀態矩陣的確定字節注入故障。第三種情況，攻擊者可以在狀態矩陣注入隨機字節故障。第四種情況，攻擊者在狀態矩陣若干個字節注入故障。

如表1所示，在相同的情況下DFA攻擊相對于其他兩種攻擊方法比起來效率更高。DFA發展到目前已有很多不同類型的分析方法，這些方法都依賴于較為嚴格的故障模型，當攻擊者沒有能力注入確定的故障模型，DFA攻擊將不再適用。與DFA相比，FSA和DFIA攻擊效率較低，但不需要嚴格的故障模型。在注入故障不確定的情況下，仍然可以恢復出密鑰信息。

表1 不同情況下的攻擊效率

3 結 語

本文提出了一種對分組密碼故障攻擊過程的形式化描述方法。不同的故障攻擊方法，雖然故障注入位置可能相同，但由于其分析機制不同、依賴的特性不同，在攻擊能力上會產生很大的差異。將所有分組密碼的故障攻擊方法納入到一個框架體系內，為評估并比較各種故障攻擊方法提供了基礎。為密碼安全防護工作提供指導。