计算机应用   2016, Vol. 36 Issue (12): 3328-3332  DOI: 10.11772/j.issn.1001-9081.2016.12.3328
0

引用本文 

许盛伟, 陈诚, 王荣荣. 针对椭圆曲线密码系统点乘算法的改进差分故障攻击[J]. 计算机应用, 2016, 36(12): 3328-3332.DOI: 10.11772/j.issn.1001-9081.2016.12.3328.
XU Shengwei, CHEN Cheng, WANG Rongrong. Improved differential fault attack on scalar multiplication algorithm in elliptic curve cryptosystem[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(12): 3328-3332. DOI: 10.11772/j.issn.1001-9081.2016.12.3328.

通信作者

陈诚(1990-), 女, 湖北随州人, 硕士研究生, 主要研究方向:保密通信、信息安全、商用密码算法、商用密码应用.E-mail: chelsea_chencheng@126.com

作者简介

许盛伟(1976-), 男, 江西吉安人, 副教授, 博士, 主要研究方向:保密通信、信息安全、公钥密码应用;
王荣荣(1991-), 女, 山东临沂人, 硕士研究生, 主要研究方向:保密通信、信息安全、公钥密码应用

文章历史

收稿日期:2016-05-11
修回日期:2016-06-23
针对椭圆曲线密码系统点乘算法的改进差分故障攻击
许盛伟1,2, 陈诚1,2, 王荣荣1,2    
1. 北京电子科技学院, 北京 100070 ;
2. 西安电子科技大学 通信工程学院, 西安 710071
摘要: 针对故障攻击椭圆曲线点乘算法失效问题,提出一种改进的差分故障攻击算法。该算法消除了非零块的假设,并引入验证机制抵抗了“故障检测”失效威胁。以SM2算法提供的椭圆曲线为例,通过软件仿真成功攻击了二进制点乘算法、二进制非相邻型(NAF)点乘算法和蒙哥马利点乘算法,3小时内恢复出了256比特私钥。针对二进制NAF点乘算法攻击过程进行了优化,将攻击时间缩短至原来的五分之一。实验结果表明,所提算法能够提高攻击的有效性。
关键词: 椭圆曲线密码系统    点乘算法    差分故障攻击    零块失效    故障检测    
Improved differential fault attack on scalar multiplication algorithm in elliptic curve cryptosystem
XU Shengwei1,2, CHEN Cheng1,2, WANG Rongrong1,2     
1. Beijing Electronic Science & Technology Institute, Beijing 100070, China ;
2. School of Telecommunications Engineering, Xidian University, Xi'an Shaanxi 710071, China
Abstract: Concerning the failure problem of fault attack on elliptic curve scalar multiplication algorithm, an improved algorithm of differential fault attack was proposed. The nonzero assumption was eliminated, and an authentication mechanism was imported against the failure threat of "fault detection". Using the elliptic curve provided by SM2 algorithm, the binary scalar multiplication algorithm, binary Non-Adjacent Form (NAF) scalar multiplication algorithm and Montgomery scalar multiplication algorithm were successfully attacked with software simulation. The 256-bit private key was restored in three hours. The attacking process of binary NAF scalar multiplication algorithm was optimized, so the attack time was reduced to one fifth of the original one. The experimental results show that the proposed algorithm can improve the effectiveness of the attack.
Key words: Elliptic Curve Cryptosystem (ECC)    scalar multiplication algorithm    differential fault attack    zero block failure    fault detection    
0 引言

椭圆曲线密码系统(Elliptic Curve Cryptosystem,ECC)作为一种高效、安全的公钥密码方案越来越得到广泛应用,国家商用密码算法SM2作为一个ECC应用案例,其中最为重要的ECC点乘运算直接影响SM2算法的效率和安全。ECC点乘算法的安全性依托于有限域上椭圆曲线的点构成的Abel群离散对数难解性,目前关于该困难问题的分析复杂度是指数阶的。然而,引入边信道攻击(Side Channel Attack,SCA)的方法可以把恢复ECC私钥的问题复杂度降到多项式阶。 边信道攻击是指利用算法执行过程中泄露出来的电磁、功耗、故障、时间等有用信息,来恢复出算法的明文或私钥等敏感信息。文献[1-2]研究了ECC硬件实现的功耗攻击和防御措施,相关研究已经比较成熟。文献[3]提出差分故障攻击的思想,在算法执行过程中注入比特故障,分析故障传播与私钥之间的关系,可以恢复出私钥。但是在算法执行过程中的中间状态点上注入故障,会导致带故障的状态点和公钥结果都不在原来正确的椭圆曲线上,通过检测中间状态点或公钥结果将会发现异常,终止算法执行,使得攻击失败。这种现象称为“故障检测”[4]失效。文献[3]的差分故障攻击假设存在非零块,受到 “零块失效”[5]的威胁,即在攻击过程中,若密钥块为全零比特,则攻击失效。文献[5]针对椭圆曲线上有点压缩的情况提出了符号变换故障攻击,并且给出了解决“零块失效”的办法:若攻击失效则判定当前被攻击的密钥块为全零比特,将该密钥块与下一个待攻击的密钥块联立成一个新的密钥块求解。但增加密钥块长度就增加了局部攻击时间。根据椭圆曲线点压缩的规则,仍可检测到符号位发生异常,符号变换故障攻击方法仍受“故障检测”的威胁。

本文提出了一种改进的差分故障攻击算法,通过在故障注入时使带故障的中间状态点仍在原来正确的椭圆曲线上,从而解决“故障检测”失效的问题。并且,改进的差分故障攻击算法各个密钥块之间互不干扰,不受全零块的影响,也能避免“零块失效”的威胁。然后用软件仿真方式模拟实现故障注入,参考SM2提供的椭圆曲线Fp-256,对3种常见点乘算法进行攻击,恢复了全部私钥。实验表明,改进差分故障攻击算法的确可以有效避免“故障检测”和“零块失效”的问题,密钥片段选择log(log (log(q))) (q为椭圆曲线的阶)为最佳。在对二进制非相邻型(Non-Adjacent Form,NAF)点乘算法攻击的过程中,另写一个进程对已经恢复出来的部分私钥进行同步NAF编码,使得攻击时间缩短至原来的五分之一。最后给出了防御差分故障攻击的建议。

1 椭圆曲线密码及其基本运算

椭圆曲线密码是一种基于有限域上椭圆曲线离散对数问题的公钥密码,具有密钥长度更短、安全性更高的优点。下面介绍椭圆曲线的基础知识和基本运算。

定义1 有限域K上的椭圆曲线E由如下方程[6]定义:

$E:{{y}^{2}}+{{a}_{1}}xy+{{a}_{3}}y={{x}^{3}}+{{a}_{2}}{{x}^{2}}+{{a}_{4}}x+{{a}_{6}}$ (1)

其中a1,a2,a3,a4,a6∈K。 椭圆曲线E(K)上的点的集合为:

$\begin{align} & E\left( K \right)=\left\{ \left( x,y \right) \right.\in K\times K:{{y}^{2}}+{{a}_{1}}xy+ \\ & {{a}_{3}}y-{{x}^{3}}-{{a}_{2}}{{x}^{2}}-\left. {{a}_{4}}x-{{a}_{6}}=0 \right\}\bigcup{\left\{ O \right\}} \\ \end{align}$ (2)

其中O为无穷远点。

椭圆曲线E(K)上的点加运算满足:对于所有的PE∈E(K),有PE+OE=OE+PE=PE;对于所有的PE=(x,y)E,有-PE=(x,-y-a1x-a3)E(其中PE-PE=OE)。 设(x1,y1)E+(x2,y2)E=(x3,y3)E,则:

${{x}_{3}}={{\lambda }^{2}}+{{a}_{1}}\lambda -{{a}_{2}}-{{x}_{1}}-{{x}_{2}}$ (3)
${{y}_{3}}=\left( {{x}_{1}}-{{x}_{3}} \right)\lambda -{{y}_{1}}-{{a}_{1}}{{x}_{3}}-{{a}_{3}}$ (4)
$\lambda =\left\{ \begin{align} &\frac{3x_{1}^{2}+2{{a}_{2}}{{x}_{1}}+{{a}_{4}}-{{a}_{1}}{{y}_{1}}}{2{{y}_{1}}+{{a}_{1}}{{x}_{1}}+{{a}_{3}}},{{x}_{1}}=x,{{y}_{1}}={{y}_{2}} \\ &\frac{{{y}_{1}}-{{y}_{2}}}{{{x}_{1}}-{{x}_{2}}},其他 \\ \end{align} \right.$ (5)

式中,x1=x2,y1=y2的情形对应的运算也称为倍点运算。点加运算和倍点运算组合使用可以构成不同的点乘算法。由于点乘算法影响着ECC密码应用的实现速度和安全,点乘算法的快速实现和安全性显得尤为重要。常见的3种ECC点乘运算[7-8]的具体实现如下:

算法1  二进制从左至右点乘算法。

输入 k(kl-1,kl-2,…,k0)2,P∈E; 输出 Q=k·P。

1) Q=O;

2) For i=l-1 down to 0

