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

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

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

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

0 引 言

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

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

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位的明文分組轉(zhuǎn)換為2維的16字節(jié)狀態(tài)矩陣，與輪密鑰K0進行異或運算后，進行 10輪函數(shù)加密操作。每一輪的加密操作包括以下步驟：

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

行移為（ShiftRows，SR），狀態(tài)矩陣每行單獨進行字節(jié)移位操作，記為SR。

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

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

1.2 故障攻擊特點分析

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

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

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

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

例如，DFA中觀測信息為

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

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

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

第二步：故障特征推測。

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

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

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

第三步：關聯(lián)度匹配。

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

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

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

2 故障攻擊效率分析研究

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

2.1 差分故障分析（DFA）

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

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

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

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

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

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

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

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

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

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

2.2 故障敏感度分析（FSA）

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

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

第二步：反推中間故障狀態(tài)。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 攻擊效率分析

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

其中，E，Pn，F(xiàn)n分別代表故障攻擊效率、所需明文數(shù)量、單個明文所需注入故障數(shù)量。

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

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

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

3 結 語

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