AES competition

Starting in the late 90s, the US National Institute of Standards and Technology (NIST) ran a contest to find a block cipher to replace Data Encryption Standard, DES. The winning cipher, previously known as Rijndael became the Advanced Encryption Standard, AES.

The entire process was completely open; even their requirements document was published and comment or criticism invited before a final version was written, and all of the later work toward the choice of a standard was public as well. The whole process was widely praised by cryptographers as a fine example of taking Kerckhoffs' Principle into account. This was in sharp contrast to some of the criticisms that had been made of the secrecy in the DES standardisation process which was run by NIST's ancestor, the National Bureau of Standards.

The final requirements specified a block cipher with 128-bit block size and support for 128, 192 or 256-bit key sizes. Evaluation criteria included security, performance on a range of platforms from 8-bit CPUs (e.g. in smart cards) up, and ease of implementation in both software and hardware.

Fifteen submissions meeting basic criteria were received, not just from the US but from many other countries as well. All of the entries were iterated block ciphers; in Shannon's terms all were product ciphers. Most used an SP network or Feistel structure, or variations of those. Several had proofs of resistance to various attacks.

In alphabetical order, the fifteen first round candidates were:

CAST-256, CRYPTON, DEAL, DFC, E2, FROG, Hasty Pudding, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, and Twofish

All are described below.

NIST succeeded in rounding up a fine group of suspects; many of the world's best-known cryptographers participated in various design teams and others contributed to analysis of candidates. We provide a table listing some of the major players involved.

After much analysis and testing, and two conferences, the field was narrowed to five finalists — Twofish, MARS, Serpent, RC6, and Rjindael. After another year of analysis and testing focused on the finalists, and another conference with all of the finalist teams giving presentations, they chose a winner. In October 2002, Rijndael was chosen to become the Advanced Encryption Standard or AES. See external links for the official standard.

The contest was open and international and extensive work was done on testing and comparing the various candidates. To facilitate this, NIST defined some standard interfaces which everybody used. For almost all candidate ciphers, implementations with these interfaces are readily available; see external links. Many, though not all, of these ciphers have open licenses. This means that anyone implementing AES has the option of adding other ciphers at minimum cost, in particular the other three finalists with open licenses — Twofish, MARS, and Serpent. This gives a cheap insurance policy against the (presumably remote) chance of someone finding a good attack on AES.

Because of the birthday attack, a cryptographic hash needs to provide output of 2n bits to resist attacks as well as a cipher with an n-bit key. NIST has therefore issued standards for the SHA-2 family of hashes — SHA-256, SHA-384 and SHA-512 to match the strength of AES, plus SHA-224 to match the 112-bit strength of Triple DES. However, those hashes are all derived from SHA and weaknesses have been shown in that, so in 2008 NIST started a contest similar to the AES contest to design an Advanced Hash Standard which can (if it proves necessary) replace SHA-2 as AES replaced DES.

AES

The Advanced Encryption Standard or AES is the algorithm formerly known as Rijndael (pronounced approximately "rhine doll"). It was designed by two Belgians, Joan Daemen and Vincent Rijmen.

It is an iterated block cipher, but not a Feistel cipher; the overall structure is an SP network. Nonlinearity is obtained by mixing operations from different algebraic groups. There are four operations.

Two give confusion:

AddRoundKey: bitwise XOR of 128-bit state and 128-bit round key

SubBytes: run individual bytes through an 8*8 S-box

The other two give diffusion, treating the 128-bit block as a four by four matrix of bytes:

ShiftRows: cyclicly shift each row by a fixed amount

MixColumns: treat each column as a polynomial over the Galois field GF(2⁸); multiply it by one constant polynomial modulo another

It encrypts 128-bit blocks with a 128, 192 or 256-bit key. The number of rounds varies with key size: 10 for 128-bit keys, 12 for 192-bit keys and 14 for 256-bit keys. The numbers of rounds were chosen based on an analysis showing that they are enough to give resistance to linear cryptanalysis and differential cryptanalysis.

The cipher is freely available for any use. See external links for much more information.

Other finalists

There were originally fifteen AES candidates, but that was narrowed to five finalists for the second round of analysis. This section covers the four ciphers that made it into the finals but did not win.

Twofish

Twofish was an AES finalist cipher from Bruce Schneier's company Counterpane. Except for the name, it has little relationship to Blowfish; Twofish was a new design.

Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is a 16-round Feistel cipher using four key-dependent 8*8 S-boxes.

The cipher is freely available for any use. It has a home page; see external links.

It has a successor named "Threefish", used in the Skein hash algorithm, a candidate in the Advanced Hash Standard contest.

Serpent

Serpent was an AES finalist cipher from an international team of well-known researchers — Ross Anderson (UK), Eli Biham (Israel), and Lars Knudsen (Norway). Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

Serpent is an SP network with 32 rounds. It uses eight 4 by 4 S-boxes, but unlike other ciphers it does not use them all in each round. Instead each round uses eight copies of the same S-box, so that 32-bit computer instructions can do eight 4-bit operations in parallel. Each of the eight S-boxes is used in four different rounds,

The cipher is freely available for any use. It has a home page; see external links.

RC6

RC6 was an AES finalist cipher from a team led by Ron Rivest. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

Like RC5, RC6 made extensive use of data-dependent rotations. RSA Laboratories have a page describing both ciphers; see external links. .

RC6 is the only one of the five finalists which does not have a completely open license; it is still proprietary to RSA Laboratories.

MARS

MARS was an AES finalist cipher from IBM. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

It uses a variant of the Feistel structure which they call a "type 3 Feistel network"; the 128-bit block is treated as four 32-bit sub-blocks; each round uses one sub-block as input and modifies all of the other three sub-blocks. Like RC6, it uses data-dependent rotations. One 9*32 S-box is used; for some operations it is treated as two 8*32 S-boxes.

