### 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 $N-1$ attack on the modular exponentiation algorithms such as BRIP and square-and-multiply-always methods. This attack makes use of the ciphertext $N-1$ as a distinguisher of low order to obtain a strong relation between side-channel leakages and secret exponent. The so-called $N-1$ 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 $N-1$ attack, several literatures propose the simplest solution, i.e. \textquotedblleft block the special message $N-1$". In this paper, we conduct an in-depth research on the $N-1$ attack based on the square-and-multiply-always (SMA) and Montgomery Ladder (ML) algorithms. We show that despite the unaccepted ciphertext $N-1$ countermeasure, other types of $N-1$ 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 $c$ such that $c^2= -1 \bmod p$ where $p$ is the prime number used as a modulus in Elgamal. Such a ciphertext can be found simply when $p\equiv 1\mod 4$. We demonstrate that ML and SMA algorithms are subjected to our new $N-1$-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.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. IET Information Security
Keywords
Elgamal cryptosystemSide-channel attacksMontgomery LadderSquare and Multiply Always$N-1$ attack
Contact author(s)
h_soleimany @ sbu ac ir
History
2019-12-11: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/761

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},
note = {\url{https://eprint.iacr.org/2018/761}},
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.