真实硬件环境下幂剩余功耗轨迹指数信息提取

吴震，陈运，陈俊，王敏

（成都信息工程学院 信息安全研究所，四川 成都 610225）

1 引言

幂剩余运算是目前许多种流行公钥算法或协议的核心运算，若该运算运行时在边信道泄露出信息，则可获取密码体制中密钥的部分信息，严重者可直接破译出密钥。

目前，针对密码设备运行时边信道信息泄露的攻击发展迅速，从计时攻击(TA,timing analysis)[1,2]到简单功耗分析(SPA,simple power analysis)[3]和差分功耗分析(DPA,differential power analysis)[4]，现在又发展出地址差分功耗分析攻击(ADPA,address-bit differential power analysis)[5,6]等各类基于功耗轨迹进行分析攻击的技术，此类攻击对密码体制算法的实现与运行时硬件安全都提出了新的挑战。

研究者根据功耗分析攻击的特性提出的各种防范方案主要从减小可测量的功耗差异、时间差异或破除功耗、时间差异与取值间的相关性等方面入手，如门电路级的防范[7]、抗测量技术[8]、重编码技术[9]、随机操作技术[10]以及综合优化压缩等功耗技术[11]等。

目前国内外对功耗分析攻击和抵抗措施的研究大量集中在分组密码体制上，同时由于实验条件的限制，研究以理论分析为主，辅之以计算机仿真结果作为支撑数据，缺乏在真实硬件环境下对公钥密码实施功耗攻击的研究、分析和实测结果。Messerges等曾断言，使用SPA攻击难以在真实硬件环境下直接获取RSA密钥[12]。

下面对真实硬件环境下幂剩余运算功耗信息泄露进行综合分析，其研究结果对所有使用幂剩余运算作为核心运算的公钥密码体制均适用（如RSA密码体制），亦可移植到椭圆曲线密码算法。

2 幂剩余运算的实现方法简析

幂剩余运算基本运算表达式为

其中，指数K为敏感信息，在RSA中，可为私钥的一部分，泄露其值或相关内容的信息实质即为泄露密钥信息。

对于幂剩余运算的实现，现已提出众多实用快速算法，基本的快速算法有如下。

算法1 从左至右（L-R,left to right）二进制表示求幂剩余算法[13]。

算法2 从右至左（R-L,right to left）二进制表示求幂剩余算法[13]。

具体算法细节与其他快速算法请参阅文献[13]。

经过对各类快速实现算法的综合考察，得到以下结论。

1) 幂剩余运算是用复杂度较低的模乘运算循环迭代来实现快速计算。迭代次数与指数的二进制长度相关，甚至相等。

2) 在每次循环内部，对应指数位Ki的不同取值会执行不同的操作，并产生不同的中间结果。

3) 在循环之间，执行条件判断操作，不同于循环内部的操作。

由于实现算法在操作上有这些特征，发展出了下述攻击方法。

3 幂剩余运算的功耗分析攻击

3.1 幂剩余实现算法中操作功耗与指数相关性分析

在实现算法中，主要的运行指令有3类：数据传输、条件判断和模乘（模平方）运算，这 3类指令对应的功耗大小、运算时间均不相同，特征明显。

通过观察大量功耗曲线与硬件电路功耗原理分析，有以下结论。

1) 在功耗轨迹上，每轮循环的边界是可分辨的，通过分析循环的次数，可得到指数的位数信息。

2) 从运算时间上看，在功耗轨迹图中每轮循环对应的功耗部分不同长短时间对应不同的 Ki值。将所有循环对应的 Ki值都推断出来，便可直接破解出指数的二进制表示。

3) 从功耗情况上看，Ki取值不同时，对应的功耗情况也不同。根据测量每轮循环对应的功耗的不同可反推出 Ki的取值，也可成功获得指数的二进制表示。

3.2 真实硬件环境下的功耗分析模型与操作相关性信息的提取技术

在进行实际功耗分析攻击时，设备自身、环境等产生的噪声均会与功耗信号混合，使得真实功耗测量值与软件仿真环境下获得的数值相差甚远。因此，在测量和分析时，需采取一定信号处理手段，将噪声信号压制，从而更有效地获取信息。

在实测了大量功耗曲线的基础上，根据总体功耗变化与各类功耗分量之间关系的综合分析，被测设备的总功耗可抽象简化成如下模型。

在模型中，Ps为静态功耗；f(O,D,t)为t时刻某项操作O在处理数据D时密码运算设备所产生的动态功耗；N(t)为t时刻的噪声总功耗；P(t)为在t时刻被测电路的总功耗。其中本文所关注的有效信息的信号为操作O的函数。

