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

李 瑋

（東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620）

1 引言

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

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

2 差分故障攻擊

差分故障攻擊是指攻擊者在密碼系統(tǒng)運(yùn)行時(shí)導(dǎo)入故障，使其執(zhí)行某些錯(cuò)誤的操作、過(guò)程或產(chǎn)生錯(cuò)誤的結(jié)果，并通過(guò)差分分析，獲取密碼系統(tǒng)的關(guān)鍵信息的方法。作為故障攻擊的一種主要分析方法，差分故障攻擊憑借其攻擊范圍廣、能力強(qiáng)且計(jì)算量小等特點(diǎn)，已引起國(guó)內(nèi)外研究學(xué)者的廣泛關(guān)注。

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

從差分故障攻擊分組密碼的發(fā)展情況來(lái)看，差分故障攻擊的成功實(shí)現(xiàn)需具備以下兩個(gè)重要組成部分：基本假設(shè)和故障模型。

2.1 差分故障攻擊的基本假設(shè)

差分故障攻擊與密碼算法的實(shí)現(xiàn)環(huán)境密切相關(guān)。因此，在分析算法之前，必須遵循以下重要的基本假設(shè)：

· 攻擊者能夠物理地運(yùn)行包含密碼運(yùn)算的實(shí)體 （設(shè)備、芯片、軟件等）；

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

· 通常要求攻擊者知道實(shí)體中實(shí)現(xiàn)的密碼算法，有時(shí)要求知道算法的具體實(shí)現(xiàn)方法；

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

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

由于攻擊者需要在密碼算法正常運(yùn)行時(shí)導(dǎo)入故障，迫使其發(fā)生錯(cuò)誤的輸出結(jié)果。如何導(dǎo)入理想的故障，成為差分故障攻擊能否成功實(shí)現(xiàn)的關(guān)鍵。在總結(jié)了國(guó)內(nèi)外的研究成果基礎(chǔ)上，本文討論了故障模型的組成。通常，一個(gè)故障模型由三元組（時(shí)刻、位置、動(dòng)作）構(gòu)成。

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

·單輪故障：是指每次僅在故障運(yùn)算的某一輪或循環(huán)出現(xiàn)故障。

·最后若干輪的隨機(jī)單輪故障：是指每次僅在故障運(yùn)算的最后輪中的任意一輪或循環(huán)出現(xiàn)故障。

·隨機(jī)單輪故障：是指每次僅在故障運(yùn)算的任意一輪或循環(huán)出現(xiàn)故障。

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

·單比特故障：是指每次故障加密（或解密）中僅某一個(gè)比特出現(xiàn)故障。

·單字節(jié)故障：是指每次故障加密（或解密）中僅某一個(gè)字節(jié)出現(xiàn)故障。

·多比特故障：是指每次故障加密（或解密）中多個(gè)比特同時(shí)出現(xiàn)故障。

·多字節(jié)故障：是指每次故障加密（或解密）中多個(gè)字節(jié)同時(shí)出現(xiàn)故障。

·隨機(jī)單比特故障：是指每次故障加密（或解密）中僅任意一個(gè)比特出現(xiàn)故障。

·隨機(jī)單字節(jié)故障：是指每次故障加密（或解密）中僅任意一個(gè)字節(jié)出現(xiàn)故障。

·隨機(jī)多比特故障：是指每次故障加密（或解密）中僅任意幾個(gè)比特同時(shí)出現(xiàn)故障。

·隨機(jī)多字節(jié)故障：是指每次故障加密（或解密）中僅任意幾個(gè)字節(jié)同時(shí)出現(xiàn)故障。

故障動(dòng)作，其包括以下類型。

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

·BSR（bit set or reset）：設(shè)定故障位置的值為預(yù)定值

（攻擊者已知該值）。

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

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

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

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

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

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

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

從表1得出，差分故障攻擊實(shí)現(xiàn)環(huán)境分為兩類：軟件模擬和真實(shí)環(huán)境。

3.1.1 軟件模擬環(huán)境下攻擊的基本步驟

（1）選定一個(gè)故障模型，即需要明確給出故障的時(shí)間、位置、動(dòng)作（通常，差分故障攻擊的故障模型是：加密算法單輪故障、特定寄存器的隨機(jī)單字節(jié)故障、RF）。

