[Next] [Up] [Previous] [Index]

Towards the 128-bit Era: AES Candidates

Improvements in the speed and power of microprocessor chips have meant that the Data Encryption Standard with its 56-bit key is subject to brute-force attacks that can be carried out by organizations of moderate size.

Although some branches of the Government of the United States, including its Chief Executive, have been pursuing policies such as export restrictions and the "Clipper chip" initiative, based on perceived dangers of the spread of strong encryption, the National Institute of Standards and Technology, another branch of the U. S. Government, has sought public submissions of an improved block cipher which would serve the specific purpose of protecting the unclassified communications of the U. S. Government, but which would also, no doubt, serve the public sector as well.

The block cipher that is accepted will be called the AES, for Advanced Encryption Standard.

Since this was written, on October 2, 2000, the cipher that will serve as the Advanced Encryption Standard has been announced, and that cipher is Rijndael, designed by Vincent Rijmen and Joan Daemen.

Because block cipher modes give block ciphers the flexibility of also serving in applications which can make use of stream ciphers, a block cipher was sought. A block length of 128 bits, making dictionary attacks more difficult, is specified, and key lengths of 128, 192, and 256 bits are to be allowed for in the designs submitted.

A larger block length also increases the speed of encipherment, by allowing more text to be enciphered at once. Where a 56-bit key does not provide enough security at present, it is possible to use Triple-DES (enciphering in DES three times over, using either two or three different keys - and with the middle encipherment done in deciphering mode for compatibility reasons) and therefore one of the goals to be met by any submitted cipher is that it be faster than Triple DES.

An idea that might occur upon first hearing about the AES effort: could a simple construction like the following, operating at speeds only slightly slower than those of single DES, provide adequate strength:

                 |
                XOR <---
  _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _
 |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
         |               |
         |-------------> +
         + <-------------|
         |               |
    -----------     -----------
    |   DES   |     |   DES   |
    -----------     -----------
         |               |
         |-------------> +
         + <-------------|
         |               |
  _ _ _ _|_ _ _ _ _ _ _ _|_ _ _ _
 |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
                 |        
                XOR <---
                 |

or, in graphical form:

one might ask. However, while it seems that the series of byte substitutions, followed by a Pseudo-Hadamard Transform, mixes together the two halves of the block well enough, attacks are possible against this type of construction that make it not much stronger than normal DES, at least in theory. If the Pseudo-Hadamard Transform, however, is replaced by something better, such as the mask-driven bit swap used in the cipher ICE, where a mask selects bits to be swapped between a pair of words, and we further enhance it by using a 4 of 8 code to ensure each byte includes both swapped and non-swapped bits, one might have something usable. The additional XOR whitening is applicable, if otherwise all sixteen bytes go through the same byte substitution.

With a better initial mixing step, and a willingness to go to double-DES speeds, though, this approach could lead to something adequate.

As block ciphers like Blowfish demonstrate, it is possible to do better than DES at faster speeds, and DES is designed for hardware implementation, and is unnecessarily slow in software. Thus, something that is designed for fast software encryption, with the required security, will be more optimal if it comes from a fresh design process.

Also, it should be noted that this illustration of how DES could be used as the basis of a 128-bit block cipher is not terribly original with me; whitening has been proposed many times before, and the use of some sort of mixing before and after using DES to increase the block size is part of Terry Ritter's Fenced DES design.

This design is not perfect: since the expression for one of the outputs of a PHT has a factor of two in it, one can, using chosen plaintexts where only the least significant byte of one particular half is varied, uncover some facts about the S-boxes used, for example. This, among other weaknesses, was noted by Bryan G. Olson. Since keeping one block the same still changes the complete output, because the other DES encipherment is different, not 256 chosen plaintexts, but a larger number, are required, but an attack is still possible.

All the AES candidate algorithms have been disclosed. I have written up descriptions of some of them in my own words, with diagrams, that may be helpful to some in understanding the algorithms. In some cases, my descriptions are not complete; for example, in several cases I omit a description of the key schedule. It may also be noted that links to the descriptions of the algorithms are available at the Block Cipher Lounge as well as at the official AES site.

Since this page was originally developed, on August 9, 1999, five algorithms were announced as those chosen for consideration in Round 2 of the AES selection process. All five of those algorithms are among those described here, and they are indicated in the list below:



[Next] [Up] [Previous] [Index]

Next
Chapter Start
Skip to Next Section
Skip to Next Chapter
Table of Contents
Main Page