13
$\begingroup$

I am wondering whether there are any properties of the curve which would technically make it easier to attack than any other curves of 256 bits in size.

I have heard that being a Koblitz curve, it has a few bits weaker security than some other curves of the same size - I was wondering if anybody has a source for a proof (or sketch proof) of this fact if it is true, and for any other properties that may make the secp256k1 considered weaker.

EDIT: I have found this website http://safecurves.cr.yp.to/index.html which states that the curve does NOT satisfy all of the safety requirements for that website - however I am unable to understand the parameters under which it is considered not safe, and explanation on this would be nice too thanks :)

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Does this answer help ? $\endgroup$
    – Ruggero
    Commented Mar 25, 2019 at 8:18

2 Answers 2

Reset to default
17
$\begingroup$

secp256k1 fails the following SafeCurves criteria, but it doesn't matter for Bitcoin's use of secp256k1:

  • CM field discriminant. secp256k1 is a Koblitz curve that admits a fast endomorphism for speeding up scalar multiplications. There is no particular vulnerability here: the same speedup you get in computing with secp256k1, an adversary gets in trying to break it, but that won't, in itself, render an infeasible attack feasible. (This is what the ‘few bits weaker security’ refers to.)

    SafeCurves conservatively rejects this because it is additional structure that could be the foundation of future breakthroughs in cryptanalysis, but nobody has made that breakthrough and we have little reason to suspect it's going to happen sooner than any other unpredictable cryptanalytic breakthroughs.

  • Ladders. secp256k1 does not admit the fast Montgomery ladder to compute $x$-restricted scalar multiplication in constant time; it does admit the much slower Brier–Joye ladder.

    Of course, you can compute fast scalar multiplication in variable time, which exposes you to timing side channel attacks. This creates a conflict between fast implementations—everyone notices when things run slowly—and secure implementations—which nobody notices until their money is gone. The SafeCurves criteria reject such conflicts that encourage performance or security, in favor of designs that encourage performance and security.

    This is relevant mainly for applications doing Diffie–Hellman, but Bitcoin does not use secp256k1 for Diffie–Hellman; Bitcoin uses secp256k1 for ECDSA signatures. (Conceivably, it would also be relevant for applications using exotic signature schemes like qDSA, but Bitcoin is not one of those.)

  • Completeness. secp256k1 does not admit the fast complete Edwards formulas to compute elliptic curve addition in constant time; it does admit the much slower complete Weierstrass formulas to compute elliptic curve addition in constant time.

    Of course, you can compute fast incomplete addition in variable time with conditionals, which exposes you to timing side channel attacks; or you could compute fast incomplete addition in constant time with carefully chosen arithmetic that has the same effect as conditionals, which takes more effort to design and audit. This creates a conflict between fast implementations, secure implementations, and easy implementations, which SafeCurves criteria avoid.

    Fortunately, it seems that pretty much everyone who matters in the cryptocurrency world has recognized that this particular kind of security (as opposed to, e.g., economic security from equitable wealth distribution) is important, and now uses libsecp256k1 to very carefully compute secp256k1 curve arithmetic in constant time at reasonable speed. So this poses more of a danger for the victims of novice implementors in novel scams; as long as you use libsecp256k1 and don't try to rewrite it at home, this doesn't pose a security problem.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Aren't Koblitz curves a few bits weaker as well? $\endgroup$
    – forest
    Commented Mar 25, 2019 at 23:43
  • $\begingroup$ The constant time group law used in libsecp256k1 is not slower than the constant time ed25519 group law... really your answer is just repeating the non-specific claims from the safecurves site and isn't terribly informative. Curves with inherently constant time group law still retain the same "conflict" just in things like the exponentiation algorithm, which is why every ed25519 implementation has a variable time signature verify.. $\endgroup$
    – G. Maxwell
    Commented Mar 26, 2019 at 15:08
  • 3
    $\begingroup$ @G.Maxwell My point is that the SafeCurves criteria failures for secp256k1 are not relevant to Bitcoin, and that secp256k1 is perfectly fine and libsecp256k1 is a safe choice—my intent was to (a) interpret the SafeCurves criteria with less jargon, and (b) show how secp256k1 in Bitcoin is fine in spite of that, which is information not clear in SafeCurves. However, I don't have performance measurements for libsecp256k1—it does not appear in eBATS. Do you have a fair performance comparison that would let me change ‘reasonable speed’ to ‘speed comparable to Ed25519’? $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 26, 2019 at 15:28
  • $\begingroup$ The ed25519 verifiers in ebats are variable time... so I guess what you'd want is a benchmark of signing or pubkey generation? I'm not aware of one. Libsecp256k1 includes benchmarks in its build and will bench both of these operations. (But this also highlights the point I was making that the claim that "completeness" avoids a conflict between performance and constant-timeess is incorrect.) $\endgroup$
    – G. Maxwell
    Commented Mar 26, 2019 at 16:05
  • $\begingroup$ @G.Maxwell eBATS includes key generation time and signing time, and provides a framework for fair comparisons on a variety of hardware. Obviously I can run libsecp256k1's benchmarks on my own computer, but that's not very meaningful for someone else's application on their own computer, so I wouldn't cite it for anyone else's reference. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 26, 2019 at 16:17
