針對橢圓曲線密碼的差分錯誤攻擊研究綜述

摘 要： 橢圓曲線密碼（ECC）是迄今為止具有最高強度的密碼系統(tǒng)。隨著集成電路、智能卡技術(shù)的發(fā)展以及嵌入式系統(tǒng)大規(guī)模的應(yīng)用，其安全性也受到了邊信道攻擊的威脅。差分錯誤攻擊（DFA）是旁路攻擊中的一種新的攻擊方式，攻擊者通過物理手段影響智能卡，從而在解密過程中誘導(dǎo)出錯誤信息，再結(jié)合差分分析恢復(fù)出私鑰信息。立足于國內(nèi)外對公鑰密碼故障分析研究的基礎(chǔ)上，在攻擊方法和防御方法兩方面對ECC算法的故障分析進行了研究概述，并指出了每個攻擊方法的優(yōu)缺點，預(yù)測了未來的研究方向。

關(guān)鍵詞： 橢圓曲線密碼； 差分錯誤攻擊； 智能卡； 防御

中圖分類號： TN915.08?34； TP309.7 文獻標識碼： A 文章編號： 1004?373X（2016）19?0063?04

Abstract： The elliptic curve cryptogram （ECC） is a cryptosystem with the highest intensity so far. With the development of the integrated circuit and smart card technology， and large?scale applications of the embedded systems， the security of ECC is threatened by side channel attack. The differential fault attack （DFA） is a new attack mode of side channel attack， by which the attacker can influence on the smart card with physical means， so as to induce the error message in decrypting process， and then the private key information is recovered in combination with differential analysis. On the basis of the study and analysis of public key cryptography failure at home and abroad， the fault analysis using ECC algorithm is researched and reviewed in the aspects of attack methods and defense methods. The advantages and disadvantages of each attack method are pointed， and the future development trend is predicted.

Keywords： elliptic curve cryptogram； differential fault attack； smart card； defense

0 引 言

隨著通信、計算機網(wǎng)絡(luò)、集成電路等技術(shù)的飛速發(fā)展，信息安全問題受到各行各業(yè)的廣泛關(guān)注。1985年，Neal Koblitz和Victor Miller各自提出了橢圓曲線密碼（Elliptic Curve Cryptogram，ECC）[1?2]，其安全性是基于橢圓曲線離散對數(shù)問題，在公鑰密碼學中獲得更多的關(guān)注與認可。與RSA等公鑰密碼算法相比，ECC具有計算量小、處理速度快、存儲空間占用小、帶寬要求低且安全性更高等優(yōu)點。因此，更適合資源受限的設(shè)備（例如智能卡）。在許多的實際應(yīng)用中，橢圓曲線密碼的私鑰存儲在智能卡中，因為加密和簽名的過程都是在卡內(nèi)完成的，如果不破壞芯片，很難知道其中隱藏的密鑰信息。

邊信道攻擊（Side Channel Attack，SCA）[3]又稱側(cè)信道攻擊，針對加密電子設(shè)備在運行過程中的時間消耗、功率消耗或電磁輻射之類的側(cè)信道信息泄露而對加密設(shè)備進行攻擊的一類方法。這類新型攻擊的有效性遠高于密碼分析的數(shù)學方法，因此給密碼設(shè)備帶來了嚴重的威脅。1996年Boneh在歐密會上首次提出了故障攻擊（Fault Attacks）[4]的概念。其主要思想是主動向密碼設(shè)備中注入錯誤，通過錯誤計算攻擊公鑰密碼的代數(shù)結(jié)構(gòu)，從而得到設(shè)備的秘密信息。原始的攻擊方法依賴模運算的代數(shù)特性，不能處理私鑰算法復(fù)雜的位操作，所以原始的這種攻擊方法只能應(yīng)用于公鑰密碼體制，不能攻擊私鑰密碼，例如DES加密標準。錯誤攻擊是對RSA公鑰密碼體制的新型攻擊方法。相比于能量攻擊，故障攻擊具有良好的抗噪聲性能，因而在安全領(lǐng)域具有廣泛的應(yīng)用前景。

錯誤攻擊的類型主要分為以下幾種：

（1） 通過控制錯誤的位置，分為三種：無控制（No Control），錯誤誘導(dǎo)的位置是任意的；輕控制（Loose Control），選擇一種變量作為攻擊目標；完全控制（Complete Control），選擇的密鑰位都作為攻擊的目標。

（2） 通過控制時間，分為三種：無控制，即引誘發(fā)生錯誤的時間不受控制；輕控制，即錯誤被引誘進裝置中只需一小部分操作的時鐘；精確控制，即錯誤引誘的時間是非常精確的。

（3） 錯誤影響密鑰位的數(shù)量，分為三類：單一錯誤位（Single Faulty Bit）；部分錯誤（Few Faulty Bit）；隨機數(shù)量的錯誤（Random Number Of Faulty Bit）。

