要安全还是效率？密码芯片上高效的ECC抗功耗攻击方案
【厚度】学术plus年终巨献：2017年 你不可以错过的重磅报告们！（全文阅读链接）
今日荐文的作者为信阳职业技术学院徐澍，黄淮学院汤震。本篇节选自论文《密码芯片上高效的ECC抗功耗攻击方案》，发表于《中国电子科学研究院学报》第13卷第1期。
摘 要：针对密码芯片在抵抗功耗攻击时存在着效率与安全两个方面的矛盾，文中通过利用奇系数梳状算法对标量进行编码，同时结合预计算方法把椭圆曲线密码标量乘法运算转化为一组小标量乘法运算，并利用基点掩码技术实施抗功耗攻击。性能分析结果表明：与传统的抗功耗攻击方案相比，给出的抗功耗攻击方案不仅可以抵抗多种功耗攻击，并且能够在存储空间和主循环运算量基本保持不变的情况下具有更高效的运算效率，在各种资源受限的应用系统中具有较好的实际应用价值。
关键词: 密码芯片；椭圆曲线密码；功耗攻击；奇系数梳状算法
1 引言
功耗攻击技术给密码芯片的安全带来了极大的威胁，但由于密码芯片自身资源限制，造成其了在采用防御功耗攻击的方法后，将会降低密码芯片运算效率，这就产生了效率与安全的矛盾，如何解决这一矛盾则成为密码芯片研究的热点问题。功耗攻击是Paul Kocher在1998年首先提出的密码分析方法，主要工作原理是密码芯片运行时，不同操作产生的功耗不同，通过采集这些泄露的功耗信息，并分析功耗之间的差异即可获取相关密钥信息。而且功耗分析具有易于实现、成功率高等诸多良好攻击特性，因而相较于传统数学攻击方法而言，功耗分析对密码芯片所带来的安全威胁更严重[1-2]。
一般来说，功耗分析因攻击手段不同主要分为两类：简单功耗攻击技术(Simple Power Attack, SPA)和差分功耗攻击技术(Differential Power Attack, DPA)。其中，密码芯片中的主流算法大都是采用椭圆曲线密码(Elliptic Curve Cryptogram, ECC)算法，这主要是因为ECC算法与传统非对称密码算法相比而言，在安全性相同的情况下ECC算法有诸如密钥长度更短，存储空间更小等一系列优势，这使得ECC算法更能够适合用在资源受限的系统。然而，当前出现了许多针对ECC的功耗攻击，包括零值寄存器攻击(Zero-value Power Attack, ZPA)与零值点攻击(Refined Power Attack, RPA)[3-4]。
国内外学者关于密码芯片的抗功耗攻击方面做了大量研究工作。
Mamiya H等人[5]给出了一种基于窗口随机化初始点的ECC抗功耗攻击方案(Window-Based Random Initial Point, WBRIP)，基本思想是通过将标量的二进制编码进行窗口化，在一个窗口内实现掩盖所执行的点加运算与倍点运算次数的目的，致使攻击者无法从中间值猜测运算过程中所执行的具体操作及相关步骤，尽管WBRIP可以抵抗多种功耗攻击，但是其运算效率需进一步提高。
张涛等人[6]给出了一种固定窗口宽度为w的非邻接表示形式的ECC抗功耗攻击算法(Fractional Width-w Non Adjacent From, FWNAF)，主要思想是利用二进制的非邻接表示形式来优化编码，减少在抵抗功耗攻击过程中所需添加伪操作的次数，从而实现运算效率的提升。
文献[7]给出一种高效的窗口随机化初始点ECC抗功耗攻击算法(Efficient-Based Random Initial Point, EBRIP)，主要思想是将标量的二进制编码表示成窗口宽度是w的非邻接表示形式，并将其分成整数部分与分数部分可实现抵抗SPA，接着再将基点分成固定部分与可变部分可实现抵抗DPA、ZPA与RPA，并且也可提升运算效率。
奇系数Comb算法是ECC标量乘法运算的一种快速计算方法，为保证算法能够抵抗功耗攻击并进一步有效提升运算效率，文中通过在奇系数Comb标量乘算法中结合添加伪操作与基点掩码技术，给出了一种密码芯片上基于奇系数Comb算法的ECC抗功耗攻击算法(Resisting Power Attacks algorithm of ECC based on Odd-only Comb Method, RPAOCM )，同BR、WBRIP及FWNAF算法相比，所给抗功耗攻击算法不仅有相同的抗功耗攻击安全性，而且具有更高的运算效率。
2 奇系数Comb标量乘算法
ECC标量乘快速算法主要有两类，一类是通过提高底层域运算来实现，另一类是对标量进行重新编码来实现。其中，奇系数Comb标量乘算法属于第二类快速算法，同时也是常用的ECC标量乘快速算法，与其它同类快速算法（诸如双基数系统快速算法[8]、阶乘展开式快速算法[9]和整数拆分表示形式快速算法[10]等）相比，具有所需存储空间较小、运算效率更高等优点。
下面给出ECC的奇系数Comb标量乘快速算法实施过程：
3 新算法设计
在所给的算法1中，由于标量的奇系数编码系数li都不为0，因而在步骤6中总是执行同样的操作步骤和顺序。也即是，每当执行一次倍点运算后就接着也执行一次点加运算，所获得的能耗图谱基本没有出现显著的功耗曲线差异，这样也就使攻击者不能根据功耗的差异来猜测相关的密钥信息。并且无论所给标量是奇数还是偶数，在步骤8中都会执行一次点加运算，因此所给标量的奇偶性也不会被泄露。因而所给算法1能够防御SPA。然而，因为已知的基点P致使运算中间值和输入之间具有一定的相关性，这就使得攻击者能够利用运算过程的中间值来推测出相关的密钥信息，因而算法1不能防御DPA。与此同时，所给的基点中可能存在有可以被攻击者利用的特殊点，从而使得算法1不能抵抗ZPA与RPA。
文中采用了基点掩码技术，即通过在标量乘运算中引入随机点将基点随机化，同时再结合预计算的方法可实现多标量乘法运算中各分基点的随机化，以此即可掩盖每个小标量乘法运算同功耗之间的相关性，这样就致使攻击者无法利用统计分析的方法，通过多次猜测来获取有效的密钥信息。所以，基于奇系数Comb编码标量乘运算Q=kP在引入随机点R之后可转化成如下形式，如式(6)所示：
其中，因为引入了随机点R，使得在返回Q时，需增加后处理操作来进行恢复：若k为奇数，则增加操作Q=Q-2P-R；若k为偶数，则增加操作Q=Q-P-R。所给基于奇系数Comb的标量乘抗功耗攻击算法具体过程如下面算法2所示：
4 仿真及性能分析
4.1 安全性分析
在算法2中，因为不存在系数为0的系数，使得其没有功耗差异的操作，所以其能耗图谱是相同的，这也说明其本身具备抵抗SPA的能力。同时，由于引入了随机点R，使得预计算表中分基点Pi和功耗之间的相关性被掩藏，进而也可隐藏可被利用的某些特殊点，因而所给算法2能防御DPA、ZPA与RPA。最后，所给算法2执行了两次后处理操作，这主要是实现两个方面的目的：一方面是用于掩盖原标量自身的奇偶性，有效提升了算法的安全性；另一方面是可减去引入的随机点，从而恢复真实的返回值。其中，文中采用了文献[12]所给的功耗仿真平台对算法1和算法2进行功耗仿真分析，如图1和图2所示（以实施DPA攻击为例）。
下面图1中给出了对算法1实施DPA攻击所获得的功耗曲线图。由图1可以看出，对算法1实施DPA攻击后，其功耗轨迹曲线出现明显的起伏，这就使得攻击者有可能推测出相关的密钥信息。虽然算法1具有相同的能力图谱可以抵抗SPA，但如果攻击者对算法1实施DPA攻击，然后对已获得的大量功耗轨迹曲线进行统计分析，攻击者将能够推测出相关的密钥信息。所以，仿真结果表明算法1是无法抵抗DPA攻击的，因而需要对其进行改进。
图1 对算法1实施DPA攻击的功耗曲线
下面图2中给出了对所给算法2实施DPA攻击所获得的功耗曲线图。由图2可以看出，算法2的功耗轨迹曲线总体来说比较平滑，并无明显的波形起伏，因而攻击者无法根据所获得的大量功耗轨迹曲线进行统计分析，来得到与之相关的密钥信息。因此，仿真结果表明所给算法2能够有效地抵抗DPA攻击。
图2 对所给算法2实施DPA攻击的功耗曲线
4.2 效率分析
表1 所给算法2和BR、WBRIP以及FWNAF抗功耗攻击算法的运算效率比较
此外，在文献[14]给出的仿射坐标系下，A=23M，D=24M，M表示模乘运算。则BR抗功耗攻击算法的总运算量为24064M，WBRIP抗功耗攻击算法的总运算量为16025M，FWNAF抗功耗攻击算法的总运算量为15766M，而算法2的总运算量为15671M。因此，所给算法2比BR算法的运算效率提升了34.88%，比WBRIP算法提升了2.21%，而与FWNAF算法的总运算量基本相似。尽管所给算法2所需的预计算量要比WBRIP算法和FWNAF算法大的多，但是预计算表能够预先存储到密码芯片中。然而，仅仅对于主循环运算来说，所给算法2比WBRIP算法与FWNAF算法的运算效率均提升了60.04%左右。由此可知，所给算法2可以同时兼顾到安全和效率两个方面，可以较好地用于各种资源受限的应用环境中。
结 语
ECC是密码安全芯片中主流的密码算法，广泛应用于各类安全环境中，而其中基于奇系数Comb的标量乘算法则是ECC中的一种快速标量乘算法，但是因为近年来出现的功耗分析技术致使密码安全芯片遭遇了非常大的安全风险和挑战。因而文中结合奇系数Comb快速标量乘算法与基点掩码技术，从而给出了一种改进的ECC抗功耗攻击算法。该算法与BR、WBRIP以及FWNAF抗功耗攻击算法相比，不仅同样能够有效抵抗多种功耗攻击，同时具有更高的运算效率。由此可知，所给RPAOCM算法能较好地解决密码芯片等类似系统因资源受限而存在效率和安全两方面矛盾的问题，能够较好地用于各类自身资源受限的应用系统中。
（参考文献略）
声明：版权归《中国电子科学研究院学报》所有。转载请务必注明出处，违者必究。文章观点不代表本机构立场。
《中国电子科学研究院学报》欢迎各位专家、学者赐稿！
投稿链接 http://kjpl.cbpt.cnki.net
电话：010-68893411
邮箱：dkyxuebao@vip.126.com