一种高效的安全SoC芯片抗功耗攻击方案

2017-12-12杨颖辉

实验室研究与探索 2017年10期

关键词：标量整数功耗

杨苏，杨颖辉

(河南牧业经济学院 a.实践教学设备管理处； b.信息与电子工程学院，郑州 450044)

一种高效的安全SoC芯片抗功耗攻击方案

杨苏a，杨颖辉b

(河南牧业经济学院 a.实践教学设备管理处； b.信息与电子工程学院，郑州 450044)

安全芯片有资源受限的问题，这致使椭圆曲线密码算法抵抗功耗攻击的方案在效率和安全两方面产生了矛盾。首先利用带符号的整数拆分形式对标量进行编码，并采用预计算和标量分割技术把标量乘运算变换成一组椭圆曲线上的点的点加运算，进而利用基点掩码实现椭圆曲线密码的抗功耗攻击。算法安全性及性能分析结果表明，基于整数拆分的抗功耗攻击方案的运算效率与传统的抗功耗攻击方法相比明显提高，可以很好地满足安全芯片等资源受限的应用系统。

椭圆曲线密码；功耗攻击分析；整数拆分形式；多标量乘算法

0 引言

功耗攻击技术是1998年由Paul Kocher率先提出的一种利用芯片工作时泄露的功耗信息来获取密钥信息的密码分析方法，这种攻击方法实现简单，攻击成功率高，比传统的数学攻击方法具有更大的威胁[1-4]。根据攻击手段不同，可分为简单功耗分析(Simple Power Attack, SPA)与差分功耗分析(Differential Power Attack, DPA)。由于椭圆曲线密码算法(Elliptic Curve Cryptogram, ECC)与其他传统公钥密码算法相比，在相同安全级别下需要的密钥更短，存储空间更小的优点，更适合密码芯片等资源受限的设备，所以出现大量针对椭圆曲线密码的功耗攻击。目前，主要有零值寄存器功耗分析(Zero-value Power Analysis, ZPA)和零值点功耗分析(Refined Power Analysis, RPA)[5-8]。本文通过对标量进行带符号整数拆分形式编码(signed integer splitting form, SISF)，将大标量乘运算转换成一组带系数的由固定且已知标量的小标量乘运算累加和的形式，然后利用标量分割随机化技术，并结合预计算表方法，提出一种椭圆曲线密码的抗功耗攻击方案，可以满足密码芯片等资源受限系统兼顾效率和安全的需求。

1 背景知识介绍

(1)

式中:n为任意正整数；ui表示拆分系数；a(i)为拆分数列。

文献[6]中根据数学模型抽象出了拆分数列a(n)的定义，即有

其中a(1)=1,n≥2，并且使用归纳法对于该定理的正确性进行了证明，同时也具体描述了整数k的带符号整数拆分形式编码算法。通过将整数拆分表示形式应用于椭圆曲线密码标量乘法运算中，并利用预计算方法，可以将大标量乘法运算变换成一组椭圆曲线上的点的点加运算形式，所以标量乘kP的形式能转化成：

u1·a(1)P+u2·a(2)P+…+un·a(n)P=

u1·P1+u2·P2+…+un·Pn

(2)

算法1基于SISF的椭圆曲线标量乘算法。

输入：k,P；

输出：Q=kP。

1.计算(um,um-1,…,u1)；

2.构造预计算表Pi；

3.令Q=O；

4.对于i从1到n，重复执行：

4.1 如果ui=1，则Q=Q+Pi；

4.2 如果ui=-1，则Q=Q-Pi；

5.返回Q。

其中，预计算表Pi=a(i)P是固定并且也是已知的，其详细的构造算法为：

算法2预计算表Pi生成算法。

输入：n,P；

输出：预计算表Pi。

1.令Q=O；

2.对于i从1到n，重复执行：

2.1S=2Q；

2.2Pi=S+P；

2.3Q=Pi+Q；

3.返回Pi。

2 新方案设计

