Bitcoin Forum
February 20, 2019, 06:43:33 PM *
News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Bitcoin secp256k1 not safe. Fails four tests.  (Read 4155 times)
jimbobway
Legendary
*
Offline Offline

Activity: 1405
Merit: 1008



View Profile
December 22, 2013, 03:21:32 AM
 #1

http://safecurves.cr.yp.to

Can anyone elaborate on this?
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1550688213
Hero Member
*
Offline Offline

Posts: 1550688213

View Profile Personal Message (Offline)

Ignore
1550688213
Reply with quote  #2

1550688213
Report to moderator
1550688213
Hero Member
*
Offline Offline

Posts: 1550688213

View Profile Personal Message (Offline)

Ignore
1550688213
Reply with quote  #2

1550688213
Report to moderator
1550688213
Hero Member
*
Offline Offline

Posts: 1550688213

View Profile Personal Message (Offline)

Ignore
1550688213
Reply with quote  #2

1550688213
Report to moderator
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2660
Merit: 1984



View Profile
December 22, 2013, 05:22:45 AM
Last edit: November 16, 2017, 07:22:16 AM by gmaxwell
 #2

The safercurve page carefully explains a number of good arguments for curve parameters and promotes DJB's curves. Indeed— DJB's parameters are generally well selected.

I'm pretty happy with the analysis overall. (and I believe some of the explanation on the rigidity page is actually due to complaints I made because it overstated the criteria even with respect to his own curves.)

...But the reduction of this complicated discussion into a safe "Yes or No" takes this over the line from being a generally informative page into being a sales pitch— along with the intellectual dishonesty inherent in any sales pitch.

As we can see with the subject line it inspired you to write: "Bitcoin secp256k1 not safe", as if there were something to be concerned about. There isn't.

This is a complicated subject which can't just be reduced to a simple binary result, especially so when you've explicitly excluded certain considerations like patents, implementation performance, and existing deployments while elevating niche applications and simplified implementations to equal prominence with being outright broken.

Lets take the False criteria one by one:

fieldequationbaserhotransferdiscrigidladdertwistcompleteind
TrueTrueTrueTrueTrueFalseTrueFalseTrueFalseTrue

CM field discriminants:
Quote
Specifically, there are speedups to the rho method for
some curves where |D| is very small, using fast "endomorphisms" derived from
D.

This is not a complete break. The limits of these speedups are reasonably
well understood, and the literature does not indicate any mechanism that
could allow further speedups for small |D|.
Basically a curve with a small |D| has security under rho attacks similar to a curve a few bits smaller. Secp256k1 has a small |D| by design as a result of designing the curve to allow high speed signature validation. I believe the endomorphisms reduce the Rho security by effectively 1.5 bits.

(There are, of course, other ways to get speedups)

DJB's comparable curve Curve25519 (which passes this test) has an order 4 bits smaller than Secp256k1 and so I believe it has similar Rho security even considering this speedup. Basically the criteria checks only for the speedup but doesn't credit the curve for having an increase in size more than enough to offset the speedup.

Secp256k1 can use this speedup for the forces of good and has a slightly larger curve that offsets the speedup for evil.

Ladders
Quote
SafeCurves requires curves to support simple, fast, constant-time
single-coordinate single-scalar multiplication, avoiding conflicts between
simplicity, efficiency, and security.
This is a requirement that basically amounts to "the simplest possible braindead implementation is both fast, secure, and constant time". Which is indeed a good idea, but it's no reason to be concerned about an existing, correct, implementation. In particular, in our application (primarily signatures) some of the security considerations in dumb applications (like ECDH failing to check that the point is on the curve), just don't apply.  This criteria is somewhat redundant with the twist criteria, which by DJB's definition we pass, since a big part of the argument for use of a simple ladder is that you don't have to test if a point is on the curve or twist.

