11
$\begingroup$

I was looking into the predictions by some researchers that RSA and Diffie-Hellman may not be secure in the next few years due to advances in math and being able to calculate the discrete logarithm problem in new ways no longer making them "impossible" to solve backwards (Math Advances Raise the Prospect of an Internet Security Crisis). Would this cause problems with Elliptic Curves? I know they are based on different principles, but could continued advances in this area compromise ECC? Can we consider ECC a replacement if RSA and DH were compromised?

$\endgroup$
20
$\begingroup$

A couple things:

  1. This article is two years old, so take its predictions with a grain of salt.
  2. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon.
  3. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those methods do not directly apply to any standard cryptographic primitive like RSA or DH, and it is not known how to translate Joux's algorithm into an attack on these primitives. The underlying math is fundamentally different.

  4. It's important to be cautious and conservative when choosing cryptographic primitives, but people have been predicting the death of RSA and DH for many years, and they've lasted this long.

Again, it's not known how to translate Joux's methods into a general-purpose algorithm for the discrete log problem in any other group. Thus, while it's possible for his attack to work in elliptic curve groups, there simply isn't any indication that this is the case.

$\endgroup$
6
$\begingroup$

I just want to highlight:

  • The new advancement need to be realized and validated.
  • ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.
$\endgroup$
  • 1
    $\begingroup$ I think the second point is an important addition. Though you can imagine advances that would only apply to one, a generic enough algorithm could break both. $\endgroup$ – otus Nov 30 '15 at 17:48
  • $\begingroup$ You can implement DH with ECC instead of the multiplicative group of a finite field, but saying that DH and ECC are quite similar is a bit sloppy. $\endgroup$ – saberobserver Nov 30 '15 at 18:01
  • 1
    $\begingroup$ @mwhs, ECC is a general term for a whole bunch of algorithms, but many of them use DH (which isn't just a protocol, but a problem), like ECIES does. $\endgroup$ – otus Nov 30 '15 at 20:50
  • 2
    $\begingroup$ Both of them use discrete log, but in different groups with very, very different algebraic properties. It's like saying a car is quite similar to a fighter jet because they both use fossil fuels. $\endgroup$ – pg1989 Dec 1 '15 at 3:51
  • 1
    $\begingroup$ @mwhs I agree that the language is sloppy, but "DH" is commonly used to refer to other uses of a Diffie–Hellman function than just a key-exchange protocol. $\endgroup$ – otus Dec 1 '15 at 10:27
3
$\begingroup$

It can affect several classes of Elliptic curves. In particular, if this curves have pairings or any other way to translate the problem to a finite field (or extension finite field). The tricky part about ECC is that if you do not pick your Elliptic curve properly, you might end up with a weak implementation. Or, with an implementation in which the problem can be reduced to a finite field.

$\endgroup$
1
$\begingroup$

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for elliptic curves is approximately $2s$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until $2020$. For more detail you can see "Yearly report on algorithms and key sizes".

$\endgroup$

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.