Bitcoin Forum

This message was too old and has been purged

This message was too old and has been purged

The way you word the thread reminds me a lot about the X-Files http://en.wikipedia.org/wiki/Trust_No_1

Disclaimer: I'm not a cryptography expert (not even close).

But I believe that the Elliptic curve [secp256k1] that is used in Bitcoin is in a special class called Koblitz curves, for some reason this makes it less likely (impossible?) that the pre-defined curve parameters have been "cooked" to make a backdoor attack possible for the creators.

Although I'm lead to believe this curve has performance benefits for signature verification, but with the drawback that it only offers about 128-bit level security vs. the assumed security level of 256-bit.

Hopefully an expert out there can explain it better than I have.

http://safecurves.cr.yp.to/ (http://safecurves.cr.yp.to/)

They don't seem to be too thrilled with secp256k1

We are using  p = 2^256 - 2^32 - 977

source: https://en.bitcoin.it/wiki/Secp256k1

Vitalik Buterin wrote a great paragraph addressing exactly your point:

source: http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/

The prime used in our curve was selected for performance reasons. Unfortunately, this won't help conspiracy theories because the prime used is what's called a Solinas prime:

   http://eprint.iacr.org/2010/058.pdf

.... named after Jerome Solinas, who is one of the NSA's top mathematicians.

so we can't trust NSA-supplied magic numbers?

next thing you know we'll find out we're all being spied on all the time to protect us from invisible islamic badguys.

Since this thread will get read more because of its incendiary first post subject without problem or solution, I'll repost more prominently a paper that I've had a glance through. Essentially, implementation of the fault attack described on compressed keys may make a ECDSA secret discoverable to an attacker with few or even one signature and security reduced to 2^50 instead of ~2^128, but may effected from a very subtle implementation client code change, such as changing the sign of the y.
http://perso.univ-rennes1.fr/reynald.lercier/file/FLRV08.pdf


This, along with other platform-dependent concerns, would seem to be a good argument for Bitcoin to pull code out of OpenSSL and roll its own implementation of ECDSA and it's own entropy gathering non-deterministic random generator, so it is not affected by compiling against blindly-trusted user libraries. FIPS140 may be a reduced-security random, and it is a compile option in OpenSSL.

It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.

There is already an old thread by Hal about this curve: https://bitcointalk.org/?topic=2699.0 (https://bitcointalk.org/?topic=2699.0)
I always been intrigued about why Satoshi choose secp256k1, Bitcoin is the only software I know that use it.

But now we have Ed25519... :)

We have a highly technical thread about this already:

https://bitcointalk.org/index.php?topic=289795.0

In this thread I actually contacted the person who is currently the head of the organization that originally selected the parameters for secp256k1 and we had a great email conversation about how the parameters were selected.  Please read that thread.

I think most of the people that participated in that thread were convinced that the parameter selections all made sense and there was no way a "back door" was placed in the parameter selection.

The same cannot be said for secp256r1.

There is a pretty good summary of most of the information starting here:

https://bitcointalk.org/index.php?topic=289795.msg3203238#msg3203238

but I think the entire thread, including the process of discovery is pretty good.

When I contacted the guy and told him Bitcoin is using secp256k1 his first response was "Fantastic!  I didn't think anyone used our curve"

Either by design or luck Bitcoin uses one of the few curves not designed or selected by either the NSA or NIST.

As Bitcoin knows from painful personal experience our ECDSA depends on a source of good random numbers but that is not the fault of the curve parameters.  It has been suggested that we move to a new ECDSA that does not require a nonce.  That would solve this random number issue once and for all.

Awesome topic.
Thanks!

If there is a backdoor, it doesn't appear to have been used yet, so what would they be waiting for?

Let's assume for a minute, that we will be able to manage a migration, that a hard-fork can be successfully executed, is there any other digital signing scheme with comparable performance, key length, history of wide usage like ECC and RSA, that we can migrate to? Anyone cares to enlighten me?

