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

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

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

中圖分類號： 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 引 言

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

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

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

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

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

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

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

2 研究進展

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

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

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

（1） 當基點[P]發生故障時。第一種情況是沒有檢查輸入點與輸出點是否在安全的橢圓曲線上，可能導致輸入點[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。]因此，橢圓曲線的對數問題可以歸結到由[P∈E]生成的階為[r]的子群上的離散對數問題，由點[P，d?E]可以計算出[d mod r。]通過選擇不同的點[P]重復上述過程，根據中國剩余定理（CRT）即可求出密鑰[d。]第二種情況是對輸入點進行檢查，假設進行上述檢測后點乘運算開始時，寄存器中產生了錯誤，出錯后的點[P]與輸入點[P]只有1 b不同，密碼芯片不再檢測輸入點是否在[E]上，計算輸出[d?P，且d?P]依賴于由[P]確定的[E=a1，a2，a3，a4，a′6，]這樣又把[E]上的DL問題轉換到[E]上的DL問題。首先計算[E]上點的數目[ord（E），]如果[ord（E）]具有小因子[r，]則可根據點[ord（E）r?P′E]和[d?ord（E）r?P′E]解決DL問題。最后根據不同的因子[r]和中國剩余定理重復上述過程恢復密鑰[d。]

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

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

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

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

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

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

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

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

3 總結與展望

錯誤攻擊是側信道攻擊方式的一種，也是近幾年的研究熱點。本文針對橢圓曲線加密算法概述了差分錯誤攻擊的幾種常見技術。主要包括二進制NAF算法、蒙哥馬利算法、符號變換攻擊。橢圓曲線的加密體制是基于復雜的離散對數問題，前兩種方法都是把在強橢圓曲線上解決離散對數的問題轉換成在弱橢圓曲線上的離散對數問題，這種攻擊方法可以通過自檢裝置進行防御。而符號攻擊是另一種錯誤誘導方法，計算仍然在原橢圓曲線上，所以其攻擊有效性提高了。可是通常的硬件防御措施對其是無效的，針對符號攻擊的防御算法[19?20]有待下一步的改進優化。

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

參考文獻

[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] 張金中，寇應展，陳財森，等.二進制方法點乘的橢圓曲線密碼故障攻擊[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控制器設計[J].計算機應用，2012（1）：86?88.

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

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

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