从模型中可以看出，静态功耗Ps和噪声总功耗N(t)是妨碍有效信息提取的信号，应尽量抑制；信号f(O,D,t)中含有操作和数据这2部分对总功耗的影响，为更好地提取操作与功耗间的相关性，需抑制数据变化部分造成的动态功耗。

利用式(2)，针对被测信号的特征，可对其进行以下处理。

1) 静态功耗 Ps可利用一般滤静处理即可消除其影响；

2) 噪声中对测量影响比较大的为高斯白噪声，因此利用去白噪方法去除大部分的N(t)；

3) 根据数据传输时采集到的信号特征制成数据信号抑制器来抑制数据D对总功耗的影响。

经过以上信号处理后，功耗信号Pn(t)近似等于∑ f(O,t)，其中f(O,t)为t时刻某项操作O执行时密码运算设备所产生的动态功耗。而通过分析P(t)，就可以获取指数与操作之间的相关性信息。

4 实测结果及其分析

4.1 测试平台的构架

根据式(2)和功耗分析需求而设计的测试平台框架如图1所示。其基本流程为由信息处理服务器将测试案例传输至边信道攻击平台，通过协议转换将数据送至受攻击单元，在受攻击单元正常运行时，由功耗检测电路采集功耗信号送至信号处理单元进行各类信号处理，处理后的结果由示波器显示，并通过示波器将数据返回至信息处理服务器。

图1 测试平台框图

在实现中密码算法协处理单元使用 Cyclone II系列的EP2C8Q208C8 FPGA芯片为核心运算芯片，片上实现了数据总线宽度为 8bit的幂剩余 R-L算法，其中底数、指数、模数均为32bit。本文演示成果所使用的算法为R-L增加预处理的模平方与模乘并行运算结构，其中模平方与模乘均用蒙哥马利算法实现。其他算法实现也可得相似结果。

4.2 操作相关性信号提取技术的实测结果

在上节所述构架的测试平台上运行指数 K为0x0f0f0f0f的幂剩余运算，在不同的信号处理模式下，获得不同的实测结果。

1) 无任何信号处理下所获得的原始功耗轨迹如图2所示。观察该图可发现无法直接获取操作的相关信息。

图2 K=0x0f0f0f0f时的原始功耗轨迹示波器截图

2) 增加了去静态功耗处理后所获得的功耗轨迹如图3所示，经观察可发现有效信号已被放大。

图3 K=0x0f0f0f0f时，抑制Ps的功耗轨迹示波器截图

3) 对该信号再进行抑制数据 D的处理，其功耗轨迹如图4所示，从图中可看出功耗总体变化较明显，但细节仍被噪声覆盖。

图4 指K=0x0f0f0f0f时，抑制Ps和D的功耗轨迹示波器截图

4) 对该信号进行降噪处理后的结果如图 5所示，该实测结果直接显示了对应指数的操作对功耗变化的影响。

图5 K=0x0f0f0f0f时，抑制Ps、D和白噪声后的功耗轨迹示波器截图

4.3 实测功耗信号与指数相关性分析

由于信号处理已抑制了数据传输信号对动态功耗Pn(t)的影响干扰，因此以下对功耗轨迹图的分析均忽略底数、模数的差异。图示均为实测结果的截屏。

图6～图9为不同指数下经过信息处理后的幂剩余运算功耗轨迹图。

经过图像对比，各功耗轨迹图上均有 33个界限分明的周期，正对应于幂剩余运算算法中的33轮迭代，其中第 1个周期对应蒙哥马利预处理，后 32个周期按时序从右到左一一对应指数的 32bit。

图6是指数为0时产生的功耗轨迹图，此轨迹图可作为 SDPA（简单差分功耗分析）攻击的基准轨迹。

图7为K=0x0f0f0f0f时的功耗轨迹，通过对比图 8 可以看出，第 2～5、10～13、18～21、26～29 个上升型周期间隔对应指数K中取值为1的位数，余下的平坦型周期间隔正对应指数K中取值为0的位数。根据功耗模型可知，上升型周期间隔的形成原因就是在指数取值为1时，2个蒙哥马利模乘器同时工作，其功耗比一个模乘器工作要大。

同理在图 8（K=0x12345678）、图 9（K=0xffffffff）中，功耗变化较大的位置正是 2个模乘器同时工作时，对应指数取值为 1；功耗变化较小的位置对应指数取值为0。

在图6～图9中，任意2个周期的时间间隔均相等，其原因是R-L并行算法消除了每次迭代的时间差异，因此无法在时间的差别上判断指数当前位的值，从而抵御了计时攻击。

图6 K=0x00000000时的幂剩余运算功耗轨迹示波器截图

图7 K=0x0f0f0f0f时的幂剩余运算功耗轨迹示波器截图

