針對滑動窗口算法的橢圓曲線密碼故障分析

張金中，寇應展，王韜，郭世澤，趙新杰

(1. 軍械工程學院 計算機工程系，河北 石家莊 050003；

2. 北方電子設備研究所，北京 100083)

1 引言

現代密碼算法可用于保證數據傳送的保密性、完整性和真實性，因而被廣泛應用于政治、經濟和軍事活動等領域。但是密碼算法的實際安全性不等同于設計安全性，密碼算法執行所依附的物理平臺會泄露出時間、電磁、功耗、聲音、故障等與密鑰密切相關的旁路信息，利用這些旁路信息進行密鑰破解的方法稱為旁路攻擊[1]。其中，故障攻擊主要利用密碼算法執行過程中的故障信息，結合算法結構破解密鑰。從故障攻擊提出至今，研究者先后對 RSA[2]，AES[3]、SMS4[4]、MIBS[5]、RC4[6]等密碼進行了故障攻擊。顯然，不論公鑰密碼、分組密碼還是流密碼，都面臨著故障攻擊的嚴重威脅。

橢圓曲線密碼（ECC，elliptic curve cryptosystem）是近年來密碼學領域研究的熱點之一，有密鑰短、安全性高、計算速度快的特點，已被廣泛應用于移動通信、電子商務等領域，也是衛星網絡、物聯網等新型網絡的首選，對其安全性進行研究顯得尤為重要。自1999年Coron[7]提出針對 ECC的簡單功耗分析（SPA, simple power analysis）和差分功耗分析（DPA, differential power analysis）開始，ECC的功耗攻擊及相關的防御措施已經逐步走向成熟，但ECC故障攻擊相關研究相對較少。

1.1 相關工作

目前針對ECC故障攻擊方法主要有3類。

1) ECC差分故障攻擊[8]。通過注入故障改變基點、基域或曲線參數，使得破解密鑰變為解決非安全橢圓曲線上的離散對數問題。研究者先后攻擊了 IEEE 802.15制定的加密方案（ECDH、ECIES和 ECMQV）[9]和蒙哥馬利算法實現的ECC[10]。

2) 符號變換故障攻擊[11]。通過注入故障改變乘運算中間變量的符號，Bl?mer成功攻擊了采用二進制非相鄰表示（NAF2）算法實現的ECC，但是密鑰恢復算法中仍存在“零塊失效”（密鑰中連續大量的零位所導致的密鑰恢復算法失效）問題。

3) 基于“漏操作”（skip instruction）的故障攻擊[12]。使橢圓曲線簽名算法在點乘運算執行過程中少執行幾次循環，有研究者通過分析故障簽名獲取部分密鑰，最終結合攻擊獲取完整密鑰。

分析表明，1)類、3)類攻擊方法的故障信息偏離了原有安全橢圓曲線，可通過檢測輸入、中間變量和輸出是否在原安全橢圓曲線上來進行防御[13]。由于符號變換故障并不使故障點偏離原安全橢圓曲線，上述措施對2)類攻擊是失效的。本文選取廣泛應用的基于滑動窗口算法的 ECC為研究對象，在點乘運算過程中引入符號變換故障，結合算法分析獲取密鑰。

1.2 本文工作

通過分析滑動窗口算法查表特性，分別基于倍點和加法運算的符號變換故障模型，給出了這 2種故障模型下的密鑰恢復過程，主要創新點如下。

1) 將符號變換故障攻擊思想引入至滑動窗口算法實現的ECC，在故障位置未知情況下，討論了倍點運算故障下的密鑰恢復過程，給出了能有效消除文獻[11]中“零塊失效”的密鑰恢復算法。仿真實驗表明：10～20個故障可在30min左右恢復完整NIST-192bit密鑰。因為這種故障分析方法主要針對倍點運算，所以對基于平方乘算法、固定窗口算法實現的ECC同樣具有威脅。

2) 基于滑動窗口算法查表特性，提出了針對查表操作的故障分析方法。仿真實驗表明：當故障精確注入到每次查表操作時，1min即可恢復完整密鑰。當故障僅注入到部分查表操作時，可恢復部分密鑰，1個故障可降低27～215的密鑰空間。

2 針對滑動窗口算法的故障攻擊

2.1 符號說明

GF(p), E：有p個元素的有限域，橢圓曲線為E。

P1, P2：橢圓曲線上的點為P1, P2。

P, k, Q, R：基點為P，私鑰為k，正確公鑰為Q，故障公鑰為R。

