The History of AES

Introduction

THE INTERNET has completely changed the way we work, do business and communicate. In less than a decade, use of the Internet has grown and developed beyond all expectations. Development continue at a rapid pace, most recently encompassing the burgeoning world of mobile phones and m-commerce. As the Internet became the most ubiquitous form of exchanging information and data, the need for Internet security prompted research in a wide array of strong cryptosystems.

While just a few decades ago the science of cryptography¹ was an esoteric endeavor employed primarily by governments to protect state and military secrets, today millions of people use cryptography, often without knowing it. For example, people who use automated teller machines use cryptography to encode the secret PINs required by the machines. The numbers are encrypted before being sent to a computer that makes sure the number matches the card.

Others use information encryption when they make a purchase over the Internet. Their credit card numbers are encrypted when they place an order.

The Data Encryption Standard

The National Bureau of Standards (NBS) was given the responsibility for developing Federal Information Processing Standards (FIPS). The Institute for Computer Sciences and Technology (ICST) has the responsibility within the NBS to recommend and coordinate standards and guidelines for improved computer utilization and information processing within the Federal Government, as well as for developing the technology needed to support these standards activities. In 1973 NBS initiated a computer security program that included the development of a government standard for computer data encryption. Since Federal standards impact on the private sector, NBS solicited the interest and cooperation of industry and user communities in this work.

In May 1973, and again in August 1974, NBS published a notice in the Federal Register inviting the submission of data encryption algorithms and techniques that might be considered for use in a data encryption standard. International Business Machines Corporation (IBM) created the algorithm named the Data Encryption Standard (DES) that satisfied the requirements of NBS and made the specifications of the algorithm available to NBS for publication as a Federal Information Processing Standard (FIPS). At the request of NBS, the National Security Agency (NSA) also conducted an exhaustive technical analysis of the DES and confirmed the soundness of the DES's encryption principle and its suitability to protect unclassified Federal data. In January 1977 the algorithm was published as a Federal standard, FIPS PUB 46.

The DES algorithm is a recirculating², 64-bit, block product cipher³ whose security is based on a secret key. DES keys are 64-bit binary vectors consisting of 56 independent information bits and eight parity bits. (Since 56 independent bits are used in a DES key, 2⁵⁶ such tests are required to guarantee finding the secret to a particular key. The expected number of tests to recover the correct key is 2⁵⁵. At one microsecond per test 1,142 years would be required to discover the secret to the encryption key.)

When DES was reaffirmed by NBS in 1993, ending December 1998, the following statement was included in the standard:

"At the next review (1998), the algorithm specified in this standard will be over twenty years old. NIST will consider alternatives that offer a higher level of security. One of these alternatives may be proposed as a replacement standard at the 1998 review."

Advanced Encryption Standard (AES)

In the January 1997 edition of the Federal Register, the U.S. National Institute of Standards and Technology (NIST), an agency of the Department of Commerce, published a request for information regarding the creation of a new Advanced Encryption Standard (AES) for non-classified government documents. It is intended that the AES will specify an unclassified, publicly disclosed encryption algorithm capable of protecting sensitive government information well into the next century. If more than one suitable candidate is identified which provides significantly better advantages in a specific application(s), NIST would consider recommending more than one algorithm.

Using the information gathered from the 1997 call for information, in the same year NIST issued a call for algorithms to the general industry and the cryptographic community. The call stipulated that the AES would specify an unclassified, publicly disclosed encryption algorithm(s), available royalty-free, worldwide. In addition, the algorithm(s) must implement symmetric key⁴ cryptography as a block cipher and (at a minimum) support block sizes of 128-bits and key sizes of 128-, 192-, and 256-bits.

THE PROPOSED DRAFT MINIMUM ACCEPTABILITY REQUIREMENTS AND EVALUATION CRITERIA

The draft minimum acceptability requirements and evaluation criteria are:

• AES shall be publicly defined.
• AES shall be a symmetric block cipher.
• AES shall be designed so that the key length may be increased as needed.
• AES shall be implementable in both hardware and software.
• AES shall either be a) freely available or b) available under terms consistent with the American National Standards Institute (ANSI) patent policy.

Algorithms which meet the above requirements will be judged based on the following factors:

1. security (i.e., the effort required to cryptanalyze),
2. computational efficiency,
3. memory requirements,
4. hardware and software suitability,
5. simplicity,
6. flexibility, and
7. licensing requirements.

On August 20, 1998, NIST announced a group of fifteen finalists entries, and from that group five algorithms were selected for further analysis. NIST evaluated the candidate algorithms and received invaluable assistance from cryptographers at computer security companies and universities around the world. Good security was the primary quality required of the winning formula, but factors such as speed and versatility across a variety of computer platforms also were considered. In other words, the algorithms must be able to run securely and efficiently on large computers, desktop computers and even small devices such as smart cards.

From left to right: Ross Anderson (Serpent), Ron Rivest (RC6), Vincent Rijmen (Rijndael), Bruce Schneier (Twofish), and Shai Halevi (MARS) photo courtesy of Markus Dichtl

The five AES finalist candidate algorithms are:

• MARS (submitted by IBM Corp.)
• RC6 (submitted by RSA Laboratories)
• Rijndael (submitted by Joan Daemen and Vincent Rijmen)
• Serpent (submitted by Ross Anderson, Eli Biham, Lars Knudsen)
• Twofish (submitted by Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson)

After numerous conferences and rigorous testing NIST announced on October 2 2000, that it had selected Rijndael (pronounced Rhine-doll) to be the proposed AES. The Rijndael developers are Belgian cryptographers Joan Daemen (pronounced Yo'-ahn Dah'-mun) of Proton World International and Vincent Rijmen (pronounced Rye'-mun) of Katholieke Universiteit Leuven. Both are highly regarded experts within the international cryptographic community.

Shortly after the announcement a draft Federal Information Processing Standard (FIPS) for the AES was published for public review and comment. Following the comment period (of at least three months), the standard will be revised by NIST, as appropriate, in response to those comments. A review, approval, and promulgation process will then follow. If all steps of the AES development process proceed as planned, it is anticipated that the standard will be completed by the summer of 2001.

The following comments are from NIST's AES homepage:

"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. Its key setup time is excellent, and its key agility is good. Rijndael's very low memory requirements make it very well suited for restricted-space environments, in which it also demonstrates excellent performance. Rijndael's operations are among the easiest to defend against power and timing attacks.

Additionally, it appears that some defense can be provided against such attacks without significantly impacting Rijndael's performance. Rijndael is designed with some flexibility in terms of block and key sizes, and the algorithm can accommodate alterations in the number of rounds, although these features would require further study and are not being considered at this time. Finally, Rijndael's internal round structure appears to have good potential to benefit from instruction-level parallelism."

For more information about AES:

• AES Homepage at csrc.nist.gov/encryption/aes provides detailed information including examinations between the five finalist algorithms.
  
  
• See Secure4Net's AES Information & Links page