Adapted from John Savard's crypto pages

The Advanced Encryption Standard (Rijndael)

The block cipher Rijndael is designed to use only simple whole-byte operations. Also, it provides extra flexibility over that required of an AES candidate, in that both the key size and the block size may be chosen to be any of 128, 192, or 256 bits. (During an early stage of the AES process, a draft version of the requirements would have required each algorithm to have three versions, with both the key and block sizes equal to each of 128, 192, and 256 bits. This was later changed to make the three required versions have those three key sizes, but only a block size of 128 bits, which is more easily accomodated by many types of block cipher design.)

The original description of Rijndael is available at: http://www.esat.kuleuven.ac.be/~rijmen/rijndael/.

However, the variations of Rijndael which act on larger block sizes apparently will not be included in the actual standard, on the basis that the cryptanalytic study of Rijndael during the standards process primarily focused on the version with the 128-bit block size.

Rijndael is a relatively simple cipher in many respects.

Rijndael has a variable number of rounds. Not counting an extra round performed at the end of encipherment with one step omitted, the number of rounds in Rijndael is:

To encipher a block of data in Rijndael, you first perform an Add Round Key step (XORing a subkey with the block) by itself, the regular rounds noted above, and as already noted, the final round with the Mix Column step, as described below, omitted.

The Rounds

Each regular round involves four steps. First is the Byte Sub step, where each byte of the block is replaced by its substitute in an S-box.

The specification for Rijndael only provided an explanation of how the S-box was calculated: the first step was to replace each byte with its reciprocal in the same GF(2^8) as used below in the Mix Column step, except that 0, which has no reciprocal, is replaced by itself (since it isn't anything's reciprocal either, it is the only value not used, so that makes sense) then a bitwise modulo-two matrix multiply was used, and finally the hexadecimal number 63 is XORed with the result. (Not C6, x7 is the MSB, if the diagram in the specification appears confusing.)

The S-box is:

 99 124 119 123 242 107 111 197
 48   1 103  43 254 215 171 118
202 130 201 125 250  89  71 240
173 212 162 175 156 164 114 192
183 253 147  38  54  63 247 204
 52 165 229 241 113 216  49  21
  4 199  35 195  24 150   5 154
  7  18 128 226 235  39 178 117
  9 131  44  26  27 110  90 160
 82  59 214 179  41 227  47 132
 83 209   0 237  32 252 177  91
106 203 190  57  74  76  88 207
208 239 170 251  67  77  51 133
 69 249   2 127  80  60 159 168
 81 163  64 143 146 157  56 245
188 182 218  33  16 255 243 210
205  12  19 236  95 151  68  23
196 167 126  61 100  93  25 115
 96 129  79 220  34  42 144 136
 70 238 184  20 222  94  11 219
224  50  58  10  73   6  36  92
194 211 172  98 145 149 228 121
231 200  55 109 141 213  78 169
108  86 244 234 101 122 174   8
186 120  37  46  28 166 180 198
232 221 116  31  75 189 139 138
112  62 181 102  72   3 246  14
 97  53  87 185 134 193  29 158
225 248 152  17 105 217 142 148
155  30 135 233 206  85  40 223
140 161 137  13 191 230  66 104
 65 153  45  15 176  84 187  22

Note that 63 in hexadecimal is 3 plus 6*16, or 36+60 or 96, and that is 99, as begins the table.

Next is the Shift Row step. Considering the block to be made up of bytes 1 to 16, these bytes are arranged in a rectangle, and shifted as follows:

from            to
  1  5  9 13      1  5  9 13
  2  6 10 14      6 10 14  2
  3  7 11 15     11 15  3  7
  4  8 12 16     16  4  8 12

Blocks that are 192 and 256 bits long are shifted like this:

from                  to
  1  5  9 13 17 21      1  5  9 13 17 21
  2  6 10 14 18 22      6 10 14 18 22  2
  3  7 11 15 19 23     11 15 19 23  3  7 
  4  8 12 16 20 24     16 20 24  4  8 12

and
from                        to
  1  5  9 13 17 21 25 29      1  5  9 13 17 21 25 29
  2  6 10 14 18 22 26 30      6 10 14 18 22 26 30  2
  3  7 11 15 19 23 27 31     15 19 23 27 31  3  7 11
  4  8 12 16 20 24 28 32     20 24 28 32  4  8 12 16

Note that in the 256 bit case, the rows are shifted 1, 3, and 4 places to the left, instead of 1, 2, and 3 places as for the other two block sizes.

Next comes the Mix Column step. Matrix multiplication is performed: each column, in the arrangement we have seen above, is multiplied by the matrix:

 2 3 1 1
 1 2 3 1
 1 1 2 3
 3 1 1 2

However, this multiplication is done over GF(2^8). This means that the bytes being multiplied are treated as polynomials rather than numbers. Thus, a byte "muliplied" by 3 is that byte XORed with that byte shifted one bit left.

If the result has more than 8 bits, the extra bits are not simply discarded: instead, they're cancelled out by XORing the binary 9-bit string 100011011 with the result (shifted right if necessary). This string stands for the generating polynomial of the particular version of GF(2^8) used; a similar technique is used in cyclic redundancy checks.

The final step is Add Round Key. This simply XORs in the subkey for the current round.

Although a three-dimensional color diagram of the round has already appeared at the beginning of the page, the Rijndael round can also be illustrated in a more conventional manner:

The extra final round omits the Mix Column step, but is otherwise the same as a regular round.

