典型分組密碼抗差分故障攻擊的安全分析*

李 瑋

（東華大學計算機科學與技術學院 上海 201620）

1 引言

分組密碼是現代密碼技術中實現數據加密、數字簽名、認證及密鑰管理的核心體制，在計算機通信和信息系統安全領域有著廣泛的應用。隨著集成電路和智能卡技術的發展以及嵌入式系統的大規模應用，單純從分組密碼算法的數學結構研究安全性能已遠遠不夠，從算法的實現角度來考慮安全問題已成為必需。在實際應用領域中，密碼算法通常使用各種芯片來實現，如智能卡、加密存儲卡、加密機芯片、手機芯片和網絡路由器芯片等，這些芯片在運行時有可能泄漏某些中間狀態信息（出錯消息、執行時間、功耗、電磁輻射等），使得攻擊者有機會采集與密鑰相關的關鍵信息，從而發現明文或密鑰。故障攻擊正是在這種背景下被提出的，由于其成功的攻擊效果和潛在的發展前景，已經引起了國內外從事密碼和微電子的研究學者的極大關注，并成為密碼分析和密碼工程領域發展最為迅速的方向之一。

故障攻擊（fault analysis），又稱故障分析，是指攻擊者使用物理方法（如電磁或激光輻射）干擾密碼芯片或軟件的正常工作，迫使其執行某些錯誤的操作，從而泄漏密碼系統的秘密信息。1996年，D.Boneh等人利用隨機硬件故障來攻擊公鑰密碼體制，此后故障攻擊在密碼分析方法中占據了重要的位置[1]。接著，E.Biham和A.Shamir于1997年針對DES密碼算法提出了差分故障攻擊方法[2]。然后，人們從故障誘導的長度、類型和持續度等方面對密碼算法的故障攻擊進行了分類，并從性能、效率、攻擊難易程度等方面研究，進而給出了 AES算法[3～9]、CLEFIA 算法[10]、KHAZAD算法[8]、FOX算法[11]、SMS4算法[12]以及RC4算法[13,14]等多種密碼體制的故障攻擊方法[15～17]。后來，故障攻擊在其自身的發展中，逐步衍生出多種攻擊方法，例如差分故障攻擊、無效故障攻擊以及碰撞故障攻擊等[2,14,18,19]，攻擊對象擴展到更多的分組密碼算法，例如IDEA算法[20]以及3-DES算法等[18]。與其他故障攻擊技術相比較，差分故障攻擊攻擊范圍廣、能力強且計算量小，因此本文將重點研究差分故障攻擊分組密碼。

2 差分故障攻擊

差分故障攻擊是指攻擊者在密碼系統運行時導入故障，使其執行某些錯誤的操作、過程或產生錯誤的結果，并通過差分分析，獲取密碼系統的關鍵信息的方法。作為故障攻擊的一種主要分析方法，差分故障攻擊憑借其攻擊范圍廣、能力強且計算量小等特點，已引起國內外研究學者的廣泛關注。

1997年，E.Biham和A.Shamir針對DES密碼提出了差分故障攻擊方法[2]。接著，根據基本假設和故障模型的不同要求，研究學者對AES算法進行了深入的研究。2003年，C.Giraud首次提出了針對AES算法的差分故障攻擊方法，在兩種不同要求的故障模型下，分別實現了對AES算法的差分故障攻擊[5]。然后，研究學者在故障模型要求較“弱”的情況下，實現了代價較小的攻擊方法[7,8]。2006年，A.Moradi等人在故障模型要求更“弱”的情況下，提出并實現了差分故障攻擊AES算法的新方法[3]。

從差分故障攻擊分組密碼的發展情況來看，差分故障攻擊的成功實現需具備以下兩個重要組成部分：基本假設和故障模型。

2.1 差分故障攻擊的基本假設

差分故障攻擊與密碼算法的實現環境密切相關。因此，在分析算法之前，必須遵循以下重要的基本假設：

· 攻擊者能夠物理地運行包含密碼運算的實體 （設備、芯片、軟件等）；

· 攻擊者能夠觀察和記錄實體的輸出情況（具體的輸出值或者輸出正確與否），包括直接訪問實體輸出值或者在通信信道上截獲信息；

· 通常要求攻擊者知道實體中實現的密碼算法，有時要求知道算法的具體實現方法；

