How big is 128 bits?

It should be fairly well known by now that the venerable DES encryption algorithm is obsolete. NIST made this official when they withdrew the DES standard on May 19, 2005. It’s probably less well known that NIST requires that all US government users move to something at least as strong as Triple-DES by 2010, but that’s what’s recommended to keep encryption secure against adversaries that have access to the bigger and faster computers that get released every year.

Triple-DES provides 112 bits of strength, which NIST says should be good through 2030. After that, US government users will need to use encryption that provides at least 128 bits of strength, like AES does. In the latest NIST guidance, it looks like 128-bits keys will be good essentially forever. Does this make sense, or should we just expect some additional guidance from NIST that increases the required key sizes even more?

From one point of view, it certainly seems like 128 bits of key is good for quite a while, perhaps even essentially forever. If you’re going to attack a symmetric algorithm, you’re probably going to have to do too many computations to do easily on a single computer. A network of many computers is a better idea. An even better idea is to do the computations in hardware instead of software. But even that’s not enough to recover a 128-bit key.

In July 1998, the DES Cracker, a special-purpose computer built by the EFF for only $250,000, managed to recover a 56-bit DES key in roughly 56 hours, and showed that an attacker with a fairly small amount of resources could defeat DES without too much trouble. The DES Cracker could test roughly 92 billion keys per second on 1,536 special-purpose chips. Given a plaintext-ciphertext pair, the overall machine could test all possible DES keys in a bit over 9 days, and you’d expect to find the key that decrypted the ciphertext in about half that time, or about 4 and a half days.

Let’s assume that we can make a special-purpose computer that can test keys one billion times faster than the DES Cracker, or roughly 92 quadrillion keys per second. Maybe Moore’s law and faster clock speeds can help us do this. Adding additional chips to our computer will also help.

Even with this huge increase in speed, such a hypothetical machine will still take roughly 100 billion years to recover a single 128-bit key. This doesn’t look too promising. So unless someone finds an incredibly severe weakness in AES, it looks like that assuming that a 128-bit key is good for essentially forever may be fairly reasonable.