by Edgar Danielyan

Much has changed since introduction of the Data Encryption Standard (DES) [2] in 1977. Our hardware is faster, we have more memory, and the use of computer networks in all areas of human activity is increasing. The widely used DES has, on several occasions, been proven to be inadequate for many applications—especially those involving the transmission of sensitive information over public networks such as the Internet, where the entire transmission may be intercepted and cryptanalyzed. Specialized hardware has been built that can determine the 56-bit DES key in a few hours. These considerations, and others, have signaled that a new standard algorithm and longer keys are necessary.

Fortunately, in January 1997, the U.S. National Institute of Standards and Technology (NIST) announced that it's time for a new encryption standard: the Advanced Encryption Standard (AES). They formalized their requirements and issued a call for candidate algorithm nominations in September 1997. The deadline for submissions was June 1998, when a total of 15 algorithms were submitted for consideration. This article shows why DES is outdated and should not be used for any purposes that require serious encryption. It also provides a brief description of the soon-to-come replacement of DES, the Advanced Encryption Standard.

Data Encryption Standard
Published as the U.S. Federal Information Processing Standard 46 in 1977, DES is still widely used, despite being proven inadequate for use in many applications. It is a symmetric block cipher (shared secret key), with its block size fixed at 64 bits. There are four defined modes of operation, with the Electronic Code Book (ECB) mode being the most widely used [1]. Additionally, DES has been incorporated into numerous other standards, such as American Bankers Association's Protection of Personal Identification Numbers in Interchange Standard, Management and Use of Personal Identification Numbers Standard, Key Management Standard, and three ANSI standards, Data Encryption Algorithm (DEA), Standard for Personal Identification Number (PIN) Management and Security, and Standard for Financial Institution Message Authentication [3]. In particular, DES is also specified as an approved algorithm in the IP Security Architecture (IPSec) standard [9], which is used in the equipment from many different suppliers.

Key Length
Key length is one of the two most important security factors of any encryption algorithm—the other one being the design of the algorithm itself. DES uses a 64-bit block for the key; however, 8 of these bits are used for odd parity and are, therefore, not counted in the key length. The effective key length is then calculated as 56 bits, giving 2⁵⁶ possible keys. A true 64-bit key has 256 times as many keys, whereas a 128-bit key is 2⁷² times "better" than a 56-bit key. As if this was not enough, DES also has so-called weak and semi-weak keys. During the encryption process, the key is used to generate two values that are used for separate purposes during the process. These 16 weak and semi-weak keys will produce values that don't appear to be random. They will give outputs of all-ones, all-zeros, or distinguishable patterns of ones and zeros. It is generally recognized that these 16 key values should not be used. The key length was known to be a factor in trusting DES soon after DES was published. For this reason, people started exploring the use of multiple encryption passes and multiple keys. Triple DES (3DES) is a way of using DES encryption three times.

The most common method is to first encrypt the data block with one key. The output of this operation is run through the decryption process with a second key, and the output of that operation is run through the encryption process again with the first key. This process makes the effective key length 112 bits long. Again, the problem with weak and semi-weak keys remains. The disadvantage of Triple DES is that it is about one-third as fast as DES when processing data. This effort just slightly extended the life of DES while a suitable alternative could be found.

Breaking the DES
In addition to the brute-force key search (for example, trying every possible key in order to recover the plaintext—for DES that would be 2⁵⁶ keys), there is also a technique known as cryptanalysis, which may be used to find the key or the plaintext. Essentially, there are two publicized ways to cryptanalyze DES: differential and linear. Discovered by Biham and Shamir in 1990, differential cryptanalysis was previously unknown to the public. In short, differential cryptanalysis looks at the difference between pairs of ciphertext and uses the information about these differences to find the key. Linear cryptanalysis, discovered by M. Matsui, on the other hand, uses a method called linear approximations to analyze block ciphers (not only DES). Because some internal structures used in DES are not designed to be strong against linear cryptanalysis, it is quite effective when used against DES. To show that the DES is inadequate and should not be used in important systems anymore, RSA Data Security [7] sponsored a challenge to see how long it would take to decrypt successively more difficult algorithms. Two organizations played key roles in breaking the DES: the distributed.net and the Electronic Frontier Foundation (EFF).

distributed.net
distributed.net [6] is a worldwide distributed computing network. Started in 1997, the company now has thousands of participants who are contributing their idle computing power to provide an equivalent of about 160,000 Pentium II computers working in parallel. The company's mission statement says, in particular:

