History has shown that it is always necessary for security to evolve to meet the demands of new technology. Moore's Law may work wonders for computing horsepower, but it creates nightmares for security specialists. In recent years, the DES (Data Encryption Standard) has become vulnerable to attack by the raw computing horsepower that even a garage hobbyist possesses. Most security applications now use a method called 3DES (triple-DES) to extend the cipher strength of DES.

The NIST (National Institute of Standards and Technology) realizes that DES may no longer be appropriate for some high-security applications. In response to this need for better cipher strength, NIST commissioned a 1997 study of the AES (Advanced Encryption Standard). The final selection of this study was an application of the Rijndael (pronounced rhine-doll) algorithm. Like DES, the AES acts as a block cipher, but with much larger key lengths and improved cipher strength.

What is the AES?

The AES algorithm converts a block of 128 bits (referred to as plain text) to a 128-bit block of encrypted data (referred to as cipher text). In the sense that they are both block ciphers, the AES algorithm is just like the DES algorithm (in standard ECB, or Electronic Code Book, mode).

The algorithm uses one of three cipher key strengths: a 128-, 192-, or 256-bit encryption key. Each encryption-key size causes the algorithm to behave slightly differently. So, the increasing key sizes not only offer a larger number of bits with which you can scramble the data, but also increase the complexity of the cipher algorithm.

The AES algorithm repeats its core a number of times, depending on the encryption-key size. Just like DES, the AES algorithm refers to these loop repetitions as "rounds," and the cipher must also complete preround and postround operations. However, unlike DES, the AES algorithm is not truly symmetric. The operations for the reverse cipher are the inverse of the forward-cipher operations, and they are performed in a different order.

The following terms are commonly used to describe the AES algorithm. It is a good idea to become familiar with these terms before reading additional literature or the FIPS (Federal Information Processing Standards) specification (Reference 1).

• A round is an iteration of the main part of the AES algorithms. AES algorithms contain a variable number of rounds, depending on the key size.
• Cipher text is the encrypted data.
• Plain text is the original unencrypted data.
• The AES algorithm expands the 128-, 192-, or 256-bit key into a number of 32-bit values. Each round receives a new 128-bit key. The total size of the key schedule depends on the key size.
• An S-box, or substitution box, is a look-up table.

Expanding into a key schedule

The AES algorithm expands the initial encryption key into a table of 32-bit values. The algorithm then subdivides the table into groups of four 32-bit values. Each round of the AES algorithm uses a key made up of four 32-bit values from the key schedule.

The total number of scheduled keys, and thus the total table size, depends on the initial key size. A scheduled key consists of four 32-bit values for each round of the algorithm and one final set of four 32-bit values. For instance, with a 128-bit key, there are 10 rounds, so the number of 32-bit values generated during the key expansion is 44. Likewise, the table size for a 192-bit key is 52 32-bit values long, and the size for a 256-bit key is 60 32-bit values long.

Listing 1 shows the algorithm for key expansion. Explanations of some of the terms in the pseudocode are as follows:

• the "key" is stored as an array of bytes and contains the encryption key;
• "key_size" is the size of the key array divided by four (that is, the number of 32-bit words that the key array forms);
• "w" is the final key-schedule array and is stored as a number of 32-bit values;
• "i" is an index variable;
• "temp" is a 32-bit temporary variable;
• "Nr" is the number of rounds, which depends on the key size;
• "word()" forms a word out of four bytes;
• "SubWord()" is a byte-by-byte substitution of a 32-bit word using the S-box look-up table; and
• "Rcon[i]" is a look-up- table value that the word formed from the byte-wide values, {2^i–1, 0, 0, 0}, gives. However, there is a slight trick to this calculation. The key-expansion algorithm calculates the first byte as an exponential within a "Galois field." Click here to find out more about the Galois field. The easiest way to implement this table is to use the example table values in the AES standard.

The AES encryption algorithm

The AES algorithm converts 128 bits of plain text to 128 bits of cipher text. The main encryption processing first moves the plain text (best thought of as an array of 16 bytes) to a 4×4-byte matrix called the "state." Figure 1 shows the transformation from the plain-text array into the state matrix. Further suboperations of the AES algorithm happen on the state matrix. When all processing is done, the final operation moves the state matrix to a cipher-text array with the same byte ordering that initial cipher operation used to move the plain-text array to the state matrix.

Listing 2 displays pseudocode for the AES cipher algorithm. As mentioned before, the number of rounds (Nr) depends on the key size. For a 128-bit key, Nr=10; for a 192-bit key, Nr=12; and for a 256-bit key, Nr=14. Note that the cipher contains four main suboperations: AddRoundKey(), SubBytes(), ShiftRows(), and MixColumns().