ki：私鑰NAF2表示的第i位為ki。

w, t：最大窗口寬度為w，算法執行中窗口的實際寬度為t。

ti：第i輪循環中窗口寬度為ti。

u, Pu：查表索引為u，查表得到的預計算值為Pu。

Qi：計算公鑰的中間變量為Qi。

2.2 橢圓曲線密碼

橢圓曲線密碼是一種基于橢圓曲線離散對數問題的公鑰密碼。定義在GF(p)上的橢圓曲線E為：y2=x3+ ax + b，其上的點可構成一個有限可交換群。令 P1=(x1, y1)∈E，則-P1=(x1,-y1)∈E，若 P2=(x2, y2)∈E，則 P1+P2=(x3,y3)，x3=(λ2-x1-x2)mod p, y3= (λ(x1-x3)-y1)mod p，其中：

前者 P1≠P2的情形稱為點加運算；后者 P1=P2的情形稱為點倍運算。對于給定橢圓曲線E,曲線上一點P以及正整數k，點kP計算稱為橢圓曲線上的點乘（標量乘），ECC主要根據點乘運算生成公鑰Q=kP。目前點乘運算的實現方式主要有平方乘算法、蒙哥馬利算法、固定窗口算法和滑動窗口算法等[14]。滑動窗口算法用二進制非相鄰表示型表示私鑰其中，ki∈{-1,0,1}，該方法可有效降低密鑰漢明重，提高計算效率，并能抵御計時[15]和功耗旁路攻擊[16]。本文主要針對滑動窗口算法展開故障分析研究。

算法1 滑動窗口算法

輸入：最大窗口w，私鑰NAF2(k)，基點P；

輸出：公鑰Q = kP；

1) 對于 i∈{1,3,…,2(2w-(-1)w/3-1)}，計算Pi= iP；

2) Q為無窮遠點，i = l-1；

3) while (i≥0) do；

① 若ki= 0, 則t =1, u =0；

② 否則，尋找滿足t≤w且u = (ki,…,ki-t+1) 為奇數時t的最大值；

③ Q = 2tQ；

④ 若 u ＞0, 則 Q = Q +Pu；

若 u ＜0, 則 Q = Q-P-u；

⑤ i = i-t；

4) 返回Q。

滑動窗口算法引入預計算表以提高密碼執行效率，但由于每次查表索引即為窗口中密鑰絕對值，攻擊者如果能夠在查表過程中注入故障，密鑰信息極有可能隨之泄露。此外，算法引入了變量 t和u來控制滑動窗口大小和滑動距離，使得不同密鑰對應窗口大小和滑動次數不同，增加了故障分析難度。下文將通過建立故障攻擊模型，進一步討論不同故障下的密鑰恢復過程。

2.3 針對滑動窗口算法的故障模型

故障模型通常指故障注入時機、位置、數目、寬度等。故障模型不同，產生的故障信息也不盡相同，對應的故障分析方法和結果也不同。需要說明的是故障攻擊包括故障注入和故障分析2個部分，本文主要研究故障分析方法，故障注入方法不作為本文研究重點，讀者可參考文獻[17]。下面給出本文符號變換故障攻擊模型。

如圖1所示，滑動窗口算法的最大窗口寬度w是固定的， t由當前待計算的密鑰值kj～ kj-w+1決定， t≤w。設一次點乘窗口滑動次數為 l，l不大于密鑰長度n。為形式化表示公鑰推算過程，用Pui表示第i輪循環中Pu或-P-u的值，即當u＞0時，Pui表示 Pu，當 u＜0時，Pui表示-P-u，則公鑰可表示為

從式(2)可知公鑰計算過程中與私鑰最相關的操作為算法 1中的第③和④步，即圖 1中倍點運算（a）和加法運算（b），因此本文選取到（a）、（b）2 處為故障注入位置；故障寬度為 1bit，僅改變符號位；故障數目由密鑰分片大小和實驗條件決定。下面分情況討論不同故障位置和注入時機對密鑰分析結果影響，以及具體的密鑰恢復過程。

2.4 故障位于倍點運算的故障分析

2.4.1 故障分析

依據算法1，首先根據當前待處理的密鑰值kj～kj-w+1計算得到ti（當kj=0時t=1），然后執行倍點運算（a）操作。若在第i-1輪（a）執行結束后注入一個符號變換故障，使得Qi→Qi’，則產生的故障公鑰可以表示為

圖1 針對滑動窗口算法的故障模型

