In cryptography we have things that are proven to be insecure, or proven to be secure, and a big collection of things that are neither. The PKCS#1 v1.5 signature security happens to be in this kind of middle ground, and has been there since 1998. Nobody has broken it, but nobody has either proven it to be secure in the forms that it is being used.
The 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18) had paper exploring PKCS#1 signature security. A preprint version of it is at https://eprint.iacr.org/2018/855. [1]
Bellare and Rogaway did show already in 1996, that when hash output size is equal to RSA key size, the signature scheme is as secure as the hash itself. Then they defined the RSA-PSS. [2]
Until now there has not been any kind of proof about security of the signatures with PKCS#1 v1.5 padding.
RSA-PSS
“But we already have RSA-PSS, and PKCS#1 v2.1 recommends use of that.“
In theory the RSA-PSS is a nice solution, but its support in SIM card environments is poorly specified, and thus implementations vary in detail. Nor is it widely expected on signature responses! Furthermore it really requires user certificates indicating that signatures are to be done in RSA-PSS format.
Like the paper notes, the RSA-PSS is very complicated, while PKCS#1 v1.5 signatures has not been shown to be broken, and therefore everybody still uses basic PKCS#1 v1.5 signatures, and therefore the authors took another attempt at proving PKCS#1 v1.5 signature properties.
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.
. . . .
Thus, even though our proofs do not immediately apply to PKCS#1 v1.5 when instantiated with standard hash functions, such as SHA-512, we show that it is still possible to instantiate PKCS#1 v1.5 signatures in a meaningful way, and based on standardized constructions, such as MGF1 from RFC 8017 or the XOFs SHAKE128 and SHAKE256 standardized by NIST in FIPS 202.
This new proof holds for a case where the hash size is at least half of the RSA modulus size (2048 bit modulus : 1024 bit hash).
External hashing with e.g. SHAKE256 producing 1024 bit hash output and signing it is provably as secure as that hash.
Proving that PKCS#1 v1.5 is safe with SHA-256 and 2048 bit RSA key size is still to be achieved, but it should be possible.
It should be noted that PKCS#1 v1.5 encryption is breakable with chosen-ciphertext attack, and RSA-OAEP should be used instead.
On the other hand, if one has single use (“ephemeral”) 1024 bit RSA key, the chosen-ciphertext does not really matter and mass factoring of single use 1024 bit RSA public keys is still beyond anybody’s capabilities.
Written and Edited by: Matti Aarnio
References
[1] https://eprint.iacr.org/2018/855
[2] Bellare, Rogaway 1996: Exact proof of RSA-FDH, RSA-PSS