90 percent of Tor keys can be broken by NSA: what does it mean?

Errata Security CEO Rob Graham has published a blog-post speculating that ninety percent of the traffic on the Tor anonymized network can be broken by the NSA. That's because the majority of Tor users are still on the an old version of the software, 2.3, which uses 1024 RSA/DH keys -- and at keylengths of 1024 RSA/DH crypto can be broken in a matter of hours using custom chips fabbed at an estimated cost of $1B. It seems likely that the NSA has spent the necessary sum and sourced these chips (likely from IBM).

This isn't the same as being able to decrypt all of Tor in realtime, but it does suggest that the NSA could selectively decrypt its stored archives of Tor traffic.

However, the new version of Tor, 2.4, uses elliptical curve Diffie-Hellman ciphers, which are probably beyond the NSA's reach.

Graham faults the Tor Project for the poor uptake of its new version, though as an Ars Technica commenter points out, popular GNU/Linux distributions like Debian and its derivative Ubuntu are also to blame, since they only distribute the older, weaker version. In either event, this is a wake-up call that will likely spur both the Tor Project and the major distros to push the update.

Yesterday's revelations about the NSA's ability to decrypt 'secure' communications were taken by many to mean that the NSA had made fundamental mathematical or computing breakthroughs that allowed it to decrypt securely enciphered messages. But it's pretty clear that's not what's going on.

Mostly, the NSA has spent $250,000,000 per year on a program of sabotage, through which they have inveigled proprietary hardware and software companies, as well as standards bodies, into deliberately introducing back-doors into their technology. This is much more frightening than the idea that the NSA has made profound mathematical breakthroughs -- such breakthroughs might stay within the NSA's walls for years or decades. But a program of systematic sabotage against common crypto tools means that anyone of sufficient skill and attentiveness is likely to discover and exploit those same back-doors -- that means that organized crime, totalitarian states, and other entities even less savory than the NSA should now be assumed to have full access to the financial system, government databases, and other sensitive systems.

But the good news is that, as the ProPublica article mentioned (quoting whistleblower Edward Snowden), "Properly implemented strong crypto systems are one of the few things that you can rely on." That means that free/open source security tools like Tor (which can be publicly inspected for sabotage) can indeed be trusted, where they use state-of-the-art crypto, and implement it well.

It's not surprising to learn that 1024 RSA/DH can be broken by spending huge sums on brute-force computation -- that was already public knowledge prior to yesterday's revelations. But crypto is asymmetrical: it is much, much easier to make crypto stronger than it is to break crypto through brute force. Merely by switching to 1025-bit RSA/DH keys, the Tor Project could double its security. Switching to 1030-bit RSA/DH keys increases the difficulty 64-fold. And by switching to more secure ciphers like elliptical curve Diffie-Hellman, Tor becomes vastly more secure still.