The safercurve page carefully explains a number of good arguments for curve parameters and promotes DJB's curves. Indeed— DJB's parameters are generally well selected.
I'm pretty happy with the analysis overall. (and I believe some of the explanation on the rigidity page is actually due to complaints I made because it overstated the criteria even with respect to his own curves.)
...But the reduction of this complicated discussion into a safe "Yes or No" takes this over the line from being a generally informative page into being a sales pitch— along with the intellectual dishonesty inherent in any sales pitch.
As we can see with the subject line it inspired you to write: "Bitcoin secp256k1 not safe", as if there were something to be concerned about. There isn't.
This is a complicated subject which can't just be reduced to a simple binary result, especially so when you've explicitly excluded certain considerations like patents, implementation performance, and existing deployments while elevating niche applications and simplified implementations to equal prominence with being outright broken.
Lets take the False criteria one by one:
| field | equation | base | rho | transfer | disc | rigid | ladder | twist | complete | ind |
| True | True | True | True | True | False | True | False | True | False | True |
CM field discriminants:
Specifically, there are speedups to the rho method for
some curves where |D| is very small, using fast "endomorphisms" derived from
D.
This is not a complete break. The limits of these speedups are reasonably
well understood, and the literature does not indicate any mechanism that
could allow further speedups for small |D|.
Basically a curve with a small |D| has security under rho attacks similar to a curve a few bits smaller. Secp256k1 has a small |D|
by design as a result of designing the curve to allow high speed signature validation. I believe the endomorphisms reduce the Rho security by effectively 1.5 bits.
(There are, of course, other ways to get speedups)
DJB's comparable curve Curve25519 (which passes this test) has an order 4 bits smaller than Secp256k1 and so I believe it has similar Rho security even considering this speedup. Basically the criteria checks only for the speedup but doesn't credit the curve for having an increase in size more than enough to offset the speedup.
Secp256k1 can use this speedup for the forces of good and has a slightly larger curve that offsets the speedup for evil.
LaddersSafeCurves requires curves to support simple, fast, constant-time
single-coordinate single-scalar multiplication, avoiding conflicts between
simplicity, efficiency, and security.
This is a requirement that basically amounts to "the simplest possible braindead implementation is both fast, secure, and constant time". Which is indeed a good idea, but it's no reason to be concerned about an existing, correct, implementation. In particular, in our application (primarily signatures) some of the security considerations in dumb applications (like ECDH failing to check that the point is on the curve), just don't apply. This criteria is somewhat redundant with the twist criteria, which by DJB's definition we pass, since a big part of the argument for use of a simple ladder is that you don't have to test if a point is on the curve or twist.
[Edit: Probably also worth noting that the common ed25519 implementations seen in the wild do not use constant time implementations for signature verification, they use WNAF, because it's faster.]
CompleteSafeCurves requires curves to support simple, fast, complete,
constant-time single-coordinate single-scalar multiplication. This includes
the SafeCurves ladder requirement but goes further by requiring
completeness. SafeCurves also requires curves to support simple, fast,
complete, constant-time multi-scalar multiplication.
This is a slightly stronger duplicate of the Ladder's requirement, and we fail it because we fail it for the same reason. Again this reduces to an implementation being more complex, and a simpler one being constant time (and/or constant time in a stronger sense).
While I agree that its good if simple implementations are possible, if you look at the hand coded ninja-assembly promoted for curve25519 its clear that the author of the page agrees that performance matters and can trump simplicity and clarity.
[Edit: Also, the fast constant time implementation used for Curve25519 requires the most significant bit of the private key be one. This breaks some applications, e.g. using the point addition to do public address derivation.]
[Edit: Now having implemented constant time / uniform memory access secp256k1; it's even simpler to make constant time than not constant time. Though the constant time versions are slightly slower than the more complex variable time code.]
Indistinguishability from uniform random stringsStandard representations of elliptic-curve points are easily
distinguishable from uniform random strings. This poses a problem for many
cryptographic protocols using elliptic curves: censorship-circumvention
protocols, for example, and password-authenticated key-exchange
protocols.
This characteristic is kinda weird. It requires that there be a bijective map between a large fraction of b bit strings and a large set of points on the curve. Basically this means that you can use the curve for steganographically embedded encrypted messages. The design of Bitcoin's curve that allows for the high performance implementation completely precludes DJB's "Elligator" mapping used for the curves there, though some other mapping may be possible. In any case, this criteria is _completely_ inapplicable to the curve Bitcoin uses for signatures.
[Edit: There is a roughly similar scheme which does work for secp256k1, described on page 8 of
http://www.di.ens.fr/~fouque/pub/latincrypt12.pdf at least one way; (which is all I needed it for) but I suspect it can be made a bijection without much work]
In short, the criteria Secp256k1 fails are not generally a concern for us. The curves' recommended by the authors did not exist when Bitcoin was created and might have been preferable. But The popular curves in widespread use today fail in generally worse ways (e.g. no evidence that they aren't cooked by the NSA) and the curve we use offers very high speed implementations and is safe for our use, even if something else would have allowed simpler implementations.
There are other criteria that the implementations of the recommended curves fail— e.g. it looks like curve25519 requires the most significant bit of the private key is set. Beyond reducing the keyspace this has the effect of making it impossible to use schemes like BIP32 for public derivation of addresses. (At least, while using the standard constant time implementations). Perhaps more interesting is that the page does not penalize curve25519 for having a non-one cofactor. As mentioned this reduces the rho-hardness, but since failure to handle it correctly has resulted in cryptographic weaknesses (e.g. in PAKE schemes). Cryptographic protocols need to multiply their values by the cofactor it's an implementation trap along the lines of the "completeness" examples and this is easier to get wrong if your cofactor isn't one as it is in secp256k1.
[2017 Edit: cofactor in 25519 caused a
total break in bytecoin/monero-- can't say I didn't tell you so]
