I'm RSA-encrypting a randomly-created AES key. Do I need padding for the RSA?

Question

There seem to be two ways to RSA-encrypt using .Net:

EncryptValue (which doesn't seem to pad the plaintext).

and

Encrypt (which does).

I was wondering, since what I'm encrypting is a cryptographically secure (cough...) AES key, do I need it to be padded by an official padding scheme? Assuming, of course, that the length of the data (the AES key) is exactly the right length, or padded by something simple e.g. zeros.

Answer 1

Yes, you need padding, because without padding

1. If the public exponent $e$ is below some threshold, decryption is trivial by the $e^\text{th}$ root attack, or extension thereof. We don't even know for sure what a safe threshold is (see this), but it depends on the size of both the AES key and the RSA public modulus.
2. If you send the same key encrypted to at least $e$ recipients (each with their public key), Håstad's broadcast attack applies. And I would not be too surprised if this attack could be extended to less recipients given the restricted plaintext space.
3. From the cryptogram, adversaries are able to test a guess of the AES key, and test if it's the same as in another session.
4. If the recipient checks that the decrypted result is below $2^k$ where $k$ is the expected AES key size (rather than just keep the low order $k$ bits of the decryption result to form the key), and does so in a way that introduces a timing dependency on the bit size of the result of the textbook RSA decryption (which is easy to let slip in any language), then they stand a risk to be vulnerable to a timing attack allowing decryption of the key.

The recommended padding is RSAES-OAEP, which solves 1/2/3, and when carefully implemented solves 4.

[Off-topic: The whole thing is even pre-packaged in .NET as RSAOAEPKeyExchangeFormatter and RSAOAEPKeyExchangeDeformatter].

Addition: Another option is RSA-KEM. In a nutshell: you generate a secret as wide as the modulus of the public key, encipher it with textbook RSA (no padding), and both sides keep the appropriate low-order bits as the AES key. As long as there is a single recipient, security against 1/3/4 is excellent: it relies on the most basic (conjectured) security properties of RSA, and necessary security properties of RSA implementations (which is no insurance they are met!). But KEM does not solve 2, and is inconvenient for several recipients anyway.