6
$\begingroup$

For encryption, we want identical plain-text's to encrypt to unique ciphers, also called Semantic Security.

For Signatures, the plain-text (i.e. message hash) is not a secret. The plain-text, if you can call it that, is publicly known. We don't need Semantic Security. There is no “plain-text”, so to speak. We aren’t encrypting.

So do we actually need padding in RSA Signatures? Does padding do more than make it harder to infer information about plain-texts (which is why we usually add it for encryption)? Or is it more of a, "well, it doesn't hurt?" situation?

What is the theory behind adding padding (PSS, PKCS, etc) to signatures?

Note: There is an existing question of similar title, but the question's body does not ask what the title asks.

Improve this question
$\endgroup$
3

3 Answers 3

Reset to default
7
$\begingroup$

do we actually need padding in RSA Signatures?

Yes if we want to:

  • Sign the hash of a message computed with a standard cryptographic hash like SHA-256, and resist attack in a chosen-messages setup (where the attacker can obtain the signature of some messages of their choice, and succeeds by signing any other message of their choice; so-called EUF-CMA security). In particular, if we directly RSA-sign a 256-bit hash, we are vulnerable to the Desmedt-Odlyzko attack.
  • Directly sign a message without hashing it. Textbook RSA signature of the bare message is insecure in more ways.

No is we have a wide-enough hash; and demonstrably so if the hash is (about) as wide as the public modulus. For references see this (currently unanswered) question asking exactly how wide the hash needs to be.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks for the clear answer! This makes sense with my broader understanding $\endgroup$
    – randyrand
    Oct 25, 2022 at 7:41
  • $\begingroup$ @randyrand: if an answer best/fully answers your question, the standard "thanks" is simply accepting it using the tick button ✓ on the left of the answer $\endgroup$
    – fgrieu ♦
    Oct 25, 2022 at 8:54
  • 1
    $\begingroup$ Yes. just leaving time for other answers. $\endgroup$
    – randyrand
    Oct 27, 2022 at 21:01
14
$\begingroup$

Actually, we don't need padding; one alternative is 'full-domain-hashing'.

For example, if you have 2048 bit RSA key with modulus $n$, you might give the message to SHAKE and extract 2047 bits; and insert a 0 bit at the front. Take that and perform the RSA private operation on it, that's your signature.

It should be easy to prove that, assuming SHAKE acts like a random oracle, that this is secure assuming the RSA problem is hard (using the rerandomization property of RSA).

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ There’s a trivial proof, which is quite loose. And then there is an optimal proof where the reduction is easy, but its analysis is a bit more involved. link.springer.com/chapter/10.1007/3-540-44598-6_14 $\endgroup$
    – K.G.
    Oct 22, 2022 at 18:14
  • $\begingroup$ So you’re saying as long as we sign a secure hash of the message, then padding is not necessary? Isn’t that what most signing algorithms already do? So padding (for signatures) is not necessary pretty much… ever? $\endgroup$
    – randyrand
    Oct 24, 2022 at 11:25
  • 2
    $\begingroup$ @randyrand: no, poncho is not saying that. SHA-256 is a secure hash for signature applications, but direct RSA signature of a SHA-256 hash is not secure. $\endgroup$
    – fgrieu ♦
    Oct 24, 2022 at 11:43
  • $\begingroup$ @K.G. there is also this (link.springer.com/article/10.1007/s00145-017-9257-9) which is tighter but based on a different problem. $\endgroup$
    – Ruggero
    Oct 25, 2022 at 9:03
  • $\begingroup$ poncho, would you consider MGF1 in PSS a method of padding that turns a secure hash into a domain hash? Is there a grey area there? $\endgroup$
    – Maarten Bodewes ♦
    Oct 25, 2022 at 10:19
11
$\begingroup$

Yes, you need padding. Textbook RSA is very problematic. The simplest attack for signatures is probably malleability. Take two RSA signatures, multiply them you will get a valid signature for the multiplication.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don’t see how padding would fix that issue. Can’t you still do that with padded signatures? Padded or unpadded, forging random new signatures is statistically useless, as long as your message is already a secure hash. (Thanks for your answer btw!!) $\endgroup$
    – randyrand
    Oct 24, 2022 at 11:10
  • $\begingroup$ If you do all or nothing padding you can't take message, signature pairs and create a new third pair. With textbook signature you can. If you have a message hash than this trivial attack won't work but you still could have issues with the hash being much shorter than the RSA key. And poncho suggested full domain hashing as an alternative to padding. $\endgroup$
    – Meir Maor
    Oct 24, 2022 at 13:55

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.