Life After DES
Burt Kaliski, Chief Scientist
Ever since DES was first proposed in the 1970s, it has been criticized for its short key size. Proposals for "brute-force" DES crackers have been circulated every so often, though until recently no DES cracker is known publicly to have been built. But the message has been the same for the past two decades: a 56-bit key would someday no longer be sufficient for security in many applications.
As a result, researchers have proposed a number of replacements for DES over the past 20 years. Not surprisingly, many proposed replacements have been broken. Indeed, it was not until the early 1990s that researchers in the open crypto community began to appreciate the design principles behind DES. The work of Eli Biham and Adi Shamir on differential cryptanalysis (which DES designer Don Coppersmith acknowledged was known previously to the DES design team) unlocked an entire series of research results on block cipher design. Still, no block cipher has emerged as a standard rivaling DES.
The announcement in 1997 that NIST would be developing an Advanced Encryption Standard (AES) (http://csrc.nist.gov/encryption/aes/aes_home.htm) has changed the landscape significantly. As the U.S. government's replcement for DES, the AES process gives a focal point for the research on alternative algorithms. Previously, the many proposals were distributed among research conferences and analysis was primarily of an academic nature. Now, 15 AES candidates (including one from RSA Laboratories (http://www.rsasecurity.com/rsalabs/rc6/) are being analyzed together by an international group of experts.
The AES is at least a year and possibly more from completion, so developers who wish to move away from DES do not yet have a clear place to go. The financial services industry has developed ANSI X9.52, a standard for "triple-DES" encryption, as one interim solution. In triple-DES, each 64-bit block of a message is encrypted with three successive DES operations rather than one, and the operations involve two or three different keys. Triple-DES offers an effective key size of 112 bits in typical applications, as opposed to 56 bits for DES -- but the encryption and decryption time per block is three times that of DES.
Another interim solution, a kind of "lightweight" triple-DES, is DESX, an algorithm developed in the 1980s by Ron Rivest for RSA Data Security. In DESX, secret values are exclusive-ored with a message block before and after an ordinary DES operation (the X stands for exclusive-or). DESX provides an effective key size of about 120 bits for exhaustive search -- with essentially no impact on encryption and decryption time. DESX also offers greater resistance to certain other types of attack than DES, though triple-DES is even stronger. An analysis of DESX can be found in an article by Phillip Rogaway in the Summer 1996 issue of RSA Laboratories' CryptoBytes newsletter (http://www.rsasecurity.com/rsalabs/cryptobytes/).
Some perspective on the choices involved in triple-DES, as well as on DES and AES, can be found in the Summer 1998 CryptoBytes article by Eli Biham and Lars Knudsen.
Both triple-DES and DESX are appropriate interim steps while waiting for AES. Also, by building in support for alternate algorithms, designers can pave the way for the eventual transition to AES.
The AES will culminate two decades of research in block cipher design with open discussion unlike anything during the development of DES. With its key size of 128 bits and larger, AES will have more than enough security against any brute-force search envisioned. While analysis of the basic design of the AES will need to continue as a means of providing assurance about the security of AES against other kinds of attack, an "AES Challenge" based on brute-force search is not something we're likely to see any time soon.