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.
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!
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.
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.
> 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?
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.
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.
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.)
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.
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.