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


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

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
RSAPSSCRTfault attacksverified security
Contact author(s)
fdupress @ gmail com
2014-04-20: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.