Also Apple doesn't seem to be particularly worried about Curve25519....

i think the points you mentioned are precisely why cryptography has gone the way it has in the past 30-40 years. algorithms are not considered usable unless everyone else is already using them, creating a chicken-and-the-egg problem that is tilted substantially to the benefit of the NSA and its sockpuppet, NIST. since people are apprehensive about using lesser-used ciphers and modes, it makes manipulation of the standards process a very potent technique for the NSA to control the quality and ubiquity of encryption.

there are few other options besides ECC for a system with small keys with, as far as anyone knows publicly, comparatively strong security. i would certainly take curve25519 over secp256k1, but migrating the BTC address space would be very non-trivial and everyone would supply the usual "but you can't prove it's broken!" argument. i'm not familiar with any other small-key ciphers that could be a good replacement.

it's too bad that NTRU has such massive key sizes and is covered by many patents: imo, it is the most interesting option for pki currently since it involves almost zero magic constants, unlike RSA and ECC.

If everyone only keeps a ultrapruned chain(not recommended of course) then NTRU key size may not be a problem as only the key hash will be kept anyway.

But in the end I think it's probably a better idea to keep the Damocles sword of ECDSA hanging over us, so that everyone feels some urgency when it comes to the adoption of deterministic addresses.

deepceleron, have you read this paper https://eprint.iacr.org/2013/734.pdf

Can you help me understand the re-use of address problem and whether it applies to the "per message secret" denoted k in the above paper.. introduced in section 2.4

To avoid using the same per message secret, what are your recommendations for best practices?

Your expertise would be appreciated, as the foundations educ. committee loosely suggested that I research this topic for publications for businesses.

I do not wish to continue to bump this thread which has an explosive title.  I want to discuss secp256k1 maturely somewhere, without frightening muggles. mods/heores/gmaxwell feel free to tell me where you'd prefer I go...

We are not playing with psychology here. Nor politics.
It's all math and science - stick to it.
The risk that these algos have a backdoor are not just some crazy theories. At least not to me. This is a serious shit :-)
Are you really going to risk all you money on the fact that there is no backdoor?
Because I'd prefer not to...

The paper I posted refers to ways of covertly weakening elliptic curve cryptography by injecting and exploiting faults in use, such as causing off-curve points to be used. This is not a large concern with Bitcoin due to it's address hash protection, but exposes the ways that it can be subverted, such as by a corrupted address generator or a backdoored random number generator. It reminds us that we must not blindly trust the address generation of Bitcoin clients or other tools like vanity generators, and to be vigilant about the random number generator used when signing, spending money.

The public key is not exposed until money is spent from a Bitcoin address. After that, there is only one layer of protection, ECDSA, and as we saw with the bad Android implementation where the random nonce is poorly implemented, address reuse may allow others to discover the private key. Therefore, best practice is to not reuse addresses.

I'm not really familiar with this level of math but I believe I can watch and draw accurate conclusions.
My actual concern is that there are no really people who would have said that bitcoins ecdsa are safe.
It's all based on no proof of a wrongdoing.
If I was to put all my money on it, I would not have been so sure. Nor should you. :)

Nothing up my sleeve numbers are a problem for ANY cryptographic scheme.  The statement "there may be a backdoor in xyz encryption" is ALWAYS true....

It is my opinion having looked into the matter intensely in the past few days that there is some misinformation being propagated here about secp256k1.  In my research I did NOT find any particularly fishy constants in the construction of this scheme.

I have some concerns about secp256k1 that have been documented and are well known, but are distinct in principle to the general message of this thread which is "somebody might know a something about that prime number."

Can we tease apart "one time secret reuse vulnerability" with "bad random numbers"?

Question 1: does the reuse of a bitcoin address make the blatant mistake of reusing the k value from the paper I linked

-or-

is this only a problem which arises if the random number generator is poor?


Question 2: will you be in miami this weekend?

