Topic: why did bitcoin choose secp256k1 over secp256r1? (Read 19387 times)

Yes, There is a python script that produces every parameter for secp256k1 from first principles, except the generator— and both myself and D. J. Bernstein have given the proof that in-advance choice of the generator is harmless outside of restricted conditions that aren't relevant to normal Bitcoin usage.

I believe that the ECC/NSA thread you referenced did eventually nail down every parameter used to create secp256k1 and answers most if not all concerns.

Because I haven't been able to piece together that the issue brought in this thread was fully resolved (maybe I missed something / read too quickly), and wanted to expose the matter at hand to more eyes.

Since then I also posted to reddit and via it found this other bitcointalk thread that sheds more light on the matter.

No trolling intended I assure you.

Why would you do that (and bump this old thread) except for pure trolling purposes?  Considering that fact that secp256r1 has unexplainable mystery parameters I can't imagine anyone outside of the NSA promoting it.

I took the question to crypto.stackexchange.

http://crypto.stackexchange.com/questions/18965/is-secp256r1-more-secure-than-secp256k1

Hm. It's the 2nd time for today when u use a personal insult as a counter-argument. "Bitcoin Foundation - Lifetime Member" under ur avatar explains the behavior though...

If you search this board for that URL, you'll find at least one thread, maybe more.  The short version is that djb has a huge ego.  The long version is that the things he dislikes about secp256k1 don't matter, or at the very least, don't matter to us.

based on this site http://safecurves.cr.yp.to/ secp256r1 (P-256) is not safe, but neither is secp256k1. Of course, it's debatable how trustable this claim is.

Curve25519 is said to be safe and there's also some other new ones assumed to be safe.

More discussion please, thanks contributors

I'm too lazy to give you the link in this forum, but I believe satoshi was asked directly and his response was:  "It was lying around". 

No one here was claiming that and if they were they would have been promptly corrected.  The the selection power in the 'random' parameter procedure would have required unknown attacks is something that has been pointed out before.  If you're going to bump an old thread, please at least refrain from insulting everyone on in the subforum.

I know this is a somewhat old thread, but as this comes up as a top answer when searching for secp256r1 , I feel some of the above points need to be clarified.

Firstly, people are comparing secp256r1 to Dual_EC_DRBG as if they're interchangeable (And some even seem to think that they're the same thing). They're not. They're two completely different algorithms that serve completely different purposes. Dual_EC_DRBG has been suspicious from the second it was published and plenty of people from the security industry have warned against using it. I believe someone recently was able to demonstrate a proof of concept of breaking the encryption when using their own curve parameters. The issue is that the specification gives a default curve that doesn't indicate where those parameters came from - it should be random.

However, secp256r1 has no such proof. There is a theoretical issue with it, though - its curve parameters are taken from a SHA1 hash (unlike Dual_EC_DRBG) of a seed value. It's very, very difficult to reverse a hash like that, which is what the NSA will have to have done in order to "trap" the algorithm. It's still theoretical and relies on them having undisclosed exploits that we're unaware of (unlike Dual_EC_DRBG which doesn't) - certainly a possibility and if you value your privacy, don't use it, but it's not quite as obvious as Dual_EC_DRBG. That doesn't make it "safe" per se, but then again it requires a much bigger leap for the NSA to have compromised. There hasn't been a "leak" (from Snowdon or otherwise) that I am aware of that indicates that secp256r1 is a honeypot, but there has for Dual_EC_DRBG.

By all means, if you're sceptical then don't use secp256r1 but let's not confuse it with a completely different algorithm.

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

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.

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.

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.

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.

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

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 ?

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

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.