2.1) Q=2Q;

2.2) If (ki==1) then Q=Q+P;

3) Return(Q)

从右至左点乘算法于此类似,平均需要l(l为k的比特长度)次倍点运算和l/2次点加运算。

算法2  二进制NAF点乘算法。

输入 k(kl-1,kl-2,…,k0)2,P∈E; 输出 Q=k·P。

1) 计算kNAF=(kl,kl-1,kl-2,…,k0)NAF[9],其中ki∈{0,1,-1}(i=0,1,…,l);

2) Q=O

3) For i=l-1 down to 0

2.1) Q=2Q;

2.2) If (ki==1) then Q=Q+P;

2.3) If (ki==-1) then Q=Q-P;

4) Return(Q)

k经过NAF编码后,其非零元素的个数减少,对应的点加(点减)次数减少,算法2平均需要l次倍点运算和l/3次点加运算。

算法3  Montgomery点乘算法。

输入 k(kl-1,kl-2,…,k0)2,P∈E;

输出 Q=k·P

1) Q=P,T=2P;

2) For i=l-2 down to 0

2.1) If (ki==1) then T=Q+T,T=2T;

2.2) If (ki==0) then T=Q+T,Q=2Q;

3) Return(Q)

Montgomery点乘算法在每轮迭代中的点加运算和倍点运算可以同时进行,平均需要l次倍点运算和l/2次点加运算。

