Security, efficiency are key to AES

Advanced Encryption Standard supplants the Data Encryption Standard and Triple-DES to strengthen security and boost efficiency.

Adopted in 1977 as Federal Information Processing Standard (FIPS) Publication 46, the aging DES encrypts data in 64-bit blocks using a 56-bit key. In 1999, the National Institute of Standards and Technology (NIST) issued a new standard, FIPS PUB 46-3, calling for the use of Triple-DES except for legacy systems. In essence, Triple-DES involves repeating the DES algorithm three times on the plaintext of using two or three different keys (112 bits or 168 bits) to produce the ciphertext.

The principal drawback of Triple-DES is that the algorithm is relatively sluggish in software. The original DES was designed for mid-1970s hardware implementation and does not produce efficient software code. Triple-DES, which has three times as many rounds of encryption as DES, is correspondingly slower. Another weakness is that DES and Triple-DES use a 64-bit block length. To gain efficiency and security, a larger block length is desirable.

Because of these drawbacks, Triple-DES isn’t a reasonable candidate for long-term use. In 2001, NIST issued AES, known as FIPS 197. AES has a block length of 128 bits and supports key lengths of 128, 192 and 256 bits.

The version of AES with a key length of 128 bits is likely to be the one most commonly implemented; this length is sufficient to provide security and requires less processing time than a longer key length. Thus far there doesn’t appear to be any critical weaknesses in either AES or Triple-DES, so the level of security is directly proportional to the key length.

The input to the encryption and decryption algorithms is a single 128-bit block. This block is arranged in a 4-by-4-byte matrix called the state array, which is modified at each round of encryption or decryption. After the final stage, the state array is converted back to a linear string of 128 bits. Similarly, the 128-bit key is depicted as a square matrix of bytes. This key is expanded into 10 individual keys – 10 rounds of processing produce the result.

A typical round consists of four stages. The ByteSub stage uses a table, referred to as an S-box, to perform a byte-by-byte substitution of the block. That is, each input byte is mapped into a unique output byte.

In the RowShift stage, the first row of the state array is not altered. For the second row, a 1-byte circular left shift is performed. For the third row, a 2-byte circular left shift is performed. For the fourth row, a 3-byte circular left shift is performed.

The MixColumns stage is a substitution that alters each byte in a column as a function of all the bytes in the column.

For the AddRoundKey stage, a 4-by4-byte portion of the expanded key is used; each byte of the expanded key is combined with the corresponding byte of the state array using the exclusive-OR function.

The structure of AES is quite simple. For both encryption and decryption, the cipher begins with an Add Round Key stage, followed by nine rounds that each include all four stages, followed by a 10th round of three stages. The last round does not use the MixColumns stage.

Only the Add Round Key stage uses the key. For this reason, the cipher begins and ends with an Add Round Key stage. Any other stage, applied at the beginning or end, is reversible without knowledge of the key and so would add no security.

The cipher provides alternating operations of XOR encryption (Add Round Key) of a block, followed by scrambling of the block in the other three stages, followed by XOR encryption, and so on. This scheme is both efficient and highly secure.

As with most block ciphers, the decryption algorithm uses the expanded key in reverse order. However, the decryption algorithm is not identical to the encryption algorithm.

Current implementations of AES are in software, but you can expect to see firmware/hardware implementations as the encryption scheme becomes more widely used.

Stallings is a network consultant and author. His most recent book is Cryptography and Network Security. He can be reached at ws@shore.net.