· 有時要求攻擊者能夠選擇和記錄實體的輸入（即選擇明文攻擊、密文攻擊或密鑰攻擊）。

2.2 差分故障攻擊的故障模型

由于攻擊者需要在密碼算法正常運行時導入故障，迫使其發生錯誤的輸出結果。如何導入理想的故障，成為差分故障攻擊能否成功實現的關鍵。在總結了國內外的研究成果基礎上，本文討論了故障模型的組成。通常，一個故障模型由三元組（時刻、位置、動作）構成。

故障時刻：攻擊需要精確控制錯誤發生的時刻，例如在運算進行到某一指定的步驟時引入故障。有些攻擊則不需要這樣精確，引入的故障只需要在運算進行到某一個范圍內，包含故障出現在算法某些部分（加密、解密、密鑰編排方案）的某些輪或循環。一般地，對于迭代分組密碼，根據故障輪或循環的位置可分為以下幾種類型。

·單輪故障：是指每次僅在故障運算的某一輪或循環出現故障。

·最后若干輪的隨機單輪故障：是指每次僅在故障運算的最后輪中的任意一輪或循環出現故障。

·隨機單輪故障：是指每次僅在故障運算的任意一輪或循環出現故障。

故障位置：攻擊需要精確控制錯誤發生的位置，例如將故障引入到某一指定的記憶單元。有些攻擊對故障發生位置的要求則比較寬松，例如只將故障引入到某一指定的范圍，包括某些寄存器的某些比特（或字節）、某些指令運算結果的某些比特（或字節），這些比特（或字節）包括以下情形。

·單比特故障：是指每次故障加密（或解密）中僅某一個比特出現故障。

·單字節故障：是指每次故障加密（或解密）中僅某一個字節出現故障。

·多比特故障：是指每次故障加密（或解密）中多個比特同時出現故障。

·多字節故障：是指每次故障加密（或解密）中多個字節同時出現故障。

·隨機單比特故障：是指每次故障加密（或解密）中僅任意一個比特出現故障。

·隨機單字節故障：是指每次故障加密（或解密）中僅任意一個字節出現故障。

·隨機多比特故障：是指每次故障加密（或解密）中僅任意幾個比特同時出現故障。

·隨機多字節故障：是指每次故障加密（或解密）中僅任意幾個字節同時出現故障。

故障動作，其包括以下類型。

·BF（bit flip）：使得故障位置的值取反。

·BSR（bit set or reset）：設定故障位置的值為預定值

（攻擊者已知該值）。

·RF（random fault）：隨機設定故障位置的值（攻擊者未知該值）。

此外，故障導入的類型取決于故障導入方法，分為以下兩種。

·瞬時故障：每次僅影響特定故障時刻、特定故障位置的特定故障動作。瞬時故障攻擊的特點是故障將很快消失，不會影響到密碼設備以后的正常工作。攻擊者先正確地使用加密設備，得到正確的密文，然后再多次向加密設備中引入故障，得到多個故障密文。攻擊者會同時利用正確密文和故障密文進行分析比較，從而發現隱藏在密碼設備中的秘密信息。這類干擾的常見例子有輻射炸彈、異常高或低時鐘的頻率和異常電壓等。

·永久故障：每次均影響所有故障時刻、特定故障位置的特定故障動作。永久故障是指向密碼設備引入不可恢復的故障。故障一旦被引入，它將永久地發生在以后的加密過程中。向密碼設備引入永久故障往往會直接破壞了密碼設備，使密碼設備喪失了正常的加解密功能。典型的永久性破壞包括凍結一個記憶單元為一固定值和切斷一條數據總線等。但是如果攻擊者能夠在獲得密鑰的情況下完全復制密碼設備，那么基于永久故障的攻擊將很有意義。

3 典型分組密碼的安全性分析

DES算法和AES算法的破譯歷程為其他分組密碼的差分故障攻擊奠定了堅實的基礎。后來，KHAZAD算法[8]、FOX算法[11]、SMS4算法[12]、CLEFIA算法[10]以及IDEA算法的安全性都相繼被驗證具有差分故障攻擊的隱患[20]，見表 1。

3.1 差分故障攻擊分組密碼的基本步驟

從表1得出，差分故障攻擊實現環境分為兩類：軟件模擬和真實環境。