算法1步骤4循环操作中，虽然只执行点加操作，然而在整个循环过程中仍然存在功耗差异，当拆分系数ui=±1时，需实施一次点加运算，而当ui=0时，执行空操作。由于基点P固定，致使密钥信息与输入之间具有相关性，从而导致标量乘法运算中存在有特殊点。所以算法1易遭受SPA、DPA、RPA和ZPA攻击。根据标量的拆分表示形式可知，对于所有不大于该标量的整数都可以由相同个数的类基表示，则可以利用标量分割的方法，不仅可以用来抵抗功耗攻击，而且通过引入一个随机整数，将大标量化为一组小标量，共用一张较小的预计算表，能够进一步提高运算效率。标量分割法是椭圆曲线标量乘运算中用于抵抗功耗攻击的一种盲乘数随机化技术，利用加上随机数r的乘数k′=k+r来替代标量k进行标量乘运算，转化为多标量乘运算，基于标量分割方法的标量乘运算一般形式为[7-10]：

kP=(xk+pr)(uP)+(yk+qr)(vP)

(3)

式中：r为随机整数；x,y,p,q,u,v为标量分割系数。为了能有效提升标量乘运算的效率，常常令x,y,p,q,u,v∈{-2,-1,0,1,2}，标量的分割次数可根据所选用的快速算法和安全性需求确定。

由于基点固定时，预计算表具有反复可利用性，所以将大标量分割成一组小标量，共用同一张较小的预计算表。以一次分割为例，令x=u=q=v=1,p=-1,y=0，则有标量乘运算kP=(k-r)P+rP。通过减去随机数r，掩盖了原始标量信息与功耗的相关性，因而可以抵抗DPA攻击。然而攻击者仍可利用拆分系数为0和1时执行不同操作而产生的功耗差异实施SPA攻击，而通过添加伪操作抵抗SPA攻击会造成不必要的效率损失。经分析可知，添加伪操作的位与拆分系数为0的位有关，可通过将两个拆分系数相加得到一个和系数li，减少ui和vi单独为0的位，以减少需要添加伪操作的个数，从而降低效率损失。同时可以将和系数ki看作一个窗口，窗口宽度为标量分割的次数的和[12]，则有基于SISF标量乘法运算kP可变换为：

kP=(k-r)P+rP=

(u1·a(1)P+u2·a(2)P+…+ua·a(t)P)+

(v1·a(1)P+v2·a(2)P+…+vt·a(t)P)=

(u1·P1+u2·P2+…+ut·Pt)+

(v1·P1+v2·P2+…+vt·Pt)=

(u1+v1)P1+(u2+v2)P2+…+(ut+vt)Pt=

(4)

根据式(4)可知，标量乘法运算转化为一个窗口宽度为2的基于SISF标量乘运算，结合抵抗SPA攻击的伪操作法，给出兼顾效率与安全的椭圆曲线密码抗功耗攻击方案。基于SISF的ECC抗功耗攻击算法的详细过程描述为：

算法3基于SISF的椭圆曲线密码抗功耗攻击算法。

输入：k,P；

输出：kP。

1.r=random(),h=k-r；

2.计算SISF(h)=(ut,ut-1,…,u1)；

3.计算SISF(r)=(vt,vt-1,…,v1)；

4.计算和系数li=(lt,lt-1,…,l1)；

5.构造预计算表Pi；

6.令Q=O,E=O；

7.对于e从2到1，重复执行：

7.1 对于i从1到t，重复执行：

7.1.1 如果li=e，则E=E+Pi；

7.1.2 如果li=-e，则E=E-Pi；

7.1.3 否则li=0，则T=E+P；

7.2Q=Q+E；

8.返回Q。

3 方案性能分析

算法3中，通过采用标量分割的方法，将标量减去一个随机整数，使得密钥信息随机化，攻击者无法获得中间结果与输入之间的相关性信息，因而该方案可抵抗DPA攻击。且由于参与标量乘法运算的标量已被随机化，使得攻击者无法找到特殊点可以利用，所以该算法也可以抵抗ZPA和RPA攻击。在步骤7的循环运算中，由于此时的和系数li仍然可为0，故在步骤7.1.3添加伪操作，从而每次循环运算中都执行两次点加操作，使其能量图谱不存在功耗差异，因此，攻击者无法获取相关信息进行密钥猜测，故该算法可以抵抗SPA攻击。

表1 算法3与WBRIP算法、EBRIP算法抗功耗攻击方案效率分析比较