當窗口滑動次數為 i且已計算的密鑰長度為 v時，Ui(Pu) = Lv(k)，那么式(4)可以轉化為

可見由于故障的引入，導致故障公鑰 R的產生，并且通過變換得到的正確公鑰 Q、故障公鑰R之間的函數關系式（5）與文獻[11]相同，可采用文獻[11]中的密鑰恢復算法進行密鑰推算。算法 4采用分而治之的思想逐片恢復密鑰（假設每個片段中都注入故障），由于片段中故障位置的任意性，將分 2種情況討論其對密鑰恢復過程的影響。

情況1 故障注入時當前待處理的密鑰位kj≠0，則u≠0，需查找預計算表并對Qi進行2次更新（乘法運算和加法運算）。

片段密鑰恢復過程如圖2所示：在n-i輪注入故障，設 Q + R= Tx，由式(5)可知 Tx= 2Li(k)。ks～ k0表示已恢復密鑰片段。恢復片段X的過程即尋找可能的組合，使其滿足其中，，滿足條件的 xs+r～xs+1即為 kj～ks+1。

圖2 u≠0時片段密鑰的恢復過程

情況 2 故障注入時當前待處理的密鑰位 kj=0，則u=0，不需要查找預計算表，對Qi只進行1次更新（只執行乘法運算）。

如圖3所示，kz1～kzr為0，假設故障注入于kzr處，使Qi+1產生符號變化，則由式(2)可得故障公鑰的表達式為

由于ti=1，因此有

同樣，如果將故障注入到kz1～kzr的任一位，均可得到Ri=R，說明u=0時故障注入分析結果等效于下一個查表操作（u≠0時）注入故障。所以滑動窗口算法故障攻擊中每次所恢復密鑰長度并不是與故障位置嚴格對應，而是與故障影響的密鑰位數密切相關。

圖3 u=0時片段密鑰的恢復過程

2.4.2 針對“零塊失效”的改進密鑰恢復算法

文獻[11]中密鑰恢復算法中的“零塊失效”（zero block failure）指密鑰中存在長段的連續0bit所導致的攻擊算法失效。這是由于相鄰2個故障之間密鑰位全是0，使得2片故障信息完全相同而無法確定中間0的個數。本文將出現“零塊”密鑰與臨近密鑰片段合并，對文獻[11]中的恢復算法加以改進。改進算法在出現“零塊”時仍然可在有效時間內恢復完整密鑰。

算法2 存在“零塊失效”的片段密鑰恢復算法

輸入：“零塊失效”出現時已恢復的密鑰片段k0～ks，“零塊失效”片段故障R1，“零塊失效”片段下一段故障R2，正確公鑰Q；

輸出：ks+1～ ks+w+r；

2) w = 1；

3) while ( w ＜ 2m) ；

4) for(所有的長度 r = 1, 2,…,m)do；

5) for(所有的二進制組合 x =(xs+1, xs+2,…,xs+r))do；

7) if ( Q + R2= Tx) then；

8) ks+1～ ks+w= 0；

9) else w = w + 1。

2.5 故障位于加法運算的故障分析

圖1中加法操作(b)只有在當前待計算的密鑰位kj≠0時才執行，并非任意位置都可以注入故障，所以本節討論情形在一定程度依賴于密鑰數值。下面就故障注入于運算(b)中2個不同變量分別討論。

2.5.1 針對變量Pu的故障分析

圖1中kj≠0時，需先執行查表操作再執行加法運算。文中假設故障注入到查表操作之后，令 Pu產生符號變換故障，即Pui→Pui’，產生故障信息為

從式(8)可知R僅與查表索引和故障密鑰位置j相關，因此一個故障僅能恢復一個窗口密鑰，下面給出故障位于Pu時的密鑰恢復算法。

算法3 故障位于Pu的密鑰恢復算法

輸入：最大窗口數w，正確公鑰Q，故障公鑰R；

輸出：密鑰k；

1) 設集合S={R|R表示故障公鑰}；

2) 初始化密鑰 kn-1～k0=0；

3) 根據 w 計算 X={xP|x=P,3P,…,2(2w- (-1)w/3-1)P}；

4) for（S中每一個元素）；

5) for（i=0; i＜n; i++）；

6) for（X中的每一個元素xP）；

7) if（2ixP+R=Q 或-2ixP+R=Q）；

8) 則 kj～kr=NAF2(x) ；

9) if（Q=kP），輸出 k。