Non-reuse is a preventative measure against generic unknown problems. The Android random fault was only exploitable when multiple sends allowed mathematical deduction of the private key, and so not reusing addresses after they have spent would have protected users.

I won't be going anywhere unless you are buying the airfare and sunscreen.

Full-strength ECDSA has a $1 billion bounty on it, in every unspent generate transaction that IS a public key.

Deepceleron, would you please PM me your email address?

Yes, I could have PMed this request.  Previously mr celeron was more prompt with my forum posts than with PMs.  Excuse the needless bump.

He's kind of a jerk

I've noticed. But his upside down picture is so funny I can't stay mad at him.

This is worth discussing...I would be willing to write a primer of some kind on finite fields if its wanted.  It looks more complicated than it really is, but that is always true in mathematics I guess.

I can read these papers because I got a math bachelors I never thought I'd use until now...I am curious as to what people with pure CS backgrounds know about finite fields and groups.  If some feedback is given, I can try to bridge the gap.

Woah, wait.  Can you explain what would qualify as "Full-strength ECDSA" as you term it?  Would a low cost perfect random number generation technique do the trick?

You know if it gets compromised, all of us will lose our bitcoins, so we'll just fork. Very simple. We have a ledger backup at all times. There's no threat.

Well that's not true because if some fellow does have a backdoor, he's probably bright enough to use his advantage wisely e.g. not create a catastrophic, obvious system wide failure before profiting immensely from theft.  But this is mythology anyway...

True but scammers are greedy and would give themselves away. Most will also want to get caught to get credit. They'll work for the nsa afterwards.

This is incorrect. The paper states a solinas prime has the form

f(2^k) = 2^m - 2ⁿ +- 1

However the curve secp256k1 is defined over finite field F_p with prime characteristic

p = 2²⁵⁶ - 2³² - 977

So "our prime" is not a solinas prime as described in your linked article. It is a generalized mersenne prime, but it needn't have the properties stated in solinas' paper.

There are 5 NIST recommended primes of the form f(2^k) = 2^m - 2ⁿ +- 1 that allow solinas reduction which define fields over curves

y² = x³ + a x + b

all with a = -3. (for example secp256r1)

secp256k1 is in fact once again different in that it specifies a=0.  So be careful with comparisons like this.  The curve in bitcoin is actually "weird" for multiple reasons.
----------------------------------------------------------------
for kicks, a decimal expansion 2²⁵⁶ - 2³² - 977 = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Thanks for the correction!

Mike, FYI the solinas curves (rather, the curves employing the primes of that form) offer a reduction/computational speed up that secp256k1 (apparently) does not.

However our curve offers a different computational speed up because of the term a=0 meaning we do not have a term linear in x; our curve is

y^2 = x^3 + 7

So there exists some methods of speeding up division due to group theoretic endomorphisms.

This message was too old and has been purged

I do not understand; 977 is prime.  I calculate the sum of your powers of two to be

-2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰ = -1071 = -3*3*7*17

This message was too old and has been purged

Careful now


But

p = 2²⁵⁶ - 2³² - 977 = 2²⁵⁶ - 2³² + (2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰)
  

p = 2²⁵⁶ - 2³² - 977 = 2²⁵⁶ - 2³² - (+2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰)

watch that pesky distributive property

whew...

This message was too old and has been purged

closer yet...see my post.

Wait a second...

...well I'm glad that's over  :)

Is that your final answer? ;)

This message was too old and has been purged

Better check wolfram alpha, shit



perhaps https://eprint.iacr.org/2013/734.pdf

*listen*

and do you want to know what is even more bizarre?

just prior to the release of ECC, there was a significant mathematical work in the realm of Elliptic Curves and Cyclic groups!  Thus it very plausible to suspect that insider knowledge of elliptic curve manipulation exists.

http://math.stanford.edu/~lekheng/flt/wiles.pdf

is it a coincidence that ECC became a standard not long after pioneering work in the exact theoretical field in which they are situated?

-bm

