On the Security of RSA-PSS in the Wild

Saqib A. Kakvi

Abstract

The RSA Probabilistic Signature Scheme (RSA-PSS) due to Bellare and Rogaway (EUROCRYPT 1996) is a widely deployed signature scheme. In particular it is a suggested replacement for the deterministic RSA Full Domain Hash (RSA-FDH) by Bellare and Rogaway (ACM CCS 1993) and PKCS#1 v1.5 (RFC 2313), as it can provide stronger security guarantees. It has since been shown by Kakvi and Kiltz (EUROCRYPT 2012, Journal of Cryptology 2018) that RSA-FDH provides similar security to that of RSA-PSS, also in the case when RSA-PSS is not randomized. Recently, Jager, Kakvi and May (ACM CCS 2018) showed that PKCS#1 v1.5 provides comparable security to both RSA-FDH and RSA-PSS. However, all these proofs consider each signature scheme in isolation, where in practice this is not the case. The most interesting case is that in TLS 1.3, PKCS#1 v1.5 signatures are still included for reasons of backwards compatibility, meaning both RSA-PSS and PKCS#1 v1.5 signatures are implemented. To save space, the key material is shared between the two schemes, which means the aforementioned security proofs no longer apply. We investigate the security of this joint usage of key material in the context of Sibling Signatures, which were introduced by Camenisch, Drijvers, and Dubovitskaya (ACM CCS 2017). It must be noted that we consider the standardised version of RSA-PSS (IEEE Standard P1363-2000), which deviates from the original scheme considered in all previous papers. We are able to show that this joint usage is indeed secure, and achieves a security level that closely matches that of PKCS#1 v1.5 signatures and that both schemes can be safely used, if the output lengths of the hash functions are chosen appropriately.

Note: This the full version of the paper that appeared at SSR 2019.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.Security Standardisation Research Conference 2019 (SSR19)
DOI
10.1145/3338500.3360333
Keywords
Digital signaturesPKCSRSAPSSLossinessSecurity reductionsTLS 1.3
Contact author(s)
kakvi @ uni-wuppertal de
History
2019-11-16: revised
See all versions
Short URL
https://ia.cr/2019/1268

CC BY

BibTeX

@misc{cryptoeprint:2019/1268,
author = {Saqib A.  Kakvi},
title = {On the Security of RSA-PSS in the Wild},
howpublished = {Cryptology ePrint Archive, Paper 2019/1268},
year = {2019},
doi = {10.1145/3338500.3360333},
note = {\url{https://eprint.iacr.org/2019/1268}},
url = {https://eprint.iacr.org/2019/1268}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.