AES: Cryptography advances into the future

The Data Encryption Standard (DES) boasts nearly universal acceptance today, with only a few exceptions. Government communications, bank electronic funds transfers, civilian satellite communications, and even computer systems’ passwords — all rely on DES for protection.

DES, officially approved as a standard in 1977, heralded a new era in cryptography. Prior to DES, hardly anything about cryptography was in the realm of public interest and analysis. DES changed all that, however. By certifying a secure algorithm, the government opened an avenue for studying and attacking cryptographic algorithms. (Note: See the sidebar for a brief description of cryptanalysis, a complementary field to cryptography. Cryptanalysis is the science of attacking cryptographic algorithms.)

There have been several criticisms directed at DES, including its inadequate 56-bit key length and an alleged trapdoor inserted by the National Bureau of Standards (NBS), the predecessor to today’s National Institute of Standards and Technology (NIST). Despite these gripes and further claims of attacks, DES has withstood the test of time, until recently: in January 1999, a cobbled-together network of 100,000 PCs cracked a DES-encoded message in slightly less than 24 hours.

It was apparent that with the availability of cheaper and faster hardware, DES would be rendered untenable in a few years. To address this problem, the NIST issued a Request For Comment (RFC) in 1997 for a standard — to be called AES, or the Advanced Encryption Standard — to replace DES. NIST would work closely with the industry and the cryptographic community to develop this next-generation private-key algorithm.

Private-key cryptography

As a bit of background, private-key cryptography uses a secret key for both encryption and decryption. The algorithm employs several iterations, referred to as rounds. Each round uses a subkey derived from the key. The transformation from plaintext to ciphertext and vice versa uses the subkey and progresses through the rounds. The selection or generation of subkeys is referred to as the key schedule.

Usually, both encryption and decryption processes use the same algorithm, with the key schedule being different.

(Note: For an introduction to computer security and cryptography, see “Java Security Evolution and Concepts, Part 1: Security Nuts and Bolts,” also by Raghavan N. Srinivas.)

AES criteria

To be a successful replacement to DES, the AES algorithm design would need to satisfy a number of criteria: strong security, simple design, good performance, and so on.

Security obviously holds the top priority for the AES algorithm. With security in mind, the algorithm must account for future resiliency — the algorithm’s designed-in ability to withstand future attacks.

Moreover, the algorithm design, contrary to conventional wisdom, should be simple so that it can be successfully cryptanalyzed.

Next on the AES criteria list: good performance. Widespread market adoption will require reasonably good performance on a variety of platforms, ranging from easy-to-crack smart cards to the largest servers. Good algorithm performance includes speed for the encryption and decryption process as well as the key schedule.

The AES process

In 1998, the NIST solicited algorithms that had to meet NIST-defined requirements. To have qualified for consideration, the algorithm must:

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

Additionally, candidate algorithms must be available worldwide on a nonexclusive, royalty-free basis.

For round one, the NIST received twenty-one submissions, of which fifteen met the requirements. Cryptanalysis, performance-related work, and comments by the cryptographic community followed. In August 1999 the NIST announced the five finalists, summarized in the table below.

These five first-round finalists have now moved on to round two, where the process continues. NIST plans to announce the final winner(s) this summer or fall.

The third AES conference: The report

The third AES conference was held at the Hilton New York Towers on April 13 and 14, corresponding to near the end of round two. Expensive rooms, endless cab lines — not my choice for a venue, but that’s a different story. However, I think that NIST organized a great conference, and the consensus among the community was that NIST so far has done a great job overseeing the AES selection.

During the show, Jim Foti of NIST, who opened the conference and outlined the remaining AES process, talked to me about the growing interest in AES. “The first AES conference had 185 participants, the second had 190, and the third has from 230 to 250 participants. A substantial number of participants are from outside the US,” Jim mentioned.

The two-day conference was split into eight sessions, four per day, with an additional informal rump session closing day one:

• Session 1: FPGA evaluations
• Session 2: Platform-specific evaluations
• Session 3: Surveys
• Session 4: Cryptographic analysis and properties I
• The rump session
• Session 5: Cryptographic analysis and properties II
• Session 6: AES issues panel
• Session 7: ASIC evaluations/individual algorithm testing
• Session 8: Algorithm submitter presentations

Session 1: FPGA evaluations

Session 1 covered field programmable gate arrays (FPGA), a type of programmable hardware. During the session it was revealed that some of the AES algorithms that performed poorly in software implementations did remarkably well in FPGA implementations. The Serpent algorithm, held up as an example, maps quite well to hardware.

During the session break, I had an interesting conversation with Whitfield Diffie, one of the pioneers of public-key cryptography. Diffie said, “There will be a diversity of AES implementations in hardware, operating systems, and Java.” Indeed, each of these — hardware, operating systems, and Java — have unique characteristics, which complicate the process of selecting an algorithm.

Session 2: Platform-specific evaluations

