Fault Attack on Elliptic Curve with Montgomery Ladder Implementation
6
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
6
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieures
Fault Attack on Elliptic Curve with Montgomery Ladder Implementation Pierre-Alain Fouque École normale supérieure - CNRS - INRIA 45 rue d'Ulm, 75230 Paris cedex 05, France Reynald Lercier DGA/CÉLAR - IRMAR, Université de Rennes La Roche Marguerite, 35174 Bruz, France Denis Réal DGA/CÉLAR - INSA-IETR, Université de Rennes La Roche Marguerite, 35174 Bruz, France Frédéric Valette DGA/CÉLAR La Roche Marguerite, 35174 Bruz, France Abstract In this paper, we present a new fault attack on elliptic curve scalar product algorithms. This attack is tailored to work on the classical Montgomery ladder method when the y-coordinate is not used. No weakness has been reported so far on such implementations, which are very efficient and were promoted by several authors. But taking into account the twist of the elliptic curves, we show how, with few faults (around one or two faults), we can retrieve the full secret exponent even if classical countermeasures are employed to prevent fault attacks. It turns out that this attack has not been anticipated as the security of the elliptic curve param- eters in most standards can be strongly reduced.
Voir
Fault Attack on Elliptic Curve with Montgomery Ladder Implementation Pierre-Alain Fouque École normale supérieure - CNRS - INRIA 45 rue d'Ulm, 75230 Paris cedex 05, France Reynald Lercier DGA/CÉLAR - IRMAR, Université de Rennes La Roche Marguerite, 35174 Bruz, France Denis Réal DGA/CÉLAR - INSA-IETR, Université de Rennes La Roche Marguerite, 35174 Bruz, France Frédéric Valette DGA/CÉLAR La Roche Marguerite, 35174 Bruz, France Abstract In this paper, we present a new fault attack on elliptic curve scalar product algorithms. This attack is tailored to work on the classical Montgomery ladder method when the y-coordinate is not used. No weakness has been reported so far on such implementations, which are very efficient and were promoted by several authors. But taking into account the twist of the elliptic curves, we show how, with few faults (around one or two faults), we can retrieve the full secret exponent even if classical countermeasures are employed to prevent fault attacks. It turns out that this attack has not been anticipated as the security of the elliptic curve param- eters in most standards can be strongly reduced.
- secure imple- mentation
- fault attack
- montgomery algorithm
- algorithm when
- montgomery implementation
- schemes imply
- such
- computation can
- montgomery ladder
Fault Attack on Elliptic Curve with Montgomery Ladder Implementation
PierreAlain FouqueReynald Lercier Ècole normale supèrieure CNRS INRIADGA/CÈLAR IRMAR, Universitè de Rennes 45 rue d’Ulm, 75230 Paris cedex 05, FranceLa Roche Marguerite, 35174 Bruz, France PierreAlain.Fouque@ens.fr Reynald.Lercier@m4x.org Denis RèalFrèdèric Valette DGA/CÈLAR INSAIETR, Universitè de RennesDGA/CÈLAR La Roche Marguerite, 35174 Bruz, FranceLa Roche Marguerite, 35174 Bruz, France Denis.Real@dga.defense.gouv.fr Frederic.Valette@m4x.org
Abstractduced. Indeed such schemes allow to use smaller keys since algorithms to compute discrete logarithms are less efficient In this paper, we present a new fault attack on ellipticin such groups than in the multiplicative group of a finite curve scalar product algorithms.This attack is tailored tofield. Ellipticcurves can be used in signature schemes as work on the classical Montgomery ladder method when thein the standard ECDSA or in encryption schemes as in the yNo weakness has been reportedcoordinate is not used.El Gamal cryptosystem.Consequently, it is useful to have so far on such implementations, which are very efficient andsecure implementations of the scalar product algorithm.In were promoted by several authors.But taking into account1999, Coron developed three countermeasures to withstand the twist of the elliptic curves, we show how, with few faultsSPA and DPA attacks on elliptic curve scalar binary expo (around one or two faults), we can retrieve the full secretHowever, the first two were shown to benentiations [8]. exponent even if classical countermeasures are employed toinefficient by Fouque and Valette in [10] and the third one prevent fault attacks.It turns out that this attack has notby Goubin in [11].All these attacks are SPA or DPA at been anticipated as the security of the elliptic curve paramother implementations of the scalar prodtacks. However, eters in most standards can be strongly reduced. Especially,uct algorithm, for instance, Montgomery algorithm when the attack is meaningful on some NIST or SECG parametheycoordinate is not used, are still believed to be secure. ters. 1.1. Previous Work Keywords:EC Cryptosystem, Montgomery Ladder, Fault Attack. Fault attacks on elliptic curve cryptosystems appeared since 2000 by Biehlet al.The ideaat Crypto’00 [1]. is to change the input points or the curve parameters or 1. Introduction also the base field so that the computations is performed on a different and weakly secure cryptographic curve.On Fault attack is a very powerful sidechannel technique tosuch curves, the discrete logarithms can be easy to com break cryptographic schemes.The idea is to inject a faultpute using PohligHellman and RhoPollard algorithm for during the computations of an implementation and to useinstance. Then,Ciet and Joye in [7] extended this attack the faulty outputs to deduce information on the secret keyby reducing the power of the attacker so that random and stored in the secure component.Bonehet al.unknown errors can be used instead of controlled ones.first intro duced this model in 1997 [3] and show how to recover secretRecently at FDTC’06, Blmeret al.[2] mounted an keys of RSA and DLogbased cryptosystems.Since theseother sidechannel attack by changing the sign of they attacks and other sidechannel attacks, many countermeacoordinate. Theyalso claimed that the attacks of Biehlet sures have been proposed so far and some implementationsal.and of Ciet and Joye can be easily avoided since it is are believed to be more secure than others.sufficient to verify at the end of the computation whether Elliptic curve cryptosystems are very important in smartthe resulting point is on the curve or not.Moreover, they card products since the computational cost is strongly reproposed an attack on the Montgomery algorithm when
1
