Saluting the data encryption legacy

[R. A. Hettinga]

<http://news.com.com/2102-1029_3-5381232.html?tag=st.util.print>

CNET News
     http://www.news.com/


 Saluting the data encryption legacy

 By  Bruce Schneier

http://news.com.com/Saluting+the+data+encryption+legacy/2010-1029_3-5381232.html


 Story last modified September 27, 2004, 9:00 AM PDT


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.
 In the days when the Internet was little more than a curiosity,
cryptography wasn't even a recognized branch of mathematics.

 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.


-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'