（4） 錯誤注入后的影響，分為瞬時錯誤和永久錯誤。

2 研究進展

1997年，Biham和Shamir將這種攻擊方法應(yīng)用于對稱密碼體制，首次提出了差分錯誤攻擊的概念[5]，并成功地攻擊了DES算法。DES是將64 b的輸入數(shù)據(jù)通過16輪的迭代運算，得到長度同樣是64 b的輸出數(shù)據(jù)。其錯誤注入點位于倒數(shù)第二輪的中間狀態(tài)，采用比特位作為單位來處理數(shù)據(jù)。這樣做只需要較少的密文就可恢復(fù)密鑰，減小了運算的復(fù)雜度。此后研究人員提出了各種不同的故障攻擊方法，成功攻擊了多種密碼體制，包括RSA?CRT算法、橢圓曲線算法、流密碼等。

2000年，來自Bell通信實驗室的三位學者Biehl等首先提出了對ECC密碼體制的差分錯誤攻擊[6]，該故障分析從位于安全的橢圓曲線上的輸入點中引入故障，使得錯誤的點位于一個較弱的橢圓曲線上，進而通過分析較弱的橢圓曲線獲取安全橢圓曲線密鑰[7]?；谶@種思想人們對IEEE 802.15制定的加密方案（ECDH，SCIES和ECMQV）和采用蒙哥馬利方法實現(xiàn)點乘的橢圓曲線密碼進行了攻擊。這類方法的主要缺點是攻擊效率較低且比較容易防御。

2005年，Ciet等提出了在確定錯誤植入位置的情況下恢復(fù)密鑰的方法[8]。通常，安全的橢圓曲線密碼體制是已知的，并且其密鑰[d∈Z]存儲在抗篡改、不可讀的設(shè)備中，當輸入橢圓曲線上的點[P]時，該設(shè)備計算并輸出[d?P]。針對ECC的故障分析根據(jù)故障位于輸入點[P]和系統(tǒng)參數(shù)不同而不同。

（1） 當基點[P]發(fā)生故障時。第一種情況是沒有檢查輸入點與輸出點是否在安全的橢圓曲線上，可能導(dǎo)致輸入點[P（x，y）?E，]使得[a′6=y2+a1xy+a3y-x3-][a2x2-a4x。]元組[a1，a2，a3，a4，a′6]確定了新的橢圓曲線[E，]該橢圓曲線的階[ord（E）]含有小因子[r，]并且[ord（P）=r。]因此，橢圓曲線的對數(shù)問題可以歸結(jié)到由[P∈E]生成的階為[r]的子群上的離散對數(shù)問題，由點[P，d?E]可以計算出[d mod r。]通過選擇不同的點[P]重復(fù)上述過程，根據(jù)中國剩余定理（CRT）即可求出密鑰[d。]第二種情況是對輸入點進行檢查，假設(shè)進行上述檢測后點乘運算開始時，寄存器中產(chǎn)生了錯誤，出錯后的點[P]與輸入點[P]只有1 b不同，密碼芯片不再檢測輸入點是否在[E]上，計算輸出[d?P，且d?P]依賴于由[P]確定的[E=a1，a2，a3，a4，a′6，]這樣又把[E]上的DL問題轉(zhuǎn)換到[E]上的DL問題。首先計算[E]上點的數(shù)目[ord（E），]如果[ord（E）]具有小因子[r，]則可根據(jù)點[ord（E）r?P′E]和[d?ord（E）r?P′E]解決DL問題。最后根據(jù)不同的因子[r]和中國剩余定理重復(fù)上述過程恢復(fù)密鑰[d。]

針對ECC故障分析的防御方法主要是通過設(shè)計一種硬件檢測裝置，檢查每一個輸出點是否在安全的橢圓曲線上；檢查所有用于計算輸出的中間點以及最終的輸出是否在橢圓曲線上。若上述兩點有一個不能成立，則阻止輸出任何點。對于改進的新型攻擊方法，硬件防御不能有效地檢測出故障點。所以在今后的研究過程中，軟件防御算法將是一個新的研究熱點。

2006年，Johannes Bl?mer和Martin Otto等人提出符號變換故障攻擊（Sign Fault Attacks，SFA）[9]，并采用二進制非相鄰表示型（Non?Adjacent Form，NAF）[10]方法實現(xiàn)運算的橢圓曲線進行了攻擊。攻擊者通過誘導(dǎo)密碼芯片出錯，改變特殊輸出點[Q]的[y]坐標符號，即[Q=-Q=（x，-y）]。與以往的攻擊方法不同，錯誤輸出點偏離了安全曲線，轉(zhuǎn)換成在弱的橢圓曲線上計算離散對數(shù)問題。而符號變換攻擊的錯誤輸出點在橢圓曲線上是有效點，密鑰可在多項式時間內(nèi)恢復(fù)。一般的輸出點檢測裝備不能檢測出錯誤的發(fā)生，符號變換攻擊的故障點不易被防御裝置檢測出來，因而具有攻擊有效性。