對于一次特定的故障攻擊，最理想的情況是每次查找預計算表都能成功注入一個符號變換故障，利用算法3可成功恢復完整密鑰。但實際情況下，故障往往不能精確注入到每次滑動，此時算法 3僅能恢復產生故障的密鑰片段，需結合格攻擊恢復完整密鑰。格攻擊所需條件是已知三元組（si,mi,ki），即簽名、消息、部分私鑰(可根據公鑰獲取到簽名)[18]。Bob[15]等人通過監視Cache中預計算表的訪存時間差異，利用Cache旁路模板信息結合隱馬爾科夫模型，獲取到部分滑動窗口中的密鑰值，在不到一小時的時間恢復了160bit完整密鑰。這與本節的情形是一致的，具體細節請參閱文獻[15]。

2.5.2 針對變量Qi的故障分析

加法操作（b）中的 Qi也是可能的故障注入點，其故障分析類似于下一輪循環時（a）操作注入故障的分析過程，這里不再贅述。二者區別是：2.4節中將故障注入于（a）處，恢復的密鑰位為圖4中ki～ks+1，即從故障注入位至已恢復密鑰位；2.5節故障位于（b）處時，所恢復密鑰位為圖中kj～ks+1，即從故障位的下一窗口（非零窗口）至已恢復密鑰位。

圖4 故障位于（a）、（b）處恢復密鑰位區別

3 攻擊實驗

在普通 PC機（CPU為 Athlon 64 3000+1.81GHz，內存為1GB）上使用C++語言（Visual C++6.0環境）編程實現了本文ECC故障攻擊，其中，故障誘導是通過軟件模擬的。

利用 2.4節故障分析方法，對 OpenSSL0.9.8a中SECG和NIST X9.62提供的8條安全橢圓曲線進行了攻擊仿真實驗，密鑰長度為192bit，故障樣本數分別為30、20、15這3種。

實驗結果如圖5所示，結果表明以下3個結論。

1) 在相同曲線條件下，3組實驗的攻擊時間有明顯不同。攻擊時間差異是由于密鑰片段大小m決定了搜索空間3m，故障樣本數越大，密鑰片段越小，攻擊時間越短。

2) 在相同故障樣本下，11條曲線的攻擊時間有明顯不同。攻擊時間差異主要是由點乘運算開銷M所引起的，即基域越大，點乘運算開銷越大。

3) 基域相同的 3條曲線（NIST 192、NIST 192v2、NIST 192v3）攻擊時間差異不大。這是由于相同基域下的曲線參數 a、b和基點對點乘運算的影響不大。

由于OpenSSL0.9.8a中自動生成的密鑰不存在大段的連續的零，為驗證算法 2，將密鑰中的一段置零，再對NIST 192 3條曲線進行故障攻擊（樣本量選取 20）。當出現“零塊”時調用算法 2，攻擊時間如圖5所示：攻擊時間比不存在“零塊”的密鑰多耗時70s左右，多余耗時主要消耗在合并密鑰塊的窮舉上。同時作者發現出現“零塊”的位置與攻擊時間也密切相關，即出現“零塊”時已知的密鑰位越多，算法2進行窮舉時點乘開銷越大，完成攻擊所需時間越多。

圖5 針對不同曲線參數恢復192bit完整密鑰所需時間

表1 針對不同密鑰、不同故障樣本的密鑰搜索空間

利用 2.5節中針對 Pu的故障分析方法，針對NIST 192的3個不同私鑰k進行故障攻擊，表1給出了不同私鑰、不同故障數樣本數的密鑰搜索空間。在每次滑動都能引入故障的情況下，恢復完整密鑰僅需1min；當故障不能精確注入到每一次滑動時，1個故障大約可以將密鑰空間降低27～215。R?mer[19]證明了在已知 12bit的密鑰和 50個簽名的情況下，格攻擊成功率可達到99%。所以利用算法 3結合攻擊，3～5個故障樣本即可恢復完整密鑰。

現有 ECC故障攻擊研究大都在仿真環境下進行，且已發表文獻中尚未有針對滑動窗口算法的ECC故障攻擊。基于符號變換的ECC故障攻擊只有一例[12]，主要針對采用 NAF2實現點乘的ECC，文中也并沒有給出具體攻擊時間。本文針對滑動窗口算法實現的 ECC進行了故障攻擊仿真實驗，給出了一種可消除了“零塊失效”問題的改進算法，通過改變故障注入點提出了一種新的故障分析方法，對不同基域下的ECC進行了攻擊仿真實驗，并給出了恢復完整密鑰所需時間。由于點乘運算實現方式中都存在倍點運算，故2.4節的故障分析方法也適用于其他采用點乘運算的密碼算法。

