AES: Who won?

Private-key cryptography has been used for ages, especially on the battlefield. It employs a shared-secret key for communication. By contrast, public-key cryptography, invented in the mid-1970s, relies on the notion of key pairs: a secret private key and a freely available public key. Public-key cryptography obviated the problem of reliable key distribution, a major drawback of private-key cryptography. On the other hand, private-key cryptography is much faster. In practice, a hybrid of these techniques is used — public-key cryptography is used to set up a session key, which becomes the basis for subsequent communication with private-key cryptography.

Approved in 1977, the Data Encryption Standard (DES) was an early standard for private-key cryptography. (See the Sidebar for more on DES.) By 1997, it had become long in the tooth, so the National Institute of Standards and Technology (NIST) issued a Request for Comment (RFC) for a new standard — the Advanced Encryption Standard (AES) — to replace DES. The NIST planned to work closely with the cryptographic community to develop this next-generation private-key algorithm. Note: For further background on AES and a report from the third AES conference, held in April 2000, see Raghavan N. Srinivas’s “AES: Cryptography advances into the future” (JavaWorld, April 2000).

For an introduction to computer security and cryptography, see “Java security evolution and concepts, Part 1: Security nuts and bolts” (JavaWorld, April 2000), also by Raghavan N. Srinivas.

The process

The cryptographic landscape had changed since the days of DES; the new standard needed to be small, hard to crack, fast, and suitable for small devices. These tough and sometimes conflicting requirements, as well as the perception that the government had botched the original DES development process, led to a common belief that the AES process was doomed under the NIST’s direction. The National Bureau of Standards (NBS), which oversaw the DES process, had been widely criticized for its closed and highly secretive approach. The NIST, which morphed out of the NBS, made the AES process far more open by soliciting active input from the cryptographic community.

The requirements

In 1998, the NIST solicited from the industry algorithms that had to meet NIST-defined requirements. The algorithms had to:

• Implement private-key cryptography
• Be a block cipher
• Work on 128-bit blocks and with three key sizes: 128, 192, and 256 bits

The NIST also stipulated that candidate algorithms had to be available worldwide on a nonexclusive, royalty-free basis. The NIST would evaluate candidates based on security margin, performance, and other factors. The institute left other questions about the selection process unanswered, including:

• Would a single or multiple algorithm be selected?
• Would the NIST insist on tweaks to the algorithm as a condition for selection?
• Would the NIST use an arbitrary tiebreaking criteria to decide a close race?

Of course, nagging doubts persisted about whether the NIST was capable of reaching a solution that would satisfy both the cryptographic and user communities.

Milestones

Table 1 lists AES’s important milestones. AES will be part of the Federal Information Processing Standards (FIPS) that will supersede DES as the standard for federal agencies to protect sensitive, unclassified information.

The third AES conference

During the third AES conference, held in New York in April 2000 (see “AES: Cryptography advances into the future“) the Rijndael entry seemed to be in the lead, although no clear consensus emerged. Attendees perceived Rijndael as possessing a simple design based on time-tested principles, as well as reasonable overall performance across varying environments. Moreover, its security margin was deemed reasonably high after several analyses of the algorithm and cryptanalytic attacks. The only doubt was whether the number of rounds (algorithms use a different number of rounds for different key sizes) was sufficient for a good security margin. The prevailing opinion at the conference was that for Rijndael to win, the number of rounds might have to be increased.

Of the other four entries, MARS was criticized for its complex design, while RC6 was singled out for its weak security margin. Twofish and Serpent had some distinct advantages and disadvantages. Table 2 provides a summary of the attendees’ general perception.

None of the candidate algorithms’ security margin was obviously superior, so no clear consensus developed at the conference or in its immediate aftermath. Indeed, the important question of whether multiple algorithms would comprise the standard remained unanswered.

Multiple algorithms vs. a single algorithm

The argument against multiple algorithms centers around the lack of interoperability among the algorithms and potentially insufficient memory requirements on some small-target devices. The main argument for multiple algorithms: any one algorithm would not suffice for all intended scenarios of AES usage (in different devices, software, and so on). Additionally, a multiple-algorithm standard might hold up better against a determined attack than a single-algorithm standard would.