Thus, the sequence of steps in Rijndael is:

ARK

BSB
SR
MC
ARK

BSB
SR
MC
ARK

...

BSB
SR
MC
ARK

BSB
SR
ARK

Because it begins and ends with an ARK (Add Round Key) step, there is no wasted unkeyed step at the beginning or end. The sequence of operations is important for facilitating decipherment, as well.

Although the sequence is not symmetrical, the order of some of the steps in Rijndael could be changed without affecting the cipher. The Byte Sub step could just as easily be done after the Shift Row step as before it.

That would change

A BSMA BSMA ... BSMA BSA

to

A SBMA SBMA ... SBMA SBA

If, on the other hand, we reversed the original sequence, we would get

ASB AMSB ... AMSB AMSB A

Although these look similar, except for the different positions of the spaces, which just mark what are termed "rounds" in the algorithm, wherever the sequence "MA" appears in the modified, but equivalent, algorithm, the sequence "AM" appears in the reverse sequence, required for decryption.

Of course, the steps also need to be reversed as well: ARK is an XOR, so that is its own inverse, but the matrix in the Mix Column step needs to be replaced with its inverse, and the S-box in the Byte Sub step needs to be replaced with its inverse for decryption as well.

What about the switch between "MA" and "AM", though? Do we need to change the order of operations for decryption?

No; with matrix multiplication, the distributive property also applies, so the round keys involved in such a reversal merely need to be multiplied by the (inverse) Mix Column matrix, and then they can be XORed in at the same time (of course, in reverse order) as was used for encryption. (XOR corresponds to addition in GF(2^8), which is where the multiplications are performed.)

The matrix for the inverse Mix Column step is:

14 11 13  9
 9 14 11 13
13  9 14 11
11 13  9 14

as can quickly be verified by making use of its symmetry, and once the answer is known:

1110 1011 1101 1001  01 00 00 00
1001 1110 1011 1101  00 01 00 00
1101 1001 1110 1011  00 00 01 00
1011 1101 1001 1110  00 00 00 01

 111  101  110  100  01 01 00 00
 110  100  111  101  00 00 01 01
1100 1000 1110 1010  00 00 10 10
1011 1101 1000 1110  01 01 10 10
   0    0    1    0  01 01 10 11

The Key Schedule

For keys 128 and 192 bits in length, the subkey material, which consists of all the round keys in order, consists of the original key, followed by stretches, each the length of the original key, consisting of four-byte words such that each word is the XOR of the preceding four-byte word and either the corresponding word in the previous stretch or a function of it. For the first word in a stretch, the word is first rotated one byte to the left, and then its bytes are transformed using the S-box from the Byte Sub step, and then a round-dependent constant is XORed to its first byte.

The round constants are:

  1   2   4   8  16  32  64 128
 27  54 108 216 171  77 154  47
 94 188  99 198 151  53 106 212
179 125 250 239 197 145  57 114
228 211 189  97...

which are, in binary:

00000001 00000010 00000100 00001000 00010000 00100000 01000000 10000000
00011011 00110110 01101100 11011000 10101011 01001101 10011010 00101111
01011110 10111100 01100011 11000110 10010111 00110101 01101010 11010100
10110011 01111101 11111010 11101111 11000101 10010001 00111001 01110010
11100100 11010011 10111101 01100001...

the successive powers of 2 in the representation of GF(2^8) used. Successive powers of 3, unlike 2, include all the values from 1 to 255, and thus several implementations of Rijndael use tables of the powers of 3, and the inverse table giving the discrete logarithm in that field, to facilitate calculations, but the round constants are still the powers of 2. (I'm not entirely sure why one needs log and antilog tables when all one is doing is muliplying by 2 and by 3, but doubtless there is a nonobvious way to implement Rijndael with greater efficiency that makes use of them. The inverse of the matrix used in the Mix Column step has the values 9, 11, 13, and 14 as its coefficients, however, so this could simply serve to limit the number of tables needed for both enciphering and deciphering, replacing six tables by two.)

For keys 256 bits in length, in addition, the S-box from the Byte Sub step alone is applied to the word from the preceding stretch for the fifth word in a stretch in addition.

Attacks on Rijndael

Although this page (and the preceding one) already have several diagrams of Rijndael, I've included yet another one, one even more simplified than the one appearing on the previous page, to make it easier to "see the forest for the trees", and see both that the Mix Column step indeed only mixes columns, and is the only place where that happens, and how the Shift Row step works with the Mix Column step to ensure that all parts of the block impinge on each other.

The standard techniques of differential and linear cryptanalysis can be adapted to be used against Rijndael. Because of the way matrix multiplication works, and because in GF(2^8), all the coefficients of the Mix Column matrix (as indeed all numbers from 1 to 255) have reciprocals, a specific attack, originally developed for use against its predecessor Square, called the "Square attack", can be used as well.

If one uses 256 blocks of chosen plaintext, where every byte but one is held constant, and that one is given all 256 possible values, then after one round of Rijndael, four bytes will go through all 256 possible values, and the rest of the bytes will remain constant. After a second round, sixteen bytes will each go through all 256 possible values, without a single duplicate, in the encipherment of the 256 blocks of chosen plaintext. (For a 128-bit block, this is every byte; for larger blocks, the rest of the bytes will remain constant.) This interesting property, although not trivial to exploit, can be used to impose certain conditions on the key when one additional round, before or after the two rounds involved, is present.

The possibility of this attack was first noted by the developers of Square and Rijndael themselves, and was noted in the paper that initially described Square.