4 ms·

> Avoid [NIST elliptic curves] if you can; they suck for other reasons. What are those reasons?

by ak217 12y ago

tptacek 12y ago
They're in a format that requires implementations to be especially careful validating input parameters to avoid leaking information; for instance, an attacker-submitted faulty coordinate can trick an implementation into performing a calculation with its secret key on the wrong curve.
- ak217 12y ago
  Thanks. I'm not entirely sure how information can be leaked in that case - just timing attacks, or something else?
  - tedunangst 12y ago
    You can change the effective modulus. Learn a secret X modulo (A, B, C, ...) and eventually you can learn what X is.
  - sarciszewski 12y ago
    Something else. If you're expecting a curve with 2^250 ish possible resultant values, and you perform a calculation on a curve with only 2^13 ish possible values, you're going to leak some information about the number you gave it. The ECC Hacks talk by Dan Bernstein and Tanja Lange explains it better than I can.
    - fryguy 12y ago
      referenced talk: https://www.youtube.com/watch?v=l6jTFxQaUJA https://www.youtube.com/watch?v=l6jTFxQaUJA
      - sarciszewski 12y ago
        Thank you for providing the link :)
  - musername 12y ago
    The point that is transmitted as part of the shared secret isn't guaranteed to be from the curve but not checked (and it'd be expensive to do so). The problem deos not exist with carefully chosen curves. TBH, It's highly unlikely I got that right, so there's an example in the first half of the talk, you might want to watch.
  - pbsd 12y ago
    Here's the most egregious case: Bitcoin's secp256k1. This curve is defined by the equation y^2 = x^3 + 7 with arithmetic modulo the prime p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1. Suppose you have some way to send a point P to a non-point-verifying adversary, and get the scalar multiplication Q = s . P back, where s is the secret key. If we send a point on the curve y^2 = x^3 + 0 over the same prime---which is technically not an elliptic curve---the arithmetic will still make sense and we will get a meaningful result. However, discrete logarithms on this second curve are very easy to compute: s = (Q_x P_y) / (P_x Q_y) mod p. Without point verification stealing the secret key is a simple matter. This example is slightly artificial; but real examples are just as deadly, however they usually recover the secret key a few bits at a time, and are a little more complicated.
    - jfindley 12y ago
      And sadly there's a patent covering point-verifying, so the workaround for this includes paying licence fees to Certicom if you're in the US. As far as I'm aware there's still no real progress on getting better curves (e.g. curve25519) into TLS, despite a lot of noise on the ML, which is a real shame. Better curves would also be faster - so it's not "just" a security thing. There's a good overview of available curves here, with a guide to their safety: http://safecurves.cr.yp.to/ http://safecurves.cr.yp.to/
      - peterwwillis 12y ago
        Re: curve25519, just do what vendors always do: add it to your implementation as a proprietary extension and wait for everyone to adopt it as de facto standard.
        tptacek 12y ago
        The problem is Apple and Microsoft. If Curve25519 isn't standardized, Google and Firefox will implement it, and Unix servers will get support through OpenSSL, and so a big chunk of the web will get to use Curve25519, which is a bit of a win. However, Apple probably won't support Curve25519 without a standard, and Microsoft definitely won't: they have a competing proposal. Which will leave the NIST curves widely used across the web as well, because IE and Safari support is critically important.
patrickod 12y ago
djb gave a good overview of general ECC curves as part of his and Tanja's talk at 31C3: http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_saal_1_-_201412272145_-_ecchacks_-_djb_-_tanja_lange.html#video http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_... I'd highly recommend watching it, it was very educational.

> Avoid [NIST elliptic curves] if you can; they suck for other reasons. What are those reasons?

by ak217 12y ago

> Avoid [NIST elliptic curves] if you can; they suck for other reasons. What are those reasons?

They're in a format that requires implementations to be especially careful validating input parameters to avoid leaking information; for instance, an attacker-submitted faulty coordinate can trick an implementation into performing a calculation with its secret key on the wrong curve.

ak217 12y ago
Thanks. I'm not entirely sure how information can be leaked in that case - just timing attacks, or something else?
- tedunangst 12y ago
  You can change the effective modulus. Learn a secret X modulo (A, B, C, ...) and eventually you can learn what X is.
- sarciszewski 12y ago
  Something else. If you're expecting a curve with 2^250 ish possible resultant values, and you perform a calculation on a curve with only 2^13 ish possible values, you're going to leak some information about the number you gave it. The ECC Hacks talk by Dan Bernstein and Tanja Lange explains it better than I can.
  - fryguy 12y ago
    referenced talk: https://www.youtube.com/watch?v=l6jTFxQaUJA https://www.youtube.com/watch?v=l6jTFxQaUJA
    - sarciszewski 12y ago
      Thank you for providing the link :)
- musername 12y ago
  The point that is transmitted as part of the shared secret isn't guaranteed to be from the curve but not checked (and it'd be expensive to do so). The problem deos not exist with carefully chosen curves. TBH, It's highly unlikely I got that right, so there's an example in the first half of the talk, you might want to watch.
- pbsd 12y ago
  Here's the most egregious case: Bitcoin's secp256k1. This curve is defined by the equation y^2 = x^3 + 7 with arithmetic modulo the prime p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1. Suppose you have some way to send a point P to a non-point-verifying adversary, and get the scalar multiplication Q = s . P back, where s is the secret key. If we send a point on the curve y^2 = x^3 + 0 over the same prime---which is technically not an elliptic curve---the arithmetic will still make sense and we will get a meaningful result. However, discrete logarithms on this second curve are very easy to compute: s = (Q_x P_y) / (P_x Q_y) mod p. Without point verification stealing the secret key is a simple matter. This example is slightly artificial; but real examples are just as deadly, however they usually recover the secret key a few bits at a time, and are a little more complicated.
  - jfindley 12y ago
    And sadly there's a patent covering point-verifying, so the workaround for this includes paying licence fees to Certicom if you're in the US. As far as I'm aware there's still no real progress on getting better curves (e.g. curve25519) into TLS, despite a lot of noise on the ML, which is a real shame. Better curves would also be faster - so it's not "just" a security thing. There's a good overview of available curves here, with a guide to their safety: http://safecurves.cr.yp.to/ http://safecurves.cr.yp.to/
    - peterwwillis 12y ago
      Re: curve25519, just do what vendors always do: add it to your implementation as a proprietary extension and wait for everyone to adopt it as de facto standard.
      - tptacek 12y ago
        The problem is Apple and Microsoft. If Curve25519 isn't standardized, Google and Firefox will implement it, and Unix servers will get support through OpenSSL, and so a big chunk of the web will get to use Curve25519, which is a bit of a win. However, Apple probably won't support Curve25519 without a standard, and Microsoft definitely won't: they have a competing proposal. Which will leave the NIST curves widely used across the web as well, because IE and Safari support is critically important.

patrickod 12y ago

djb gave a good overview of general ECC curves as part of his and Tanja's talk at 31C3: http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_saal_1_-_201412272145_-_ecchacks_-_djb_-_tanja_lange.html#video http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_... I'd highly recommend watching it, it was very educational.