Score:6

Crypto

Do RSA signatures really need padding?

randyrand

10/22/23, 6:05 AM

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.

2083

3 + 3

kelalaka

10/22/23, 4:08 PM

possible dupe of [Is there an easy way to make textbook RSA secure enough so it can be used in real life?](https://crypto.stackexchange.com/q/95915/18298) 2) [RSA signatures without padding?](https://crypto.stackexchange.com/q/26852/18298) 3 [Why hash the message before signing it with RSA?](https://crypto.stackexchange.com/q/12768/18298)

randyrand

10/24/23, 10:52 AM

Hmm, at least for me, those do not help me understand.

kelalaka

10/24/23, 3:03 PM

I think what you need to learn about the attack models on the signature schemes then your question will become more clear. Here read from here [Relation between attack and attack model for signatures](https://crypto.stackexchange.com/q/9063/18298) or on [Wikipedia Digital Signature Forgery](https://en.wikipedia.org/wiki/Digital_signature_forgery) and see an attack [here](https://crypto.stackexchange.com/q/88020/18298)

Score:14

Crypto

poncho

10/22/23, 2:17 PM

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

+ 6

K.G.

10/22/23, 6:14 PM

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. https://link.springer.com/chapter/10.1007/3-540-44598-6_14

randyrand

10/24/23, 11:25 AM

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?

fgrieu

10/24/23, 11:43 AM

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

Ruggero

10/25/23, 9:03 AM

@K.G. there is also this (https://link.springer.com/article/10.1007/s00145-017-9257-9) which is tighter but based on a different problem.

Maarten Bodewes

10/25/23, 10:19 AM

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?

poncho

10/25/23, 11:07 AM

Yes, I would consider MGF1 to be padding; however, that really is semantics...

Score:11

Crypto

Meir Maor

10/22/23, 8:14 AM

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.

+ 2

randyrand

10/24/23, 11:10 AM

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

Meir Maor

10/24/23, 1:55 PM

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.

Score:7

Crypto

fgrieu

10/24/23, 11:58 AM

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.

+ 3

randyrand

10/25/23, 7:41 AM

thanks for the clear answer! This makes sense with my broader understanding

fgrieu

10/25/23, 8:54 AM

@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

randyrand

10/27/23, 9:01 PM

Yes. just leaving time for other answers.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Do RSA signatures really need padding?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.