why did bitcoin choose secp256k1 over secp256r1?

[behindtext]

something i find rather disconcerting about bitcoin is a lack of justification/explanation for some of the design decisions, in particular the choice of doing 256-bit ecdsa keypairs over secp256k1 vs secp256r1 (a.k.a. P-256) for wallets.

the best i could find on the forum is this thread from 2011 - https://bitcointalk.org/?topic=2699.0

NIST recommends use of secp256r1, and more generally prefers random curve parameters to the Koblitz ones. i can only speculate why this choice was made, here are a couple possible reasons:

* NIST sets standards for NSA / US govt crypto and is genuinely concerned about everyone's security. they have found that random curves are more secure than Koblitz ones.
* NIST has made an intentionally poor suggestion to use secp256r1, so it acts as a honeypot. they have found that Koblitz curves are actually more secure than the random ones.

with those reasons in mind i could see bitcoin having analogous justifications:

* Satoshi had information which led him/them to believe that secp256r1 was indeed a honeypot and that secp256k1 was the better choice for real security
* Satoshi knew that secp256k1 was weak and intentionally included it in bitcoin to make bitcoin into a honeypot

considering that the design decisions for both BTC and NIST ciphers are both entirely opaque, it is difficult to make a good guess as to their motivation. i have similar reservations about using base58 everywhere, but that is less a concern from a security perspective.

can anyone provide a justification for using secp256k1 over secp256r1 besides "that's just the way it is" or "so it was written in the great book"?

[1714042006]

1714042006

[1714042006]

1714042006

[Mike Hearn]

The random curves aren't really any more or less secure than the other curves, they are merely more conservative. Given some arbitrary constants with which to initialize the algorithms, choosing random numbers (or more specifically, nothing-up-my-sleeve numbers) is one way to build trust that there are no funny games being played with the specific choices.

However, the GLV method allows for much faster computations when these constants are not randomly chosen but rather chosen according to some criteria. It opens up the possibility that by selecting values in this way, some unknown weakness is introduced, but nobody has ever been able to show that the non-random curves actually are more insecure.

There have been no further discussions of this topic since the original thread you linked to.

[behindtext]

However, the GLV method allows for much faster computations when these constants are not randomly chosen but rather chosen according to some criteria. It opens up the possibility that by selecting values in this way, some unknown weakness is introduced, but nobody has ever been able to show that the non-random curves actually are more insecure.

yeah, i had seen that it does offer some speed advantages. i don't believe signature checking speed is currently a bottleneck, but extra cpu cycles always help.

[gmaxwell]

yeah, i had seen that it does offer some speed advantages. i don't believe signature checking speed is currently a bottleneck, but extra cpu cycles always help.

Signature checking is, in fact, a major bottleneck. It didn't use to be but it is now. Sadly, Ed25519 didn't exist back then...

[Mike Hearn]

sipa was saying that he thinks it's possible to maybe double the speed of signature checking by using an implementation specifically created just for that curve (this is beyond the GLV optimizations). But we'll see.

[ShadowOfHarbringer]

yeah, i had seen that it does offer some speed advantages. i don't believe signature checking speed is currently a bottleneck, but extra cpu cycles always help.

Signature checking is, in fact, a major bottleneck. It didn't use to be but it is now. Sadly, Ed25519 didn't exist back then...

Perhaps somebody should start selling some kind of PCI-Express slot dedicated ASIC coprocessor for such computations to mitigate that bottleneck ?

If Bitcoin becomes really popular, such needs may arise in the future - i can see a market for that then.

[behindtext]

yeah, i had seen that it does offer some speed advantages. i don't believe signature checking speed is currently a bottleneck, but extra cpu cycles always help.

Signature checking is, in fact, a major bottleneck. It didn't use to be but it is now. Sadly, Ed25519 didn't exist back then...

i've always been a bit wary of djb crypto, despite the guy being a pretty big producer idea-wise. his algos are not nearly as well-studied as the standard ones and he has a tendency to assign "frankenlicenses" on his code.

i guess any change to bitcoin crypto would require a hard fork in the absence of plumbing that would facilitate smooth cipher changes.

[justusranvier]

i've always been a bit wary of djb crypto, despite the guy being a pretty big producer idea-wise. his algos are not nearly as well-studied as the standard ones and he has a tendency to assign "frankenlicenses" on his code.

