Dr. Dobb's Journal December 1998

The AES Candidates

NIST received 15 algorithms in response to its request for AES candidates. They came from companies, universities, and individuals. Ten of the submissions came from outside the U.S.; all but one submission have non-U.S. nationals as at least one coauthor. Three submissions have been broken already, two before the First AES Conference and one during.

Each algorithm has a 128-bit block size, and must support key lengths of 128-, 192, and 256-bits. (Of course, you can always support different key lengths simply by fixing some key bits.) The algorithms will be judged on security (of course), but also speed, flexibility, and simplicity. Speed is speed of encryption and speed of key setup, and is judged on different platforms ranging from high-end microprocessors to 8-bit smart cards to hardware. Flexibility includes suitability to different encryption tasks: encrypting large blocks, changing keys rapidly, fitting into low-powered embedded processors, and the like. Simplicity is the design -- simple enough to facilitate analysis.

Here's a list of the submissions, with a few editorial comments.

• CAST-256. CAST is a family of ciphers designed by Carlisle Adams; as far as I know, none have been broken. This family member (256) is similar to the others. It has a conservative number of rounds, and is slower than some of the other candidates. And the 4 KB of required tables make it difficult to implement in some applications.
• LOKI-97. Like LOKI-89 and LOKI-91, LOKI-97 fell to a differential attack.
• Frog. The algorithm is slow, key setup glacial, and there are many cryptographic problems with the algorithm. A first break was published before the First AES Candidate Conference, and some are extending the attack.
• Mars. IBM gave the world DES, and Mars is its submission to AES. The algorithm is very fast on the Pentium Pro/II, but has some large tables. Still, the pedigree and impressive design document make this a strong candidate despite its "kitchen sink" appearance.
• Magenta. Where do I start? There are so many security problems with this algorithm that it was broken during the question session at the First AES Candidate Conference.
• RC6. This submission, by Ron Rivest and others at RSA Data Security Inc., builds on the success of RC5. It's the fastest submission on the Pentium Pro/II (22 percent faster than Twofish), but its performance drops by almost a factor of three on Pentium machines. It's slow on smart cards, and doesn't fit in smart cards with low RAM. An excellent candidate all the same, with a comprehensive analysis document.
• Decorrelated Fast Cipher (DFC). Serge Vaudenay is an excellent cryptographer, and this is an interesting submission. It uses some radical techniques to provide security in surprisingly few rounds. Performance is mediocre, though; 64-bit multiplies are expensive on most platforms. I've heard this called a "research cipher."
• Serpent. It's pretty hard to find anything wrong with this submission. It's not the fastest, but that's only because of its overly conservative design. It works on low-memory smart cards and 32-bit CPUs. And its design team includes two of the most impressive names in cryptanalysis this decade -- Eli Biham and Lars Knudsen.
• E2. This is NTT's submission, another Feistel network. The design document is impressive, and I like this cipher a lot. It's not as fast as some others, but is likely to be a strong candidate.
• Rijndael. A variant of Square, the chief drawback to this cipher is the difficulty Americans have pronouncing it. Square is a strong algorithm, and Rijndael seems to be a strong variant of it. The designers, Vincent Rijmen and Joan Daemen, know what they are doing.
• DEAL. This is a variant of triple-DES, designed by Lars Knudsen. There has been some cryptanalysis, but it looks strong. I don't know how credible the idea is for AES, though. Triple-DES already exists as an alternative for those not interested in migrating to AES.
• Hasty Pudding Cipher (HPC). Take everything you can think of, throw it in a cipher, shake well, then add some attitude. "Bizarre" is all that I can say.
• Crypton. Like Rijndael, it is a variant of the Square algorithm. Like Rijndael, it is efficient on a variety of platforms. Unlike Rijndael, it was not developed by the authors of Square, but by a Korean professor. Crypton has some clever design elements, but unfortunately the author is not playing by NIST's rules; he's modifying the key schedule after the deadline, changing the design, and so on. I fear that the language and culture barrier will prevent this algorithm from going as far as it could.
• Twofish. Twofish was designed by Bruce Schneier, John Kelsey, Chris Hall, and Niels Ferguson of Counterpane Systems, David Wagner of University of California at Berkeley, and Doug Whiting of Hi/fn Inc. I've already said enough about it.
• SAFER+. A member of the SAFER family, designed in part by James Massey, this algorithm was submitted by Cylink. It was designed for 8-bit microprocessors, and is very slow on 32-bit machines. The 256-bit key version is even slower than triple-DES.

Noticeably absent is a submission from the NSA. The word is that the NSA had a submission ready, but that NIST asked them not to submit. NIST would prefer that the NSA help them as an impartial evaluator, not as a combatant. (Skipjack is not an AES candidate because it does not meet NIST's submission criteria: Both the key length and the block length are too short.)

At this writing, 12 AES candidates remain unbroken. This could easily change by the time you read this. Aside from dedicated attacks against the different algorithms, there is a new development in the cryptanalysis world. Eli Biham, Alix Biryukov, and Adi Shamir invented something called "impossible cryptanalysis," which they have used profitably against Skipjack. Since none of the AES submissions have been designed with impossible cryptanalysis in mind (with the possible exception of Biham's own Serpent), it will be interesting to see how they fare.

The NIST web site (http://www.nist.gov/aes/) has discussion groups on the different algorithms, and links to the home pages of the various candidates.

-- B.S.