针对滑动窗口算法的椭圆曲线密码故障分析

张金中，寇应展，王韬，郭世泽，赵新杰

(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.