Everything he does is non-standard. He invented his own FHS and init implementation, just because. Integrating his software with any system vaguely unix-like is an enormous pain in the ass that people only ever tolerated because the alternatives to his software (Bind) sucked that much at the time.

[gmaxwell]

i've always been a bit wary of djb crypto, despite the guy being a pretty big producer idea-wise. his algos are not nearly as well-studied as the standard ones and he has a tendency to assign "frankenlicenses" on his code.

Ed25519 is not curve25519. Ed25519 is the work of Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang..

"frankenlicenses" on some code are irrelevant, as no one is married to a particular implementation... though the reference Ed25519 implementation is public domain.

i guess any change to bitcoin crypto would require a hard fork in the absence of plumbing that would facilitate smooth cipher changes.

Bitcoin can smoothly pick up new signature methods. We've even done a deployment of this with P2SH.  But the big speedup of Ed25519 is perhaps not the cost and risk which is why no one is proposing it at least now.

[gafter]

something i find rather disconcerting about bitcoin is a lack of justification/explanation for some of the design decisions, in particular the choice of doing 256-bit ecdsa keypairs over secp256k1 vs secp256r1 (a.k.a. P-256) for wallets...

can anyone provide a justification for using secp256k1 over secp256r1 besides "that's just the way it is" or "so it was written in the great book"?

Since 2007 there is evidence that the supposedly random constants in secp256r1 may have been manipulated by the NSA to provide a backdoor.  See http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115.  Presumably Satoshi was aware of this.  The Koblitz curves cannot have been so "cooked"; see http://crypto.stackexchange.com/questions/10263/should-we-trust-the-nist-recommended-ecc-parameters/10273#10273.

[gmaxwell]

That thread is a _little_ misleading.  The author is writing about the traditional characteristic 2 koblitz curves (e.g. NIST k curves). SECP256k1 is a curve which is not part of the nist standard. It is a generalization of the koblitz but with a prime field that admits similar optimizations. The design freedom for it is this generalization is somewhat larger than than that available for characteristic 2 koblitz. ... but the design space still is substantially constrained, and I agree with the conclusion that it reduces the room for carefully selected values.

[jdbtracker]

I don't think satoshi did things lightly, I've started understanding Bitcoin more and more and now I'm looking into C++ code and I think he had very carefully thought out systems but brushed off the questions to encourage exploration.

This algorithm is fast and not implemented widely so it would be less exploited, and the internal structure could have something to do with it... but what would the insight have been? I'm intrigued to find out.

I also thought about the size of ecdsa... it's tiny when compared to similar schemes.

[cnd]

Thanks to Snowden & Bruce Schneier, we now know the answer. secp256r1 has an NSA backdoor - see http://www.linuxadvocates.com/2013/09/is-openssls-cryptography-broken.html

So - while a backdoor is not really a "honeypot" this is the best answer:-

* NIST has made an intentionally poor suggestion to use secp256r1, so it acts as a honeypot. they have found that Koblitz curves are actually more secure than the random ones.

* Satoshi had information which led him/them to believe that secp256r1 was indeed a honeypot and that secp256k1 was the better choice for real security

[samson]

Thanks to Snowden & Bruce Schneier, we now know the answer. secp256r1 has an NSA backdoor - see http://www.linuxadvocates.com/2013/09/is-openssls-cryptography-broken.html

So - while a backdoor is not really a "honeypot" this is the best answer:-

* NIST has made an intentionally poor suggestion to use secp256r1, so it acts as a honeypot. they have found that Koblitz curves are actually more secure than the random ones.

* Satoshi had information which led him/them to believe that secp256r1 was indeed a honeypot and that secp256k1 was the better choice for real security

RedHat have consistently refused to include ECC in their products for a long time now.

They won't discuss why apart from saying 'possible patents' which in my opinion is bullshit.

However they have recently decided that these patent issues have been resolved after so many years of bullshit and in the next version of RedHat Enterprise Linux they will include the OpenSSL version with ECC support it's been lacking for so long.

It's worth mentioning that they made it into quite a complex job to upgrade to an ECC compliant OpenSSL without potentially wrecking your linux installation.