"We will deploy our software to form an immense, globally distributed computer that solves large-scale problems and provides an accessible pool of computational power to projects that need it. This deployment will also demonstrate the real-world utility of both distributed computing in general and our software in particular."

It may be said that they are doing well: projects undertaken and successfully completed by distributed.net include the CS Cipher, DES III, DES II 2, and RC5-56 challenges. At the time of writing, distributed.net is working on two projects: breaking RC5 with a 64-bit key and finding Optimal Golomb Rulers (OGRs). The idea behind distributed.net is that it is possible to distribute chunks of data over the Internet to be processed in parallel by participating computers during their idle time. The results of these calculations are then sent to a central computer that coordinates the distributed computation. The same principle is used by the SETI (Search for Extraterrestrial Intelligence) @ Home project.

Electronic Frontier Foundation
The EFF's DES cracking computer was designed by Cryptography Research, Advanced Wireless Technologies, and the EFF [5]. The design was based upon theoretical work by Michael Wiener [10]. It checked 90 billion keys per second, was assembled in six Sun 2 cabinets, and had 27 boards and 1800 custom chips. Built for less than $250,000, it found the key in approximately 56 hours of brute-force search.

DES I
The DES I contest was the first attempt to prove that DES is no longer fit for any serious use. It was completed on June 17, 1997, by R. Verser in a collaborative effort, after checking about 14 percent (10,178,478,175,420,416 keys) of the key space. It took 84 days.

DES II
There were, in fact, two DES II challenges. distributed.net participated in the first one, which began on January 13, 1998, and completed it on February 23, 1998. About 63 quadrillion keys were checked. At the end, the participants of distributed.net were checking 28 gigakeys per second. The decrypted text was "The unknown message is: Many hands make light work." The EFF won the second challenge on July 15, 1998, in less than three days, with distributed.net coming in second. This time the plaintext read "It's time for those 128-, 192-, and 256-bit keys."

DES III
The DES III contest, announced by RSA Data Security on December 12, 1998, to start on January 18, 1999, was also a success. In an official press release, RSA said:

"First adopted by the federal government in 1977, the 56-bit DES algorithm is still widely used by financial services and other industries to protect sensitive on-line applications, despite growing doubts about its vulnerability to hackers. It has been widely known that 56-bit keys, such as those offered by the government's DES standard, offer marginal protection against a committed adversary."

It took 22 hours and 15 minutes for Electronic Frontier Foundation's Deep Crack computer and distributed.net's worldwide distributed computing network to find out the 56-bit DES key, decipher the message, and win the $10,000 contest. The decrypted message read "See you in Rome (Second AES Conference, March 22-23, 1999)" and was found after checking about 30 percent of the key space. This latest exercise finally proved that DES belongs to the past.

AES Timeline
In April 1997, NIST organized a workshop to consider criteria and submission guidelines of candidate algorithms; later in September, an official call for nominations was published in the U.S. Federal Register. By June 1998, 15 algorithms were submitted to the NIST for consideration:

	CAST-256 (Entrust Technologies)
	CRYPTON (Future Systems)
	DEAL (Richard Outerbridge, Lars Knudsen)
	DFC (National Centre for Scientific Research, France)
	E2 (NTT)
	FROG (TecApro Internacional)
	HPC (Rich Schroeppel)
	LOKI97 (Lawrie Brown, Josef Pieprzyk, Jennifer Seberry)
	MAGENTA (Deutsche Telekom)
	Mars (IBM)
	RC6 (RSA)
	Rijndael (Joan Daemen, Vincent Rijmen)
	Safer+ (Cylink)
	Serpent (Ross Anderson, Eli Biham, Lars Knudsen)
	Twofish (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson)

NIST asked for public comments on these 15 algorithms and set the date for the second AES candidate conference to March 1999, to be held in Rome, Italy. The candidate algorithms were tested from both cryptological and performance viewpoints. One of the original NIST requirements for the algorithm was that it had to be efficient both in software and hardware implementations. (DES was originally practical only in hardware implementations.) Java and C reference implementations were used to do performance analysis of the algorithms. A few months later, a NIST press release announced the selection of 5 out of 15 algorithms that survived rigorous testing and cryptanalysis. This fact is not to say that the algorithms that were not selected were broken or were without merit. Those algorithms either were not as efficient, or were not as practical to implement.

