… The naive way to break an encryption algorithm is to brute-force the key. The complexity of that attack is 2n, where n is the key length. All cryptanalytic attacks can be viewed as shortcuts to that method. And since the efficacy of a brute-force attack is a direct function of key length, these attacks effectively shorten the key. So if, for example, the best attack against DES has a complexity of 239, that effectively shortens DES’s 56-bit key by 17 bits.
That’s a really good attack, by the way.
Right now the upper practical limit on brute force is somewhere under 80 bits. However, using that as a guide gives us some indication as to how good an attack has to be to break any of the modern algorithms. These days, encryption algorithms have, at a minimum, 128-bit keys. That means any NSA cryptanalytic breakthrough has to reduce the effective key length by at least 48 bits in order to be practical.
There’s more, though. That DES attack requires an impractical 70 terabytes of known plaintext encrypted with the key we’re trying to break. Other mathematical attacks require similar amounts of data. In order to be effective in decrypting actual operational traffic, the NSA needs an attack that can be executed with the known plaintext in a common MS-Word header: much, much less.
So while the NSA certainly has symmetric cryptanalysis capabilities that we in the academic world do not, converting that into practical attacks on the sorts of data it is likely to encounter seems so impossible as to be fanciful.
More likely is that the NSA has some mathematical breakthrough that affects one or more public-key algorithms. There are a lot of mathematical tricks involved in public-key cryptanalysis, and absolutely no theory that provides any limits on how powerful those tricks can be.
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.
If we think that’s the case, the fix is easy: increase the key lengths.
Assuming the hypothetical NSA breakthroughs don’t totally break public-cryptography — and that’s a very reasonable assumption — it’s pretty easy to stay a few steps ahead of the NSA by using ever-longer keys. We’re already trying to phase out 1024-bit RSA keys in favor of 2048-bit keys. Perhaps we need to jump even further ahead and consider 3072-bit keys. And maybe we should be even more paranoid about elliptic curves and use key lengths above 500 bits.
NSA surveillance: A guide to staying secure
I’m not a crypto guy by any means, but I’ve been following the field for some time. To me, RSA still seems to me to be the best bet for public key encryption. It’s been around a long time and public academics haven’t found a back door yet. Surely the NSA knows the most about it, but as time increases without a breakthrough in the public domain, the likelihood increases that the NSA hasn’t found a breakthrough either.
ssh2 using RSA with IDEA or blowfish is a good way to go for computer logins. GnuPG (GPG) with RSA and IDEA would be a good solution for general use. Or for written communications, use a one time pad. Just my 2 cents.