2 差分故障攻击 2.1 故障注入模型

故障攻击通常由两个部分组成:故障注入以及故障分析。故障注入模型中的故障往往为随机的一比特翻转故障,注入方法多样。对于硬件而言,可以使用精密设备通过改变温度、电压或者电磁干扰等方法,使得计算中的变量发生一比特翻转故障;对于软件而言,可以采用异或的方式使得计算中的变量发生一比特翻转故障。令Q(i)和P(i)分别表示第i轮迭代前,变量Q和P的中间状态值。Q(i)注入一比特翻转错误后表示为(i),P(i)注入一比特翻转错误后表示为(i)

2.2 一般故障攻击

一般故障攻击包括差分故障攻击[3]和符号变换故障攻击[5]

差分故障攻击[3]的步骤是:给ECC点乘计算设备(如密码芯片)输入基点P,经过l轮运算,得到正确的公钥Q;再次输入基点P,在第i(l-m≤i<l)轮迭代中,随机注入一比特故障到中间状态点Q(i)上,得到带故障信息的中间状态点(i),完成剩余的l-i轮运算,得到带故障信息的公钥(l);将(l)与正确的公钥Q比较,由于假设私钥k的连续m位中至少有一个非零比特,可以通过遍历的方法找到故障注入的位置,并恢复出私钥k的最低m位;以此类推,可以恢复出未知密钥的最低连续m位;重复上述操作可以恢复出全部私钥k。

符号变换故障攻击[5]与差分故障攻击的分析方法类似,区别仅在于故障注入位置不同。以算法2为例,由于对椭圆曲线上的点进行了压缩处理,所以椭圆曲线上的点P(x,y)中,y只有1比特,称为符号位。在进行Q+P运算时,若改变点P的符号位,则变成Q-P运算。符号变换故障攻击的故障注入位置为算法2的第2.2) 或2.3) 步骤中点P的符号位。差分故障攻击的故障注入位置可以是点P,也可以是点Q。

为方便与下面介绍的改进算法进行对比,文中暂将差分故障攻击和符号变换故障攻击简称为一般故障攻击。

2.3 改进的差分故障攻击

使用一般故障攻击方案时,如果检查点乘执行过程中的中间状态点或者最后的结果点是否在原来正确的椭圆曲线上,则会发现异常,终止操作,使得攻击失败;而改进差分故障攻击方案将故障注入到x坐标值上,并计算相应的y坐标值,使得注入故障后的点仍在原来正确的椭圆曲线上,经过点加和倍点后的最终结果点也在原来正确的椭圆曲线上,这样就避免了“故障检测”的威胁。

