Cryptanalysis of Ha-Moon's Countermeasure of Randomized Signed Scalar Multiplication

Katsuyuki OKEYA  Dong-Guk HAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.5   pp.1140-1147
Publication Date: 2005/05/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.5.1140
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
elliptic curve cryptosystems,  side channel attacks,  SPA,  DPA,  Ha-Moon's countermeasure,  finite Markov chain,  

Full Text: PDF>>
Buy this Article

Side channel attacks (SCA) are serious attacks on mobile devices. In SCA, the attacker can observe the side channel information while the device performs the cryptographic operations, and he/she can detect the secret stored in the device using such side channel information. Ha-Moon proposed a novel countermeasure against side channel attacks in elliptic curve cryptosystems (ECC). The countermeasure is based on the signed scalar multiplication with randomized concept, and does not pay the penalty of speed. Ha-Moon proved that the countermeasure is secure against side channel attack theoretically, and confirmed its immunity experimentally. Thus Ha-Moon's countermeasure seems to be very attractive. In this paper we propose a novel attack against Ha-Moon's countermeasure, and show that the countermeasure is vulnerable to the proposed attack. The proposed attack utilizes a Markov chain for detecting the secret. The attacker determines the transitions in the Markov chain using side channel information, then detects the relation between consecutive two bits of the secret key, instead of bits of the secret key as they are. The use of such relations drastically reduces the search space for the secret key, and the attacker can easily reveal the secret. In fact, around twenty observations of execution of the countermeasure are sufficient to detect the secret in the case of the standard sizes of ECC. Therefore, the single use of Ha-Moon's countermeasure is not recommended for cryptographic use.