3.1.1 軟件模擬環境下攻擊的基本步驟

（1）選定一個故障模型，即需要明確給出故障的時間、位置、動作（通常，差分故障攻擊的故障模型是：加密算法單輪故障、特定寄存器的隨機單字節故障、RF）。

（2）在故障模型下，通過選擇明文及相應的正確和故障密文對，對密碼算法的執行過程進行數學分析（即差分分析），給出計算子密鑰信息的步驟和數學表達式（有時同時可以根據盒的差分分布表來判定計算相應子密鑰平均所需要的故障密文對的數目）。

（3）利用軟件模擬該故障模型，并按照第（2）步中給出的方法和步驟編寫計算機程序進行模擬試驗，通過對試驗數據進行數學處理和計算，求得若干子密鑰，從而根據密碼算法中的密鑰編排方案求出原始密鑰。

3.1.2 實際環境下攻擊的基本步驟

（1）選定一個故障模型，即需要明確給出故障的時間、位置、動作（通常，差分故障攻擊的故障模型是：加密算法單輪故障、特定寄存器的隨機單字節故障、RF）。

（2）在故障模型下，通過選擇明文及相應的正確和故障密文對，對密碼算法的執行過程進行數學分析（即差分分析），給出計算子密鑰信息的步驟和數學表達式（有時同時可以根據盒的差分分布表來判定計算相應子密鑰平均所需要的故障密文對的數目）。

（3）根據故障模型，選定特定的故障導入方法，產生特定的故障動作。

表1 典型分組密碼的差分故障攻擊研究

（4）任選一組明文作為輸入，正常執行加密（或解密）運算，觀察獲得正確密文；將上述明文分別再次作為輸入，異常執行加密（或解密）運算（即在加密運算或密鑰編排過程中導入一次故障），分別觀察獲得故障密文。

（5）根據正確明文和故障密文判斷哪些是符合故障模型的（即有效的）正確密文和故障密文對，并按照故障模型中的故障時刻和位置，對這些有效的正確密文和故障密文進行分類。

（6）對每一種分類數據進行數學處理和計算，求得若干子密鑰的信息；根據全部分類所求得的子密鑰信息和密鑰編排方案求出原始密鑰。

3.2 攻擊評價標準

一個“好”的差分故障攻擊方法需要通過以下3個方面來衡量。

· “弱”的基本假設（由弱到強排列）：唯密文攻擊、已知明文攻擊、選擇明文攻擊、選擇密文攻擊、選擇密鑰攻擊。

· “弱”的故障模型：容易實施、成本低。

· 攻擊代價小：故障數少、計算量少、存儲量少。

4 未來的研究方向

在差分故障攻擊分組密碼及其防御技術方面，我們認為以下內容是需要進一步研究的。

· 具體芯片平臺上模擬仿真試驗研究：故障攻擊的實現包含有兩種方式，可以在硬件上通過激光、微探針等方式實現，或者通過計算機軟件模擬技術進行仿真。現階段，國內的研究工作主要集中于計算機軟件模擬仿真層面，還沒有在具體的芯片平臺上進行實驗。

· 差分故障攻擊分組密碼的效率提高：國內外目前使用的故障攻擊的技術均采用瞬時故障導入，攻擊時要保證故障的導入精確位置，否則故障導入次數越多，攻擊的代價越大。因此，未來方向是：如何通過改變故障誘導的位置，在故障誘導的實施難度相同的情況下，針對分組算法提出新的攻擊方法，并降低攻擊的代價。

· 其他故障攻擊方法的研究：差分故障攻擊是一種簡單有效的密碼分析方法，因此不僅成功地用于分析大量的分組密碼算法，如 DES、3-DES、IDEA和AES等，還可以應用在一些廣泛使用的算法結構，如SP型結構和Feistel型結構等。然而，作為故障攻擊的其他方法，例如無效故障攻擊和碰撞故障攻擊等，目前國內外研究成果較少。因此，有必要對其他故障攻擊方法的基本假設、故障模型及攻擊方法展開進一步的研究。

·分組密碼抗故障攻擊的設計與實現方法：目前國內外抗故障攻擊的技術主要有基于復用和基于碼的技術。為了防御故障攻擊，密碼芯片須在輸出結果前進行自檢，但已有的做法執行效率很低或者其編碼器可能會遭到破壞，因此需要研究效率更高、安全性更佳的算法故障自檢技術。

