NSA and ECC

[Altoidnerd]

My point being, it is very possible that the NSA has secret knowledge of elliptic curves.

It is very possible santa claus does as well.  Only evidence for a vulnerability is notable in this regard.

[1714022380]

1714022380

[1714022380]

1714022380

[1714022380]

1714022380

[1714022380]

1714022380

[AnonyMint]

Seed has a generic meaning. Is that the best FUD you can do to avoid addressing the point?

There is nothing in the scheme that we use which can be generically described as a seed either.  Our curve meets the SafeCurves definition of "Fully Rigid" (as I explained to you elsewhere by comparison to curve25519).

Edits:

Btw, I guess you forgot that is the first time you've told me that.

It isn't:

I specifically addressed your transparency FUD when you were spewing it elsewhere on the forum:

The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1.

secp256k1 is "somewhat rigid" not "fully rigid":

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

https://bitcointalk.org/index.php?topic=151120.msg3131916#msg3131916

Also some of us don't want to trust an industry consortium.

http://secg.org/
http://www.secg.org/collateral/sec2_final.pdf

Given that efficiency claims have been arbitrary.

http://safecurves.cr.yp.to

Subsequent research (and to some extent previous research) showed that essentially all of these efficiency-related decisions were suboptimal, that many of them actively damaged efficiency, and that some of them were bad for security.

[gmaxwell]

secp256k1 is "somewhat rigid" not "fully rigid":

Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread_.

Given that efficiency claims have been arbitrary.

There is nothing arbitrary about it, with use of the efficient endomorphism enabled libsecp256k1 is (AFAIK) the fastest implementation of ECDSA verification on general purpose hardware in existence, obviously if it contained an implementation of schnorr signatures over this group they'd be even faster due to being able to skip the modular inversion too, but as far as I know it is unparalleled by any other actual ECDSA implementation with comparable security...

Nor are there any obviously strictly superior alternatives, _even today_ much less several years ago, the best contenders have a cofactor greater than one— allowing a non-prime group at a minimum costs several bits of security (e.g. equal or worse to the rho improvement from the efficient endomorphism), and depend on implementation hacks that require private keys to be in a particular sub-group, making things like multiparty key derivation (e.g. BIP32) incompatible with those implementations.

[hashman]

secp256k1 is "somewhat rigid" not "fully rigid":

Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread_.

Thanks as usual gmaxwell.. hanging on your words here!

Well this one doesn't explain G so it's not all the parameters..  and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?"

I also hadn't noticed until recently that b (=7 in secp256k1) can be replaced with anything at all with no effect on all bitcoin operations..  so definitely a waste of time investigating that choice further.      .

[gmaxwell]

Well this one doesn't explain G so it's not all the parameters..  and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?"

Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.

The term 'fully rigid' comes from safer curves and I complained to DJB that his own curves had no obvious specification for their generator on the site, and (after some back and forth there I gave him a sage implementation of an 'attack' in a contrived protocol) the page was revised to include an argument why the base point selection is irrelevant "What about rigid choices of base points? For each curve considered by SafeCurves, the specified base point is a generator of the specified subgroup. SafeCurves does not place restrictions on the choice of this base point [...]".

[AnonyMint]

@gmaxwell, in any case I think you'd have to admit that one-time use Lamport signatures employing a cryptographic hash with considerable cryptanalysis history, would be more immune (against theft of coins) to potential and unknown number theoretic vulnerabilities whether planted or discovered after the fact.

I acknowledge we had the prior discussion in some thread wherein you pointed out that the public keys are hashed so aren't known until the spend, so the attacker would only have a short period of time to issue a double-spend. Nevertheless as the mining has become incredibly centralized (one or two pools control 50+% of hashrate last time I checked), taken together with potential vulnerabilities that might reduce attack to trivial calculation, then the hash may not be enough protection since the public key is revealed when the transaction is sent.

[cypherdoc]

and specifically about these five constants:

They've already been explained in this thread.  In summary:

The first constant we care about is p; TierNolan already explained that one.  It's the largestsmallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

From that we can explain b.  If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one.  I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless.

N is just the order of the elliptic curve; no explanation needed.

The last piece of the puzzle is the choice for G.  Since the order of the elliptic curve is prime, we can pick any point on the curve (except infinity), and get a group with the same order (i.e. there are no subgroups).  Why SECG picked the particular G they did is unexplained.  However, there is no reason to believe any G is weaker or stronger than any other G (against a compliant ECDSA verifier).  I would guess that either G is totally random, or it has sentimental meaning to the author(s).

Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1?

why does the wiki constant for p say this:  p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

instead of this:  p = 2^256 - 2^32 - 977 ?

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

[DeathAndTaxes]

They are equivalent: 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 = 977.

