[Resource Topic] 2018/761: New Single-Trace Side-Channel Attacks on a Specific Class of Elgamal Cryptosystem

Welcome to the resource topic for 2018/761

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

Authors: Parinaz Mahdion, Hadi Soleimany, Pouya Habibi, Farokhlagha Moazami


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.

ePrint: https://eprint.iacr.org/2018/761

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .