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
-
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}
}