Session 2 covered platform-specific evaluations — implementation of algorithms on a variety of platforms, including PA-RISC, IA-64, Alphas, high-end smart cards, and DSPs (digital signal processors). Nothing conclusive emerged from the session, and it was clear that no single algorithm suited all contexts. The Rijndael algorithm seemed to perform reasonably well on the different platforms overall.

At lunch, I sat with the Serpent algorithm authors Ross Anderson and Eli Biham; PGP (Pretty Good Privacy) author Phillip Zimmerman; Ron Rivest of RSA Laboratories; and Brian Snow of the National Security Agency. Politics and mathematics intertwined throughout the lunch conversation, themes that also summarized the general tenor of the conference.

Session 3: Surveys

After lunch came session 3, devoted to surveys and performance comparisons, including a comparison of Assembly, C, and Java implementations.

Session 3’s last paper — presented by Andreas Sterbenz of the Institute for Applied Information Processing and Communications (IAIK) in Graz, Austria — covered Java performance. Sternbenz’s paper showed that RC6 emerged as the fastest algorithm for Java, while Rijndael did well for 128-bit keys but not as well for longer key lengths. Apparently, although Rijndael has a nice key schedule, it uses additional rounds for longer key lengths.

At the reception at the end of the day, I spoke with Sterbenz about the AES candidates’ support based around the JCE (Java Cryptography Extension) architecture. “Programming of these algorithms in Java for performance requires some special techniques,” he said. “Nonoptimized implementations will obviously suffer performance problems. I think Java implementations of AES will be widely available on a variety of platforms. I hope AES will be available from Sun in a future version of Java.”

Regarding his implementation experience, he claims, “RC6 was the simplest to optimize. [The other candidates] had varying complexities for optimization. However, I like Rijndael the best.”

Concerning Java and AES performance, I exchanged email with Jim Dray, senior computer scientist in NIST’s security division, who wrote a paper on the performance analysis of the final round Java candidates. Dray said, “Anyone writing Java code that uses block cipher functionality will need to know about AES. The hope is that AES will be included in future releases of Sun’s cryptographic service provider package.”

Dray, when asked about Java’s perceived performance problems, added, “Many useful cryptographic applications can be developed entirely in Java. The performance differential between Java and some other languages should also become less of an issue as the overall performance of computing platforms continues to increase.”

Dray reported that NIST used an API, developed in conjunction with Cryptix, for the Java study. “In fact,” he added, “I’ve just completed a JCE 1.2 cryptographic service-provider package containing the five AES finalists.” In his study, the Rijndael and RC6 algorithms performed well for the most part, Dray reported.

Session 3’s bottom line: performance depends on the implementations, and, although some patterns emerged, nothing is set in stone.

Session 4: Cryptographic analysis and properties I

Session four in part covered cryptographic analysis and properties. (Session 5 would continue the next day where session 4 left off.)

It’s worth noting that, all else being equal, increasing an algorithm’s number of rounds can increase its strength. For example, the Serpent algorithm, which is perceived as having the highest security margin out of the finalists, employs 32 rounds — more than any of its competitors.

In session 4, it was revealed that none of the candidate algorithms were subjected to cryptanalytical attacks up to their potential number of rounds. However, some attacks on reduced rounds of the respective algorithms indicated potential weaknesses. In particular, session 4 participants discussed attacks on the MARS and Serpent algorithms.

The rump session

The open and informal rump session, which ran to eight o’clock the first night, proved quite useful and informative. The rump session presentations were:

• A comparative study of the performance of AES final candidates using FPGAs
• Empirical correlations in AES round functions
• Cryptanalytic progress: lessons for AES
• IP Security (IPSec) and key agility for AES
• Trawling Twofish (revisited)
• Semiequivalent keys in MARS
• A second Twofish retreat
• Data-dependent rotations and the pseudorandomness of (idealized) RC6
• Hard-to-analyze ciphers
• Implementation of the five AES finalists on ARM
• Performance of AES candidates on the TriMedia VLIW media processor

The topics listed above make it clear that numerous factors need to be considered in the selection of AES. For example, IPSec changes keys frequently — at the IP packet level. Consequently, key agility is very important.

After the late evening rump session, I got my fix of Thai food and called it a day.

Session 5: Cryptographic analysis and properties II

Session 5 picked up where session 4 had left off the previous day. Three separate papers all demonstrated attacks on reduced rounds of the Rijndael algorithm, thus raising a general concern that Rijndael might not be very secure unless its designers increase the number of rounds it uses.

However, the session’s general consensus was that not enough cryptanalysis has been done for a cryptographic algorithm, which is supposed to withstand attacks well into the coming decades.

Session 6: AES issues panel

NIST may decide to incorporate a combination of the five candidate algorithms into the final AES standard. Miles Smid, the session 6 chair and a former NIST employee, expounded on the unique candidate combinations available for the AES final standard — 31 possible combinations, to be precise (selecting all five, four of five, and so on). The big question is: what will be the winning combination?

