Schneier on Security

The Legacy of DES

The Data Encryption Standard, or DES, was a mid-’70s brainchild of the National Bureau of Standards: the first modern, public, freely available encryption algorithm. For over two decades, DES was the workhorse of commercial cryptography.

Over the decades, DES has been used to protect everything from databases in mainframe computers, to the communications links between ATMs and banks, to data transmissions between police cars and police stations. Whoever you are, I can guarantee that many times in your life, the security of your data was protected by DES.

Just last month, the former National Bureau of Standards—the agency is now called the National Institute of Standards and Technology, or NIST—proposed withdrawing DES as an encryption standard, signifying the end of the federal government’s most important technology standard, one more important than ASCII, I would argue.

Today, cryptography is one of the most basic tools of computer security, but 30 years ago it barely existed as an academic discipline. In the days when the Internet was little more than a curiosity, cryptography wasn’t even a recognized branch of mathematics. Secret codes were always fascinating, but they were pencil-and-paper codes based on alphabets. In the secret government labs during World War II, cryptography entered the computer era and became mathematics. But with no professors teaching it, and no conferences discussing it, all the cryptographic research in the United States was conducted at the National Security Agency.

And then came DES.

Back in the early 1970s, it was a radical idea. The National Bureau of Standards decided that there should be a free encryption standard. Because the agency wanted it to be non-military, they solicited encryption algorithms from the public. They got only one serious response—the Data Encryption Standard—from the labs of IBM. In 1976, DES became the government’s standard encryption algorithm for “sensitive but unclassified” traffic. This included things like personal, financial and logistical information. And simply because there was nothing else, companies began using DES whenever they needed an encryption algorithm. Of course, not everyone believed DES was secure.

When IBM submitted DES as a standard, no one outside the National Security Agency had any expertise to analyze it. The NSA made two changes to DES: It tweaked the algorithm, and it cut the key size by more than half.

The strength of an algorithm is based on two things: how good the mathematics is, and how long the key is. A sure way of breaking an algorithm is to try every possible key. Modern algorithms have a key so long that this is impossible; even if you built a computer out of all the silicon atoms on the planet and ran it for millions of years, you couldn’t do it. So cryptographers look for shortcuts. If the mathematics are weak, maybe there’s a way to find the key faster: “breaking” the algorithm.

The NSA’s changes caused outcry among the few who paid attention, both regarding the “invisible hand” of the NSA—the tweaks were not made public, and no rationale was given for the final design—and the short key length.

But with the outcry came research. It’s not an exaggeration to say that the publication of DES created the modern academic discipline of cryptography. The first academic cryptographers began their careers by trying to break DES, or at least trying to understand the NSA’s tweak. And almost all of the encryption algorithms—public-key cryptography, in particular—can trace their roots back to DES. Papers analyzing different aspects of DES are still being published today.

By the mid-1990s, it became widely believed that the NSA was able to break DES by trying every possible key. This ability was demonstrated in 1998, when a $220,000 machine was built that could brute-force a DES key in a few days. In 1985, the academic community proposed a DES variant with the same mathematics but a longer key, called triple-DES. This variant had been used in more secure applications in place of DES for years, but it was time for a new standard. In 1997, NIST solicited an algorithm to replace DES.

The process illustrates the complete transformation of cryptography from a secretive NSA technology to a worldwide public technology. NIST once again solicited algorithms from the public, but this time the agency got 15 submissions from 10 countries. My own algorithm, Twofish, was one of them. And after two years of analysis and debate, NIST chose a Belgian algorithm, Rijndael, to become the Advanced Encryption Standard.

It’s a different world in cryptography now than it was 30 years ago. We know more about cryptography, and have more algorithms to choose among. AES won’t become a ubiquitous standard in the same way that DES did. But it is finding its way into banking security products, Internet security protocols, even computerized voting machines. A NIST standard is an imprimatur of quality and security, and vendors recognize that.

So, how good is the NSA at cryptography? They’re certainly better than the academic world. They have more mathematicians working on the problems, they’ve been working on them longer, and they have access to everything published in the academic world, while they don’t have to make their own results public. But are they a year ahead of the state of the art? Five years? A decade? No one knows.

It took the academic community two decades to figure out that the NSA “tweaks” actually improved the security of DES. This means that back in the ’70s, the National Security Agency was two decades ahead of the state of the art.

Today, the NSA is still smarter, but the rest of us are catching up quickly. In 1999, the academic community discovered a weakness in another NSA algorithm, SHA, that the NSA claimed to have discovered only four years previously. And just last week there was a published analysis of the NSA’s SHA-1 that demonstrated weaknesses that we believe the NSA didn’t know about at all.

Maybe now we’re just a couple of years behind.

This essay was originally published on CNet.com

Posted on October 6, 2004 at 6:05 PM • View Comments