The cipher is now freely available. It has a home page; see external links.

Unconventional AES candidates

This section covers two AES candidate ciphers that introduced new design ideas. Neither was chosen for consideration in the final round.

Hasty Pudding

The Hasty Pudding cipher or HPC, from Rich Schroeppel was, in some ways, the most interesting of the AES candidates. It did not make it into the finals.

Hasty Pudding is a variable size block cipher; blocks can be any size the application requires. It therefore might be ideal for things like encrypting disk blocks; see large block ciphers. Also, quoting the home page "Arbitrary sets, such as dates, or the printable subset of ascii, or the 20-bit primes, can be encrypted to themselves." Key size is also variable; any integer number of bits. For AES use, the block size would be fixed at 128 bits and key size at 128, 192 or 256 bits.

Hasty Pudding is also a tweakable block cipher, though it was designed before that term came into use. What is now called the "tweak" is called "spice" in Hasty Pudding.

The cipher is freely available for any use. It has a home page; see external links.

FROG

FROG was an AES candidate cipher; it did not make it into the finals.

Like Hasty Pudding, FROG is a variable size block cipher and a rather unorthodox design. It supports block sizes from 8 to 128 bytes and key sizes from 5 to 125 bytes. For AES use, the block size would be fixed at 128 bits and key size at 128, 192 or 256 bits.

FROG introduced a novel design principle. Most block ciphers use round keys as data, thereby making each round different, but each round uses exactly the same sequence of operations. FROG uses data derived from the primary key as a program for an interpreter, so that each round can use a different sequence of operations. Eight rounds are used. Encryption and decryption are fast, but the key schedule is rather slow because it has to build a program for the interpreter.

While it was generally agreed that FROG was an interesting bit of work, it was found to have some weaknesses .

Other AES candidates

This section covers the other ciphers that were proposed as AES candidates but not chosen for consideration in the final round.

CAST 256

CAST-256 was an AES candidate cipher from a Canadian team; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

It is a Feistel-like cipher extended to four 32-bit sub-blocks instead of the two sub-blocks used in CAST-128 for 64-bit blocks. In the terms used by the MARS team, it is a "type one Feistel network"; each round takes one 32-bit sub-block as input and alters one 32-bit sub-block; 48 rounds are used. The F function and S-boxes are from CAST-128.

It is freely available for any use. There is an RFC describing it; see external links.

CRYPTON

CRYPTON was an AES candidate cipher from a Korean team; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

CRYPTON uses an SP network with 12 rounds, does byte-level substitutions, and for some operations treats the 128-bit text as a four-by-four array of bytes. Overall, the design is rather similar to AES though some of the operations are different.

DEAL

DEAL, the Data Encryption Algorithm with Larger blocks was an AES candidate cipher; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

DEAL is a Feistel cipher using DES as the F function. Six rounds were used with a 128-bit or 192-bit key and 8 rounds with a 256-bit key. The idea was originally proposed by Lars Knudsen, but the AES submission was from Richard Outerbridge. Knudsen was a member of the Serpent team for AES.

DEAL has approximately the overheads of Triple DES, making it too slow to be a competitive candidate for AES. There were also some cryptanalytic results against the cipher.

DFC

DFC or De-correlated Fast Cipher was an AES candidate cipher from a French team; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is a six-round Feistel cipher using a single 6 by 32 S-box.

This cipher was based on Serge Vaudenay's theoretical work on decorrelation theory. That theory gives methods of constructing ciphers which are provably immune to differential cryptanalysis, linear cryptanalysis, and any other attacks that meet some fairly broad assumptions.

However, some attacks on DFC were found by going outside those assumptions, timing attacks on some implementations and a more general attack using a variant of differential analysis .

E2

E2 was an AES candidate cipher from Nippon Telephone and Telegraph; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is a 12-round Feistel network using a single 8 by 8 S-box.

There has been no published cryptanalysis of the full E2, but there is an attack on a reduced-round version .

Camellia shares some design features with E2 and has largely replaced it.

LOKI97

LOKI97 was an AES candidate cipher from an Australian group; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. LOKI97 is one of a whole family of LOKI ciphers designed by the same group. It is a 16-round Feistel cipher with an F function that is basically two rounds of an SP network. This contrasts with DES where the F function is a single SP round.

The cipher is freely available for any use. It has a home page; see external links.

MAGENTA

MAGENTA or Multifunctional Algorithm for General-purpose Encryption and Network Telecommunication Applications was Deutsche Telekom's entry in the AES competition. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is a Feistel cipher with six or eight rounds.

MAGENTA is often cited as an example of Kerckhoffs' Principle, a demonstration of why unpublished and therefore unanalysed ciphers cannot be trusted. Of the 15 AES candidates, 14 were made public before the first AES conference. The MAGENTA team were the one exception; they made nothing public until their conference presentation. That presentation was given one morning, to an audience that included many of the world's top cryptographers. Some saw flaws, and there was intense discussion over lunch. By that evening, a draft paper on breaking the cipher was circulating and the final version was presented at the second AES conference. The attackers included members of both the Twofish and Serpent teams, plus others.

Safer+

Safer+ was an AES candidate cipher; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is an SP network using two S-boxes. 8 rounds are used with a 128-bit key, 12 for a 192-bit key, and 15 for a 256-bit key.

Safer+ is one of a family of SAFER or Secure and Fast Encryption Routine ciphers designed by James Massey and co-workers for Cylink Corporation. All of these ciphers are unpatented and freely available for any use. There have been published attacks on some of them, but later versions have modifications to block those attacks.