This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[Remember remember the 5th of November]

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

[ivroer]

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.

[Mashuri]

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

They don't seem to be too thrilled with secp256k1

[lnternet]

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:

The simplicity of these parameters gives the NSA / NIST very little wiggle room to create a deliberately bad curve. And even the specific values of 0, 7 and 977 can be justified by security and efficiency constraints, so the chance that Bitcoin’s elliptic curve parameters were chosen with any malicious intent is very low indeed.

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

[Mike Hearn]

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.

[behindtext]

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.

[deepceleron]

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

With the curve secp256k1, the order of the twist is
3×197×1559×96769×
146849×2587814237219×375925338294461779×
101009178936527559588563023359.
So on implementations without protections, the attacker can compute the discrete logarithm in the twist with a cost of 2⁵⁰ and retrieve the secret scalar for n = 256.

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.

[pera]

There is already an old thread by Hal about this curve: 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...

[BurtW]

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.

[BurtW]

There is already an old thread by Hal about this curve: 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...

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.

[BurtW]

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.

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.

[piotr_n]

Awesome topic.
Thanks!

[MatthewLM]

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

[oakpacific]

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

[behindtext]

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.

[oakpacific]

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.

[Altoidnerd]

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.

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

[piotr_n]

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