从表1可以看出，算法3与WBRIP算法和EBRIP算法功耗攻击方案相比效率分别提高了69.72%和10.94%，这会大大满足芯片等便携式设备的高效性需求，说明固定基点标量乘运算中，所给方案具有更好的性能。另外，该方案还可以根据安全和效率需求进行多次标量分割。由性能分析结果表明：该方案可以满足安全和效率两方面的需求，尤其适用于对存储空间要求不高的密码加密部件等应用系统中。

4 结语

通过结合基于带符号整数拆分形式多标量乘快速算法和标量分割随机化方法，从而给出了一种新的ECC抗功耗攻击方案，既能抵御多种功耗攻击，同时也有更高的运算效率。并且由于该方案所构造生成的预计算表是固定且已知的，所以可以预先存储到应用系统中，不需要再重新计算，这样就只需要考虑主循环加密运算，能够更好地应用于安全芯片等资源受限的便携式系统中，具有较好理论研究和实际应用价值。

[1] Kocher P, Jaffe J, Jun B.Introcuction to differential power analysis and related attacks [EB/OL].http://www.Cryptography.com/dpa/ technical,1998.

[2] Kocher P, Jaffe J, Jun B.Differential power analysis [C]//Advanced in Cryptology-CRYPTO’99.California, USA: Springer Verlag, 1999: 388-397.

[3] Coron J S.Resistance against differential power analysis for elliptic curve cryptosystems[J].Crypt- ographic Hardware and Embedded Systems, 1999, 292-302.

[4] 王正义, 赵俊阁.基于带符号双基数系统的抗功耗攻击方案算法[J].计算机应用, 2011, 31(11): 2973-2974.

[5] 陈俊, 陈运.抗功耗分析攻击的椭圆曲线梳状优化算法[J].成都信息工程学院学报, 2010, 25(4): 341-344.

[6] 石润华, 钟诚.一种快速的椭圆曲线标量乘方法[J].计算机工程与应用, 2006(2): 156-158.

[7] 张宁.能量分析攻击下安全的椭圆曲线标量乘法[D].西安：西安电子科技大学, 2007.

[8] 刘铎, 戴一奇.计算椭圆曲线上多标量乘的快速算法[J].计算机学报, 2008, 31(7): 1131-1137.

[9] 赖晖.椭圆曲线密码体制中的快速点乘算法[J].微计算机信息, 2007, 23(3): 228-229.

[10] 马博.基于ECC算法的智能卡抗功耗攻击研究[D].西安：西安电子科技大学, 2010.

[11] Knudsen E.Elliptic scalar multiplication using point halving [C]//Advances in Cryptology-ASIACRYPT’99.New Youk: Springer-Verlag, 1999, 1716(274): 135-149.

[12] Morain F, Olivos J.Speeding up the computations on an elliptic curve using addition-subtraction chains [J].Theoretical Informatics and Applications, 1990, 24(6): 120-126.

[13] Purohit G N, Rawat S A, Kumar M.Elliptic curve point multiplication using MBNR and point halving [J].International Journal of Advanced Networking and Applications, 2012, 3(5): 1329-1337.

[14] 王玉玺，张串绒，张柄虹．一种改进的固定基点标量乘快速算法[J]．计算机科学，2013，40(10)：135-138．

[15] Fong K, Hankerson D, Lopez J, et al.Field inversion and point halving revisited[J].IEEE Transactions on Computers, 2004, 53(8): 1047-1059.

[16] Barua R, Pandey S K, Pankaj R.Efficient window-based scalar multiplication on elliptic curves using double- base number system [C]//Lecture Notes in Computer Science.Berlin: Springer-Verlag, 2007: 351-360.

ASecurityandEfficiencySchemeofResistingPowerAttacksforSoC

YANGSua,YANGYinghuib

(a.Practice Teaching Equipment Management Office； b.School of Information and Electronic Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450044, China)

The contradiction between efficiency and security lies in the scheme of resisting power analysis attack for ellipse curve cryptography due to the limited resource of security chip.Firstly, combining with the method of the pre-computation table and scalar division, scalar multiplication was turned into a set of point addition of ellipse curve by coding the scalar with signed integer splitting form.And then a scheme based on signed integer splitting form was presented by basic point masking algorithm.Security and performance analysis shows that the improved scheme has higher efficiency comparing with other resisting power analysis attacks, and can be used in the limited resource system preferably.

ellipse curve cryptography; power analysis attack; integer splitting form; multiple scalar multiplication algorithm