（2）在故障模型下，通過(guò)選擇明文及相應(yīng)的正確和故障密文對(duì)，對(duì)密碼算法的執(zhí)行過(guò)程進(jìn)行數(shù)學(xué)分析（即差分分析），給出計(jì)算子密鑰信息的步驟和數(shù)學(xué)表達(dá)式（有時(shí)同時(shí)可以根據(jù)盒的差分分布表來(lái)判定計(jì)算相應(yīng)子密鑰平均所需要的故障密文對(duì)的數(shù)目）。

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

3.1.2 實(shí)際環(huán)境下攻擊的基本步驟

（1）選定一個(gè)故障模型，即需要明確給出故障的時(shí)間、位置、動(dòng)作（通常，差分故障攻擊的故障模型是：加密算法單輪故障、特定寄存器的隨機(jī)單字節(jié)故障、RF）。

（2）在故障模型下，通過(guò)選擇明文及相應(yīng)的正確和故障密文對(duì)，對(duì)密碼算法的執(zhí)行過(guò)程進(jìn)行數(shù)學(xué)分析（即差分分析），給出計(jì)算子密鑰信息的步驟和數(shù)學(xué)表達(dá)式（有時(shí)同時(shí)可以根據(jù)盒的差分分布表來(lái)判定計(jì)算相應(yīng)子密鑰平均所需要的故障密文對(duì)的數(shù)目）。

（3）根據(jù)故障模型，選定特定的故障導(dǎo)入方法，產(chǎn)生特定的故障動(dòng)作。

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

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

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

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

3.2 攻擊評(píng)價(jià)標(biāo)準(zhǔn)

一個(gè)“好”的差分故障攻擊方法需要通過(guò)以下3個(gè)方面來(lái)衡量。

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

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

· 攻擊代價(jià)?。汗收蠑?shù)少、計(jì)算量少、存儲(chǔ)量少。

4 未來(lái)的研究方向

在差分故障攻擊分組密碼及其防御技術(shù)方面，我們認(rèn)為以下內(nèi)容是需要進(jìn)一步研究的。

· 具體芯片平臺(tái)上模擬仿真試驗(yàn)研究：故障攻擊的實(shí)現(xiàn)包含有兩種方式，可以在硬件上通過(guò)激光、微探針等方式實(shí)現(xiàn)，或者通過(guò)計(jì)算機(jī)軟件模擬技術(shù)進(jìn)行仿真。現(xiàn)階段，國(guó)內(nèi)的研究工作主要集中于計(jì)算機(jī)軟件模擬仿真層面，還沒(méi)有在具體的芯片平臺(tái)上進(jìn)行實(shí)驗(yàn)。

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

· 其他故障攻擊方法的研究：差分故障攻擊是一種簡(jiǎn)單有效的密碼分析方法，因此不僅成功地用于分析大量的分組密碼算法，如 DES、3-DES、IDEA和AES等，還可以應(yīng)用在一些廣泛使用的算法結(jié)構(gòu)，如SP型結(jié)構(gòu)和Feistel型結(jié)構(gòu)等。然而，作為故障攻擊的其他方法，例如無(wú)效故障攻擊和碰撞故障攻擊等，目前國(guó)內(nèi)外研究成果較少。因此，有必要對(duì)其他故障攻擊方法的基本假設(shè)、故障模型及攻擊方法展開(kāi)進(jìn)一步的研究。

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

5 結(jié)束語(yǔ)

綜上，在差分故障攻擊方法中，攻擊者可以利用密碼系統(tǒng)中泄漏出來(lái)的故障信息來(lái)破譯密碼算法的密鑰，大大提高了攻擊的速度，并降低了攻擊的計(jì)算量。在實(shí)際應(yīng)用中，隨著越來(lái)越多的分組密碼廣泛應(yīng)用于諸如智能卡、移動(dòng)設(shè)備等安全性較差的環(huán)境中，系統(tǒng)的關(guān)鍵信息泄露在所難免，這些重要信息的泄露對(duì)于一個(gè)密碼系統(tǒng)來(lái)說(shuō)是一個(gè)極其危險(xiǎn)的攻擊，因?yàn)樗馕吨到y(tǒng)將徹底失去安全性保證。因此，如何利用旁路攻擊技術(shù)，特別是差分故障分析分組密碼的安全性，是一項(xiàng)非常必要且有現(xiàn)實(shí)意義的研究課題。未來(lái)的研究工作應(yīng)圍繞上述研究點(diǎn)開(kāi)展，力求在理論和實(shí)踐上有所突破，將該領(lǐng)域的研究工作不斷推向前進(jìn)。

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密碼算法的差分故障攻擊.計(jì)算機(jī)學(xué)報(bào)，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