Defeating Countermeasures Based on Randomized BSD Representations

Pierre-Alain Fouque 1, 2 Frédéric Muller Guillaume Poupard Frédéric Valette
1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 ENS Paris - École normale supérieure - Paris
Abstract : The recent development of side channel attacks has lead implementers to use increasingly sophisticated countermeasures in critical operations such as modular exponentiation, or scalar multiplication on elliptic curves. A new class of countermeasures is based on inserting random decisions when choosing one representation of the secret scalar out of a large set of representations of the same value. For instance, this is the case of countermeasures proposed by Oswald and Aigner, or Ha and Moon, both based on randomized Binary Signed Digit (BSD) representations. Their advantage is to offer excellent speed performances. However, the first countermeasure and a simplified version of the second one were already broken using Markov chain analysis. In this paper, we take a different approach to break the full version of Ha-Moons countermeasure using a novel technique based on detecting local collisions in the intermediate states of computation. We also show that randomized BSD representations present some fundamental problems and thus recommend not to use them as a protection against side-channel attacks.
Type de document :
Communication dans un congrès
Marc Joye and Jean-Jacques Quisquater. Cryptographic Hardware and Embedded Systems - CHES 2004: 6th International Workshop, 2004, Cambridge, MA, United States. Springer, 3156, pp.312-327, 2004, Lecture Notes in Computer Science. 〈10.1007/978-3-540-28632-5_23〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00563963
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 7 février 2011 - 16:29:00
Dernière modification le : mardi 24 avril 2018 - 17:20:13

Lien texte intégral

openaccess

Identifiants

Collections

ENS-PARIS | PSL

Citation

Pierre-Alain Fouque, Frédéric Muller, Guillaume Poupard, Frédéric Valette. Defeating Countermeasures Based on Randomized BSD Representations. Marc Joye and Jean-Jacques Quisquater. Cryptographic Hardware and Embedded Systems - CHES 2004: 6th International Workshop, 2004, Cambridge, MA, United States. Springer, 3156, pp.312-327, 2004, Lecture Notes in Computer Science. 〈10.1007/978-3-540-28632-5_23〉. 〈inria-00563963〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

36

Contact


archive-ouverte@inria.fr