8
$\begingroup$

The safecurves site is substantially advertising material for the deservedly well regarded curve25519/ed25519 family curves with a rather one sided presentation. Some of the criteria it names are largely or completely irrelevant for some applications, others are essentially duplicates of each other, while it omits criteria that ed25519 fails which have resulted in serious vulnerabilities many times.

Secp256k1 admits an efficient endomorphism that can be used to make operations a fair bit faster. Attacks are among the things it makes faster: the presence of the endomorphism reduces security by about 0.8 bits. However, secp256k1 has a bigger group size than some other popular '256 bit' curves. For example, secp256k1 has about 1.2 bits higher discrete log security than ed25519 even considering the endomorphism.

The currently conjectured discrete log security for all reasonable 256 bits curves is high enough that small differences probably do not matter, so it would be more interesting to think about security in terms of 'unknown attacks' unfortunately it isn't really easy to do much there. One might guess that the fact that secp256k1 is j-invariant zero might admit some future attack but it could just as well prevent some future attack.

One clearly positive security property of secp256k1 is that it doesn't have a cofactor. The presence of a cofactor and the incomplete handling of it resulted in many vulnerabilities in various protocols (PAKEs, ZKPs, traceable ring signatures), including a total break in Monero family cryptocurrencies. The safecurves "Completeness" and "ladders" criteria both indirectly require the presence of a cofactor but it never mentions this trade-off, so I think this is the best example of how that resource is best considered marketing copy rather than an earnest attempt at scholarship.

Arguments that its somewhat more complex to write constant time code for secp256k1 than ed25519 seem pretty subjective to me: Many ed25519 implementations fail to be constant time, and constant time code exists for secp256k1. At the end of the day using naively written low level cryptographic primitives is a bad idea regardless of the curve, and if you're using well developed code this isn't an issue. Similarly, abstract claims about performance don't really matter: for performance what matters is how things benchmark out in actual applications. To the extent that applications use variable time operations for performance reasons in at least some functions the same applies to all curves, if not in their group law in their exponentiation algorithm.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ criteria that ed25519 fails which have resulted in serious vulnerabilities Do you have any examples? $\endgroup$
    – forest
    Commented Mar 27, 2019 at 23:17
  • 1
    $\begingroup$ Just sour grapes from Bitcoin maxis being stuck with an old and poorly researched curve. It was a better choice than those suspect NIST curves, back in the day, but the science and the industry did move on since. Indeed, all they can argue is that 256k1 is not particularly worse that 25519, but do fail to show 25519 shortcomings. $\endgroup$
    – Walter K
    Commented Jun 12, 2019 at 1:15
  • $\begingroup$ @forest (I'm ignoring walter K's uncivil response) -- sure, I gave examples in my post: e.g. having a cofactor have resulted in vulnerable PAKE implementations, and ZKP implementations including a total break in the monero cryptocurrency ( jonasnick.github.io/blog/2017/05/23/… ). Cryptographic protocols are designed assuming that group elements are all part of a large/strong prime order group, unsoundness results. It's a trade-off, availability of the montgomery ladder is great for DH, but cofactor stinks for most other uses. $\endgroup$
    – G. Maxwell
    Commented Jun 12, 2019 at 4:52
  • $\begingroup$ FWIW, Bitcoin isn't stuck with any particular curve and could adopt something else fairly easily, but at the moment it isn't particularly clear than something else would be obviously superior. Other things have different trade-offs. I would choose 25519 without much concern for something that primarily needed highspeed DH... but that isn't something that is interesting in the bitcoinosphere. $\endgroup$
    – G. Maxwell
    Commented Jun 12, 2019 at 4:55
  • 1
    $\begingroup$ @G.Maxwell, the co-factor itself isn't the problem here, surely it's the implementation. If you correctly handle low order/small subgroup attacks you're fine. $\endgroup$
    – Woodstock
    Commented May 11, 2021 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.