AES: Cryptography advances into the future

Find out the latest steps towards the development of the Advanced Encryption Standard, the next-generation standard for private-key cryptography

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.

Five finalist candidates
Cryptographic algorithmSubmitterMain proMain con
MARS IBM High security margin Complex implementation 
RC6 RSA Laboratories Very simple Low security margin 
Rijndael Joan Daemen, Vincent Rijmen Simple design, good overall Insufficient rounds 
Serpent Ross Anderson, Eli Biham, Lars Knudsen High security margin Complex design and analysis, poor performance 
Twofish Bruce Schneier and others at Counterpane Systems Reasonable performance, security margin Complex design 

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.

1 2 Page 1
Page 1 of 2