The whole thing stinks of a secret court order to me.

Does this give more credence to Ed25519 ?

[oakpacific]

Why have I found nobody, before gmaxwell, trying to verify if the secp256r1 constants make sense? Why?

[gmaxwell]

Why have I found nobody, before gmaxwell, trying to verify if the secp256r1 constants make sense? Why?

The spec described it as random, and if you looked at and didn't think too hard the claim of random sounded pretty good... "They used a cryptographic hash to set the values, not really any algebraic structure going to be found there!".

Like a lot of things, its seems completely obvious in hindsight, but personally I only thought to reconsider it while I was in the middle of blabbering off to someone "there is no real reason to be concerned, they set them randomly using ... wait a minute!",  ... and even then I'd been spending time dorking around with zero knoweldge proofs based on the fiat-shamir heuristic, in which an attacker grinds at a hash hoping to get a lucky value the has him make successful validation probes.

I wasn't the first person to express some reservations about the methodology used for the NIST curves (e.g. the Brainpool curve RFC shows the NIST curves no love), though I'm not aware of anyone pointing out that someone could have tested seeds until they got a weaker (or stronger) one until I did, though I sure others _must_ have realized it. It's also more obvious in contrast to secp256k1 and ed25519 which have fewer— almost no— degrees of freedom.

[Mike Hearn]

It was recognised in a presentation by djb and Tanja Lange in May:

   http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf

Search the slides for the name Jerry Solinas. Also see the slide containing the phrase "But what if the NSA knows a weakness". And as you note, the Brainpool RFC says explicitly that the NIST curves don't provide any justification for their seed values.

I would guess that there were probably only 10-15 people in the world who knew about this issue before the Snowden blowup though.

[oakpacific]

Why have I found nobody, before gmaxwell, trying to verify if the secp256r1 constants make sense? Why?

The spec described it as random, and if you looked at and didn't think too hard the claim of random sounded pretty good... "They used a cryptographic hash to set the values, not really any algebraic structure going to be found there!".

Like a lot of things, its seems completely obvious in hindsight, but personally I only thought to reconsider it while I was in the middle of blabbering off to someone "there is no real reason to be concerned, they set them randomly using ... wait a minute!",  ... and even then I'd been spending time dorking around with zero knoweldge proofs based on the fiat-shamir heuristic, in which an attacker grinds at a hash hoping to get a lucky value the has him make successful validation probes.

I wasn't the first person to express some reservations about the methodology used for the NIST curves (e.g. the Brainpool curve RFC shows the NIST curves no love), though I'm not aware of anyone pointing out that someone could have tested seeds until they got a weaker (or stronger) one until I did, though I sure others _must_ have realized it. It's also more obvious in contrast to secp256k1 and ed25519 which have fewer— almost no— degrees of freedom.

The NSA had our psychology nailed, it knows well that we won't be bothered to run some tests over its constants, even if millions of us depend on ECC everyday.

Otoh, it's pretty fortunate to be trained and spanked in the Bitcoin world everyday, the "nothing between you and your enemy but cryptography" design makes sure no one should cease being paranoid(or at least vigilant) without getting punished.

[oakpacific]

It was recognised in a presentation by djb and Tanja Lange in May:

   http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf

Search the slides for the name Jerry Solinas. Also see the slide containing the phrase "But what if the NSA knows a weakness". And as you note, the Brainpool RFC says explicitly that the NIST curves don't provide any justification for their seed values.

I would guess that there were probably only 10-15 people in the world who knew about this issue before the Snowden blowup though.

I saw this presentation, but I haven't seen careful examination of the constants other than what gmaxwell did, also the slide mentions Apple's usage of Curve25519 rather than a NIST curve, I wonder if they are also aware of their problems.

[e4xit]

Some basic google-fu still turns up surprisingly little about the secp256k1 curves used for this protocol, even after so many years.

Does anybody have any good articles/reviews/demos on this curve which might help reveal why it was chosen for bitcoin, or indeed, if it is suitable for long-term bitcoin use?

http://www.secg.org/collateral/sec2_final.pdf (2.7.1) provided a small amount of info on this but I guess what I would really be looking for is sources proving that using Koblitz curves is more secure (or the security/limitation thereof is better understood) than using "provably random" curves...?