The winner: Rijndael

On Oct. 2, the NIST selected a single algorithm as the winner: Rijndael (pronounced as “Reign Dahl,” “Rain Doll,” or “Rhine Dahl”).

The NIST’s fact sheet explains, “When considered together, Rijndael’s combination of security, performance, efficiency, ease of implementation, and flexibility makes it an appropriate selection for the AES. Specifically, Rijndael appears to be consistently a very good performer in both hardware and software across a wide range of computing environments regardless of its use in feedback or non-feedback modes.” Vincent Rijmen, one of Rijndael’s designers, said, “We are, of course, very happy. I think that Rijndael will be used in many applications. Some people definitely want to have AES; others told me they would use Rijndael anyway, irrespective of the outcome of the process, because it suits their application well.” Regarding the other finalists, he said, “I can imagine that for some other applications, people will still want to use other algorithms.”

Susan Landau, senior staff engineer at Sun Microsystems and author of several articles related to privacy, cryptography, and AES (see Resources), said about Rijndael, “It was my favorite of the algorithms: a clean and succinct description, good reasons for its design parameters, efficient implementations.”

As for the selection of a single algorithm, Jim Dray, senior computer scientist at the NIST, said, “The one versus multiple AES algorithm issue is complex, and strong arguments were made on both sides. Since the AES will specify a single algorithm, developers will be able to build AES-compliant systems without the added complexity of algorithm-selection mechanisms.”

The future

After a three-month public review, the US secretary of commerce will likely sign a Federal Information Processing Standard (FIPS) formalizing the AES as a US government standard. More significantly, it’s expected that other governments and private standards will adopt AES (just as they adopted DES), heralding a new generation of cryptography. Table 3 illustrates the projected schedule.

Raif S. Naffah, senior software engineer at Forge Research and the project leader of the Java implementation at Cryptix for the AES quest, said, “Everything in the cipher world from now on will be measured, quantified, and compared to the AES. Be it in speed, strength, block size, key size, number of rounds, and so on — it will be relative to the AES. It is the yardstick!”

Implications for Java developers

Several Java implementations of Rijndael already exist — Cryptix and IAIK, for example. Maxine Erlund, senior engineering manager responsible for Java security and networking at Sun Microsystems, said, “Now that Rijndael has been chosen as the Advanced Encryption Standard, we’re investigating the possibility of including an implementation of Rijndael in our SunJCE Cryptographic Service Provider for the upcoming Java 2 Platform, Standard Edition (merlin) release.”

The role of the NIST

Many believe the NIST performed admirably in a task that seemed impossible to execute to the general satisfaction of the cryptographic community.

Bruce Schneier, a leading cryptographer on the Twofish team, summed it up, “I have nothing but good things to say about NIST and the AES process. Given their resources, I think NIST did an outstanding job refereeing. They were honest, open, and fair. They had the very difficult job of balancing the pros and cons of the ciphers, and taking into account all the comments they received.”

Asked about his algorithm not being selected, Schneier added, “Participating in AES is about the most fun a block-cipher cryptographer could possibly have, and the Twofish team certainly did have a lot of fun. We would do it all over again, given half the chance.”

Andreas Sterbenz, developer of the Java Rijndael implementation at the Institute for Applied Information Processing and Communications (IAIK) in Graz, Austria, also commented on the effectiveness of the process. “It had a very positive affect on the crypto community,” said Sterbenz, “and has resulted in the design of many new algorithms. All of the finalists seem to be as good an algorithm as any we have had in the past.”

Conclusion

The NIST managed to win over the naysayers by keeping the AES development process open and on track. Contrary to some skeptics, NIST did not pick an algorithm that originated in the United States, one of the main criticisms of DES.

An unencumbered AES (not protected by patents, that is) should result in several implementations ranging from smart cards to supercomputers, thus paving the way for the standard’squick and universal adoption.

Future resiliency, one of the NIST’s original requirements, is very hard to incorporate into any algorithm, since future attacks can (and will) become more sophisticated as technology progresses. Only time will tell if the NIST’s choice was a good one.

Source: www.infoworld.com