If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA?

Question

As far as I know, IND-CPA is used to protect against frequency analysis. But if RSA is only used to encrypt symmetric keys, what's wrong with using only textbook RSA because random keys are very unlikely to repeat?

Answer 1

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed.

Now, the first important thing to note is that the RSA assumption states that RSA is hard to invert when given a random element in the ring. So, if you choose a random value $x$ between $0$ and $N-1$ and then compute $x^e \bmod N$, then according to the RSA assumption it will be hard to find $x$. However, this doesn't mean that it's hard to find some of $x$ (and knowing some of the key is disastrous), and it also doesn't mean that it's hard to invert RSA when $x$ is not a random element between $0$ and $N-1$. For example, what happens if $x$ is a random 128-bit string (converted to a big number)?

The good news is that we actually do have a (partial) answer for this. First, consider the case of $e=3$. In this (quite common) case, if $N$ is 2048 bits long then for any string $x$ of length at most 682 bits, it is trivial to invert and find $x$ when given $y=x^e \bmod N$. This is due to the fact that when $e=3$, the length of $x^e$ is 3 times the length of $x$. If the length of $x$ is less than 682 bits then the length of $x^e$ is less than 2048, and so $x^e \bmod N$ equals $x^e$ over the integers (this is because no modular reduction ever takes place). Note that finding a cube root over the integers is easy (just do a "binary search" over the possibilities). I stress that the conclusion from this is not to use a larger $e$; the conclusion is not to do plain RSA.

However, since people are often not yet convinced by this, there is another attack that works for any $e$, including large values. In this attack, when the input $x$ is of length 128 bits, it is possible to find $x$ in about $2^{64}$ time, given $x^e \bmod N$. In general, it is possible to invert RSA in time that is square-root of the string length of the input. So, this is not secure. Now, you may want to say: OK, so I'll use a 256-bit key! However, note that instead of having 256-bit security you'll have 128-bit security. More importantly, this attack that takes square-root time is an indication that this is a really bad idea. So, don't do it! (References for the attack: the basic attack on plain RSA appears in this paper by Dan Boneh et al. (Why Textbook ElGamal and RSA are Insecure), and removing the space requirement in that paper can be achieved using the technique in this paper by Oorschot and Wiener (Parallel Collision Search with Cryptanalytic Applications.)

This leads to another possibility which is to choose a random $x$ between $0$ and $N-1$ and to compute $x^e \bmod N$. Then, using a hash function $H$, derive a key $k=H(x)$ to use for symmetric encryption. In the random oracle model (with $H$ being a random oracle) this is actually secure, and will even be CCA-secure if the symmetric scheme is CCA secure (this is actually a CCA-secure KEM/DEM scheme; see the next paragraph for more on this). However, without a random oracle we have no idea how to prove this secure.

In general, we know that in order to get a CPA-secure hybrid encryption scheme, we need both the asymmetric and symmetric scheme to be CPA secure; likewise for CCA security. However, there are more efficient ways of working, which is the KEM/DEM paradigm. This is more relaxed than hybrid encryption, since the asymmetric part defines a random key for the symmetric encryption, but it's not necessarily in the hands of the encryptor to determine what the key will be. I will leave you to look up the KEM/DEM paradigm if you are not familiar with it.