图8 K=0x12345678时的幂剩余运算功耗轨迹示波器截图

图9 K=0xffffffff时的模剩余计算功耗轨迹示波器截图

图10为增加了抵抗SPA攻击静态掩盖算法的幂剩余运算对应功耗轨迹图，指数K=0x12345678。

图10 K=0x12345678时增加抗SPA攻击算法的功耗轨迹示波器截图

算法3 抗SPA攻击静态掩盖的R-L算法输入：正整数P,N,K=(Kt-1,Kt-2,…,K1,K0)输出：C=Pkmod N

算法3实质是对应不同的指数取值都做相同的操作，消除因操作差异所产生的功耗差异，获得抗SPA攻击效果。从功耗轨迹上看，其功耗变化与图9（K=0xffffffff）没有差别，因此具有抗 SPA攻击能力。

5 结束语

在对实测的大量功耗轨迹数据进行对比观察和理论分析后，证实真实硬件环境下功耗分析模型的正确性。并应用以该模型为基础的有效信息提取技术制成测试平台，在实际测试中成功实施了对32bit指数的幂剩余运算的SPA攻击，成功获取其对应的指数值，证实利用SPA攻击可成功破译RSA的密钥，推翻了Messerges等关于使用SPA攻击难以在真实硬件环境下获取RSA密钥的论断[12]。同时通过对静态掩盖抗 SPA攻击算法功耗轨迹图的分析，证实在算法中添加伪操作能够使幂剩余运算电路抵御针对操作相关性的SPA攻击。

文中提出的功耗分析模型和方法对所有使用幂剩余运算作为核心运算的公钥密码体制均适用（如 RSA密码体制），亦可移植到椭圆曲线密码算法。

此外，作者利用该模型和信息提取技术，还成功实施对幂剩余算法的SDPA、DPA等攻击，篇幅所限，研究结果将另文讨论。

致谢

作者诚挚感谢成都信息工程学院信息安全研究所的同仁：万武南、索望、张金全、陈艾东，研究生杜之波、周俐莎、朱冰、刘鹤、李姗姗等，感谢他（她）们在课题研究进行中和论文撰写期间所做的大量协助工作和给予的无私帮助！

[1] KOCHER P.Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other systems[A].Proceedings of Advances in Cryptology-CRYPTO’96[C].1996.104-113

[2] DHEM J F,KOEUME F,LEROUX P A,et al.A practical implementation of the timing attack[A].Proceedings of CARDIS 1998[C].1998.14-16.

[3] MESSERGES T S,DABBISH E A,SLOAN R H.Investigations of power analysis attacks on smartcards[A].Proc USENIX Workshop Smartcard Technology[C].Chicago,Illinois ,USA ,1999.151-161.

[4] KOCHER P,JAFFE J,JUN B.Differential power analysis[A].Proceedings of Advances in Cryptology[C].1999.388-397.

[5] ITOH K,IZU T,TAKENAKA M.Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA[A].CHES 2002[C].2003.129-143.

[6] ITOH K,IZU T,TAKENAKA M.A Practical Countermeasure against address-bit differential power analysis C D[A].CHES 2003[C].2003.382-396.

[7] CORSONELLO P.An Integrated Countermeasure against Differential Power Analysis for Secure Smart-Cards[M].The Circuit is Under Patenting.US Provisional Patent Application 60/643,165.

[8] RATANPAL G B,WILLIAMS R D,BLALOCK T N.An on-chip signal suppression countermeasure to power analysis attacks[J].IEEE Transactions on Dependable and Secure Computing,2004,1(3): 179.

[9] MESSERGES T S.Securing the AES finalists against power analysis attacks[A].Proceedings of Fast Software Encryption Workshop 2000[C].2000.150-164.

[10] GEBOTYS C H.A Table masking countermeasure for low-energy secure embedded systems[J].IEEE Transactions on Very Large Scale Intergration(VLSI) systems,2006,14(7): 740-753.

[11] 陈运,吴震,陈俊,万武南,吕永其.防范边信道攻击的等功耗编码实现算法[J].电子科技大学学报,2008,37(2): 168-171.CHEN Y,WU Z,CHEN J,et al.Implementation of equivalent power consumption coding secure against side channel attack[J].Journal of University of Electronic Science and Technology of China,2008,37(2):168-171.

[12] MESSERGES T S,DABBISH E A,SLOAN R H.Power analysis attacks of modular exponentiation in smartcards[A].Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems(CHES,99)[C].1999.144-157.

[13] 陈运.信息加密原理[M].成都:电子科技大学出版社,1996.CHEN Y.The Principle of Information Encryption[M].Chengdu:University of Electronic Science and Technology of China Press,1996.