WAN Wu-nan,CHEN Jun.A Simple Power Analysis Attack on the Montgomery Modular Exponentiation Algorithms[J].Journal of Chengdu University of Information Technology,2016,(04):348-352.
针对Montgomery模幂算法的选择明文SPA攻击
- Title:
- A Simple Power Analysis Attack on the Montgomery Modular Exponentiation Algorithms
- 文章编号:
- 2096-1618(2016)04-0348-05
- 关键词:
- 侧信道攻击; 简单功耗分析; Montgomery模乘算法; 选择明文; 模幂算法
- Keywords:
- side channel attack; simple power analysis; Montgomerymultiplication algorithm; chosen plaintext; module exponentiation algorithm
- 分类号:
- TN918.4
- 文献标志码:
- A
- 摘要:
- 大整数模幂运算的核心是大整数模乘运算,一般采用Montgomery模乘算法实现。针对Montgomery模乘算法实现方式中大整数拆分成多个字节或字相乘存在功耗泄露问题,提出一种选择能产生Montgomery模乘算法的某操作数由多个字节或字为零组成的大整数的特定明文,简单功耗分析(simple power analysis,SPA)的方法。通过输入特定明文,一条功耗曲线就能将模幂算法中平方和乘运算位置区分出来,私钥攻击难度下降。在搭建真实的8051智能卡芯片攻击环境下,输入特定明文进行SPA攻击,1024比特私幂指数私钥攻击准确率可达99%。实验结果表明可选特定明文数量多,用单一的屏蔽特殊明文的方法无法有效防范文中提出的SPA攻击,最后给出防范此选择明文SPA攻击的建议。
- Abstract:
- Large module multiplication which is normally implemented by the Montgomery multiplication algorithms is the kernel of large module power multiplication.Accord to the problem that power leakages are mainly caused by multiplication operations of many bytes or words which the large integers are divided intoin the Montgomery multiplication algorithms, a chosen particular message simple power analysis attack is proposed in this paper, when an operationwhich is composed of many zero bytes or wards is generated by the particular message. Squaring operations and multiplication operations canbe?distinguished by using one power trace which is generated by the specific message inputin modular exponentiation algorithms, and thereby make secret exponent analysis less difficult. The correctness rate of private exponents with 1024 bits could reach 99% when the particular message is inputted during SPA attack in smart card 8051 chip. The experimental results indicate that there are many optional specific plaintexts, thus the method of the single shielding could not protect effectively against the proposed SPA attack. Finally, we will give advice on countermeasures to such enhanced chosen message SPA techniques.
参考文献/References:
[1] Kocher P, Jaffe J, Jun B. Differential power analysis[C]. Advances in Cryptology-CRYPTO'99, California, USA: Springer, 1999: 789-789.
[2] S M Yen, W C Lien, S J Moon,et al. Power Analysis by Exploiting Chosen Message and Internal Collisions-Vulnerability of Checking Mechanism for RSA-Decryption[C].Proc. Mycrypt '05,2005:183-195.
[3] Messerges T S,Dabbish E A,Sloan R H.Investigations of power analysis attacks on smartcards[C].Proc USENIX Workshop Smartcard Technology, Chicago,Illinois,USA: IEEE Press,1999:151-161.
[4] M F Witteman, Jasper G J van Woudenberg,et al. Defeating RSAMultiply-Always and Message Blinding Countermeasures[C].The Cryptographers' Track at the RSA Conference 2011, San Francisco, CA, USA,2011:14-18.
[5] E AkalpKuzu, A Tangel.A new style CPA attack on the ML implementation of RSA[C].Computer Science and Engineering Conference(ICSEC), 2014.
[6] A P Fouque,F Valette.The Doubling Attack-WhyUpwards is Better Than Down wards,Proc. Int'l WorkshopCryptographic Hardware and Embedded Systems(CHES '03),2003: 269-280.
[7] S M Yen, W C Lien, S J Moon,et al.Power Analysis by Exploiting Chosen Message and Internal Collisions-Vulnerabilityof Checking Mechanism for RSA-Decryption[C], Proc. Mycrypt '05,2005:183-195.
[8] Naofumi Homma, Atsushi Miyamoto,TakafumiAoki,et al. Comparative power analysis of modular exponentiation algorithms[J]. IEEE Transations on computer,2010,59(6): 795-807.
[9] 曹娜娜. 针对8051芯片RSA算法的选择明文SPA攻击[D]. 成都:成都信息工程学院, 2012,14-38.
[10] J Heyszl, A Ibing, S Mangard,et al.Clustering Algorithms for Non-profiled Single-Execution Attacks on Exponentiations[C]. Smart Card Research and Advanced Applications.Volume 8419 of the series Lecture Notes in Computer Science,2014:79-93.
[11] C Clavier, B Feix, G Gagnerot,et al.Horizontal Correlation Analysis on Exponentiation[C]. Proc. ICICS, ser. Lecture Notes in ComputerScience,2010,6476:46-61.
[12] Montgomery,P I. Modular Multiplication Without Trial Division[J]. Mathematics of Computation,1985,44(170):519-521.
[13] Dusse S R,KaliskiJr B S. A Cryptographic Library for the Motorola DSP56000.Advances in Cryptology-FUROCRYPT90,1990.
[14] Knuth D E,The Art of Comparing Montgomery Multiplication Algorithms[J].IEEE Micro,1996,16(3):26-33.
相似文献/References:
[1]万武南,陈 俊.针对双重掩码模幂算法的二阶互相关功耗分析攻击[J].成都信息工程大学学报,2016,(04):353.
WAN Wu-nan,CHEN Jun.A Second Order Cross Correlation Power Analysis Attack on
Double Blinding Exponentiation Algorithms[J].Journal of Chengdu University of Information Technology,2016,(04):353.
[2]匡晓云,黄开天,兰 天,等.针对SM4密码算法的模板攻击[J].成都信息工程大学学报,2021,36(05):499.[doi:10.16836/j.cnki.jcuit.2021.05.004]
KUANG Xiaoyun,HUANG Kaitian,LAN Tian,et al.Template Attack Against SM4 Cryptographic Algorithm[J].Journal of Chengdu University of Information Technology,2021,36(04):499.[doi:10.16836/j.cnki.jcuit.2021.05.004]
[3]曹家华,吴 震,王 燚,等.基于CNN-BPR的S-Box功耗随机化侧信道攻击[J].成都信息工程大学学报,2022,37(01):16.[doi:10.16836/j.cnki.jcuit.2022.01.003]
CAO Jiahua,WU Zhen,WANG Yi,et al.Side Channel Attack of S-box Power Randomization based on CNN-BPR[J].Journal of Chengdu University of Information Technology,2022,37(04):16.[doi:10.16836/j.cnki.jcuit.2022.01.003]
备注/Memo
收稿日期:2016-07-01 基金项目:国家自然科学基金面上资助项目(61572086); 四川省大数据与智慧城市创新开放基金资助项目(RWS-CYHKF-01-20150003); 四川省教育厅重点资助项目(16ZA0212)