Can anyone recommend a good ECC video for beginners?  I watched 1 or 2 but they were kind of dry, so please let me know if you know of some really good ones.  Not looking to become an expert...I just want to learn some of the basic principles. Thanks. JF

It's well known thath you can't have an elliptic curve over any arbitrary field. If you have an EC over a cyclic group, the discrete logarithm can be easily computed. You need special groups over which you contrstruct EC for them to be usable in cryptography.

This message was too old and has been purged

It seems it can be great idea to make new curve based on open and peer reviewed standards.

There is no need to do that.  There is nothing wrong with or even slightly hinky about the curve we are using as discussed in detail in the thread described in this post:

https://bitcointalk.org/index.php?topic=419259.msg4568250#msg4568250

You are right. That's what I get for trying to be smart about a subject I don't understand well. The point was that you have to be careful when selecting the finite field.

This message was too old and has been purged

so........ where does all that put us about the likelihood
that insider knowledge of elliptic curve manipulation
exists?

After researching this quite a bit and several emails with one of the guys from the group that designed secp256k1 without input from NIST or the NSA.  I personally, and many others who were involved, are convinced that all the parameters used in the secp256k1 curve are reasonable and can be accounted for.  In other words, as opposed to the more popular secp256r1 curve, which was designed directly by NIST/NSA and uses "magic numbers" supplied directly by them, there are no "magic numbers" used in the design of the curve we use in the Bitcoin protocol.

Yeah using secp256r1 would have been a nightmare.  The NSA doesn't screw up this badly.   Cryptographic constants should be "nothing up my sleeve numbers".  Lets look how the NSA "randomly" came up with the parameters for secp256r1


Ok so lets work backwards.  
We want p & q to be prime numbers (or probably prime).  
So we use a generator to try values in sequence and use the first curve for a given security strength which meets our requirements.  Why do we use the FIRST value?  To provide a level of reassurance that it is legit and not chosen for a malicious reason.  If there were 4872498374938247398 valid curves and the NSA picked the 4872498374938247399th one that would be suspicious right.  Alright so we are using the first one we find, building some trust here.  That is good.

Ok so how do we seed the generator.  We take the hash of some number at random? WTF?  Did some 2 bit scammer on bitcointalk come up with this method?  I mean this is the fracking NSA. They know a "little" about cryptography.  There is no possible way they "forgot" that this makes all the subsequent steps worthless.  I mean it is like saying "You can trust me because you can trust me" See I am not asking you to trust me blindly.  I gave you a specific reason why you can trust me."

Now the NSA isn't stupid.  The obvious elephant in the room is how do we know the "random" seed value is random.  Maybe the NSA went through quadrillions of random seed values until they found one which when hashes produces a sequence such that the first valid curve is the one which has a property that the NSA knows has a weakness.  In other words all the song and dance about following this generator sequence and performing various checks is predicated on the generator seed being chosen "fairly" but they just happened to forget that the seed for the generator isn't provable or even probably fair (nothing up my sleeve) and thus the entire process is security theater.

Formally

You can stop reading at step #1.  The foundation is sand.  So what was the domain parameter seed picked at random over all others (you can trust us <wink> <wink>)?
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90

A totally arbitrary number.  Was this the first one the NSA tried?  Or did they have their super computer crunching for years before they came up with this seed which when you follow the rest of their "sleight of hand" generator produced the "random" curve which is EXACTLY what they wanted it to be for some reason only they know?  The rest of their security process is just feel good security.  It is the wand in a magic trick so you don't look closely to the fact that the magician is just cheating with his other hand.

Now if the seed for secp256r1 was say the first 160 bits of pi well we would have at least some confidence that the curve produced was strong.  It would be a rather extreme coincidence that the first 160 bits of pi happened to produce a curve which the NSA knew was weak.

Unless one can deeply understand the math and cryptography for
themselves, we all have to trust the community and those
that do have the specialized knowledge.

I try to understand as best I can as a hobby, but
I simply don't have the time or energy to devote
to understanding every aspect of Bitcoin.