Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm

Jaecheol Ha1+, Yongje Choi2, Dooho Choi2+, and Hoonjae Lee3
 

1Hoseo University, Asan, ChungNam, Korea

jcha@hoseo.edu 

2ETRI, Daejeon, Korea

{choiyj, dhchoi}@etri.re.kr 

3Dongseo University, Busan, Korea

hjlee@dongseo.ac.kr 

 

 

Abstract

The naive implementation of an exponentiation used in public key cryptography may reveal a secret key to the attacker by several side-channel attacks. Recently, a novel square-always exponentiation algorithm based on trading multiplications for squarings is proposed. This algorithm for RSA implementation is faster than existing regular countermeasures against side-channel attacks. This paper suggests that the right-to-left square-always exponentiation algorithm is vulnerable to some sidechannel attacks: collision distance-based doubling, chosen-message SPA, and CPA-based combined attacks. The chosen-message SPA attack can be intactly applied to this algorithm. The other two attacks are variants of the doubling attack and SPA-based combined attack, respectively. In addition, the paper presents an improved right-to-left square-always algorithm resistant to existing and proposed power analysis attacks by using the additive message blinding method and the message update technique before the main iterative operation.

Keywords: RSA Cryptosystem, Side-Channel Attack, Simple Power Analysis, Square-Always Exponentiation

 

+: Corresponding author: Jaecheol Ha
Dept. of Information Security, Hoseo University, 20, Hoseo-ro 79-Gil, Babang-Eup, Asan-Si,

Chungnam, 336,795, Korea, Tel: +82-(0)41-540-5991, Web: http://islab.hoseo.ac.kr/jcha

 

Journal of Internet Services and Information Security (JISIS), 4(4): 38-51, November 2014 [pdf]