Making RSA–PSS Provably Secure against Non-random Faults

Abstract : RSA–CRT is the most widely used implementation for RSA signatures. However, deterministic and many probabilistic RSA signatures based on CRT are vulnerable to fault attacks. Nevertheless, Coron and Mandal (Asiacrypt 2009) show that the randomized PSS padding protects RSA signatures against random faults. In contrast, Fouque et al. (CHES 2012) show that PSS padding does not protect against certain non-random faults that can be injected in widely used implementations based on the Montgomery modular multiplication. In this paper, we prove the security of an infective countermeasure against a large class of non-random faults; the proof extends Coron and Mandal's result to a strong model where the adversary can choose the value of the faulty signatures modulo one of the prime factors of the RSA modulus. This fault model is clearly strictly more general than Coron and Mandal's, and it captures most of the non-random faults of Fouque et al. Such non-random faults induce, together with the infective countermeasure, more complex probability distributions than in the original proof; we analyze them using careful estimates of character sums over finite fields. The security proof is formally verified using appropriate extensions of EasyCrypt, and provides the first application of formal verification to provable (i.e. reductionist) security in the context of fault attacks.
Type de document :
Communication dans un congrès
Cryptographic Hardware and Embedded Systems - 2014, Sep 2014, Busan, South Korea. Springer, LNCS 8731, pp.206 - 222, 2014, CHES 2014. 〈http://www.chesworkshop.org/ches2014/start.php〉. 〈10.1007/978-3-662-44709-3_12〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094057
Contributeur : Pierre-Alain Fouque <>
Soumis le : jeudi 11 décembre 2014 - 15:39:07
Dernière modification le : mercredi 16 mai 2018 - 11:23:29
Document(s) archivé(s) le : jeudi 12 mars 2015 - 10:55:53

Fichier

FaultRSA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Gilles Barthe, François Dupressoir, Pierre-Alain Fouque, Mehdi Tibouchi, Jean-Christophe Zapalowicz, et al.. Making RSA–PSS Provably Secure against Non-random Faults. Cryptographic Hardware and Embedded Systems - 2014, Sep 2014, Busan, South Korea. Springer, LNCS 8731, pp.206 - 222, 2014, CHES 2014. 〈http://www.chesworkshop.org/ches2014/start.php〉. 〈10.1007/978-3-662-44709-3_12〉. 〈hal-01094057〉

Partager

Métriques

Consultations de la notice

642

Téléchargements de fichiers

154