# Why don't use random padding in RSA?

Consider the following scenario:

Sender S sends a message to receiver R. He uses a hybrid encryption scheme with RSA as key-encapsulation algorithm and AES-256-CTR (4byte-counter) and SHA256-HMAC. These algorithms are specified and already known by the receiver → the receiver knows the encrypted key length: 32byte AES-key + 12byte AES-nonce + 64byte HMAC-key = 108byte

Why don't use RSA(SECURE_RANDOM(404) || key-block) as padding-scheme?

1. The length is already known by the receiver, so there is no reason to indicate it.
2. If the key-capsule is altered it will be detected because the decrypted keys will be wrong and the HMAC-verification will fail.
3. It shouldn't be susceptible against padding-oracle-attacks because the application cannot distinguish between correct decryption and defect padding (in contrast to PKCSv1.5 and OAEP after standard).

There probably is a very good reason not to do this, but I'm not seeing it.

• Probably because we want to be more confident in 2. $\;$ – user991 Jul 19 '15 at 11:56
• Maybe, but if the result is that we are susceptible to padding oracle attacks, we are doing sth. wrong... – K. Biermann Jul 19 '15 at 12:02
• You would have a problem formally proving (3). However, there are much simpler things that you can do than OAEP. For example, chooses a random string R 2040 bits long and sends RSA(R). Then, use H(R) as the key where H is SHA256. This can be proved secure in the random oracle model and is much simpler. – Yehuda Lindell Jul 19 '15 at 12:08
• Good idea, have you a link to a prove/analysis? – K. Biermann Jul 19 '15 at 12:10
• AFAIK what Yehuda described is called RSA KEM. I believe it comes with a pretty strong security proof. – CodesInChaos Jul 19 '15 at 12:27