19
$\begingroup$

Is RSASSA-PKCS1-v1_5 a good signature scheme to recommend that people use in new systems? Is it believed to be secure and represent the state-of-the-art in RSA-based signatures?

I understand that RSA-PSS is a newer signature scheme, also standardized in PKCS #1. I found a memo from RSA recommending that people transition to RSA-PSS. Is that right? Would it be better to recommend that people use RSA-PSS, instead of RSA-PKCS1-v1_5? If you were going to recommend a single RSA-based signature scheme, which would you recommend that new systems use?

Practical relevance: for instance, at the moment the current draft of the WebCryptoAPI recommends supporting RSASSA-PKCS1-v1_5 (but not RSA-PSS).

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ It's very important not to confuse RSASSA-PKCS1-v1_5 (the signature system) and RSAES-PKCS1-v1_5 (the encryption system). The latter is very broken in practice. Do not use RSAES-PKCS1-v1_5! $\endgroup$
    – CodesInChaos
    Dec 30, 2012 at 15:59

3 Answers 3

Reset to default
12
$\begingroup$

PSS is harder to implement because it uses randomness -- randomness is hard on many embedded systems like smart cards.

The most proclaimed advantage of PSS is that it has a "security proof" with, apparently, a rather tight reduction (see this page for some references). Security proofs are not an easy subject; the proof for OAEP (the encryption padding which is like the "sister protocol" to PSS) was found out to be wrong by Shoup and then repaired again by Fujisaki, Okamoto, Pointcheval and Stern, albeit with some casualties on the tightness front. I do not know how much all of this extends to PSS, but it shows that security proofs, however cool they may be, also need the "peer scrutiny" on which cryptographic security is traditionally built.

On the other hand, v1.5 signatures have been exposed "in the wild" for twice as long as PSS, and remain unbroken. In my opinion, this is very good and I quite trust that kind of security.

On a practical point of view, using a signature algorithm implies using a key storage device which knows that algorithm (smart card, HSM, software implementation...). The choice is not necessarily up to the application which requests the signature.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Indeed. In a typical setup, I would worry more about side channel attacks on the implementation, factorization of the modulus, and attacks on the hash, than about attacks on RSASSA-PKCS-v1_5. Only if the adversary can obtain the signature of many chosen messages, which is unusual, do I see the slightest practical risk that a new attack could emerge, like some have been found in this setup against ISO/IEC 9796(-1) and ISO/IEC 9796-2 scheme 1. $\endgroup$
    – fgrieu ♦
    Sep 21, 2012 at 5:56
  • 3
    $\begingroup$ It's important to note that PSS isn't broken when used without randomness, the security reduction just becomes less tight. $\endgroup$
    – CodesInChaos
    Dec 30, 2012 at 16:01
  • 2
    $\begingroup$ If randomness is an issue, it is possible to fully de-randomize RSASSA-PSS, while fully keeping the security, by replacing the randomness with $\operatorname{HMAC}(\text{private key}, H(M))$. Since $H(M)$ is computed as part of RSASSA-PSS, the overhead is constant. Proof sketch: to one not knowing the private key, if $\operatorname{HMAC}$ and $H$ are secure, then the modified scheme is indistinguishable from RSASSA-PSS supplemented with a gnome that caches RSASSA-PSS signatures of all previously submitted messages; and that gnome-supplemented signature scheme is secure if RSASSA-PSS is. $\endgroup$
    – fgrieu ♦
    Sep 1, 2017 at 15:56
5
$\begingroup$

The answer is either "no" or "it depends".

Generally speaking, RSA-PSS is more robust, in the sense that you don't have to take as many extra precautions in order to use it securely. RSA-PKCS#1-v1.5 is OTOH more widely supported by pre-exisiting software, but you sometimes have to patch the way it is used in order to prevent exploits. For instance, if you use RSA-PKCS#1-v1.5 with the MD5 or SHA1 hash algorithms, and sign data originally sent to you from 3rd parties, you have to add a chunk of random data to the data-to-be-signed in order to prevent collision attacks. This is not necessary if you use RSA-PSS.

