Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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).

share|improve this question
1  
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! – CodesInChaos Dec 30 '12 at 15:59

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
1  
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. – fgrieu Sep 21 '12 at 5:56
It's important to note that PSS isn't broken when used without randomness, the security reduction just becomes less tight. – CodesInChaos Dec 30 '12 at 16:01
up vote 2 down vote

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.

share|improve this answer
2  
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. – poncho Sep 20 '12 at 23:06
@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. – fgrieu Sep 21 '12 at 6:07
2  
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. – Henrick Hellström Sep 21 '12 at 6:39
1  
@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). – fgrieu Sep 21 '12 at 7:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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