基于Montgomery算法安全漏洞的SPA攻击算法

doi:10.3969/j.issn.1000-436x.2013.z1.020

摘要/Abstract

摘要：

公钥密码体制的算法大多基于有限域的幂指数运算或者离散对数运算。而这些运算一般会采用Montgomery算法来降低运算的复杂度。针对Montgomery算法本身存在可被侧信道攻击利用的信息泄露问题，从理论和实际功耗数据2方面分析了Montgomery算法存在的安全漏洞，并基于该漏洞提出了对使用Montgomery算法实现的模幂运算进行简单能量分析（SPA,simple power analysis）攻击算法。利用该算法对实际模幂运算的能量曲线进行了功耗分析攻击。实验表明该攻击算法是行之有效的。

关键词: 模幂运算, 侧信道攻击, 简单能量分析攻击, Montgomery算法

Abstract:

The Montgomery algorithm is widely used to reduce the computational complexity of large integer modular exponentiation. The SPA (simple power analysis) attacks against public-key cryptosystems based on Montgomery algo-rithm implementation were presented by exploitation of the inherent security vulnerability which that sensitive informa-tion leakage could be used by side-channel attack. The chosen-message SPA attacks were focused on, which enhance the differences of operating wave-forms between multiplication and squaring correlated to the secret key by using the input of particular messages. In particular, a SPA attack against RSA cryptosystem was showed based on large integer modular exponentiation. The results show that the attack algorithm is correct and effective.

Key words: modular exponentiation, side-channel attack, simple power analysis, Montgomery algorithm

甘刚,王敏,杜之波,吴震. 基于Montgomery算法安全漏洞的SPA攻击算法[J]. 通信学报, 2013, 34(Z1): 156-161.

Gang GAN,Min WANG,Zhi-bo DU,Zhen WU. Simple power analysis attack against cryptosystems based on Montgomery algorithm[J]. Journal on Communications, 2013, 34(Z1): 156-161.

图/表 18

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

表1

参考文献 14

[1]	KOCHER P , JAFFE J , JUN B . Differential power analysis[A]. Pro-ceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology[C]. 1999.388-397.
[2]	P KOCHER C . Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[A]. Advances in Cryptology-CRYPTO' 96, Lecture Notes in Computer Science[C]. 1996.104-113.
[3]	韩军，曾晓洋，汤庭鳌．基于时间随机化的密码芯片防攻击方法[J]．计算机工程， 2007,33(2):6-8. HAN J , ZENG X Y , TANG T A . Modeling timing randomization in cryptographic chip against power analysis attack[J]. Computer Engi-neering, 2007,33(2):6-8.
[4]	成为，谷大武，郭筝等．一种针对RSA-CRT的功耗分析攻击方法[J]．通信技术， 2011,6(44):123-125. CHENG W , GU D W , GUO Z , et al. A power analysis attack against RSA-CRT[J]. Communications Technology, 2011,6(44):123-125.
[5]	吴震，陈运，陈俊等．真实硬件环境下幂剩余功耗轨迹指数信息提取[J]．通信学报， 2010,31(2):17-21. WU Z , CHEN Y , CHEN J , et al. Exponential information's extraction from power traces of modulo exponentiation implemented on FPGA[J]. Journal on Communications, 2010,31(2):17-21.
[6]	ACICMEZ O , SEIFERT J P , KOC C K . Predicting Secret Keys Via Branch Prediction[R]. Topics in Cryptology-CT-RSA, 2007.
[7]	ACIICMEZ O , KOC C K , SEIFERT J P . On the Power of Simple-Branch Prediction Analysis[R]. Cryptology ePrint Archive, 2006.
[8]	李志强，严迎建，段二鹏．差分能量攻击所需样本数量研究[J]．计算机工程， 2013,38(24):128-132. LI Z Q , YAN Y J , DUAN E P . Research on sample amounts needed by dif-ferential power attack[J]. Computer Engineering, 2013,38(24):128-132.
[9]	KADLOOR S , KIYAVASH N , VENKITASUBRAMANIAM P . Miti-gating timing side channel in shared schedulers[J]. arXiv preprint arXiv:1302.6123, 2013.
[10]	BAUER A , JAULMES E , PROUFF E , et al. Horizontal and vertical side-channel attacks against secure RSA implementations[A]. Topics in Cryptology-CT-RSA 2013 Springer Berlin Heidelberg[C]. 2013.1-17.
[11]	PROUFF E , RIVAIN M . Masking against side-channel attacks: a formal security proof[A]. Advances in Cryptology-EUROCRYPT 2013 Springer Berlin Heidelberg[C]. 2013.142-159.
[12]	杜之波，陈运．防范边信道攻击的逆伪操作实现算法[J]．计算机工程， 2010,36(3):131-133. DU Z B , CHEN Y . Implementation algorithm of pseudo modular in-version secure against side channel attack[J]. Computer Engineering, 2010,36(3):131-133.
[13]	BRICKEL E F . A survey of hardware implementations of RSA[A]. Proceedings of the Advances in Cryptology(CRYP TO'89)[C]. Santa Barbara, USA, 1990.368-370.
[14]	MARCELO E K , NAOFUMI T . A hardware algorithm for modular multiplication division based on the extended Euclidean algorithm[A]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences[C]. 2005.3610-3617.

攻击方法	曲线条数	成功率	其他操作
对任意底数M的SPA	无法定量分析	无法保证100%	无
对选择底数M的SPADPA	幂指数二进制长度＞8 000	100%100%	无虑波处理，对齐操作