Paper 2014/252

Making RSA-PSS Provably Secure Against Non-Random Faults

Gilles Barthe, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Mehdi Tibouchi, and Jean-Christophe Zapalowicz

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 article, 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 force the faulty signatures to be a multiple of one of the prime factors of the RSA modulus. Such non-random faults induce more complex probability distributions than in the original proof, which we analyze using careful estimates of exponential sums attached to suitable rational functions. 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.

Note: An external archive containing code and formal proofs can be found at https://www.easycrypt.info/downloads/ches14/faultyPSS.tar.bz2

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RSAPSSCRTfault attacksverified security
Contact author(s)
fdupress @ gmail com
History
2014-04-20: received
Short URL
https://ia.cr/2014/252
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/252,
      author = {Gilles Barthe and François Dupressoir and Pierre-Alain Fouque and Benjamin Grégoire and Mehdi Tibouchi and Jean-Christophe Zapalowicz},
      title = {Making {RSA}-{PSS} Provably Secure Against Non-Random Faults},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/252},
      year = {2014},
      url = {https://eprint.iacr.org/2014/252}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.