橢圓曲線一般定義在兩種域中，二進制域[GF（2m）]和素數(shù)域[GFp]。當符號攻擊素數(shù)域[（p>3）]時，基點[P]被攻擊后的坐標點為[（x，-y）；]若符號變換攻擊二進制域，基點[P]被攻擊后的坐標為[（x，x-y）]。當前，符號變換攻擊假定橢圓曲線[E]被定義在素數(shù)域中，且在相同的輸入條件下重復(fù)增加攻擊次數(shù)以至少[12]的概率恢復(fù)密鑰[d。]目前，標量乘運算實現(xiàn)方式主要有二進制NAF方法（從左至右或從右至左）、蒙哥馬利二進制方法。

Bl?mer提出的二進制NAF算法成功地以至少[12]的概率恢復(fù)了密鑰[d。]蒙哥馬利二進制算法[11]若其密鑰位是非零的，則運算中既有加法也有倍加；若其密鑰位是零，則運算中只有倍加。這種算法易受時間和能量攻擊的影響。所以不能同時抵抗多種側(cè)信道攻擊。

2008年，Pierre?Alain Fouque和Reynald Lercier提出蒙哥馬利階方法[13]攻擊橢圓曲線。此種方法的優(yōu)點是不使用[y]坐標僅需較少的錯誤即可恢復(fù)密鑰，此時它并不關(guān)心特殊點是在原來的橢圓曲線上還是在轉(zhuǎn)換后的橢圓曲線（Twist of an Elliptic Curve）上，結(jié)果算法對于點[（x：y：z）∈E]仍然有效，只是[y∈Fp2]代替了簡單的[y∈Fp。]而且特殊點從強橢圓曲線到弱曲線上時也不會被偵查出來，所以恢復(fù)密鑰的成功率大大提高。同時，對于安全抵抗簡單能量分析蒙哥馬利也是一種有效的方法。

2009年，Alexey 提出了新的錯誤攻擊橢圓曲線標量乘算法[14]。提出假設(shè)，假定攻擊者可以誘導(dǎo)中間點[Q]的[x]坐標值發(fā)生錯誤，錯誤發(fā)生的時間可以精確的選擇。其錯誤誘導(dǎo)算法過程如下：

這種改進的標量乘算法經(jīng)過計算分析表明，對于廣泛的橢圓曲線，它的適用性和有效性都比以前的攻擊方案優(yōu)越，而且可以在可實行的時間內(nèi)恢復(fù)密鑰。其不足在于算法有點小復(fù)雜，要求誘導(dǎo)的錯誤數(shù)量是線性的且多項式時間復(fù)雜度被要求不超過[O1N，]其中[N]是初始域[K]的階。

隨著技術(shù)逐漸趨于成熟，錯誤攻擊成功攻擊了私鑰密碼體制、公鑰密碼體制。后來的研究學者們基于以上的攻擊方法也做出了許多的改進。針對橢圓曲線算法及符號變換攻擊的原理，提出了改進的符號變換攻擊方案，即二進制方法點乘的橢圓曲線密碼故障攻擊[15]。該算法通過改變錯誤注入位置，減少故障對私鑰的數(shù)值依賴，有效解決了原算法中出現(xiàn)的“零塊失效”問題。又例如控制電路的有限狀態(tài)機跳變故障模型，2011年朱巍巍提出了橢圓曲線的一種新故障攻擊方法[16?18]，對帶點檢測防御能力的二進制NAF型橢圓曲線進行了理論分析。與符號攻擊方法相比，該方法產(chǎn)生的故障還在原來的曲線上，并通過增加預(yù)計算，提高了攻擊效率。

3 總結(jié)與展望

錯誤攻擊是側(cè)信道攻擊方式的一種，也是近幾年的研究熱點。本文針對橢圓曲線加密算法概述了差分錯誤攻擊的幾種常見技術(shù)。主要包括二進制NAF算法、蒙哥馬利算法、符號變換攻擊。橢圓曲線的加密體制是基于復(fù)雜的離散對數(shù)問題，前兩種方法都是把在強橢圓曲線上解決離散對數(shù)的問題轉(zhuǎn)換成在弱橢圓曲線上的離散對數(shù)問題，這種攻擊方法可以通過自檢裝置進行防御。而符號攻擊是另一種錯誤誘導(dǎo)方法，計算仍然在原橢圓曲線上，所以其攻擊有效性提高了?？墒峭ǔ５挠布烙胧ζ涫菬o效的，針對符號攻擊的防御算法[19?20]有待下一步的改進優(yōu)化。