The former provides some clarity on how 977 was chosen ("nothing up my sleeve" http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number).

[Peter R]

I understand that secp256k1's p has the form

     2^256 - 2^32 - x

because this is a sort of generalized Mersenne prime and the "32" means that  modular reductions can be carried out efficiently with 32-bit words.

But I still don't understand why x = 977.  Mathematica tells me that there were lots of choices:

Code:

Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969

 

Why not 263 = 2^8 + 2^2 + 2^1 + 2^0?  It's the smallest.

Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter?  For example, 487 is closer to 512 than 977 is to 1024.  

[cypherdoc]

I understand that secp256k1's p has the form

     2^256 - 2^32 - x

because this is a sort of generalized Mersenne prime and the "32" means that  modular reductions can be carried out efficiently with 32-bit words.

But I still don't understand why x = 977.  Mathematica tells me that there were lots of choices:

Code:

Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969

 

Why not 263 = 2^8 + 2^2 + 2^1 + 2^0?  It's the smallest.

Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter?  For example, 487 is closer to 512 than 977 is to 1024.  

What do words have to do with these calculations?

[BurtW]

I understand that secp256k1's p has the form

     2^256 - 2^32 - x

because this is a sort of generalized Mersenne prime and the "32" means that  modular reductions can be carried out efficiently with 32-bit words.

But I still don't understand why x = 977.  Mathematica tells me that there were lots of choices:

Code:

Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969

 

Why not 263 = 2^8 + 2^2 + 2^1 + 2^0?  It's the smallest.

Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter?  For example, 487 is closer to 512 than 977 is to 1024.  

I believe the choice of 977 was explained up thread.  Something about a (future?) optimization if it is as close to 1024 as possible without going over 1024 therefore the choice is 977.

[Peter R]

I believe the choice of 977 was explained up thread.  Something about a (future?) optimization if it is as close to 1024 as possible without going over 1024 therefore the choice is 977.

I noticed that line of reasoning but it didn't make sense to me in the same way that the explanation for the 2^32 term did.  The "32" corresponds to the bit width of physical registers on many processors.  The "10" relates to ??

In other words, how does 977 being close to but smaller than 1024 (2^10) lead to more optimizations than 487 being close to but smaller than 512 (2^9)? 

I'm not actually worried; I think secp256k1 is highly secure.  I'm just wondering if I'm missing something...

[BurtW]

From the letter I got from Dan Brown, shown here:

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

We have:

2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small.  This form is for efficiency.  I am not sure why this particular value of s is chosen, because I expect that smaller s could be found.  Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024.  I would not be surprised if s was the smallest value of this form, but I did not check.  In any case, there are no known weak classes of prime order field for elliptic curves.

So t could be any of the values you found less than 1024.  I don't know but if all of them are equally safe then the guy/group that decided may have just picked 977 just because it was the largest number less than 1024 and no other reason.  It would be interesting to track down the person that was there in the room when that decision was made.  Alas, all of my attempts to do that have failed.

[Peter R]

From the letter I got from Dan Brown, shown here:

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

We have:

2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small.  This form is for efficiency.  I am not sure why this particular value of s is chosen, because I expect that smaller s could be found.  Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024.  I would not be surprised if s was the smallest value of this form, but I did not check.  In any case, there are no known weak classes of prime order field for elliptic curves.

So t could be any of the values you found less than 1024.  I don't know but if all of them are equally safe then the guy/group that decided may have just picked 977 just because it was the largest number less than 1024 and no other reason.  It would be interesting to track down the person that was there in the room when that decision was made.  Alas, all of my attempts to do that have failed.

Thanks Burt.  It's interesting to note that 263 would have been the choice for t that Dan Brown expected.  My new theory is that they just screwed up a minus sign somewhere and picked 977 instead of 263 lol.  

[DeathAndTaxes]

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 .  I know I am highly original in my naming convention.

[justusranvier]

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 .  I know I am highly original in my naming convention.

One of these: http://safecurves.cr.yp.to/bada55.html

[cypherdoc]

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 .  I know I am highly original in my naming convention.

One of these: http://safecurves.cr.yp.to/bada55.html

Yep, those are badass

[ThomasCrowne]

Regarding the OP.

"If the NSA coulda you can bet your bottom dollar they woulda!"   -me

[hashman]

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 .  I know I am highly original in my naming convention.

One of these: http://safecurves.cr.yp.to/bada55.html

Yep, those are badass

I can't help but notice that not one of the safecurves.cr.yp.to families are implemented by openssl:

