Score:1

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

ke flag

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.

bk2204 avatar
fr flag
Yes, you pretty much always need padding for RSA. OAEP with SHA-2 is typically recommended, although PKCS #1 v1.5 can be acceptable (but it has a higher risk of security-relevant implementation errors).
Score:4
ng flag

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.

forest avatar
vn flag
Can't you just use RSA-KEM for this?
fgrieu avatar
ng flag
@forest: yes, I'll add this. But there is a limitation: it does not solve 2.
in flag
RSA-KEM with a symmetric key-wrap (SIV, AES-KW) solves 2, doesn't it?
fgrieu avatar
ng flag
@Neil Madden: Sorry, I do not get how you propose to send the same key to multiple users using [RSA-KEM](https://www.rfc-editor.org/rfc/rfc5990.html#page-3) and [AES-KW](https://www.rfc-editor.org/rfc/rfc3394#section-2.2.3).
in flag
Run RSA-KEM for each recipient, which returns a derived symmetric key (and its encapsulation). Use that symmetric key to encrypt the shared key using AES-KW.
fgrieu avatar
ng flag
@Neil Madden: ah, had missed that. Yes it's perfectly fine.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.