11
$\begingroup$

IND-CPA is used to protect against frequency analysis AFAICT. But if RSA is only used to encrypt symmetric keys (AFAICT) then what's wrong with using only textbook RSA because random keys are very unlikely to repeat?

$\endgroup$
  • $\begingroup$ This would still be vulnerable to CCA attacks and was at least exploited once. So we make sure we miss nothing and it's always secure and make it IND-CCA2 (by using OAEP) $\endgroup$ – SEJPM Jul 7 '15 at 16:58
  • $\begingroup$ ... and please don't forget. The scheme broken by Bleichenbacher was way stronger than textbook RSA. $\endgroup$ – SEJPM Jul 7 '15 at 17:06
  • $\begingroup$ @SEJPM so for random session keys, textbook RSA is CPA-secure but not CCA-secure and it's the latter we want. $\endgroup$ – jkabrg Jul 7 '15 at 17:07
  • $\begingroup$ We want as much security as we can have (with "negligible" effort). Just to be sure. Textbook RSA by itself isn't even IND-CPA, because you can find low-entropy messages by trying them out (=academically broken). If you also consider this: Assuming you use e=3 and send the exact same message to three other people (hybrid encryption, one symmetric key), then everyone having all three (encrypted) messages can read the message. $\endgroup$ – SEJPM Jul 7 '15 at 17:39
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For small $e$, there's an even faster attack. $\:$ Even for large $e$, the amount of space used can be made trivial. $\:\:$ $\endgroup$ – user991 Jul 7 '15 at 17:56
  • $\begingroup$ @RickyDemer Thanks; forgot to include that. Will edit now. $\endgroup$ – Yehuda Lindell Jul 7 '15 at 20:19
  • $\begingroup$ By the link I gave, both instances of "and space" should be removed. $\;$ $\endgroup$ – user991 Jul 7 '15 at 20:37
  • $\begingroup$ Thanks, I actually don't think I knew about this, so this is really important! $\endgroup$ – Yehuda Lindell Jul 7 '15 at 20:44
  • 1
    $\begingroup$ Just to be sure; isn't the first to last paragraph describing KEM with the hash replacing a KDF? Maybe you could somehow link KEM with this paragraph in the answer? $\endgroup$ – Maarten - reinstate Monica Jul 7 '15 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.