Cryptology ePrint Archive: Report 2014/252

Making RSA-PSS Provably Secure Against Non-Random Faults

Gilles Barthe and François Dupressoir and Pierre-Alain Fouque and Benjamin Grégoire and 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.

Category / Keywords: public-key cryptography / RSA, PSS, CRT, fault attacks, verified security

Date: received 9 Apr 2014, last revised 9 Apr 2014

Contact author: fdupress at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20140420:152136 (All versions of this report)

Short URL: ia.cr/2014/252

Discussion forum: Show discussion | Start new discussion