Topic: NSA and ECC - page 2. (Read 48818 times)

The bada55 curves were created to show the worthlessness "verifyably random" (at least as done by NIST), they are "random"— but the authors (ab)used the process to make sure the parameters had "bada55" in them. You are supposed to imagine an attacker armed with a mathematical breakthrough who could compromise 1/2^24 random curves doing the same kind of seed grinding.

I didn't believe the post I was responding to was at all talking about the bada55 curves, the subject had drifted and the post was talking about the curves recommended by the site. Presumably if I failed to answer the authors question he could respond.

Okay but my point remains that I think the person you were replying to appeared to be ask why not use bada55 curves which claim verifiable randomness of the parameters and the post from Peter R preceding it asked why 977 was arbitrarily chosen and appears (?) no sufficient justification has been provided.

I hope we agree there is a distinct difference between "arbitrarily or even justifiably chosen" and "verifiably random"?

Edit: note I did not dig into the bada55 curves to make sure I understand what they mean by verifiable random. So I am not sure if it is distinct. I am just speaking conceptually above.

Unlike the NIST curves the Bitcoin curve is not "random": There is no parameter question there. The comments on the safer curves page addresses a whole host of analysis points, so with the randomness off the table I was speaking to some of the other things where there are meaningful engineering differences between Bitcoin and curve25519.

If I am not mistaken, aren't you moving the goal posts in that you appear to be talking about bits of security which is orthogonal to what he was talking about verifiable randomness of the parameters to eliminate any suspicion of a backdoor?

For normal usage I am considering a signature verification operation which just for fun is:

sig = ((HashOfThingToSign + EccMultiply(Gx,Gy,RandNum)%N*privKey)*(modinv(RandNum,N))) % N

If I stare at this long enough I can convince myself you are right..  and the more I deal with really big numbers like these
the more I think it is bulletproof.   


 but I'd still love to hear some story about where these lovely numbers Gx and Gy come from,

0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

or

55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424

I've heard:  "value of G should be generated canonically (verifiably random)."

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.

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? 

Regarding the OP.

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

Yep, those are badass

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

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.

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.  

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

https://bitcointalksearch.org/topic/m.3183975

We have:


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.

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

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.

What do words have to do with these calculations?

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:

 

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.  

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

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

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