Paper 2018/761

New Single-Trace Side-Channel Attacks on a Specific Class of Elgamal Cryptosystem

Parinaz Mahdion, Hadi Soleimany, Pouya Habibi, and Farokhlagha Moazami

Abstract

In 2005, Yen et al. proposed the first N1 attack on the modular exponentiation algorithms such as BRIP and square-and-multiply-always methods. This attack makes use of the ciphertext N1 as a distinguisher of low order to obtain a strong relation between side-channel leakages and secret exponent. The so-called N1 attack is one of the most important order-2 element attacks, as it requires a non-adaptive chosen ciphertext which is considered as a more realistic attack model compared to adaptive chosen ciphertext scenario. To protect the implementation against N1 attack, several literatures propose the simplest solution, i.e. \textquotedblleft block the special message N1". In this paper, we conduct an in-depth research on the N1 attack based on the square-and-multiply-always (SMA) and Montgomery Ladder (ML) algorithms. We show that despite the unaccepted ciphertext countermeasure, other types of attacks is applicable to specific classes of Elgamal cryptosystems. We propose new chosen-message power-analysis attacks with order-4 elements which utilize a chosen ciphertext such that where is the prime number used as a modulus in Elgamal. Such a ciphertext can be found simply when . We demonstrate that ML and SMA algorithms are subjected to our new -type attack by utilizing a different ciphertext. We implement the proposed attacks on the TARGET Board of the ChipWhisperer CW1173 and our experiments validate the feasibility and effectiveness of the attacks by using only a single power trace.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. IET Information Security
Keywords
Elgamal cryptosystemSide-channel attacksMontgomery LadderSquare and Multiply Always attack
Contact author(s)
h_soleimany @ sbu ac ir
History
2019-12-11: last of 2 revisions
2018-08-20: received
See all versions
Short URL
https://ia.cr/2018/761
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/761,
      author = {Parinaz Mahdion and Hadi Soleimany and Pouya Habibi and Farokhlagha Moazami},
      title = {New Single-Trace Side-Channel Attacks on a Specific Class of Elgamal Cryptosystem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/761},
      year = {2018},
      url = {https://eprint.iacr.org/2018/761}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.