# 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

It is an important feature to be able to see if encryption/decryption failed. Sure, padding oracles are a problem, but so is a protocol that doesn't perform intrinsic verification of the performed operation.

If you have a key agreement protocol then you need some kind of method of validating that the decryption of the symmetric key succeeded. Now you could do this by adding a separate authentication tag over some constant value calculated by the generated/decrypted key. That would however leak this information to an attacker. So you probably need to perform the MAC calculation over some challenge, which you would also need to include in the message. You could also create an additional key using the decrypted value as seed, and use that to verify the result, but again: additional operations are required and there is still an authentication tag to be sent. Note that MAC tags can also be vulnerable to (time based) oracle attacks.

What you really don't want is implicit verification, i.e. using the resulting keys and see if you get verification errors over the actual data. I'm using a protocol that does this and it makes for horrific implementation choices. In an update of the protocol explicit authentication with a third key (used to HMAC the handshake) is being utilized.

So currently there is intrinsic verification of the result, in your scheme there isn't. That said, your scheme is probably secure. RSA KEM is even more secure so if you like your scheme you should probably go for RSA KEM and send an authentication tag within the same message containing the encapsulated key.

• Why do I not want implicit verification (except for the reason that it is slower)? – K. Biermann Jul 20 '15 at 16:36
• Because it is unclear what causes the failure, the key agreement or a protocol / integrity failure. Furthermore your implementation may need to report back to the key agreement procedure that there has been a failure. That makes for horrific code. DecryptFile should not report back to higher/earlier parts of the protocol. – Maarten Bodewes Jul 20 '15 at 16:45