Also in session 6, Don Johnson of Certicom spoke about the need for future resiliency — AES’s ability to withstand powerful attacks in the future. Johnson believes that although it’s unfair to pit today’s cryptographic technology against tomorrow’s as-yet-unseen attack technology, the battle must be fought nonetheless. He held up powerful Quantum computing as an example of what future attackers may have at their disposal.

Johnson also wondered what would happen if NIST were to select only one algorithm and it failed. If that happened, Johnson posits that the algorithm’s rounds could be increased to address the issue. Johnson also questioned whether a single-algorithm AES standard would work across different platforms — RISC, smart cards, FPGA, etc. He concluded that at this point there are more questions than answers.

Similarly, Ian Harvey of NCipher shared his thoughts about the implications of multiple algorithms in the standard. He thought that a multiple-algorithm AES standard would help guard against Intellectual Property (IP) attacks. With an IP attack, an individual or institution tries to prove that the AES algorithm, or part of it, was their intellectual property (usually in the form of patents). Such an attack on AES could force the withdrawal of the algorithm and/or products that incorporate it.

Session 7: ASIC evaluations/individual algorithm testing

Although I missed session 7, which covered ASIC evaluations and individual algorithm testing, the session papers and various attendees I spoke to revealed that the results were inconclusive in helping to pick one of the five candidates. Further, the evaluation results could be interpreted in a variety of ways.

Session 8: Algorithm submitter presentations

Session 8 resembled a presidential candidate debate — “your algorithm is insecure for seven rounds,” “my algorithm is the most secure,” and so on. After the participants drew lots to determine order, Rijndael was presented first, followed by Serpent, MARS, RC6, and Twofish.

Rijndael presenter Vincent Rijmen pushed the message of good security, overall good performance, and simplicity of design.

Ross Anderson, who presented for Serpent, extolled that algorithm’s large number of rounds, which makes it very secure. He noted that Serpent met the NIST criteria precisely. He also pointed out that Serpent did very well in hardware and reasonably well with smart cards.

Shai Halevi presented for MARS. MARS has been criticized for a complex design because it seemed as if different IBM groups designed the algorithm’s various parts. Turning that criticism on its head, Halevi pitched the complexity as a unique heterogeneous structure of the algorithm.

RC6 presenter Ron Rivest highlighted the algorithm’s simplicity and security. He claimed that RC6 showed good performance on 32-bit computers and Java. It should be noted that some cryptanalytic attacks revealed specific problems in the algorithm, which might preclude RC6 from winning.

Bruce Schenier, who presented for Twofish, claimed that the algorithm’s performance generally did not suck. Attacks on Twofish have been rebuffed. He then meandered onto a discussion of giant squids; the audience seemed to enjoy the comic relief.

I spoke with Schenier about the relevance of AES for Java developers. He offered this perspective: “Java developers should not care much about the AES conference. The Java Cryptography Architecture permits for very easy plug-in of different algorithms, and most developers will be working at this level anyway.”

Session 8, continued: Audience Q&A and remaining issues of the AES development effort

Of all the questions asked in the audience Q&A, the one that generated the most debate was whether the final AES standard should include multiple candidate algorithms. The motivation behind a multiple algorithm AES standard goes something like this: if the primary algorithm fails, implementations could switch to the backup. However, the conferencees voiced considerable skepticism — after all, since the candidate algorithms hovered around the same security margin, if one algorithm is broken, they all would be. Furthermore, a multiple-algorithm AES would increase implementation difficulty. However, since IP attacks have become critical, the group felt a backup algorithm would be prudent.

Despite all the arguments for multiple algorithms, most attendees were not in favor, while the presenters were divided on the issue.

After the Q&A, Ed Roback of NIST summarized the timeline for the rest of the process. Comments for round 2 are due before May 15, and can be sent to [email protected]. The winner(s) will be announced this summer or fall. If everything goes well, AES will become a federal standard in 2001.

I had 60 minutes to make it to LaGuardia and assumed that I would miss my flight, but New York surprised me again. The cab driver made it to the airport such that I managed to take an earlier flight back to Boston. After two days of straight crypto talk, I was waiting to do my googoo gaagaa talk with my two-year-old son.

Conclusion

Inadequate cryptanalysis attack on the algorithms raises some serious doubts about whether the process has been allowed to run its due course. However, the need to replace DES is urgent. At the conference, the general consensus was to choose a single algorithm as part of the standard, with a potential backup. Further, because the security margin for the candidate algorithms is so close, the cryptographic community feels concerned that the NIST may use an artificial tiebreaker to decide the issue.

Whatever NIST does, it will have a profound impact in commercial standards as well. It’s anticipated that AES, like DES, will be adopted by the private sector. I’ll be keenly watching this summer’s olympics of information scrambling.

Source: www.infoworld.com