NSA and ECC

[BurtW]

Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!  So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.

G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.

He meant

If I can pick G I can set G to ("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!

It is just a typo,  ("expired") is a point on the curve.

[BurtW]

This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected:

Select P₀

P₁ = n₀*P₀
P₂ = n₁*P₁
P₃ = n₂*P₂
...
G = n_M*P_M

Now all these "premined" key pairs could maybe be used in some way

But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?

[chriswilmer]

This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected:

Select P₀

P₁ = n₀*P₀
P₂ = n₁*P₁
P₃ = n₂*P₂
...
G = n_M*P_M

Now all these "premined" key pairs could maybe be used in some way

But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?

Wait wait wait... I may be out of my depth here, but isn't the generating point supposed to be able to generate a group of the same size as the order of the curve? If you pick G to be a multiple of an existing point on the curve, then it won't be a "good" generator... it will only generate a smaller sub-group. Am I making any sense?

[BurtW]

Our group is prime and has no sub groups so any point should work as G.

This brings up something that I have been wondering about:

If any point will work equally well for G why not use an "easy" point or an "obvious" point?

x = 0 or x = 1 or x = 2ⁿ all come to mind.

Anyone have any idea why G is not a more "obvious" starting point?

[chriswilmer]

Our group is prime and has no sub groups
 so any point should work as a G.

Ah ha! Thanks. I was wondering why the group order needed to be prime.

[gmaxwell]

Anyone have any idea why G is not a more "obvious" starting point?

Not being able to answer that was why I spent a bunch of time trying to come up with "attacks" that selection of a non-obvious G could yield. But all I could come up with doesn't seem to be too much. ::shrugs::

Ah ha! Thanks. I was wondering why the group order needed to be prime.

Not just that, but if there are subgroups there are reductions that allow you to solve the DLP with basically no more work than solving it over a field thats the size of the largest factor.

[bfever]

Our group is prime and has no sub groups so any point should work as G.

This brings up something that I have been wondering about:

If any point will work equally well for G why not use an "easy" point or an "obvious" point?

x = 0 or x = 1 or x = 2ⁿ all come to mind.

Anyone have any idea why G is not a more "obvious" starting point?

Well, the point must lie on the curve, so it must satisfy   y² = x³ + 7 (mod p).

So x=0, means y²=7, which has no solution for an integer y, so there is no point on the curve with x coordinate 0.
Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way.

I think there is no "obvious" solution, so one starts with a "random" value for x and incrementing this until x³+7 has an integer square root.

I saw some posts of people generating their own curves incorporating hex-art and/or hashes of "copyright notes" into the value + a counter.
It really should not be different, the only thing is everybody needs to use the same G otherwise the key pairs (public/private key) don't match.

[gmaxwell]

...

1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534  is a point on our curve, as is
2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430

and so on. The first missing x, other than zero obviously, is 5.

[fpgaminer]

So x=0, means y2=7, which has no solution for an integer y, so there is no point on the curve with x coordinate 0.
Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way.

We aren't dealing with your ordinary, run-of-the-mill integers here.  We're dealing with a finite field!  y² = 1³ + 7 has a solution (two, in fact).  It's 4218F20AE6C646B363DB68605822FB14264CA8D2587FDD6FBC750D587E76A7EE.  Square that number, modulus our prime, and you get 8.

So yeah, G could have been selected as an obvious, nothing-up-my-sleeve number.  It wasn't.  I'd bet on it being some sentimental thing, like the hash of the author's name or something.

[BurtW]

...

1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534  is a point on our curve, as is
2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430

and so on. The first missing x, other than zero obviously, is 5.

Now I am really out of my depth here but since P = n * G is a very commonly needed operation is is faster or simpler to use, for example the point:

x = 1, y = 29896722852569046015560700294576055776214335159245303116488692907525646231534 as G

In other words, is there any possible efficiency argument that can be made for the selection of G?

In my gut I expect that any G is equally computationally difficult as far as P = n * G goes.  Correct?

[gmaxwell]

In other words, is there any possible efficiency argument that can be made for the selection of G?
In my gut I expect that any G is equally computationally difficult as far as P = n * G goes.  Correct?

Not for our G.

It should be possible, with an expensive search (e.g. >2^32 tries), to find a G that results in a lower hamming weight in the multiplies in a particular implementation and get a very small speed improvement. But I can find nothing about our G that suggests such a thing was done.

[AnonyMint]

He's worried about constants that have no explanation. The SEC random curves have "random numbers" in them, but are they really random? AFAIK nobody knows how one might exploit the algorithms if they weren't, but hesitation is reasonable.

However Bitcoin does not use a random curve. It uses a Koblitz curve where there are explanations for why the constants are the way they are.

He is also worried about math breakthroughs and the shorter key sizes of ECC, and he recommending never use unless required:

https://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography

And he recommends using symmetric instead of public-key (so Lamport instead):

https://www.schneier.com/blog/archives/2013/09/the_nsas_crypto_1.html

And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds:

https://bitcointalk.org/index.php?topic=309594.msg3332190#msg3332190

Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto.

Until the government requires them to do so because Bitcoin becomes a tax-haven. The G20 has been ramping up their plans to go after all tax havens.

Ok, so your take is basically the same as the commenter on Schneier's blog (https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1678526).

Basically he says what you are saying - that a recommended 'random' number generator for use with ECC has been proven to have backdoors, and that some families of ECC curves have weaknesses. However, because we're using secp256k1, a known curve with explainable/justifiable constants, the concern cited by Bruce is not applicable to Bitcoin in addition to the weak motivation for attacking it anyhow.

Thanks for the reply.

Disagree that he said that, also disagree that makes Bitcoin safe. See links above.

Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway).

That bright spot is not assured:

https://bitcointalk.org/index.php?topic=309594.msg3331735#msg3331735

[gmaxwell]

And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds:

There is no seed in the scheme Bitcoin uses, I am not sure how many times you will need to be told this.

[jedunnigan]

Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography.

[gmaxwell]

Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography.

Their rigidity page doesn't appear to explain the choice of generator for any of their "Fully rigid" cases.  See upthread that it would be preferable for the generator to be rigid too, if not essential.

[AnonyMint]

And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds:

There is no seed in the scheme Bitcoin uses, I am not sure how many times you will need to be told this.

Seed has a generic meaning.

http://www.thefreedictionary.com/seed
8. A source or beginning

Is that the best FUD you can do to avoid addressing the point?

Is the only way you know how to discuss and debate is via personal insults?

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

Edit: since he edited his reply below, I will add he has deleted all my retorts which have refuted his reply below (specifically refuting full rigidity, his claim of decreased degrees-of-freedom, and his claim that he isn't being disingenuous). He even deleted my attempt to add my retorts to my thread. I would add a link to my retorts (and I bet you can find them if you really want to), yet he would then likely delete this post or edit or some other infantile, weasel, trolling behavior. Enjoy the bliss.

The edit I made which gmaxell refers to in his reply below is the definition of "seed" quoted above, as if he doesn't know the English language.

Also he edited his upthread post to remove his large point size text that I quoted above. Good to see he is embarrassed and had to backtrack on his trolling.

[gmaxwell]

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.

As an aside: I've now removed AnonyMint from this thread. (Also, note that he edited the message after I responded to it, my quote is the version at the time I responded)

[BurtW]

Presumably, since it was government work,  it should be possible to FOIA any records they have relating to the procedures they used to generate those ECC parameters.

Please go back and read this entire thread, especially the part where this exact idea was brought up and the part where I personally emailed the current committee head and did get some of the answers to our questions.

BTW out of all the threads I have ever participated in this one is, by far, my favorite.

[bluemeanie1]

I've been reading up recently on the revelations that the NSA is subverting implementations/service providers to undermine various internet crypto standards (see this: http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security).

Now this has all of the basic hallmarks of a 'scare campaign' where people are led to believe that crypto techniques/mathmatics themselves are insecure rather than the truth that the NSA is attacking the services or implementations directly (much easier). Therefore I was ready to write this off as 'not relevant' to an open source peer reviewed protocol like Bitcoin.

However, something Bruce Schneier (someone intimately familiar with the mathematics behind crypto algorithms) said has given me some concern. He is suggesting that the ECC constants have been manipulated to facilitate subversion (see his blog comment here: https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929). For his full essay, go here: https://www.schneier.com/essay-446.html.

Any thoughts on implications here we need to be concerned about?

the fact is Elliptic Curve mathematics are a somewhat mysterious region of mathematical knowledge.  They were used in the famous proof of Fermat's Last Theorem: http://en.wikipedia.org/wiki/Wiles%27_proof_of_Fermat%27s_Last_Theorem , thus it's not implausible to suggest that perhaps there are aspects to Elliptic Curves that are not public information.  The Fermat Proof was incredibly complex and verbose.  Note that Fermat's Last Theorem was only proven very recently, here's something interesting

  an Elliptic Curve is

 

  while Fermat's Last Theorem is

  that no three positive integers a, b and c can satisfy the equation
 
  if n is an integer not equal to one or two.

Elliptic Curve Cryptography relies on the supposed computational difficulty of the Discrete Logarithm Function.  http://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem

Supposedly, according to modern public crypto knowledge, there are no shortcuts to solving this problem.  As long as there are no shortcuts, then ECC remains secure.  Interestingly, Fermat's Last Theorem was proven in 1993, and ECC came into widespread use around 2005 [1].  Coincidence?

 [1] although it was suggested earlier

[withnail]

"somewhat mysterious region of mathematical knowledge"

no it is not. it might be so 100 years ago but not now. It is a generalization of ordinary arithmetic (ordinary arithmetic is arithmetic on a "flat line") and it is a major branch of present day math.

See a mathematician's take on NSA backdoor

http://jiggerwit.wordpress.com/2013/09/25/the-nsa-back-door-to-nist/

this will appear in AMS Notices.

As a lot of folks have pointed out, it is unlikely that SHA-2 has been compromised, since to compromise it you need genuine breakthrough in math (say, progress towards P vs NP, if you know what it is) not just sloppiness with malicious intentions. I mean if you can crack SHA-2 then getting insanely rich is the least you can do; try domination of the world, dude.