一般故障攻击在对每个私钥块进行恢复时,需要假设长度大于或等于m的私钥块中必须有非零比特,猜测密钥块时也假定最高位为“1”,这样使得私钥中出现连续m个“0”时攻击失效,也称为“零块失效”[9]。改进攻击算法中不需要这一假设,也可以寻找到故障注入位置,所以,私钥k中可以出现m长的全零块。

对于一般故障攻击,通过检测中间状态点或公钥结果点,判断这些点是否在原来正确的椭圆曲线上或符号位是否符合点压缩规则,可以发现异常,使得攻击失败。改进攻击算法在注入故障的时候加入了验证机制(即将故障注入到x坐标值上,并计算相应的y坐标值),保证注入故障后的点和输出结果点仍在原来正确的椭圆曲线上或符号位符合点压缩规则,不会发现异常,确保攻击正常进行。

下面提出的改进差分故障攻击算法在没有增加平均故障个数和攻击复杂度的基础上,成功避免了“零块失效”和“故障检测”的问题,增强了攻击的可行性。此外,最佳密钥片段长度m选择log(log(log(q)))(q为椭圆曲线的阶)。当攻击二进制NAF点乘算法时,密钥恢复过程中加入同步的NAF编码,可以使攻击时间更短。

本文讨论的椭圆曲线E均为非奇异的[10],并且可以对同一基点P重复计算k·P。算法1~算法3的结构相似(都有点加和倍点运算),迭代次数几乎相同(算法3的迭代次数少1) ,所以改进的攻击方案对这三种点乘算法的攻击效果相同。故障注入位置放在点乘算法每轮计算的倍点运算或者点加运算之前的效果一样(并且故障注入位置可以是点P,也可以是点Q),下面仅讨论故障注入位置为倍点运算之前的情况。假设已知私钥k的长度为l。在私钥恢复过程中,设${\rm{t}} \ge \left\lceil {1/m} \right\rceil $,将私钥(kl-1,kl-2,…,k0)2分成t个block(blockt-1,blockt-2,…,block0),其中对于i=0,1,…,t-1,blocki的比特长度不超过m。假设每次只在一个block中随机注入一比特翻转错误,且错误注入到x坐标值中。

算法4 改进的差分故障攻击算法。

1) 输入P∈E,经过l轮迭代之后得到正确的Q(l)=Q=k·P。令b=0,B=0。

2) while (B<l),此时已知私钥k的低B比特,执行步骤3) ~6) (若最后一个block长度小于m,不影响操作,在计算时k的最高位取到kl-1)。

3) 输入P∈E,按照点乘算法迭代执行,在私钥k的blockb块迭代运算过程中,随机注入一比特翻转错误到某个中间状态的Q(i)的x坐标值上(假设注入位置为算法1的2.1) 步运算之前的Q值),记为x′,将x′代入方程(1) ,若能解出y′(即y′为有限域K上的整数,若有两个解则按规则取y值。若对y值有压缩,则按照点压缩规则取值),则(x′,y′)为点(i)的坐标;若不能解出y′,则在Q(i)的x值上另一个位置注入一比特错误,重复步骤3) 操作。

4) 完成剩余迭代操作,最后获得错误的(l)(这样点(i)(x′,y′)仍在椭圆曲线E上,或者符合点压缩规则,可以避免“故障检测”)。

5) 设l-B-m-1≤j<j′<l-B,执行步骤6) ,找到注入故障的轮数j′(现在已知Q(l)(l),步骤5) 和步骤6) 的目的是找到错误注入的位置j′,并恢复出私钥的部分比特)。