In the original 1998 submission of EMSA-PSS by Bellare and Rogaway to IEEE P1363 (which is based on the 1996 paper by the same authors), the encoding takes a mask generation function G as a parameter. In this specification, the message M is taken as input, and a fresh random 20 octet string seed is generated. A 20 octet digest w = G(seed||M) is generated, and that w is in turn used for generating the mask.

In the final IEEE P1363 specification of EMSA4, as well as the PKCS#1 v2.1 specification of RSASSA-PSS, the input is a digest of the message instead of the message itself, which makes the algorithm vulnerable to collisions in the underlying hash function, but OTOH allows for the seed length to be parametrizable.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I don't believe that PSS will save you from a non-collision-resistant hash function. With PSS, the first step is to hash the message as given (without adding any unpredictable salt); and the following operations work solely on the hash, and not the original message. Hence, if this hash function is not collision-resistant, neither is the PSS signature operation. $\endgroup$
    – poncho
    Sep 20, 2012 at 23:06
  • $\begingroup$ @Henrick Hellstroöm: you are referring to adding randomness at the beginning of a message to reinforce MD5 or SHA against collision attacks. As poncho said, this is no argument in favor of RSA-PSS. $\endgroup$
    – fgrieu ♦
    Sep 21, 2012 at 6:07
  • 4
    $\begingroup$ Actually, the original PSS proposal by Rogway and Bellare included a different hashing mechanism that calculated the digest as Hash(padding||salt||M). This was later changed in PKCS#1 v2.1, but that algorithm is commonly referred to as RSASSA-PSS. $\endgroup$
    – Henrick Hellström
    Sep 21, 2012 at 6:39
  • 1
    $\begingroup$ @Henrick Hellström: Ahhh, I did not know that; only knew about RSASSA-PSS as in PKCS#1v2.1, which starts by hashing the message. I now see your point. I read RSA-PSS as RSASSA-PSS in your answer, and used the former for the later in my comment. Perhaps you could include the description of RSA-PSS in your answer (one benefit is it would allow me to revise my vote). $\endgroup$
    – fgrieu ♦
    Sep 21, 2012 at 7:13
3
$\begingroup$

I'm not going to add any analysis, but just some RFC quotes and timelines about RSA signing ('signature scheme with appendix'), PKCS #1 v1.5 and PSS ('probabilistic signature scheme')

February 2003 Users encouraged to move away from RSASSA PKCS #1 v1.5 in RFC 3447 PKCS #1: RSA v2.1, §8: Signature schemes with appendix, p. 36

Two signature schemes with appendix are specified in this document: RSASSA-PSS and RSASSA-PKCS1-v1_5. Although no attacks are known against RSASSA-PKCS1-v1_5, in the interest of increased robustness, RSASSA-PSS is recommended for eventual adoption in new applications. RSASSA-PKCS1-v1_5 is included for compatibility with existing applications, and while still appropriate for new applications, a gradual transition to RSASSA-PSS is encouraged. [emph. added]

November 2016 RSASSA PKCS #1 v1.5 is deprecated by RFC 8017 PKCS #1: RSA v2.2, §8: Signature Scheme with Appendix, p. 32, and PSS is declared "required".

Two signature schemes with appendix are specified in this document: RSASSA-PSS and RSASSA-PKCS1-v1_5. Although no attacks are known against RSASSA-PKCS1-v1_5, in the interest of increased robustness, RSASSA-PSS is REQUIRED in new applications. RSASSA-PKCS1-v1_5 is included only for compatibility with existing applications.

Not signing, but encryption*

*I've mixed up RSASSA-PKCS1-v1.5 and RSAES-PKCS1-v1.5 a few times, maybe others have. This is included for their benefit...

PKCS #1 v1.5 for encryption has been deprecated for 20 years.

October 1998 RSAES PKCS #1 v1.5 is deprecated in RFC 2437 PKCS #1 RSA v2.0, §7 Encryption Schemes, p. 11 in lieu of RSAES-OAEP. (same wording repeated in RFC 3447)

RSAES-OAEP is recommended for new applications; RSAES-PKCS1-v1_5 is included only for compatibility with existing applications, and is not recommended for new applications.

November 2016 RFC 8017, §8: Encryption Schemes, p. 17 brings some slightly stronger wording.

RSAES-OAEP is REQUIRED to be supported for new applications; RSAES-PKCS1-v1_5 is included only for compatibility with existing applications.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.