The selected algorithms were Mars, RC6, Rijndael, Serpent, and Twofish. These algorithms were accepted as cryptologically strong and flexible, as well as able to be efficiently implemented in software and hardware. In August 2000, the National Security Agency published the VHDL model for performance testing of algorithms when implemented in hardware. Finally, in October 2000, a NIST press release announced the selection of Rijndael as the proposed Advanced Encryption Standard.

Rijndael
Rijndael [4] (pronounced "Reign Dahl", "Rain Doll", or "Rhine Dahl") was designed by Joan Daemen, PhD (Proton World International, Belgium) and Vincent Rijmen (Catholic University of Leuven, Belgium). Both authors are internationally known cryptographers. Rijndael is an efficient, symmetric block cipher. It supports key and block sizes of 128, 192, and 256 bits. The main design goals for the algorithm were simplicity, performance, and strength (that is, resistance against cryptanalysis). When used in Cipher Block Chaining Message Authentication Code (CBC MAC) mode, Rijndael can be used as a MAC algorithm; it also may be used as a hash function and as a pseudo random number generator (both are special mathematical functions widely used in cryptography; an example of a hash function is Message Digest 5 (MD5)—a popular message digest algorithm by Ron Rivest). In their specification of the algorithm, the authors specifically state the strength of Rijndael against differential, truncated differential, linear, interpolation, and Square attacks. Although Rijndael is not based on Square [8], some ideas from the Square algorithm design are used in Rijndael.

Square is a 128-bit symmetric iterated block cipher designed by Daemen, Rijnmen, and Knudsen. Its primary design goal was strength against both linear and differential cryptanalyses; the high degree of parallelism of the Square algorithm allows efficient implementation on parallel computers.

Of course, the length of the key is also very important, especially because the most efficient known attack against Rijndael is an exhaustive key search. It would take 2²⁵⁵ runs of Rijndael to find a key 256 bits long. To the credit of the authors, Rijndael does not use "parts" or tables from other algorithms, making it easy to implement alone.

Table 1: Comparing DES and AES

	DES	AES
Key Length	56 bits	128, 192, or 256 bits
Cipher Type	Symmetric block cipher	Symmetric block cipher
Block Size	64 bits	128, 192, or 256 bits
Developed	1977	2000
Cryptanalysis resistance	Vulnerable to differential and linear cryptanalysis; weak substitution tables	Strong against differential, truncated differential, linear, interpolation and Square attacks
Security	Proven inadequate	Considered secure
Possible Keys	256	2128, 2192, or 2256
Possible ASCII printable character keys*	957	9516, 9524, or 9532
Time required to check all possible keys at 50 billion keys per second**	For a 56-bit key: 400 days	For a 128-bit key: 5 x 1021 years

* When a text password input by a user is used for encryption (there are 95 printable characters in ASCII).

**In theory, the key may be found after checking 1/2 of the key space. The time shown is 100% of the key space.

Summary
It is expected that AES will be officially published as a Federal Information Processing Standard (FIPS) in April–June 2001, and implementations of AES in various security systems probably will surface shortly thereafter. In the meantime, authoritative information on AES developments may be found on NIST's Web site. The full mathematical specification of the algorithm and reference implementations in C and Java are also available from the same Web site.

References
[1] Applied Cryptography, 2nd edition, by Bruce Schneier, 1996, John Wiley & Sons.

[2] National Institute of Standards and Technology (NIST),
http://www.nist.gov

[3] American National Standards Institute (ANSI),
http://www.ansi.org

[4] The Rijndael Specification,

[5] Electronic Frontier Foundation,
http://www.eff.org

[6] distributed.net,
http://www.distributed.net

[7] RSA Security,
http://www.rsa.com

[8] Square Specification,


[9] Kent, S., Atkinson, R., "Security Architecture for the Internet Protocol," RFC 2401, November 1998.

[10] Michael Wiener, "Efficient DES Key Search," Proceedings of the CRYPTO'93 Conference, August 1993.

[11] Madson, C., Doraswamy, "The ESP DES-CBC Cipher Algorithm With Explicit IV," RFC 2405, November 1998.

[A prior version of this article was published in the February 2001 issue of the ;login: magazine].

EDGAR DANIELYAN is a Cisco Certified Network, Design and Security Professional, as well as member of ACM, USENIX, SAGE, and the IEEE Computer Society. He has worked for a national telco, a bank, the United Nations, and the Ministry of Defense, among others. Currently self-employed, he consults and writes on internetworking, UNIX, and security. E-mail: edd@danielyan.com