Dr. Dobb's Journal December 1998

The Current State of DES

DES is the Data Encryption Standard, the current standard encryption algorithm. On July 17, 1998 the Electronic Frontier Foundation (EFF) announced the construction of a DES brute-force hardware cracker (http://www.eff.org/ descracker/). This $220,000 device can break a DES key in an average of 4.5 days.

The news here is not that DES is insecure, that hardware algorithm-crackers can be built, nor that a 56-bit key length is too short; cryptographers have been saying it for years. Technological predictions made about the declining costs of such a machine, made in the late 1970s, the 1980s, and the early 1990s, turned out to be dead-on.

The news is how long the government has been denying that these machines were possible. As recently as June 8, 1998, Robert Litt, principal associate deputy attorney general at the Department of Justice, denied that it was possible for the FBI to crack DES. "[It is a myth that] we have supercomputers that can crack anything that is out there," Litt said. "Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message...We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department." (See the full story at http://www.wired.com/news/news/politics/story/12830.html.)

My comment was that the FBI was either incompetent, or lying, or both. No one uses Pentiums to break DES, except as a demonstration. Anyone could have told Litt that.

EFF's machine is not innovative engineering. It is not state-of-the-art cryptography. It is not cutting-edge technology. The machine uses old, boring chip technologies, simple hardware design, not-very-interesting software, and no cryptography. This is not a marvel of engineering; the only interesting thing is how straightforward the design really is.

Moreover, the machine scales nicely. EFF spent $220,000 on its first machine. They can spend another $220,000, and the double-sized machine will run twice as fast. Now that the basic design work is done, implementation improvements and performance tweaks can increase the performance (or decrease the price) by at least a factor of five. And Moore's Law predicts that the same machine will be either twice as fast or twice as cheap in another 18 months.

The EFF machine broke DES, but it could just as easily have been designed to break any other encryption algorithm. The attack was against the key length, not against the algorithm design (see http://www.counterpane.com/keylength .html). Moreover, a slightly more expensive design would have used FPGAs, allowing the system to work against a variety of algorithms and algorithm variants.

The only solution here is to pick an algorithm with a longer key. DES has a fixed 56-bit key. Triple-DES has a 112-bit key; there isn't enough silicon in the galaxy or enough time before the sun burns out to brute force triple-DES. DES-X and XORing additional key blocks before the first round and after the last round add considerable security to DES, and is much cheaper than triple-DES.

The EFF is a civil liberties group, and this was just a demonstration project. Government agencies like the FBI and the NSA would presumably spend a lot more time engineering a more efficient solution. It is reasonable to assume that any country with an intelligence budget has built this sort of machine, probably one a couple of orders of magnitude faster.

There are undoubtedly many, many technical improvements that can be made to the EFF design to make brute-force search cheaper and faster. But the fact that a civil liberties group can use old technology to build something that the administration has denied can be built -- that's the real news.

-- B.S.