Why don't use random padding in RSA?

Question

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.

Answer 1

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.