AddRoundKey() performs an exclusive-OR of each column with a 32-bit value from the key schedule for that round. As previously mentioned, the key schedule divides into groups of four 32-bit values, and, likewise, the state matrix has four columns. The column number c acts as an offset into the key schedule for the specified round to address the correct 32-bit key. For each column c,

{S_0,c, S_1,c, S_2,c, S_3,c}={S_0,c, S_1,c, S_2,c, S_3,c} xor w[round*4+c]

SubBytes() substitutes each byte in the state matrix with a new value. It splits each byte in the state matrix into two 4-bit nibbles. SubBytes() uses each nibble to address a 2-D 16×16-byte look-up table, or S-box. The high nibble addresses the row, and the low nibble addresses the column of the S-box such that S'=S-box[S_high][S_low].

ShiftRows() switches the order of the column entries for a single row in the state matrix. The ShiftRows() operation acts independently upon each row. Depending on the row number, the column order shifts circularly a number of positions. This operation does not change row 0. Row 1 circularly shifts to the left by one column. Likewise, row 2 shifts to the left by 2, and row 3 shifts to the left by 3. Figure 2 graphically depicts the operation.

MixColumns() mixes the values for any given column with other values from the same column. The MixColumns() operation is the most complex aspect of the AES algorithm. However, it is comprehensible when you twist your brain the right way. MixColumns() uses the concept of multiplying two numbers in a Galois field, GF(2⁸). Operating on a single column at a time, MixColumns() multiplies the column (in a Galois field) by a 4×4-byte matrix. Figure 3 shows the operation.

The result of the multiplication in the figure is a set of four equations that can be quickly calculated using shifts and exclusive-OR operations to determine the new values for each column c in the state matrix:

S'_0,c=({02}·S_0,c) xor ({03}·S_1,c) xor S_2,c xor S_3,c
S'_1,c=S_0,c xor ({02}·S_1,c) xor ({03}·S_2,c) xor S_3,c
S'_2,c=S_0,c xor S_1,c xor ({02}·S_2,c) xor ({03}·S_3,c)
S'_3,c=({03}·S_0,c) xor S_1,c xor S_2,c xor ({02}·S_3,c)

The AES inverse cipher

The inverse cipher converts the cipher text that the AES algorithm produces to the original plain text. The cipher and deciphering algorithms share the same key schedule but use the scheduled keys in opposite order.

Listing 3 contains pseudocode for the inverse-cipher algorithm. The deciphering algorithm starts and ends with the same moves between the I/O array and the state matrix that the cipher algorithm used. Also, the deciphering algorithm performs the same number of rounds as did the cipher algorithm.

Note that the new suboperations start with the prefix "Inv." These operations are simply the inverse of the cipher-algorithm suboperations.

InvShiftRows() simply moves the column entries in a single row back to where they were before the ShiftRows() operation applied its row shift. Figure 4 shows a graphical representation of the reordering of the column entries in each row. As before, row 0 is unaffected. Row 1 circularly shifts one column to the right, row 2 shifts two positions, and row 3 shifts three positions.

The InvSubBytes() operation returns the inverse of the SubBytes() operation for each byte entry in the state matrix. The deciphering algorithm carries out InvSubBytes() in exactly the same manner as the SubBytes routine; however, it uses a new 16×16-byte look-up table. (See Reference 1 for the inverse look-up table.)

InvMixColumns() is a little more complex to perform but requires no more knowledge than the MixColumns() operation. InvMixColumns() uses a new 4×4-byte matrix to perform the Galois-field multiplication. Figure 5 shows the new multiplication, and the text that follows shows the resulting equations. Just like the MixColumns() operation, InvMixColumns() performs the multiplication on a single column at a time.

Although the larger multiplication factors are a bit more computation-intensive, the InvMixColumns() operation carries out the multiplication in the exact same manner as the MixColumns() multiplication:

S'_0,c=({0E}·S_0,c) xor ({0B}·S_1,c) xor ({0D}·S_2,c) xor ({09}·S_3,c)
S'_1,c=({09}·S_0,c) xor ({0E}·S_1,c) xor ({0B}·S_2,c) xor ({0D}·S_3,c)
S'_2,c=({0D}·S_0,c) xor ({09}·S_1,c) xor ({0E}·S_2,c) xor ({0B}·S_3,c)
S'_3,c=({0B}·S_0,c) xor ({0D}·S_1,c) xor ({09}·S_2,c) xor ({0E}·S_3,c)

Applications of the AES

Because the NIST only recently approved the AES algorithm, it has not yet been deployed into as many applications as DES. The AES seems first to be making headway in secure-IP (Internet Protocol) networking. The latest version of the Unix OS NetBSD incorporates the AES algorithm for its implementation of the networking protocol IPSec. Because secure-networking protocols tend to use the most cryptographically strong cipher shared between two nodes, and network nodes tend to be software upgradeable, security services should fully deploy the AES in the short term.