4 結束語

在故障攻擊方面主要有3個研究方向：故障注入、故障分析、故障攻擊檢測與防護，本文主要對滑動窗口算法的橢圓曲線密碼故障分析進行了研究，并通過軟件仿真進行了驗證。以下方面值得在將來進行后續研究和關注：第一，研究FPGA上的故障注入方法，利用文中故障分析方法，開展對ECC故障攻擊物理實驗；第二，研究ECC故障攻擊檢測與防護措施。

[1] KOEUNE F, STANDAERT F X. A tutorial on physical security and side-channel attacks[A]. Foundations of Security Analysis and Design III: FOSAD 2004/2005 Tutorial Lectures[C]. Forli, Italy, 2005.78-108.

[2] BONEH D, DEMILLO R, LIPTON R. On the importance of checking cryptographic protocols for faults[A]. Eurocrypt 1997[C]. Konstanz,Germany, 1997. 37-51.

[3] MUKHPOADHYAY D. An improved fault based attack of the advanced encryption standard[A]. AFRICACRYPT 2009[C]. Gammarth,Tunisia, 2009. 421-434.

[4] 李瑋, 谷大武. 基于密鑰編排故障的SMS4算法的差分故障分析[J].通信學報, 2008, 29(10): 135-142.LI W, GU D W. Differential fault analysis on the SMS4 cipher by schedule[J]. Journal on Communications, 2008, 29(10):135-142.

[5] 趙新杰, 王韜, 王素貞等. 針對 MIBS的深度差分故障分析[J]. 通信學報, 2010, 31(12): 82-89.ZHAO X J, WANG T, WANG S Z, et al. Research on deep differntial fault analysis against MIBS[J]. Journal on Communications, 2010,31(12): 82-89.

[6] BIHAM E, GRANBOULAN L, NGUYN P Q. Impossible fault analysis of RC4 and differential fault analysis of RC4[A]. FSE 2005[C].Lisbon, Portugal, 2005. 359-367.

[7] CORON J S. Resistance against differential power analysis for elliptic curve cryptosystems[A]. CHES 1999[C]. Massachusetts, USA, 1999.292-302.

[8] BIEHL I, MEYER B, MLLER V. Differential fault attacks on elliptic curve cryptosystems[A]. CRYPTO 2000[C]. Berlin, Germany, 2000.131-146.

[9] ANTIPA A, DANIEL B, MENEZES A, et al. Validation of elliptic curve public keys[A]. PKC 2003[C]. Miami, USA, 2003.211-223.

[10] FOUQUE P A, LERCIER R. Fault attack on elliptic curve with montgomery ladder implementation[A]. FDTC 2008[C]. Washington DC,USA, 2008. 92-98.

[11] BLOMER J, OTTO M, SEIFERT J P. Sign change fault attacks on elliptic curve cryptosystems[A]. FDTC 2006[C]. Yokohama, Japan,2006. 36-52.

[12] SCHMIDT J M, MEDWED M. A fault attack on ECDSA[A]. FDTC 2009[C]. Lausanne, Switzerland, 2009. 93-99

[13] EBEID N, LAMBERT B. Securing the elliptic curve montgomery ladder against fault attacks[A]. FDTC 2009[C]. Lausanne, Switzerland,2009. 46-50.

[14] 王潮, 時向勇,牛志華. 基于Montgomery曲線改進ECDSA算法的研究[J]. 通信學報, 2010, 31(1): 9-13.WANG C, SHI X Y, NIU Z H. The research of the promotion for ECDSA algorithm based on Montgomery-form ECC[J]. Journal on Communications, 2010, 31(1): 9-13.

[15] BRUMLEY B B, RISTO M H. Cache-timing template attacks[A].ASIACRYPT 2009[C]. Tokyo, Japan, 2009. 667-684.

[16] REDDY E K. Elliptic curve cryptosystems and side-channel attacks[J]. International Journal of Network Security, 2011,12(3): 151-158.

[17] GIRAUD C, THIEBEAULD H. A survey on fault attacks[A].CARDIS 2004[C]. Toulouse, France, 2004. 22-27.

[18] SMART N P, GRAHAM N H. Lattice attacks on digital signature schemes[J]. Codes and Cryptography, 2001, 23(3): 283-290.

[19] ROMER T, SEIFERT J P. Information leakage attacks against smart card implementations of the elliptic curve digital signature algorithm[A]. E-smart 2001[C]. Cannes, France, 2001. 211-219.