Pages:
Author

Topic: This message was too old and has been purged - page 3. (Read 7931 times)

hero member
Activity: 784
Merit: 1000
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.
full member
Activity: 121
Merit: 103
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.
hero member
Activity: 784
Merit: 1000
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....
legendary
Activity: 1190
Merit: 1004
If there is a backdoor, it doesn't appear to have been used yet, so what would they be waiting for?
legendary
Activity: 2053
Merit: 1356
aka tonikt
Awesome topic.
Thanks!
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
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.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
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... Smiley

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.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
We have a highly technical thread about this already:

https://bitcointalksearch.org/topic/nsa-and-ecc-289795

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://bitcointalksearch.org/topic/m.3203238

but I think the entire thread, including the process of discovery is pretty good.
sr. member
Activity: 532
Merit: 261
­バカ
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... Smiley
legendary
Activity: 1512
Merit: 1036
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

Quote
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 250 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.
full member
Activity: 121
Merit: 103
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.
legendary
Activity: 1526
Merit: 1134
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.
sr. member
Activity: 299
Merit: 253
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:
Quote
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/
full member
Activity: 135
Merit: 107
http://safecurves.cr.yp.to/

They don't seem to be too thrilled with secp256k1
member
Activity: 89
Merit: 14
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.
legendary
Activity: 1862
Merit: 1011
Reverse engineer from time to time
The way you word the thread reminds me a lot about the X-Files http://en.wikipedia.org/wiki/Trust_No_1
legendary
Activity: 1260
Merit: 1168
This message was too old and has been purged
legendary
Activity: 1260
Merit: 1168
This message was too old and has been purged
Pages:
Jump to: