Topic: NSA and ECC - page 12. (Read 48711 times)

Schneier's reasoning is basically this: we don't know what cryptanalysis the NSA is capable of (Schneier might after seeing the leaked documents, but he's not letting on). But it is likely that if there were a weakness it would likely affect only certain categories of curves. The random curves were (presumably) chosen at random, but so were the Koblitz curves: there are many possible Koblitz curves, and the specific ones enumerated in the standard (like secp256k1) were purportedly chosen at random from the set of possible Koblitz curves of that length. But here's the rub: how do we know the NSA didn't search through the space of Koblitz curves looking for one that was secure as far as academia knew, but susceptible to attacks based on mathematics only the NSA knew?

Pre-Snowden, this would have been considered tinfoil hat paranoia because it is not a new concern. The exact same situation existed with DES, which was the federal standard for cryptography for decades. Designed by IBM but with parameters chosen by the NSA, some paranoids thought they had inserted a back door (there was even a Senate investigation). But as we later found out, the tweaked S-boxes strengthened the algorithm against differential cryptanalytic attacks, which weren't known to the public until recently.

The rules of the game until now had been: we work with the NSA through NIST competitions to standardize cryptography. The NSA continues to collect the intelligence it needs through exploiting side channels, weak random number generators, bugs, and even strong-arm techniques, but the algorithms are secure. You can trust the math.

These new revelations apparently throw that out the window. In recent years the NSA actively pushed NIST for standards that it knew were insecure. Not easy-to-get-wrong, like DSA (choose a predictable K value, or reuse an old value and you reveal your private key - a slight of hand that puts the master keys inside the RNG, something which the app has little control over and the NSA can influence), but rather fundamentally broken in subtle ways. How do we know they did not do the same for ECDSA, or any other standardized crypto system that has chosen parameters?

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

EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this.

FWIW, the "random" curves have their parameters selected by a deterministically random machine search... this seems like it would have made choosing their parameters maliciously even harder.

I do sometimes worry about ECC since there are techniques for DLP solving which have scalability more like modern factoring but which (currently) only apply to supersingular curves. If someone figures out how to apply them to ordinary curves, e.g. by solving a related problem on extension fields, we'd need to use ECC with more RSA like key sizes to obtain comparable security.

Fortunately none of this is fundamental to Bitcoin— Bitcoin could add another checksig operator very quickly if there appeared to be an urgent need... and addresses which are not reused only have their public keys exposed to a hypothetical ECC cracker for a brief time between a spend announcement and confirmation.

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.

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.

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.

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?