Most Tor Keys May Be Vulnerable To NSA Cracking 236
Ars Technica reports that security researcher Rob Graham of Errata Security, after analyzing nearly 23,000 Tor connections through an exit node that Graham controls, believes that the encryption used by a majority of Tor users could be vulnerable to NSA decryption: "About 76 percent of the 22,920 connections he polled used some form of 1024-bit Diffie-Hellman key," rather than stronger elliptic curve encryption. More from the article: "'Everyone seems to agree that if anything, the NSA can break 1024 RSA/DH keys,' Graham wrote in a blog post published Friday. 'Assuming no "breakthroughs," the NSA can spend $1 billion on custom chips that can break such a key in a few hours. We know the NSA builds custom chips, they've got fairly public deals with IBM foundries to build chips.' He went on to cite official Tor statistics to observe that only 10 percent of Tor servers are using version 2.4 of the software. That's the only Tor release that implements elliptical curve Diffie-Hellman crypto, which cryptographers believe is much harder to break. The remaining versions use keys that are presumed to be weaker."
Re:well (Score:5, Informative)
Just use bigger DH, with better cipher. AES-256? Maybe. Twofish? OK.
Bruce Schneier himself advises avoiding elliptic-curve, as being intellectually tainted by the spooks. [theguardian.com]
Re:Question: multi-layer encryption (Score:4, Informative)
**This message has been encrypted twice with the ROT13 method**
Re:well (Score:5, Informative)
Wrong Guardian Schneier link. :-)
http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance [theguardian.com]
From Item 5:
"Prefer symmetric cryptography over public-key cryptography. Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can."
Re:a few hours for one key would be good (Score:5, Informative)
This is not an hypothetical case. In my last job we were in direct competition with IBM and were exchanging crucial pricing information through email. There has been precedents of ECHELON being used to gain economic intelligence (google "echelon airbus boeing" to learn about that)
About Tor versions (Score:5, Informative)
Re:Guess who is funding Tor? (Score:5, Informative)
Re:well (Score:4, Informative)
He hasn't reversed himself from that link you cited - he was just pointing out an NSA recommendation, and was against it then, as well. See his comment to a poster further down:
Bruce Schneier September 30, 2005 11:39 AM
"'Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques'
"But ECC was less researched than the others algorithms!"
I agree with you, not the NSA.
Re:Question: multi-layer encryption (Score:3, Informative)
Re:well (Score:5, Informative)
We certainly need more research, but it looks like an RC4 complete break (that would be the big, recent breakthrough - would love to see the details, now we know about it) and 1024-bit RSA keys are the meat and potatoes of BULLRUN. And since PCI Compliance for a while advised everyone to use RC4 as a workaround to the BEAST attack... yeah. NSA. Bastards.
They set the constants for all of the NIST curves, however. And if they have a SHA-1 preimage (and it's their algorithm they no longer even recommend, so they might) then they could set them any way they wanted. Or just try repeated phrases until they got bit patterns they were after. prime256v1/secp256r1 and all that jazz? We can't trust them anymore. They're NSA-derived - and the way it turns out they've been behaving, we therefore assume that they ARE backdoored, even if they use them themselves.
The curve Tor uses is curve25519. That is not NIST-derived, NSA didn't pick parameters out of a hat for that one: DJB made it independently. It's been designed, and the reasons for the choices thoroughly explained. It's extremely fast due to its structure, it's good even through the twist, the implementation is so careful that it's constant-time to avoid timing attacks, and we have a rough idea how strong it probably is (around 2^110-ish). Ed25519 is also similarly good and makes a great signature scheme (and you could do DH with it better as well), although you probably don't want to use SHA-512 with it anymore, because NSA - Skein-512-512 is probably the way to go. I don't trust NIST's choices anymore. They are ALL NSA, and thus ALL potentially-tainted.
Unless elliptic curves in general are crackable, which would be quite a wheeze, and of course a possibility. Certicom (NSA) have been doing those for a long time: but the 25519 curves are the product entirely of civilian mathematical research, at least. For now, Schneier is spooked and notes RSA still works fine, if slowly, and maybe bigger keys... 3072-bit? 4096-bit? Against an adversary like this - and it's clear that they consider EVERYONE an adversary - we need the margin.
I note DSA and ECDSA really need strong random numbers for every signature (see fail0verflow's Sony crack for a practical exploit), and GCM fails quicker than it should with non-random keys. Reasonable conclusion: subtle RNG backdoors. We should keep a special look-out for those. Other choices exist which aren't similarly affected (particularly, Ed25519 does not need random numbers per-signature, neither does RSA, although RSA blinding does).
What next? AES-128-CCM use in TLS, perhaps, or OCB-AES-128? (Note I'm specifically NOT recommending AES-256/192 because of the meet-in-the-middle attack - I'd rather move to TWOFISH-256.) Ed25519 DH in TLS? All commercial CAs are toast, the model has been so thoroughly subverted that it can't possibly continue to work. What about DNSSEC? Could do the job. But we can't trust the US to manage the internet anymore. We're meeting in November to see what we have to do: maybe if we remake it used good RSA or Ed25519 keys and take the hands of the root out of ICANN, because ICANN is the US and the US has spectacularly demonstrated it cannot be trusted to manage anything, probably no country can... which means, perhaps, it's time to dig the root KSK revocation key out of mothballs: if there's no trust, there's no point. We're going to need a treaty, a .INT. This isn't a quick-fix.
Schneiers most recent comment.... (Score:5, Informative)
Bruce Schneier http://www.wired.com/opinion/2013/09/black-budget-what-exactly-are-the-nsas-cryptanalytic-capabilities/ [wired.com] stated that "Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily."
I'd not rush from DH to ECC but would strongly recommend a move to 2048-bit or above keys
And have just realised that I haven't posted to Slashdot for many years...And yet somehow my .sig is still relevant. NSA may have dropped their plans for mandatory Escrow 15 years ago after the quote was made...but they didn't change the fundamental goal: to read everything.