Joan and Vincent are the inventors of the Rijndael algorithm, which won the NIST AES competition. They can be contacted at [email protected] and [email protected], respectively.
On October 2, 2000, the National Institute of Standards and Technology announced that the winner of the Advanced Encryption Standard competition was our submission, Rijndael. In this article, we'll present our design and explain our design choices and how they make the cipher resistant against currently known cryptanalytic attacks. We'll also give some guidelines for an efficient implementation.
All operations used in Rijndael are either byte-shuffling operations, or those defined over the finite field GF(28). Addition in this field corresponds to the well-known bitwise XOR operation. The multiplication operation in this field is more complex, and often implemented with lookup tables. More information on finite fields can be found in Introduction to Finite Fields and Their Applications, by R. Lidl and H. Niederreiter (Cambridge University Press, 1986). We also provided a brief introduction to finite fields in the document that accompanied our submission, available at http://www.rijndael.com/.
Because Rijndael uses no arithmetic operations, the description of Rijndael assumes no endianness. The performance on specific platforms may be influenced by the representation that the implementer uses. We use hexadecimal notation to represent byte values. However, the numerical value of a byte is never used.
Description
Rijndael is a block cipher, not unlike Square (described in our article "The Block Cipher Square Algorithm," DDJ, October 1997). Both Rijndael's input block length and key length are variable: They can independently be varied between 128 and 256 bits in increments of 32 bits. NIST will only standardize the versions with an input block length of 128 bits and a key length of 128, 192, or 256 bits.
Rijndael has been designed following the wide-trail strategy, which provides resistance against linear and differential cryptanalysis. In the strategy, the round transformation is divided into different components, each with its own functionality.
We define the state of the block cipher as the intermediate result of the encryption process. The state is represented by a rectangular byte array with four rows. The number of columns is determined by the block length: If the block length is N, the number of columns Nb equals N/32. The state is initialized with plaintext in the order a0,0, a1,0, a2,0, a3,0, a0,1, a1,1..., as in Figure 1.
The round transformation is built from component transformations that operate on the state. Finally, at the end of the cipher operation, the ciphertext is read from the state by taking the state bytes in the same order.
The cipher key is similarly pictured as a rectangular array with four rows. The number of columns of the cipher key is denoted by Nk and is equal to the key length divided by 32; see Figure 2. Sometimes the cipher key is pictured as a linear array of 4-byte words. The words consist of the 4 bytes that are in the corresponding column. The number of rounds is denoted by Nr and depends on the values Nb and Nk; see Table 1.
The round transformation is composed of four different component transformations. In pseudo-C notation, you have Example 1(a). The final round of the cipher is slightly different. It is defined by Example 1(b). In this notation, the functions (Round, ByteSub) operate on arrays to which pointers (State, RoundKey) are provided. In the final round, the MixColumn step has been removed. The component transformations are specified in the following paragraphs.
The ByteSub transformation is a nonlinear byte substitution, operating on each of the state bytes independently. The transformation uses the same substitution table (or S-box) for every byte. The S-box has been selected to make Rijndael resistant against linear and differential attacks, as well as interpolation attacks. This is ensured by requirements such as having a low correlation between input bits and output bits and the fact that the output cannot be described as a simple mathematical function of the input.
In ShiftRow, the last three rows of the state are shifted cyclically over different offsets. Row 1 is shifted over C1 bytes, row 2 over C2 bytes, and row 3 over C3 bytes. The shift offsets C1, C2, and C3 depend on the block length Nb. The different values are specified in Table 2. The operation in Figure 3 ensures that bytes of one column are spread out to four different columns.
In MixColumn, the Nb columns of the state are transformed by means of a multiplication with a fixed matrix; see Figure 4. The operations are performed in GF(28): Addition is the bitwise XOR, and multiplication is not the standard integer multiplication. The coefficients of the matrix are based on a linear code with maximal distance between code words. This ensures a good mixing between the bytes of each column. Together with the ShiftRow operation, this operation ensures that after a few rounds, all output bits depend on all input bits. A second design criterion for the coefficients was the possibility of efficient implementation.
In the round-key addition operation, a round key is applied to the state by a simple bitwise XOR. The round-key length is equal to the block length Nb.
The round keys are derived from the cipher key by means of the key schedule. This consists of two components: the key expansion and round-key selection. The basic principles are:
- The total number of round-key bits is equal to the block length multiplied by the number of rounds plus 1 (for example, for a block length of 128 bits and 10 rounds, 128×(10+1)=1408 round-key bits are needed).
- The cipher key is expanded into an expanded key.
- Round keys are taken from this expanded key in the following way: The first round key consists of the first Nb words, the second one of the following Nb words, and so on.
The expanded key is a linear array of 4-byte words and is denoted by W[Nb(Nr+1)]. The first Nk words contain the cipher key. All other words are defined recursively in terms of words with smaller indices. The key schedule depends on the value of Nk: There is a version for Nk
6, and a version for Nk>6; see Example 2 for a pseudo-C description.
When the cipher key words have been used, every following word W[i] is equal to the XOR of the previous word W[i-1] and the word Nk positions earlier W[i-Nk]. For words in positions that are a multiple of Nk, a transformation is applied to W[i-1] prior to the XOR and a round constant is XORed. This transformation consists of a cyclic shift of the bytes in a word, denoted with Rot, followed by SubByte, and the application of a table lookup to all 4 bytes of the word. SubByte uses the same S-box as ByteSub but operates on 4-byte words instead of states. If Nk>6, there is an extra application of SubByte: For i-4, a multiple of Nk, SubByte is applied to W[i-1] prior to the XOR.
Example 2 is admittedly a bit sloppy. When the total number of round-key bits needed is not an exact multiple of the number of bits in the cipher key, the given code will calculate too many round-key bits.
The round constants are independent of Nk and defined by: Rcon[i]=(RC[i],0,0,0), with RC[1]=1, RC[i]=2
RC[i-1] multiplication in the field GF(28).
Round key i is given by the round-key buffer words W[Nbi] to W[Nb(i+1)]. The key schedule can be implemented without explicit use of the array W. For implementations where RAM is scarce, the round keys can be computed just-in-time using a buffer of Nk words.
The cipher Rijndael consists of an initial round-key addition, followed by Nr-1 rounds, and a final round. In pseudo-C code, this gives Example 3. When encrypting multiple blocks, the key expansion can be done once beforehand and stored.
Implementation Aspects
Rijndael can be programmed by simply implementing the different component transformations. This is straightforward for RowShift and AddRoundKey. The implementation of ByteSub requires a table of 256 bytes. AddRoundKey, ByteSub, and RowShift can be efficiently combined and executed serially per state byte.
The transformation MixColumn requires matrix multiplication in the field GF(28). The choice for the coefficients of the polynomial c(x) has been influenced by implementation considerations. Indeed, the matrix has only entries 1, 2, and 3. Multiplication with 1 doesn't take any instructions. Multiplication with 2 can be implemented with a shift and a conditional XOR. Since 3x=(2
1)x=(2x)(1x), multiplication with 3 can be done by multiplying with 2, then XORing the argument.
However, the use of a conditional instruction can cause weaknesses with respect to timing attacks (see "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and Other Systems," by P.C. Kocher, Advances in Cryptology, Proceedings of Crypto'96, edited by N. Koblitz, Springer-Verlag, 1996), because the execution time of the operation may depend on the input value. The timing attack can be countered by inserting additional NOP-operations to make the execution time of both branches equal to one another, but this will probably introduce weaknesses with respect to a power analysis attack. The use of a table effectively counters these types of attacks. We define the 256-byte table X2 as: X2[i]=i2. Thus, multiplication with 2 is implemented as a table lookup, while multiplication with 3 can be implemented as i3=X2[i]i. The matrix multiplication can now be implemented with a fixed succession of XORs in table lookups.
The straightforward implementation uses only 8-bit operations. On many processors, this results in suboptimal performance. We'll now examine how the performance can be improved on 32-bit processors with a reasonable size of cache. Similar techniques can be applied to 16-bit or 64-bit processors.
The performance increase results from the combination of the operations ByteSub, ShiftRow, and MixColumn. Let a denote the value of the state before the application of the three operations and let b denote the output. The equalities in Figure 5(a) hold for the first column of b. You now define four extended tables Ti[x]; see Figure 5(b), and you get Figure 5(c).
The operations ByteSub, ShiftRow, and MixColumn can be executed with four table lookups and three XOR operations per column. The same tables can be used for each column of b. Each T-table has a size of 1 KB. One additional XOR operation per column implements AddRoundKey and completes the implementation of the round transformation.
This feature makes Rijndael very fast on Pentiums and other high-end processors, while not overburdening low-end processors. It is probably one of the most important factors in the selection of Rijndael over the other fast finalists.
The Inverse Cipher
The round transformation of Rijndael is not a Feistel network. An advantage of a Feistel cipher is that the inverse cipher is almost the same as the cipher.
Since the round transformation of a Feistel cipher is an involution, only the order of the round keys has to be inverted. For Rijndael, this is not the case. In principle, the decryption has to be done by applying the inverses of the component transformations in inverse order.
However, the round transformation and the cipher structure have been designed to alleviate this problem partially. By using some algebraic properties, we can derive an equivalent representation of the inverse cipher that has the same structure as the cipher. This means that a round of the inverse cipher looks the same as a round of the cipher, except that ByteSub, MixColumn, and ShiftRow have been replaced by their inverses. The round keys in this representation are different from the round keys used in the encryption mode. A more detailed description of the inverse cipher can be found in the document that accompanies the submission, or in our upcoming book on Rijndael (to be published by Springer-Verlag).
Performance
In "Fast Implementations of AES Candidates," (Proceedings of the Third AES Candidate Conference, 2000), K. Aoki and H. Lipmaa report a performance of 243 Mbps for an assembly-language implementation on a 450-MHz Pentium II. An online performance table for various platforms can be found at http://www.tml.hut.fi/~helger/aes/table.html.
Further Reading
More details about the AES process can be found on NIST's AES site: http://www.nist.gov/aes. For more information on Rijndael, go to http://www.esat.kuleuven.ac.be/~rijmen/rijndael, or visit the Rijndael fan page at http://www.rijndael.com/.
DDJ