6) 假设i=j′,u∈{0,1,-1}al-i-B,遍历u。已知Q(i)=(Qa(l)-aP)/2l-i。当B=0时,a=u=(u0,u1,…,ul-i-1)2,计算(l)=2(…2(2(2a(i)⊕u0P)⊕u1P)⊕…)⊕ul-i-1P;当B>0时,a=(u0,u1,…,ul-i-B-1,kB-1,…,k1,k0)2,计算a(l)=2(…2(2(2(…2(2(2a(i)⊕u0P)⊕u1P)⊕…)⊕ul-i-B-1P)⊕kB-1P)⊕…)⊕k0P。若满足下面的条件,就找到了注入故障的轮数j′:每次选定i和u时,计算Qu(i),改变一比特值得到u(i)并计算u(l),判断u(l)是否等于u(l)。若没有满足(l)=u(l)的i,则令j=j′,并跳转到步骤5) ;若找到满足(l)=(l)的i,则j′=i,并且得到关于私钥k的未知部分的低(l-j′-B)比特值(之前已经恢复出低B个比特值(kB-1,…,k1,k0)),即(kl-j′-1,kl-j′-2,…,kB)=(u0,u1,…,ul-j′-B-1),令b=b+1,B=l-j′,跳转到步骤2) 。

7) 输出(kl-1,kl-2,…,k0)。

步骤6) 中,针对算法1和算法3,取u∈{0,1}l-i-B;针对算法2,取u∈{0,1,-1}l-i-B。每个block的大小是动态划分的,总是以私钥k的未知部分的低m位作为下一个注入错误的block图 1可以帮助理解每次注入错误的位置。

图 1 一比特故障注入位置

假设椭圆曲线E的阶为q,令m=O(log(log(log(q)))),私钥k的长度为l比特。因为在连续m个比特串中随机选择注入位置,所以恢复全部密钥需要注入t=O((l/m)log m)个错误。第一次注入错误后,恢复block0所需的点操作次数为(l/(log l))(m2/(log m))2m;第二次注入错误后,恢复block1所需的点操作次数为(l/(log l))(2m2/(log m))2m;以此类推,第t次注入错误后,恢复blockt-1所需的点操作次数为(l/(log l))(tm2/(log m))2m,所以从算法1和算法3中恢复出私钥k需O(2m(log q)3(log m)/log l)次点操作。同理,从算法2中恢复出私钥k需O(3m(log q)3(log m)/log l)次点操作。使用算法4对不同点乘算法进行攻击,注入的故障类型都为随机一比特翻转,且都可以攻击成功,不同算法对应的注入故障次数与恢复全部私钥需要的点操作次数如表 1所示。

表 1 不同点乘算法恢复私钥的情况

算法4的步骤3) 和4) 中,对软件或硬件实现的点乘算法的中间状态Q(i)均可实现故障注入,得到带有故障信息的${\tilde{Q}}$(i),最后算出有故障的结果${\tilde{Q}}$(l)。同理,步骤5) 和6) 中的故障注入和椭圆曲线点加运算和倍点运算也可以在软硬件平台实现,可根据需要编写合适的攻击代码。所以,上述改进的差分故障攻击方案对软件实现和硬件实现的ECC点乘算法均可攻击。另外,软件实现的故障注入是通过异或操作使得一比特翻转,而硬件的故障注入需要特殊设备,并且软件实现点乘的部分操作更方便,实验环境更简单,本文将采用软件仿真的方法实现故障攻击。

3 实验结果分析

为了便于操作,本文对软件实现的点乘算法进行攻击,采用异或的方法对某一比特实施翻转操作,模拟故障注入。实验环境为普通PC(CPU为Inter Core i5-2450m 2.50GHz,内存为2GB),编译环境为Visual Studio 2012。分别采用一般故障攻击方法和改进的差分故障攻击方法对3种ECC点乘算法进行攻击,并在软件实现的代码中加入验证机制。攻击实验采用的椭圆曲线参考SM2算法提供的Fp-256,其中椭圆曲线参数(如素数p、系数a和b、基点P的横坐标和纵坐标等)均为256比特,私钥k也为256比特。下面分别从三个方面进行实验。

3.1 一般故障攻击与改进差分故障攻击的比较

针对SM2加解密算法中Fp-256椭圆曲线,在由私钥计算公钥的点乘算法过程中,分别用一般故障攻击方法(由于文献[2]的攻击方法与文献[5]的攻击方法仅故障注入的变量不同,分析方法一致,所以表 2中的实验以文献[2]的攻击方法为例)和本文提出的改进差分故障攻击方法恢复256比特长的私钥k。这里对两个私钥(k1′ 和k2′)进行恢复,并且讨论密钥片段长度m=4的情况。其中k1′的全零块长度小于4,k2′存在长度大于4的全零块。表 2中k1′和k2′表示用一般故障攻击,k1″和k2″表示用改进差分故障攻击,实际攻击结果如下。