5 結束語

綜上，在差分故障攻擊方法中，攻擊者可以利用密碼系統中泄漏出來的故障信息來破譯密碼算法的密鑰，大大提高了攻擊的速度，并降低了攻擊的計算量。在實際應用中，隨著越來越多的分組密碼廣泛應用于諸如智能卡、移動設備等安全性較差的環境中，系統的關鍵信息泄露在所難免，這些重要信息的泄露對于一個密碼系統來說是一個極其危險的攻擊，因為它意味著系統將徹底失去安全性保證。因此，如何利用旁路攻擊技術，特別是差分故障分析分組密碼的安全性，是一項非常必要且有現實意義的研究課題。未來的研究工作應圍繞上述研究點開展，力求在理論和實踐上有所突破，將該領域的研究工作不斷推向前進。

1 Boneh D,DeMillo R A,Lipton R J.On the importance of checking cryptographic protocols for faults.Advances in Cryptology—EUROCRYPT,Berlin,Springer-Verlag,1997,1233:37～51

2 Biham E,Shamir A.Differential fault analysis of secret key cryptosystems.Advances in Cryptology-CRYPTO’97,Berlin,Springer-Verlag,1997,1294:513～525

3 Moradi A,Shalmani M T M,Salmasizadeh M.A generalized method of differential fault attack against AES cryptosystem.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2006,4249:91～100

4 Blomer J,Seifert J P.Fault based cryptanalysis of the advanced encryption standard (AES).Financial Cryptography—FC,LNCS,Berlin,Springer-Verlag,2003,2742:162～181

5 Giraud C.DFA on AES.Advanced Encryption Standard 4-AES 2004,Springer-Verlag,2005,3373:27～41

6 Chen C N,Yen S M.Differential fault analysis on AES key schedule and some countermeasures.In:Proceedings of the Australasian Conference on Information Security and Privacy-ACISP,Springer-Verlag,2003,2727:118～129

7 Dusart P,Letourneux G,Vivolo O.Differential fault analysis on AES.Applied Cryptography and Network Security,Berlin,Springer-Verlag,2003,2846:293～306

8 Gilles P,Quisquater J J.A differential fault attack technique againstSPN structures,with application to the AES and KHAZAD.Cryptographic Hardware and Embedded Systems-CHES,2003,2779:77～88

9 Amir M,Mohammad T M S,Mahmoud S.A generalized method of differential fault attack against AES cryptosystem.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2003,4249:91～100

10 Chen H,Wu W,Feng D.Differential fault analysis on CLEFIA.International Conferenceon Information and Communication Security-ICICS,Berlin,Springer-Verlag,2007,4861:284～295

11 Breveglieri L,Koren I,Maistri P.A fault attack against the FOX cipher family.Fault Diagnosis and Tolerance in Cryptography-FDTC,Berlin,Springer-Verlag,2006,4236:98～105

12 張蕾，吳文玲.SMS4密碼算法的差分故障攻擊.計算機學報，2006，29（9）：1594～1600

13 Hoch J J,ShamirA.Faultanalysis of stream ciphers.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:240～253

14 Biham E,Granboulan L,Nguyên P Q.Impossible fault analysis of RC4 and differential fault analysis of RC4.Fast Software Encryption-FSE 2005,Berlin,Springer-Verlag,2005,3557:359～367

15 Biehl I,Meyer B,Müller V.Differential fault analysiss on elliptic curve cryptosystems.International Crytology Conference-CRYPTO 2000,Santa Barbara,California,USA,Berlin,Springer-Verlag,2000,1880:131～146

16 Jonathan J H,Shamir A.Fault analysis of stream ciphers.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:240～253

17 Lin I C,Chang C C.Security enhancement for digital signature schemes with fault tolerance in RSA.Information Sciences,2007,177(19):4031～4039

18 Hemme L.A differential fault analysis against early rounds of(Triple-)DES.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:254～267

19 Blomer J,Krummel V.Fault base on collision attack on AES.Fault Diagnosis and Tolerance in Cryptography-FDTC 2006,Berlin,Springer-Verlag,2006,4236:106～120

20 Clavier C,Gierlichs B,Verbauwhede I.Fault analysis study of IDEA.Topics in Cryptology-CT-RSA,2008,4964:274～287