[Edit: Probably also worth noting that the common ed25519 implementations seen in the wild do not use constant time implementations for signature verification, they use WNAF, because it's faster.]

Complete
Quote
SafeCurves requires curves to support simple, fast, complete,
constant-time single-coordinate single-scalar multiplication. This includes
the SafeCurves ladder requirement but goes further by requiring
completeness. SafeCurves also requires curves to support simple, fast,
complete, constant-time multi-scalar multiplication.
This is a slightly stronger duplicate of the Ladder's requirement, and we fail it because we fail it for the same reason. Again this reduces to an implementation being more complex, and a simpler one being constant time (and/or constant time in a stronger sense).

While I agree that its good if simple implementations are possible, if you look at the hand coded ninja-assembly promoted for curve25519 its clear that the author of the page agrees that performance matters and can trump simplicity and clarity.

[Edit:  Also, the fast constant time implementation used for Curve25519 requires the most significant bit of the private key be one. This breaks some applications, e.g. using the point addition to do public address derivation.]

[Edit: Now having implemented constant time / uniform memory access secp256k1; it's even simpler to make constant time than not constant time. Though the constant time versions are slightly slower than the more complex variable time code.]

Indistinguishability from uniform random strings
Quote
Standard representations of elliptic-curve points are easily
distinguishable from uniform random strings. This poses a problem for many
cryptographic protocols using elliptic curves: censorship-circumvention
protocols, for example, and password-authenticated key-exchange
protocols.
This characteristic is kinda weird. It requires that there be a bijective map between a large fraction of b bit strings and a large set of points on the curve. Basically this means that you can use the curve for steganographically embedded encrypted messages. The design of Bitcoin's curve that allows for the high performance implementation completely precludes DJB's "Elligator" mapping used for the curves there, though some other mapping may be possible.  In any case, this criteria is _completely_ inapplicable to the curve Bitcoin uses for signatures.

[Edit: There is a roughly similar scheme which does work for secp256k1, described on page 8 of http://www.di.ens.fr/~fouque/pub/latincrypt12.pdf at least one way; (which is all I needed it for) but I suspect it can be made a bijection without much work]

In short, the criteria Secp256k1 fails are not generally a concern for us. The curves' recommended by the authors did not exist when Bitcoin was created and might have been preferable.  But The popular curves in widespread use today fail in generally worse ways (e.g. no evidence that they aren't cooked by the NSA) and the curve we use offers very high speed implementations and is safe for our use, even if something else would have allowed simpler implementations.

There are other criteria that the implementations of the recommended curves fail— e.g. it looks like curve25519 requires the most significant bit of the private key is set. Beyond reducing the keyspace this has the effect of making it impossible to use schemes like BIP32 for public derivation of addresses. (At least, while using the standard constant time implementations).  Perhaps more interesting is that the page does not penalize curve25519 for having a non-one cofactor. As mentioned this reduces the rho-hardness, but since failure to handle it correctly has resulted in cryptographic weaknesses (e.g. in PAKE schemes). Cryptographic protocols need to multiply their values by the cofactor it's an implementation trap along the lines of the "completeness" examples and this is easier to get wrong if your cofactor is one as it is in secp256k1.

[2017 Edit: cofactor in 25519 caused a total break in bytecoin/monero-- can't say I didn't tell you so]
genjix
Legendary
*
expert
Offline Offline

Activity: 1232
Merit: 1000


View Profile
December 22, 2013, 05:28:32 AM
 #3

at least for the ind tests, I know the parameters for secp256k1 were deliberately chosen as low numbers.

very nice website btw
justusranvier
Legendary
*
Offline Offline

Activity: 1400
Merit: 1006



View Profile WWW
December 24, 2013, 01:31:03 AM
 #4

Even if secp256k1 was completely broken, isn't the attack window extremely small anyway as long as you don't reuse addresses?

Basically an attacker can only compromise funds if he can see the public key in an unconfirmed transaction, break it, and get a conflicting transaction mined all before the first one gets included in a block, right?
kuverty
Sr. Member
****
Offline Offline

Activity: 714
Merit: 250



View Profile
December 25, 2013, 02:45:35 AM
 #5

Thanks for the link!

███████████████████████████
███████████████████████████
███████████████████████████
███████████████████████████
███████████████████████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀███████████
                ███████████
                ███████████
▄▄▄▄▄▄▄▄▄▄▄     ███████████
███████████     ███████████
███████████     ███████████
███████████     ███████████
███████████     ███████████
███████████     ███████████
VELIC.



.


.


.


.
▄██████████████████▄
██▀              ▀██
██   ▄▄▄▄▄▄▄▄▄▄   ██
██   ▀▀▀▀▀▀▀▀▀▀   ██
██   ▄▄▄▄▄▄▄▄▄▄   ██
██   ▀▀▀▀▀▀▀▀▀▀   ██
██   ▄▄▄▄▄        ██
██   ▀▀▀▀▀        ██
██                ▀▀
██
██                ██
██▄              ▄██
▀██████████████████▀
.


bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 30, 2013, 05:21:20 PM
 #6

The safercurve page carefully explains a number of good arguments for curve parameters and promotes DJB's curves. Indeed— DJB's parameters are generally well selected.


hi there Gmaxwell,

 Im working on a project called Confidence Chains.  you can read about it here http://altchain.org

 My initial thought was to use the secp256k1 curve simply to be conformant with Bitcoin and make Bitcoin users more comfortable.

 I have read a number of posts about the problems of this curve and that other curves are optimal.  What curve do you suggest and why?  The usage is similar to Bitcoin, if you have any quick questions about it, you can post them here.  It would be great to get your input on this.

thanks, -bm

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
Pages: [1]
  Print  
 
Jump to:  

Bitcointalk.org is not available or authorized for sale. Do not believe any fake listings.
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!