表 2 两种攻击方法关于“零块失效”的对比

两种攻击方法恢复全部私钥所需注入的平均故障个数相同。表 2中k1′和k1″的结果分别为181min和185min,说明改进差分故障攻击的时间没有明显增加;k2′和k2″的结果说明一般故障攻击遇到长度大于m的全零密钥块时攻击失败,改进差分故障攻击则攻击成功。

检测点乘计算的结果点是否在原来正确的椭圆曲线上或符号位是否符合点压缩规则。由于改进的差分故障攻击方法自带验证机制,保证了带故障信息的中间状态点和点乘结果点不会被检测到异常,可以抵抗“故障检测”的威胁;一般故障攻击方法没有验证机制,遇到检测则攻击失败。

表 3 不同攻击方案的效果比较

实验结果表明:一般故障攻击方案加入“故障检测”,则攻击失败;改进差分故障攻击方案加入“故障检测”,攻击成功。一般故障攻击方案中,若私钥k出现长度大于m的连续“0”,文献[3]方案攻击失败,文献[5]方案攻击失败;改进差分故障攻击方案中,若私钥k出现长度大于m的连续“0”,攻击成功。如表 3所示,改进差分故障攻击的健壮性更强。

3.2 密钥片段长度对攻击时间的影响

用本文的改进差分故障攻击方法对256比特长的私钥k进行攻击,当密钥片段长度m分别为2、4、6、8时,恢复出全部私钥所需注入的平均故障个数和恢复出全部私钥所需的攻击时间如表 4所示。

表 4 不同密钥片段的实验结果对比

实验结果表明当密钥片段长度m增加时,需要注入的平均故障个数相差不大,都是可以接受的范围。恢复全部私钥k的攻击时间随着密钥片段长度的增加而显著增长。当度m=2和m=4时,总的攻击时间相同,均为3.1h;当m=6和8时,攻击时间分别为12.3h和49.8h。恢复全部私钥所需注入的平均故障个数和总攻击时间的实验结果与第2.3节的理论值基本一致。密钥片段选择log(log(log(q)))(q为椭圆曲线的阶)时攻击时间最短,当椭圆曲线的素数p为256比特长时,密钥片段长度m选择4。

3.3 攻击三种点乘算法

用改进的差分故障攻击方法(即算法4) 对算法1、算法2、算法2′以及算法3进行攻击,私钥长度为256,密钥片段长度选择4。算法2中每个密钥比特有三种取值(ki∈{0,1,-1}),算法2′是对算法2的改进,具体改进方法是提前对2m种密钥片段分别进行NAF编码并存储,若已恢复出部分密钥比特(即部分密钥比特为已知时),编程时可以另外建一个进程计算已知密钥比特的NAF编码,在密钥恢复过程的算法4中第6) 步仍遍历,u∈{0,1}l-i-B,但计算时调用对应的NAF编码。实验结果见表 5

表 5 攻击不同点乘算法所用时间对比

对不同的点乘算法进行攻击时,恢复全部私钥所需注入的平均故障个数相同。对算法1和算法3的攻击时间相同;算法2′是对算法2的优化,前者的攻击时间约为后者的五分之一,如表 5所示。攻击算法2′的时间甚至比攻击算法1的时间更短,因为密钥k经过NAF编码后非零比特数减少。

综上所述,实验结果与理论值基本一致。2.3节提出的改进差分故障攻击方案可以恢复出私钥k的全部比特,并且有效避免了“零块失效”和“故障检测”的问题,比一般故障攻击方案更有效。此外,改进差分故障攻击方案没有增加恢复全部私钥需要注入的平均故障个数和攻击复杂度。后两个实验均采用改进的差分故障攻击方案,所以都具有上述优点。攻击时密钥片段长度不同,攻击时间也不同,最佳密钥片段长度选择log(log(log(q)))(q为椭圆曲线的阶)。改进的差分故障攻击方案可以有效攻击从左至右点乘算法、二进制NAF点乘算法和Montgomery点乘算法。当攻击二进制NAF点乘算法时,作一些优化可以使攻击时间更短。

4 防御措施

本文提出的故障攻击方案可对软件实现和硬件实现的ECC点乘算法进行攻击,第3章攻击实验中的故障诱导是通过软件模拟实现的。在现实场景中,建议密码算法的计算全过程都要在安全的环境下进行,防止攻击者能够获取中间状态的计算值以及注入故障。例如在受保护的内存或芯片中进行计算,这样可以降低故障注入的风险。

