# Is RSA padding needed for single recipient, one-time, unique random message?

I want a way to encrypt files using this process: http://crypto.stackexchange.com/a/15 . That is: generate a random password, use that to AES-encrypt a file, and use an RSA public key to encrypt the random password.

I can arrange for the password (= AES key) to be randomly generated every single time, and can arrange things so that doing so again with either the same or a different RSA key will result in a new AES password being generated. My question is whether I need to use padding when doing RSA encryption of the unique AES key.

I've read the answers to several closely related questions, especially Is RSA of a random nonce with no padding safe? and also Does RSA padding have to be unpredictable if the payload is?, which state that padding is necessary. But, as I read the replies, it seems to be necessary in the context of multiple recipients, in which there multiple RSA public keys, but only one random AES password (random but generated once only, not generated anew for each RSA key / recipient).

Basically, in my case, I don't see how padding an already known-to-be-uniquely-random message would make it any more random.

So: Am I just confused and missing something, or are the linked answers only emphasizing the need for padding in multiple recipient cases (where the password stays the same)?

-
Why do you want to avoid the padding? –  CodesInChaos Mar 26 '12 at 18:49

I recommend that you stick with the standard padding methods, even in your scenario.

Here's one reason, if your 'random password' consists only of the AES key, and you use the raw RSA operation on it (that is, zero pad it to the size of the RSA modulus, and then compute $M^e \bmod N$), then yes, there does exist weaknesses; there's a meet-in-the-middle attack on it that will search through possible values of $M$ faster than brute force.

Here's how that would work; in a preprocessing phase, the attacker would generate two lists of integers between 1 and $2^{128/2}$ (assuming we're attacking a 128 bit AES key) $A_i$ and $B_i$. Then, he computes two lists, one consisting of the values $A_i ^ {-e} \bmod N$, and the other consisting of the values $B_i ^ e \bmod N$

Now, when the attacker sees an encrypted message $M^e \bmod N$, he computes the list $(M^e \bmod N) \cdot (A_i ^ {-e} \bmod N) = (M \cdot A_i^{-1})^e \bmod N$, and then scans that list for values in common with the $B_i ^ e \bmod N$ list (which can be done by sorting the lists and doing one pass through both of them). If there is a pair with $(M \cdot A_i^{-1})^e \bmod N = B_j ^ e \bmod N$, the attacker then knows the value $M = A_i \cdot B_j$.

If the size of the lists $A_i$, $B_i$ are $k$ elements long, the attacker has just searched through $k^2$ values of the message in $O(k \log k)$ time.

Now, I'm not sure how much concern this attack would be in practice; however, RSA with standard padding methods do not have this concern; that would appear (to me at least) enough of a reason to stick with the standard methods.

Another way to look at it; raw RSA (that is, RSA without padding) is fragile; while RSA with good padding is not. Given that good padding is easy to do, why wouldn't you do good padding?

-
great, thanks @poncho. from reading other posts, it looked like I had to do something extra--hence more susceptible to introducing an implementation error. now I see that openssl rsautl does PKCS#1 v1.5 padding by default, so its actually easier to pad correctly (you have to ask for -raw). –  jrgray Mar 26 '12 at 20:10

One thing you can do in this scenario, if you really don't want to use padding, is to use key encapsulation (RSA-KEM) instead.

That is, instead of first generating a random AES key and then padding it to the full RSA message length, you instead generate a random RSA plaintext and then derive your AES key from that using a suitable KDF. Since the RSA plaintext is randomly chosen from the full message space, and is only ever encrypted with one RSA key, it's safe to use raw "textbook RSA" to encrypt it.

-

One of the more straight forward attacks against RSA is when the encryption exponent and the integer encoded message are both "sufficiently" small values. It is possible that the ciphertext $c = m^e$ will be less than the modulus $n$. This would mean that $m^e$ is directly encoded as the ciphertext and then easily factored since it doesn't take advantage of the RSA security assumption. RSA padding protects against that sort of attack.

For small exponents, this could plausibly happen. A 2048 bit modulus with an exponent of 3 would need the plaintext to be (about) an integer value at least $2^{682}$ (aka, a value of 1 at or beyond the 682-nd least significant bit position), well longer than a raw AES key. Plaintext passwords are likely to be even shorter than the actual AES key.

To avoid this, at a minimum you would need to ensure that your encryption exponent and plaintext message always combine to be sufficiently large. The size of the exponent itself could ensure this (for messages other than 0 and 1), such as the typical $e = 65,537$. But if $e$ is small, then either calculate the minimum necessary size of $m$ and check each message, or verify that each $m^e > n$ at encryption time. (Consider the constraints on the randomly generated passwords. You mention it will be used as an AES key, but your use of the word "password" suggests it might be something like an ASCII string that is later transformed into an AES key.)

Or you could (and should!) just use RSA padding.

-