6
$\begingroup$

Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key.

In this case, the size of the message is increased, as the block size of the RSA encryption (depending on the modulus size) is much bigger than the actual size of the symmetric key. This also leads to using some special padding schemes (like OAEP).

For example: Assuming we want 128-bit security - 128-bit symmetric key, encrypted with 2048-bit RSA yields 256 byte output, which is 16 times the size of the symmetric key.

On the other hand, when the increase in size is an issue, one can make use of ECDH (with some safe curve). Take the recipient's public key $rP$, generate a random value $s$, compute $rsP$ and use KDF to obtain the symmetric key from its $x$-coordinate. The encrypted message is sent along with the sender's public key $sP$.

In this case (for 128-bit security), one uses some safe curve over 256-bit prime field, the size of $sP$ $x$-coordinate is 32 bytes, which is twice the size of the symmetric key.

Here comes my question - besides being more computationally demanding (two scalar point multiplications vs. one exponentiation), are there any additional security considerations one should take when substituting RSA with ECDH in this case?

$\endgroup$
  • $\begingroup$ The ECDH alternative is usually less computationally demanding. (It at least seems you state the opposite.) $\endgroup$ – otus Oct 12 '15 at 17:54
11
$\begingroup$

Yes, there are a few reasons to prefer ECDH over RSA:

  1. ECDH will perform much better;
  2. ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs;
  3. ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP.

For the forward secrecy you require two ephemeral key pairs (to perform ephemeral-ephemeral Diffie-Hellman). Ephemeral key pairs cannot be used for authentication, so you require additional steps if you wanted to use a static ECDH key pair for this.

There are a few drawbacks as well:

  1. RSA is generally much better understood;
  2. there is some discussion about EC security and domain parameters: you may need to validate the public key point or use one of the Safe Curves.

Although you may have to perform more modular calculations - including modular exponentiation - for ECDH, the modular calculations are over much smaller numbers, leading to a much better performing algorithm, especially regarding calculations that use the private key.

Textbook or raw RSA is perfectly able to handle big secret keys; any normal sized secret key can be directly encrypted with a normal sized RSA public key. It's just required to interpret the padded secret key as a number. RSA padding schemes such as OAEP are required to obtain security.

$\endgroup$
  • $\begingroup$ Or: a more complex cryptosystem does not automatically translate to a slower cryptosystem; often the complexity is required to obtain a faster cryptosystem. $\endgroup$ – Maarten Bodewes Oct 12 '15 at 18:30
  • 1
    $\begingroup$ I disagree with the forward secrecy point. You get forward secrecy when you use short lived keys and no forward secrecy when you use long term keys regardless of which algorithm you choose. ECDH has fast key generation which makes it preferable for forward secrecy, but generating one RSA key per minute is easily feasible was well. $\endgroup$ – CodesInChaos Oct 12 '15 at 19:32
  • 1
    $\begingroup$ @CodesInChaos Well, lets just agree that adding key pair generation of comparable security is certainly not a good idea. RSA key pair generation doesn't take constant time and I certainly don't want that server zooming in our testing dept. It's OK if you have no strict performance requirements and/or latency concerns, but I still count the easily obtained forward secrecy a pro for ECDH. $\endgroup$ – Maarten Bodewes Oct 12 '15 at 19:53
  • $\begingroup$ I strongly disagree with your "normal sized secret key can be directly encrypted with a normal sized RSA public key" statement. Doing $m^e mod n$ with a 128-bit $m$, $e=3$ for example will not lead to an overflow , so the attacker only needs to compute the cubic root to find $m$. That problem doesn't exist for $e=63337$, but to claim any RSA with $e=3$ as not normal sized would be rather strong. Instead, use a KEM. As an example: Generate $m$ randomly of same size as $n$, then use a KDF to get the AES key. $\endgroup$ – Henryk Plötz Oct 12 '15 at 22:01
  • $\begingroup$ @HenrykPlötz I really don't understand what you didn't get about " Instead OAEP padding is required to increase (or even obtain) security" but I rewrote the answer just the same. Please notify me if it is still not right in your opinion (and why). $\endgroup$ – Maarten Bodewes Oct 12 '15 at 22:24

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.