Paper 2018/855
On the Security of the PKCS#1 v1.5 Signature Scheme
Tibor Jager, Saqib A. Kakvi, and Alexander May
Abstract
The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable. We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply. In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ACM CCS 2018
- DOI
- 10.1145/3243734.3243798
- Keywords
- Digital SignaturesPKCSRSAlossinesssecurity reductionstandards
- Contact author(s)
- saqib kakvi @ upb de
- History
- 2018-09-20: received
- Short URL
- https://ia.cr/2018/855
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/855,
author = {Tibor Jager and Saqib A. Kakvi and Alexander May},
title = {On the Security of the {PKCS}#1 v1.5 Signature Scheme},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/855},
year = {2018},
doi = {10.1145/3243734.3243798},
url = {https://eprint.iacr.org/2018/855}
}