$ openssl ecparam -list_curves
  secp112r1 : SECG/WTLS curve over a 112 bit prime field
  secp112r2 : SECG curve over a 112 bit prime field
  secp128r1 : SECG curve over a 128 bit prime field
  secp128r2 : SECG curve over a 128 bit prime field
  secp160k1 : SECG curve over a 160 bit prime field
  secp160r1 : SECG curve over a 160 bit prime field
  secp160r2 : SECG/WTLS curve over a 160 bit prime field
  secp192k1 : SECG curve over a 192 bit prime field
  secp224k1 : SECG curve over a 224 bit prime field
  secp224r1 : NIST/SECG curve over a 224 bit prime field
  secp256k1 : SECG curve over a 256 bit prime field
  secp384r1 : NIST/SECG curve over a 384 bit prime field
  secp521r1 : NIST/SECG curve over a 521 bit prime field
  prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field
  prime192v2: X9.62 curve over a 192 bit prime field
  prime192v3: X9.62 curve over a 192 bit prime field
  prime239v1: X9.62 curve over a 239 bit prime field
  prime239v2: X9.62 curve over a 239 bit prime field
  prime239v3: X9.62 curve over a 239 bit prime field
  prime256v1: X9.62/SECG curve over a 256 bit prime field
  sect113r1 : SECG curve over a 113 bit binary field
  sect113r2 : SECG curve over a 113 bit binary field
  sect131r1 : SECG/WTLS curve over a 131 bit binary field
  sect131r2 : SECG curve over a 131 bit binary field
  sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field
  sect163r1 : SECG curve over a 163 bit binary field
  sect163r2 : NIST/SECG curve over a 163 bit binary field
  sect193r1 : SECG curve over a 193 bit binary field
  sect193r2 : SECG curve over a 193 bit binary field
  sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect239k1 : SECG curve over a 239 bit binary field
  sect283k1 : NIST/SECG curve over a 283 bit binary field
  sect283r1 : NIST/SECG curve over a 283 bit binary field
  sect409k1 : NIST/SECG curve over a 409 bit binary field
  sect409r1 : NIST/SECG curve over a 409 bit binary field
  sect571k1 : NIST/SECG curve over a 571 bit binary field
  sect571r1 : NIST/SECG curve over a 571 bit binary field
  c2pnb163v1: X9.62 curve over a 163 bit binary field
  c2pnb163v2: X9.62 curve over a 163 bit binary field
  c2pnb163v3: X9.62 curve over a 163 bit binary field
  c2pnb176v1: X9.62 curve over a 176 bit binary field
  c2tnb191v1: X9.62 curve over a 191 bit binary field
  c2tnb191v2: X9.62 curve over a 191 bit binary field
  c2tnb191v3: X9.62 curve over a 191 bit binary field
  c2pnb208w1: X9.62 curve over a 208 bit binary field
  c2tnb239v1: X9.62 curve over a 239 bit binary field
  c2tnb239v2: X9.62 curve over a 239 bit binary field
  c2tnb239v3: X9.62 curve over a 239 bit binary field
  c2pnb272w1: X9.62 curve over a 272 bit binary field
  c2pnb304w1: X9.62 curve over a 304 bit binary field
  c2tnb359v1: X9.62 curve over a 359 bit binary field
  c2pnb368w1: X9.62 curve over a 368 bit binary field
  c2tnb431r1: X9.62 curve over a 431 bit binary field
  wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls12: WTLS curvs over a 224 bit prime field
  Oakley-EC2N-3:
   IPSec/IKE/Oakley curve #3 over a 155 bit binary field.
   Not suitable for ECDSA.
   Questionable extension field!
  Oakley-EC2N-4:
   IPSec/IKE/Oakley curve #4 over a 185 bit binary field.
   Not suitable for ECDSA.
   Questionable extension field!

What's the consensus here.. should we not be using openssl?  Should we use openssl and add the safecurves by hand?  Or just ignore the supposed vulnerabilities listed by the safecurves website and continue to use one of the above curves like secp256k1? 

[gmaxwell]

I can't help but notice that not one of the safecurves.cr.yp.to families are implemented by openssl:

All of the curves most preferred on there are ones that DJB made. Some of them have no implementation in software, only the curve25519/ed25519 stuff has any non-trivial deployment at all.

While the analysis there is generally good and thoughtful, I believe that the page crosses the line into being a bit ... uh .. marketing motivated. This has been discussed before several times— e.g. it cites several points which are irrelevant to us (e.g. the elegator encoding), are 'one time costs' completeness making a correct implementation take some more work, and other points which are compensated by increased security of secp256k1 in other respects.  (E.g. the efficient endomorphism for secp256k1 that yields very fast verification for our curve reduces security by a couple bits, which is pretty comparable to the cofactor of 8 in ed25519 that reduces their security by a couple bits (actually slightly more).

Whats implemented in openssl has more or less nothing to do with what bitcoin uses, and getting rid of openssl wouldn't change it.