NSA and ECC

[natb]

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?

[Mike Hearn]

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.

[natb]

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.

[gmaxwell]

The SEC random curves have "random numbers" in them, but are they really random?

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.

[maaku]

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.

[natb]

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.

...

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

This is the key revelation to me as well. It seems that the trust in the parameters chosen for the various curves must be questioned at this point. Does anyone have a history of how our secp256k1 curve parameters were chosen, by whom, and by what process it was tested to give it a 'recommended curve' stamp of approval? It is just a curiosity for me - the point that the Bitcoin framework allows for a substitution of signing technique is noted and understood in the event that a flaw was discovered in our curve, or techniques to accelerate cracking ECC itself were discovered.

[etotheipi]

In case you don't follow slashdot, there was an article today from John Gilmore about obstructionism by NSA folks he's seen over the years:

http://www.mail-archive.com/cryptography@metzdowd.com/msg12325.html

It's mostly about simple obstruction of implementing standardized security systems.  But it wouldn't surprise me if the same folks also attempted some more subtle things, like trying to inject pre-selected "random" constants into crypto systems.  But I'm not all that familiar with the processes they use or how easy that would be.

[gmaxwell]

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

Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field)  curves but for the random ones which almost everyone else uses.

Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document. I believe Bitcoin is the only widespread user of the SECP*k curves.  (Although the curve used in Ed25519 has a similar structure, which is also why it's performance is similar).

P256k1 was not included in any of the NIST standards, it's only a part of the certicom spec. So if you're hypothesizing NIST as the _specific_ vector of pushing for weak ECC then your theory really should exclude Bitcoin's curve from the start.  (In other words: good rational reasoning is that if your argument is ECC is dubious because NSA influences NIST, then you should equally find our use of a non-nist curve comforting, no?)

(This isn't to say that I would find it hard to believe that certicom is a pawn of CSE. )

I would, however, be concerned that the "vulnerability" were the use of koblitz form alone. Part of the problem is that once you start assuming mystery math anything is possible.  My comments about the public keys not being disclosed with good use and our ability to upgrade still stand... though, uh, if our upgrade option were to change to a non-koblitz curve (or a much larger field) I'd have some concerns about the scalability impact.  Making things more secure against conjectured weaknesses doesn't help if the fixes make the system non-viable or drive us into centralization.   (Though I've long wondered with PGP, which doesn't really have the same scaling concerns doesn't use multiple asymmetric schemes in parallel in such a way that an attacker would have to break all of them...)

Personally, I'd like to see us deploy— as an option— Lamport/Merkle signatures because they have totally orthogonal security properties and are based on assumptions most cryptographers would consider fundamentally stronger... plus they answer any QC fud. They also permit very fast validation, even with trivially implemented code (fast SECP256k1 validation is far from trivial).  The tradeoff is that the signatures are much larger... but at least signatures don't end up in the UTXO set. I haven't considered this urgent, but it's been on my long term wishlist since early 2011.

It might be fun to ask certicom to publish the procedure used to select SECP256k1's parameters. Though the design space of near maximally sized "Koblitz"  curves is smaller than you may be guessing. It may be the case that we could reverse engineer the procedure.

[markm]

In case you don't follow slashdot, there was an article today from John Gilmore about obstructionism by NSA folks he's seen over the years:

http://www.mail-archive.com/cryptography@metzdowd.com/msg12325.html

It's mostly about simple obstruction of implementing proper security systems.  But it wouldn't surprise me if the same folks also attempted some more subtle things, like trying to inject pre-selected "random" constants into crypto systems.  But I'm not all that familiar with the processes they use or how easy that would be.

The part (a post or few up and down that page) about "good guys" aka "on our side" seems weird since we seem to be heading toward or to have already reached (maybe long ago  by now) a place where we have figured out certain actions are bad, and that therefore it wouldn't be good to do those acts. So is this about whether good guys can do bad things, deliberately, with aforethought, and still be considered to be good guys?

Is the fundamental problem here that we think that, as good guys, we would prefer having to fight world war three in a world of perfect cryptography for all than to fight it in some kind of Luddite hell in which encryption is only for two-legs, four-legs shouldn't have it? (CF "four legs good, two legs bad", Orwell, Animal Farm)

Do we want to be four-legs, with two-legs looking after us, maybe believing the propaganda promulgated by the conclusion of Animal Farm that two legs really is some kind of superior being, that we could never govern ourselves so need two-legs to govern us?

Are we so weak and pitiful that we need to cripple ourselves before the enemy does so that we can intercept to find out ahead of time how exactly the enemy plans to attempt to cripple us?

-MarkM-

EDIT: maybe its not "we" (the people) who are weak and pitiful but that the Peter Principle is still in effect so "they" (the so called government or its agencies) are?

[gmaxwell]

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

Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field)  curves but for the random ones which almost everyone else uses.

Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document.

So I went and looked at the actual seeds because I wanted to see if I could perhaps reproduce the secp256k1 curve through low entropy methods...

And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible.

E.g. the seed for  P-256r is c49d360886e704936a6678e1139d26b7819f7e90.  They procedure generates random data by feeding the seed into SHA1. There is no reason I could tell that the seed wouldn't have been something like "15" (and all lower values would have failed the test).

Secg says about these curves:

Verifiably random parameters offer some additional conservative features. These parameters are chosen
from a seed using SHA-1 as specified in ANSI X9.62 [1]. This process ensures that the parameters
cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future
special-purpose attacks, and no trapdoors can have been placed in the parameters during their generation.

But that a great big fucking lie, since a special purpose attack only has to applicable to randomly selected curves more often than you can iterate sha1 for you to be able to slip one into one of these "verifiable random" curves. Maybe they used this freedom to apply additional tests and make them stronger... Maybe?

SECG adds another tidbit:

The elliptic curve domain parameters over (primes) supplied at each security level typically consist of examples of two different types of parameters — one type being parameters associated with a Koblitz curve and the other type being parameters chosen verifiably at random — although only verifiably random parameters are supplied at export strength and at extremely high strength.

I would note that if you read "verifiable random" as "backdoored as all fuck" the fact that only verifiable random are provided for export strength (<=128 bit), and perhaps thats some suggestion that the Koblitz curves are not "backdoored as all fuck". Though thats really handwavy speculation... and it could just be that they didn't care about the performance of the export grade ones. (Or... made the export grade ones weak and the others stronger?!)
 

[maaku]

Just to make sure I have this right, Bitcoin does not use these "backdoored as all fuck" ECC specifications?

or

Does bitcoin use an ECC specification with a "magic number"?

Bitcoin uses a curve whose magic numbers were specified by Certicom - thanks for the correction, gmaxwell - a U.S. subsidary of Research in Motion (makers of Blackberry, who have been funneling user communications into the NSA since the early days, apparently) that owns most of the patents related to ECC. Whether that is more or less threatening in light of recent revelations, I'll let you decide.

[gmaxwell]

Bitcoin uses a curve whose magic numbers were specified by Certicom -

Certicom is canadian. And in our curve the magic numbers are generally more tightly constrained by the special form of the curve. But who knows. The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage.

[maaku]

Once again I defer to gmaxwell. I drive by their headquarters in Scotts Valley about once a month .. but apparently this is just the headquarters of their U.S. branch. They are in fact a Canadian company.

[niko]

Someone versed in ECC timeline should sift through the appropriate meeting minutes on certicom site, perhaps they already hint at how parameters were chosen.

[e4xit]

... The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage.

Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers?

[jackjack]

... The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage.

Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers?

AFAIK wallet.dat is encrypted using AES

[gmaxwell]

Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers?

No. The wallet encryption is relatively boring symmetric cryptography. We've intentionally designed it to be slow to inhibit brute-forcing. The fast stuff I'm discussing in this thread is primarily ECDSA signature validation, which must be very fast because all full nodes validate all the transactions.   

[BurtW]

Speaking of the ECDSA, I was wondering if it might be a good idea to have everyone start including a second (more secure?) signature algorithm that does not require a random nonce.  Then when a vast majority of the network nodes contain the new "nonceless" signature algorithm switch over to it but leave the current algorithm as a deprecated option.

On the other hand, thinking out loud here, using the nonce allowed us to discover the bad RNG on android devices.  By switching the ECDSA we might actually mask any future RNG issues which might then cause even harder to detect problems like identical private key generation.

[fpgaminer]

I was wondering if it might be a good idea to have everyone start including a second (more secure?) signature algorithm that does not require a random nonce.

gmaxwell proposed BIP 0032.5, calling for the usage of a deterministic version of ECDSA.  Deterministic ECDSA signature generation (like the one defined by RFC 6979) is compatible with existing ECDSA verification implementations, so any Bitcoin client could use it today.  Neat!  I have a thread open discussing RFC 6979.

On the other hand, thinking out loud here, using the nonce allowed us to discover the bad PRNG on android devices.

It may be wise for applications to run continuous health checks on any RNG they're using.  FIPS 140-2 requires a simple one, for example.  Maybe even run a cut-down version of DIEHARD every so often?

[Mike Hearn]

And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible.

E.g. the seed for  P-256r is c49d360886e704936a6678e1139d26b7819f7e90.  They procedure generates random data by feeding the seed into SHA1. There is no reason I could tell that the seed wouldn't have been something like "15" (and all lower values would have failed the test).

Well, damn. Presumably they'd argue the seed is also supposed to be random for "extra randomness" or something?

If the NSA did know of an attack on ECC for specific curve parameters, doing a brute force search over SHA-1 inputs until you found a breakable output would appear one way to do it.

It'd be really fantastic to know where the hell that seed value came from. Schneier might have a point about not trusting ECC! Or at least only using it with something like curve25519.

BTW what do you mean by "all lower values would have failed the test"? edit: never mind, you mean the seed selection algorithm would be: start at sha1(1), generate candidate parameters, check to see if they are usable, if not move on to sha1(2), etc.