# Why use randomness in digital signature algorithms?

I understand why randomness has to be employed in encryption, because deterministic ciphers are not IND-CPA. I don't understand why digital signature schemes that employ randomness, like RSA-PSS, are any better than purely deterministic ones like RSA-FDH. Isn't it still likely that RSA-FDH is EUF-CMA?

Acronyms:

• IND-CPA: indistinguishable under chosen plaintext attack
• RSA-FDH: Hash the message, then apply textbook RSA
• RSA-PSS: Another RSA variant
• EUF-CMA: Existentially unforgeable under (adaptive) chosen message attack
• Maybe not a problem for EUF-CMA, but leaking information about the plaintext may be an issue in other situations. I'm not sure that the message and signature are always available to an attacker at the same time. In that case a deterministic signature will (at least) indicate to an attacker if a message is identical to one that was send before. – Maarten Bodewes Apr 23 '15 at 16:51
• "I don't understand why digital signature schemes that employ randomness, like RSA-PSS, are any better than purely deterministic ones like RSA-FDH." - could you point out where this claim is made? – Maarten Bodewes Apr 23 '15 at 16:53
• Worth noting: in "RSA-FDH: Hash the message, then apply textbook RSA", Hash is not the run-of-the-mill SHA-something; it needs to be (near) as wide as the RSA key. – fgrieu Apr 23 '15 at 21:31
• @Maarten Bodewes: I added a quote in my answer. – fgrieu Apr 23 '15 at 22:05

The main benefit of adding randomness in RSA signature padding is that it simplifies and strengthens security arguments. At least that's claimed by PKCS#1v2, paragraph above 8.1.1 (emphasis mine)

RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a “tighter” security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures-How to Sign with RSA and Rabin (in proceedings of Eurocrypt 1996)] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [Jean-Sébastien Coron: On the Exact Security of Full Domain Hashing (in proceedings of Crypto 2000)].

De-randomization can be used to turn a randomized signature scheme (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random salt) into a deterministic one: we use some CSPRNG seeded with the (hash of the) message to be signed instead of true randomness, essentially transforming the scheme into a deterministic one (similar to deterministic RSA-FDH), with a security proof. The weakness in that simple argument is that an adversary that hypothetically could get benefit of some characteristic the random portion may have, can now try messages until finding one with the corresponding pseudo-randomness having that characteristic, then obtain a signature; so quantitative security bounds on the number of signature queries (rather than any kind of oracle queries) necessary to make a forgery is not as good as with the original randomized scheme.

Update following comment: in the above I'm considering a truly secure CSPRNG, but one that is known to the attacker, which can thus run it without querying the signature-producing device/oracle. That conceivably could matter: a real-life attacker might have a low and hard limit on the number of signatures for chosen message she can obtain from a remote server, but can run the CSPRNG (and whatever other computation involving the public key) at high speed with her own CPUs.

Note: My answer above is at the hand-waving level, with no proof, rather than a precise comparison of the security of RSA-PSS and RSA-FDH for stated security criteria and hypothesis on RSA; which is complex.

While some fault-based attack (like Dan Boneh, Richard A. DeMillo, Richard J. Lipton's On the Importance of Checking Cryptographic Protocols for Faults, in proceedings of EuroCrypt 1997) indeed are blocked by a randomized message, this is an a posteriori rationalization; such attacks should be blocked by independently checking any signature produced against the public key before it is output.

Randomized rather than deterministic padding has an influence for side-channel attacks, but it is debatable that randomizing improves security; when doing some DPA attacks, a known random input is often the ideal setup (note that the padded message gets known to the adversary in any RSA signature scheme).

• Is there any criterion stronger than EUF-CMA which RSA-PSS satisfies but RSA-FDH doesn't? From your answer, it seems to me that the main advantage of RSA-PSS is greater mathematical rigour (proofs with fewer assumptions or simplifications) – jkabrg Apr 23 '15 at 12:29
• Is your second paragraph assuming that the CSPRNG actually isn't CS? – jkabrg Apr 23 '15 at 12:44
• @user3491648: That's not my domain of expertise, but I do not think there is something intrinsically stronger than EUF-CMA that RSA-PSS satisfies but deterministic RSA-FDH doesn't; however the assumptions for proof that RSA-PSS is EUF-CMA might be weaker than for deterministic RSA-FDH; and my understanding is that (as stated with a conditional in the answer) the quantitative security (as measured by the minimum number of signatures an adversary demonstrably needs to obtain for success with a certain probability) is stronger for RSA-PSS than for deterministic RSA-FDH. – fgrieu Apr 23 '15 at 12:48
• Is this quantitative benefit useful? – jkabrg Apr 23 '15 at 12:50
• No. $\:$ In SUF-CMA, the adversary could also succeed by producing an accepted signature-message pair such that the signer did produce that signature, but not for that message. $\:$ Also, in both cases, the adversary could succeed by producing any accepted signature-message pair for a message that the signer did not sign, including if the signer already produced that signature (on one or more different messages). $\;\;\;\;$ – user991 Apr 23 '15 at 23:01

RSA-FDH is EUF-CMA in the random oracle model, unfortunately I only found a source in German for that proof. Basically it is game hopping, until you end up with breaking the random oracle assumption.

Slides about a similar approach can be found here on pages 39-51 (by Alejandro Hevia), which also addresses the topic of key reduction and key length.

Under a stronger assumption (Phi-hiding), Kakvi and Kitz presented a new proof in Optimal Security Proofs for Full Domain Hash, Revisited (2012).

• So is there any reason to prefer a randomized approach like RSA-PSS? More rigorous security proof? – jkabrg Apr 23 '15 at 12:02
• The slides state, that FDH is secure with at least 4096 bits, if you set limits on the oracle queries as stated a few slides earlier. The security proof is quite loose. I think the security of PSS was tight in the random oracle model, but I am not entirely sure atm. – tylo Apr 24 '15 at 10:03