Topic: NSA and ECC - page 11. (Read 48804 times)

Whozit's conjecture or whatever, written in a margin long ago, took frikkin centuries for academics to figure out.

Had the guy maybe not really solved it himself afterall but just imagined he had?

I made a proof, as a child, of the four colour theorem that still looks good to me. In my late teens someone even tried submitting it to Scientific American because it looked so good. Yet to this day I still have not managed to get any actual proper refutation of it or explanations as to how, if it is not a "proof", it fails to be one.

My maths teacher when I first came up with it said the whole thing was so far beyond him he could not even begin to judge if it was or was not mathematically a proof but that it sure seemed to be an irrefutable argument to him, lacking as he was in deep enough mathematical training to figure out where it went wrong, if it did in fact go wrong. (It is so simple, even children "get it", thus suspect as in hmm maybe it is not state-able mathematically in rigorous math.)

So between the margin-written thing that people bumped heads with for so long, and my own personal experience, it does not seem far fetched at all to me that some kid somewhere pointed out some insanely simple thing that mathematicians had all overlooked and continue still to overlook.

Then too there is Bell's Theorem, which even now while Joy Christian keeps pointing out Bell's massive deep fundamental flaw in it a lot of physicists just cannot see / understand the flaw, seemingly because they make the same categorical or dimensional error themselves in judging his work.

-MarkM-

It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards.

At the other hand, from what I understand these constants are like 10 years old.
If there is any secret math that can be used to exploit ECC with a certain curve parameters (and NSA had known about it before these constants were chosen), it would basically mean that all the academic world sucks, if it have not managed to discover the same formulas ever since then. It even seems unlikely that such a breakthrough math inventions would not have leaked out, for all these years.

So there is still hope... but it would still be good to find out how (and why) these constants were picked up.

So maybe there is a class or category of attacks, making all ECC broken, and they iterated through SHA1 generating curves knowing they could, with their clever class or category, break them, but wanting to not bother recommending those the public already had found attacks for?

The attacks known to the public would maybe mostly be individual subsets of the secret class or individual classes of the secret category or something like that.

(I'd have to go read up on what class and category mean in class theory and category theory if I wanted to check whether I used the words set, class and category correctly.)

-MarkM-

Maybe better ask first if the generation methodology is classified.

These slides are interesting:

http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

It says right out that the NSA generated the curves:


However it also implies that the generation criteria might be more complicated than just "iterate a hash input until a functioning curve is found". Is it possible the seed looks strange because large classes of output curves were discarded due to known attacks?

This might be Mr Solinas' email address: [email protected]

We could ask him if how the curves were generated is reproducible.

Apparently the NSA controlled all membership to the IEE P1363 working group:

http://grouper.ieee.org/groups/1363/WorkingGroup/announcements/Nov96.txt


This just looks worse and worse, doesn't it. I didn't realise ECC was so heavily influenced by the NSA before. I thought it had been primarily developed by the academic sector.

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.

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.

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?

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.

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.   

AFAIK wallet.dat is encrypted using AES

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?

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

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.

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.

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.

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:

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:


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?!)
 

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?

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.

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/[email protected]/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.

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.