# Why does RSA signature need padding?

Actually, I think I know why, but consider RSA2048 and SHA256. What about to, instead of padding, just use pbkdf2 with just 1 iteration to expand the 256bits hash to full 2048bits and use those 2048bits as an input for the plaintext RSA?

What would be wrong with that crypto-schema?

• That's called RSA-Full Domain Hash and assuming PBKDF2 with 1 iteration and 2048 bit output behaves like a random oracle that maps exactly into the range $[0,n)$, this is provably secure. To weaken the previous assumption it suffices to generate a 4096 bit hash and reducing it $\bmod n$. – SEJPM Jan 2 '19 at 18:50
• PBKDF2 is for passwords. HKDF-expand would probably be a better idea. Or MGF1, but then you'd have PSS padding. Basically you're asking why you need padding to replace it with your own padding scheme. – Maarten Bodewes Jan 2 '19 at 19:16
• @MaartenBodewes I need a scheme without randomness. I need the same paintexts to have a same signature. According to your comment I should check PSS padding... thanks – smrt28 Jan 2 '19 at 19:33
• You can set the salt size to zero bytes for PSS. – Maarten Bodewes Jan 2 '19 at 19:57
• You want to used PBKDF2, HKDF-expand or MGF1 to get to 2047 bit, not 2048. That or you need to reduce the result modulo N at least for verification. – fgrieu Jan 2 '19 at 23:07

As indicated in the comments, using PBKDF2 instead of e.g. PSS is replacing the padding scheme with another padding scheme. PBKDF2 is used as a key derivation scheme that accepts a password. Although that password needs to be encoded as bytes first, it does mean that you use PBKDF2 differently from how it is intended.

If PBKDF2 is used without a salt then you would have a deterministic scheme. If you do use a salt, then you'd need to somehow put it in your signature scheme. That's not necessarily a huge problem, but your current scheme is not fully described at best.

Similarly, you probably simply mask out the most significant (leftmost) bit of the PBKDF2 result to zero. That's fine as long as you describe it correctly and perform verification correctly. It's slightly awkward that the result is within the range $$[0, 2^{(l - 1)})$$ rather than $$[0, {N - 1})$$ to create a full domain hash but I guess we can look past that.

PSS is provable secure (given the usual pre-conditions, such as RSA and the used hashes being secure of course). Your padding scheme on the other hand lacks any kind of security proof (although, as SEJPM already commented, it would probably be easy to show that it generates a full domain hash, and that's considered secure). I don't see why it would not be secure - I think it is even likely that it is rather secure. However, with any cryptanalysis on a fully described scheme, that's just an educated guess.

The question is why you would need it since PKCS#1 v1.5 padding (for signature generation) only requires a prefix / postfix in addition to the hash value and PSS can be configured to use a single hash function (or any combination of two secure hash functions, one for the data and one as configuration parameter for MGF1).

If you'd study PSS you'll probably conclude that it is not that different from your scheme at all...

• The data I ecrypt is actually a single PBKDF2 hashed password. So why to add padding to something what is already random and long enough? Maybe just to follow the standards. I checked OpenSSL sources and the default RSA padding just sets 1st byt to 0, 2nd to 2, then random nonzero bytes follows, then 0 and then the plaintext. I don't see any reason adding padding there artificially. MGF1 is just naive data+block_order hashed. How it could be proven more secure than PBKDF2? – smrt28 Jan 4 '19 at 16:18
• Oh boy, you are confusing encryption and signature generation. Both use different padding schemes and, more importantly, different keys. This is an XY problem. What are you trying to achieve? – Maarten Bodewes Jan 4 '19 at 16:33
• Check github.com/smrt28/tc-play/blob/yubikey/README.md, the Yubikey section. Hope, you'll realize it's not as crazy as it looks. ;-) – smrt28 Jan 4 '19 at 16:40
• Oh yeah. Right. Ok, why not just implement v1.5 padding for signature generation? That's deterministic and combined with raw RSA decryption with the private key gives you a 100 percent normal scheme, which may be implemented with any device offering the scheme. And it remains unbroken after all those years. PSS with a zero byte salt would be provable secure but hardware devices are unlikely to support it. – Maarten Bodewes Jan 4 '19 at 16:49
• I'm forced to use decipher function on the device sinc it's the only available function there. I take the user password, PBKDF2 it and pass it throuh the decip. Yubikey function and PBKDF2 the result again. Basically, I don't sign or encrypt anything, so I don't think if padding would be necessary there. – smrt28 Jan 4 '19 at 17:03