DES Defies Demise

The deeply embedded crypto algorithm lives on in 3DES, but that standard demands careful design and informed choices.

You have only until Sept. 9 to object to the federal governments proposed decertification of the Data Encryption Standard. After reading the proposal, Im tempted to complain that it would not leave DES sufficiently dead.

Many would say that its already been 15 years since the end of this algorithms useful life, even though theyd likely agree with the laudatory eulogy by crypto guru Bruce Schneier. Knowledge of DES implementation issues will continue to be important, however, to those who want to build or buy secure systems.

Finding DES "no longer sufficient to adequately protect federal government information," the National Institute of Standards and Technology announced at the end of last month its recommendation to withdraw Federal Information Processing Standard 46-3, which defines the governments use of an algorithm it first certified in 1976.

Even upon its debut, DES was not universally admired. Many experts, including Whitfield Diffie, now chief security officer at Sun Microsystems, have suggested that it was meant to be breakable—but only, they archly noted, with the kind of resources found at the National Security Agency. Martin Hellman, who collaborated with Diffie in originating public-key cryptography, predicted in 1979 that technical progress would make DES "totally insecure within 10 years."

Four years after that estimated end-of-life date, in 1993, Michael Wiener at Bell Northern Research designed a machine using off-the-shelf components to crack a DES key every 3 hours, at an estimated construction cost of less than $1 million. By July 1998, the Electronic Frontier Foundation had designed an array of custom chips, controlled by an ordinary PC, capable of finding an average of one DES key every 4.5 days at a total project cost of less than $220,000.

Expanding the EFFs machine to match the 3-hour speed of the BNR design might have cost as much as $2 million, but thats an upper bound ignoring economies of scale: I estimate that the actual cost of building that larger system would have been only about $700,000, possibly less than $500,000.

Before the century ended, though, it clearly wasnt even necessary to build a full-scale cracking machine. In January 1999, the Distributed.net coalition linked the EFF system with almost 100,000 PCs across the Internet to examine candidate DES keys at a rate of 245 billion per second, defeating RSA Security Inc.s DES Challenge III competition in just a little more than 22 hours. Its no surprise, then, that RSA Principal Software Engineer Peter Trei borrowed a line from the movie "The Wizard of Oz" to say, upon learning of the NIST proposal soon after it was published, that DES was now "really most sincerely dead."

Except that it is not—at least not entirely.

It would still be acceptable, under the regime proposed by NIST, to continue using DES in its role as a building block of the TDEA (Triple Data Encryption Algorithm) that is also commonly known as triple DES or 3DES. This will be a relief to the many IT hardware builders whove embedded proven DES engines into high-security devices—including hard disks, tape drives and smart-card chip sets—but buyers should beware.

Depending on how its done, 3DES doubles or triples the effective length of the encryption key, from the 56 bits of DES to 112 or 168 bits. The shorter of those equivalent lengths corresponds to the popular 3DES mode of encrypting with one key, decrypting with a second key, then re-encrypting with the first.

The result, though, is not quite as secure as a 112-bit key length would imply: Hellman and collaborator Ralph Merkle have devised an attack that requires "only" 36 thousand trillion steps, admittedly more a theoretical than a practical concern for some time to come due to the methods memory demands of hundreds of thousands of terabytes. Of immediate concern, though, are naive modes of implementing 3DES that are actually (though not obviously) as easy to crack as single DES.

Buyers must understand, therefore, that having triple DES is not a yes-or-no proposition but a stupid-or-smart proposition—it demands careful design and informed choice.

Technology Editor Peter Coffee can be reached at peter_coffee@ziffdavis.com.

To read more Peter Coffee, subscribe to eWEEK magazine.

28571.gif

Check out eWEEK.coms Security Center for the latest security news, reviews and analysis. And for insights on security coverage around the Web, take a look at eWEEK.com Security Center Editor Larry Seltzers Weblog.

77042.gif

Be sure to add our eWEEK.com developer and Web services news feed to your RSS newsreader or My Yahoo page