5 结语

本文利用提出的改进差分故障攻击算法对几种常见的ECC点乘算法进行攻击,该攻击算法不受“故障检测”和“零块失效”的干扰,仍能恢复全部私钥,而一般故障攻击方法遇到这两个问题会使攻击失败。与一般故障攻击方法相比,改进差分故障攻击方法没有明显增加攻击时间和平均故障个数。通过软件仿真实现对SM2提供参考的椭圆曲线FP-256进行攻击,实验结果表明改进差分故障攻击算法具有上述优点,密钥片段长度选择log(log(log(q)))(q为椭圆曲线的阶)为宜。对二进制NAF点乘算法进行攻击时作了一些优化,大大缩减了攻击时间。下一步工作将思考如何攻击comb点乘算法,以及如何从算法上防御故障攻击。

参考文献
[1] 李浪, 李仁发, 童元满, 等. 嵌入式加密芯片功耗分析攻击与防御研究进展[J]. 计算机研究与发展, 2010, 47 (4) : 595-604. ( LI L, LI R F, TONG Y M, et al. Development on power analysis attack and defense of embedded cipher chip[J]. Journal of Computer Research and Development, 2010, 47 (4) : 595-604. )
[2] 李浪, 杨柳, 李肯立, 等. 一种椭圆曲线密码算法ECC旁路攻击方法研究[J]. 计算机应用研究, 2013, 30 (3) : 889-890. ( LI L, YANG L, LI K L, et al. Research on side-channel attack methods of ECC[J]. Application Research of Computers, 2013, 30 (3) : 889-890. )
[3] BIEHL I, MEYER B, MVLLER V. Differential fault attacks on elliptic curve cryptosystems[C]//CRYPTO'00:Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, LNCS 1880. Berlin:Springer, 2000:131-146.
[4] EBEID N, LAMBERT R. Securing the elliptic curve Montgomery ladder against fault attacks[C]//FDTC'09:Proceedings of the 2009 Workshop on Fault Diagnosis and Tolerance in Cryptography. Washington, DC:IEEE Computer Society, 2009:46-50.
[5] 张金中, 寇应展, 王韬, 等. 针对滑动窗口算法的椭圆曲线密码故障分析[J]. 通信学报, 2012, 33 (1) : 71-78. ( ZHANG J Z, KOU Y Z, WANG T, et al. Fault analysis on elliptic curve cryptosystems with sliding window method[J]. Journal on Communications, 2012, 33 (1) : 71-78. )
[6] ANDREAS E.椭圆曲线及其在密码学中的应用——导引[M].吴铤,董军武,王明强,译.北京:科学出版社,2007:11-20. ( ANDREAS E. Elliptic curves and their applications to cryptography:an introduction[M]. WU T, DONG J W, WANG M Q, translated. Beijing:Science Press, 2007:11-20. )
[7] 赵前进.椭圆曲线密码点乘算法的并行调度研究[D].郑州:信息工程大学,2010:19-23. ( ZHAO Q J. Research on parallel schedule of scalar multiplication of elliptic curve cryptography[D]. Zhengzhou:Information Engineering University, 2010:19-23. ) http://cdmd.cnki.com.cn/Article/CDMD-90008-1011271132.htm
[8] 刘红明.公钥密码的抗边信道攻击研究与实现[D].上海:上海交通大学,2014:72-78. ( LIU H M. Research and implementation of countermeasures against side channel attacks for public key[D]. Shanghai:Shanghai Jiao Tong University, 2014:72-78. ) http://cdmd.cnki.com.cn/Article/CDMD-10248-1015033237.htm
[9] BLÖMER J, OTTO M, SEIFERT J P. Sign change fault attacks on elliptic curve cryptosystems[C]//FDTC 2006:Proceedings of the Third International Workshop on Fault Diagnosis and Tolerance in Cryptography, LNCS 4236. Berlin:Springer, 2006:36-52.
[10] 肖攸安. 椭圆曲线密码体系研究[M]. 武汉: 华中科技大学出版社, 2006 : 41 -46. ( XIAO Y A. Research on Elliptic Curves Cryptography[M]. Wuhan: Huazhong University of Science and Technology Press, 2006 : 41 -46. )