國內(nèi)外提出的錯誤分析防御方法都是針對特定某一攻擊，無法同時防御其他多種邊界信道攻擊。近期，多邊界信道攻擊被廣泛地應(yīng)用到密碼分析領(lǐng)域，取得了單一邊界信道無法達到的攻擊效果。期望一種算法，可以在注入較少錯誤的前提下，運算簡單、攻擊效率高。因此，研究不同密碼體制如何防御多信道攻擊[21]已經(jīng)成為該領(lǐng)域的研究熱點。對ECC等公鑰密碼體制的邊界信道攻擊算法研究具有廣泛的研究和發(fā)展前景。

參考文獻

[1] KOBLITZ N. Elliptic curve cryptosystems [J]. Mathematics of computation， 1987， 48（177）： 203?209.

[2] MILLER V S. Use of elliptic curve in cryptography [C]// Proceeding of 1985 Advances in Cryptology?Crypto. Berlin： Sprin?ger?Verlag， 1985： 417?426.

[3] IZU T， TAKAGI T. A fast parallel elliptic curve multiplication resistant against side channel attacks [C]// Proceedings of 2002 5th International Workshop on Practice and Theory in Public Key Cryptosystems. Paris： Springer Berlin Heidelberg， 2002： 280?296.

[4] DAN B， DEMILLO R A， LIPTON R. On the importance of checking cryptographic protocols for fault [C]// Proceedings of 1997 International Conference on the Theory and Application of Cryptographic. Konstanz： Springer?Verlag， 1997： 37? 51.

[5] BIHAM E， SHAMIR A. Differential fault analysis of secret key cryptosystems [C]// Proceedings of 17th Annual International Cryptology Conference. Santa Barbara： Springer?Verlag， 1997： 513?525.

[6] BIEHL I， MEYER B， MüLLER V. Differential fault attacks on elliptic curve cryptosystems [C]// Proceedings of 20th Annual International Cryptology Conference. Santa Barbara： Springer Berlin Heidelberg， 2000： 131?146.

[7] DAN B， DEMILLO R A， LIPTON R J. On the importance of eliminating errors in cryptographic computations [J]. Journal of cryptology， 2001， 14（1）： 101?119.

[8] CIET M， JOYE M. Elliptic curve cryptosystems in the pre?sence of permanent and transient faults [J]. Designs， codes and cryptography， 2005， 36（1）： 33?43.

[9] BL?MER J， OTTO M， SEIFERT J P. Sign change fault attacks on elliptic curve cryptosystems [C]// Proceedings of 2006 Third International Workshop on Fault Diagnosis and Tole?rance in Cryptography. Yokohama： Springer?Verlag， 2006： 36?52.

[10] BECKER A. Methods of fault analysis attacks on elliptic curve cryptosystems [D]. Darmstadt： Darmstadt University of Technology， 2006.

[11] JOYE M. Fault?resistant calculations on elliptic curves： US 8457303 [P]. 2010?07?22.

[12] 祝力.公鑰密碼及其故障分析研究[D].上海：上海交通大學，2007.

[13] FOUQUE P A， LERCIER R， REAL D， et al. Fault attack on elliptic curve with Montgomery ladder implementation [C]// Proceedings of 2008 Fifth International Workshop on Fault Diagnosis and Tolerance in Cryptography. Washington， D. C.：IEEE， 2008： 92?98.

[14] CHILIKOV A， TARASKIN O. New fault attack on elliptic curve scalar multiplication [EB/OL]. [2009?05?28]. http：//eprint.iacr.org/2009/528.pdf.

[15] 張金中，寇應(yīng)展，陳財森，等.二進制方法點乘的橢圓曲線密碼故障攻擊[J].計算機工程，2011（20）：100?102.

[16] ZHU Weiwei， YAN Yingjian， LIU Kai. State machine skip fault attacks on elliptic curve scalar multiplication [J]. Journal of Information Engineering University， 2011（4）： 159?161.

[17] 朱巍巍，嚴迎建.基于隨機故障感染運算的橢圓曲線點乘算法[J].計算機工程，2011（24）：112?113.

[18] 嚴迎建，李志強，段二朋，等.橢圓曲線點乘的抗故障攻擊FSM控制器設(shè)計[J].計算機應(yīng)用，2012（1）：86?88.

[19] 張偉.智能卡中ECC標量乘模板攻擊研究[D].西安：西安電子科技大學，2013.

[20] 張濤.面向密碼芯片的旁路攻擊關(guān)鍵技術(shù)研究[D].成都：電子科技大學，2008.

[21] 王家良，錢琦鋒，韋磊，等.ECC算法軟件優(yōu)化的研究綜述[J].智能電網(wǎng)，2012（2）：131?136.