Hacker News Reader

Comment by ak217 | Hacker News Reader

> 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.

Thanks. I'm not entirely sure how information can be leaked in that case - just timing attacks, or something else?

You can change the effective modulus. Learn a secret X modulo (A, B, C, ...) and eventually you can learn what X is.

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.

referenced talk: https://www.youtube.com/watch?v=l6jTFxQaUJA

Thank you for providing the link :)

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.

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.

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/

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.

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.

re: Apple, that may be true for browsers, but they're already using it in other, not publicly exposed ways such as some of iOS file encryption.

How are they a problem? Firefox/Chrome/OpenSSL can still pick up Curve25519, and Microsoft can still hold out for their own proposal; neither cancels the other out and we're already stuck with NIST curves (rfc4492). In fact, TLS specifically advertises what curves are available so that an upgraded server/client can use stronger curves in the future - optionally.

I know MS will be dicks and try to force their own version of everything, but i'll bet Apple will implement anything that there's a half-decent reference implementation of. That just leaves Microsoft, and the easiest way to defeat their proposal is to get their customers to demand they support the thing everyone else already implements, which would be Curve25519.

DJB said in his recent talk that Microsoft is going to adopt "26 new curves", and he seemed pretty happy about it. But I'm not sure whether that means Microsoft will support Curve25519 or not. If they will indeed support 26 new curves, but they won't support Curve25519, that would be pretty silly of them.

You missed some subtext. Read Bernstein's posts on CFRG to see his take on the MSFT proposal.

Let's imagine a scenario that could result from this:

1. DJB criticizes NIST and other standardization institutes and their curve selection choices

2. CFRG fails to recommend a curve (or a suite of curves) for TLS WG

3. Microsoft refuses to adopt Curve25519

4. Everyone else does

5. Interop problems

6. ?????

7. Everyone who has to clean up after this is aligned strongly towards standardization processes.

That's how they are a problem.

(For the record: This isn't a conspiracy theory, I don't think anyone wants this to happen and is actively trying to manipulate things to make it happen, it's merely a hypothesis on what could happen.)

Apple already uses Curve25519 for iOS encryption, so it's not like they're a stranger to it: https://www.apple.com/br/ipad/business/docs/iOS_Security_Oct...

> 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.

I thought Google was pushing for it to be adopted in TLS 1.3. Did everyone else reject that idea or what happened?

Actually, CFRG's doing a consensus call to adopt a rough draft from agl containing Curve25519 as an RG document right now - and I feel fairly comfy saying we seem to have good consensus and running code for X25519 (the Montgomery-x key exchange over the curve known as Curve25519, introduced in that paper). Implementers are already pushing ahead. I wouldn't think the TLS group or anyone else needs to delay that work any longer - it's been quite long enough already in my opinion.

Not quite so sure about signatures, but that's more a PKIX WG problem with more (CA-style) inertia behind it, so that won't move very quickly no matter what. The chairs want to resolve signatures after the curve and key exchange algorithm, which the TLS WG participants seem to want sorted out first.

This kind of invalid curve attack exists against all elliptic curves, so it's a bit difficult to argue that they're a reason to prefer one curve type over another.

The situation is a bit different in the presence of point compression, in which case you're typically concerned with twist security, but the security of the NIST P-256 quadratic twist is pretty decent, so again this isn't a strong argument against it.

The two good reasons to choose something like Curve25519 over NIST P-256 are 1/ speed and 2/ the fact that it's somewhat simpler to obtain side-channel protected implementations. For SSH key exchange, it's pretty much a wash for most realistic settings (only a server that spends significant CPU time simply establishing SSH connections would care about the performance difference here).

I chose the singular example for its simplicity; invalid curve attacks are, of course, much more general (smooth-order curve + CRT). That said: how would you mount an invalid curve attack on a curve in Edwards form? It is obvious if the adversary is using Hisil's d-less formulas, but it does not seem obvious otherwise.

It certainly depends on the precise arithmetic being used, but for the usual complete addition law, for example, I'm pretty sure I can recover k from the computation of [k]P where P is of the form (0,y) (or (0:Y:1) in the projective case) and not on the curve. That's a cute idea for a paper that I'll probably write up, by the way; thanks!

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_-_... I'd highly recommend watching it, it was very educational.

Reply on news.ycombinator.com