On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks

Yasuyuki SAKAI; Kouichi SAKURAI

doi:10.1093/ietfec/e88-a.1.154

On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks

Yasuyuki SAKAI, Kouichi SAKURAI

Full Text Views

0

Share
Cite this

Summary :

In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.154-160

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.1.154

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Tamper-Resistance

Cite this

Copy

Yasuyuki SAKAI, Kouichi SAKURAI, "On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 1, pp. 154-160, January 2005, doi: 10.1093/ietfec/e88-a.1.154.
Abstract: In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.154/_p

Copy

@ARTICLE{e88-a_1_154,
author={Yasuyuki SAKAI, Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks},
year={2005},
volume={E88-A},
number={1},
pages={154-160},
abstract={In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.},
keywords={},
doi={10.1093/ietfec/e88-a.1.154},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 154
EP - 160
AU - Yasuyuki SAKAI
AU - Kouichi SAKURAI
PY - 2005
DO - 10.1093/ietfec/e88-a.1.154
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - In this paper we propose a new side channel attack, where exponent recodings for public key cryptosystems such as RSA and ECDSA are considered. The known side channel attacks and countermeasures for public key cryptosystems were against the main stage (square and multiply stage) of the modular exponentiation (or the point multiplication on an elliptic curve). We have many algorithms which achieve fast computation of exponentiations. When we compute an exponentiation, the exponent recoding has to be carried out before the main stage. There are some exponent recoding algorithms including conditional branches, in which instructions depend on the given exponent value. Consequently exponent recoding can constitute an information channel, providing the attacker with valuable information on the secret exponent. In this paper we show new algorithms of attack on exponent recoding. The proposed algorithms can recover the secret exponent, when the width-w NAF and the unsigned/signed fractional window representation are used.
ER -