Advanced Encryption Standard (AES)
"The security of the encryption scheme must depend only on the secrecy of the key, and not on the secrecy of the algorithm." - Kerckhoff's Principle.
Synopsis
AES can also be referred to as American Encryption Standard. The NIST (American National Institute of Standards and Technology) began an international competition in 1997 with the goal of setting a new symmetric encryption standard to surpass DES. By 1999 only 5 out of 15 competitors remained: MARS of IBM, RC6 of RSA Labs, Serpent of Ross Anderson, et. al., Twofish of Bruce Schneier et. al. and finally Rijndael of Joan Deamon & Vincent Rijmen from Belgium, who actually won the competition. Rijndael was chosen as the standard because it had the best combination of security, efficiency, performance, flexibility and is easy to implement.
AES Process
Not every detail of AES is covered here, only the highlights. However, the entire specification for AES can be found at the NIST web site under FIPS 197 at http://csrc.nist.gov/publications. AES is a restricted version of Rijndael. Rijndael is a symmetric block encryption cipher that actually does not build upon the classical Feistel network. Rijndael takes a variable input size of 128, 192 or 256 bit word along with a variable key size of either 128, 192 or 256 bits. All combinations of block and key lengths are possible, however. A block of plaintext is encrypted via several rounds with repetitive variable functions. The total number of rounds depend on block and key lengths as described in the following table:
| Block length = |
128
|
192
|
256
|
| Key length 128 |
10 rnds
|
12
rnds
|
14
rnds
|
| Key length 192 |
12
rnds
|
12
rnds
|
14
rnds
|
| Key length 256 |
14
rnds
|
14
rnds
|
14
rnds
|
AES Round
AES performs the following 4 high-level steps for each round:
The input enters the round as 16 octets or 128-bits total.
1. Along with a key size of 128 bits, each plaintext octect is Xor'ed with each key octet.
2. Each of the 16 results is then used as an index into an S-box that maps the input octet to an output octet. All 16 S-boxes are identical and each S-box is a 16 x 16 table containing 256 unique hexadecimal values.
3. All 16 octets are rearranged in a specific order as shown below.
4. Each of the 4 groups of 4 octets enters one of the 4 linear mixing functions.
AES Mixer
The MixColumn operation replaces a 4-octet column with another 4-octet column as shown in the following diagram:
AES Algorithm
Rijndael_Cipher(byte State, byte Key)
{
// Part 1
AddRoundKey(State, ExpandedKey);
// Part 2
for (long j = 1; j < Nr; j++) // Nr is the number of rounds
{
// Substitution - SBox replacement (non-linearity)
SubBytes(State);
// Permutation - rearrangement (linearity)
RowsShift(State);
// Diffusion - columns transformation (linearity)
MixCol(State);
// Round Key Added - XoR (key influence)
AddRoundKey(State, (ExpandedKey + Nb * j));
}
// Part 3
SubBytes(State);
RowsShift(State);
AddRoundKey(State, ExpandedKey + Nb * Nr);
}
There are basically 3 parts to this algorithm.
1. The first part consists of an Xor operation of the first round key with the block.
2. The second part is the regular round rotation.
3. The third part is another round rotation but doesn't include the column mixing.
AddRoundKey Operation
The AddRoundKey routine calculates its own inverse by adding (Xor) the round key to the state. For all i from 0 to Nb words where Nb is the number of columns in the state, the following is performed:
(r0i, r1i, r2i, r3i) = (r0i, r1i, r2i, r3i) ⊕ (k0i, k1i, k2i, k3i)
SubBytes Operation
This operation consists of substitution boxes which specifies how each byte of a block should be replaced by another value. The multiplicative inverse byte a(j,i) is computed from the GF(28) (Galois Fields - the polynomial representation modulo an irreducible polynomial of degree 8). The list of 256 bytes of an S-box are constructed replacing each non-zero byte (i.e. a representative of the GF(28) by its multiplicative inverse. An affine transformation is then applied over GF(28) such as in the following matrix format:
| y0 | | 10001111 | | x0 | | 1 | | y1 | | 11000111 | | x1 | | 1 | | y2 | | 11100011 | | x2 | | 0 | | y3 | = | 11110001 | | x3 | + | 0 | | y4 | | 11111000 | | x4 | | 0 | | y5 | | 01111100 | | x5 | | 1 | | y6 | | 00111110 | | x6 | | 1 | | y7 | | 00011111 | | x7 | | 0 |
RowsShiftOperation
The next step in the round is a byte level permutation on the state. First of all internally there exists a 2-dimensional array of bytes called the state. This state has 4 rows of bytes and Nb columns where Nb equals the block length divided by 32. So the first row is not shifted. The second row is a circular left byte-wise shift of 1 (not bitwise). The third row takes a circular left byte-wise shift of 2 places and finally the last row is circular byte-wise shifted by 3 places as shown in the following:
RowsShift before RowsShift after 0 1 2 3 0 1 2 3 4 5 6 7 5 6 7 4 8 9 10 11 10 11 8 9 12 13 14 15 15 12 13 14
MixCol Operation
The MixCol routine does a column by column operation on the state where Sb(x) = Sc(x) ⊕ Sa(x) mod(x4 + 1). So in matrix format you have:
| Sb0 | | 02 03 01 01 | | Sa0 | | Sb1 | = | 01 02 03 01 | x | Sa1 | | Sb2 | | 01 01 02 03 | | Sa2 | | Sb3 | | 03 01 01 02 | | Sa3 |
Key Expansion
The Rijndael algorithm has variable key length of 128, 192 or 256 bits and a complex key expansion process. The Xor-ing of the sub-key before the first round and the last round effects every bit of the round result. The key expansion consists of the number of round key bits equaling 32 bits x Block Length x (Round Numbers + 1). So the memory storage depends on the size of the main key length. For key expansion, the decryption process is the same. The keys are produced on-line and on the fly because every subsequent word is equal to the Xor of the previous word. The key expansion algorithm is as follows:
Rijndael_KeyExpansion(byte Key, word ExpandedKey)
{
for (int j = 0; j < Nk; j++)
{
ExpandedKey[j] = (Key[4*j], Key[4*j+1], Key[4*j+2], Key[4*j+3]);
}
for (j = 0; j < Nk; j++)
{
hold = ExpandedKey[j - 1];
if (j % Nk == 0)
{
hold = SubBytes(RotationByte(hold)^Rcon[i/Nk];
}
ExpandedKey[j] = ExpandedKey[j - Nk]^hold;
}
}
Mathematics of AES
Rijndael uses algebraic structure such as fields and polynomials for its mathematical strength. Rijndael is based on GF(28), where each of its element is an octet. The bits in the octet are the coefficients of the poly over Z2 modulo Z2 poly m(x) = x8 + x4 + x3 + x + 1, which is irreducible. Addition is simply a bitwise Xor. Since addition modulo 2 is the same as Xor, each element is its own negation.
For key expansion, Rijndael uses a sequence of constants represented by Ci = xi-1 mod m(x). The MixColumn operation performs a multiplication by the fixed poly c(x) = 03x3 + 01x2 + 01x + 02 and the InvMixColumn operation is multiplication by d(x) = 0Bx3 + 0Dx2 + 09x + 0E. The S-box performs a multiply by x4 + x3 + x2 + x + 1 and then an addition of x6 + x5 + x + 1. The inverse for an S-box consists of multiplying by the poly x6 + x3 + x and then adding the poly x2 + 1.
Round
In each round, operations are performed on a state consisting of Nb 4-octet columns.
1. The S-box is applied to each octet in the state.
2. No action on Row 0 of the state.
Row 1 is rotated left 1 column.
Row 2 is rotated left 2 + ┕Nb / 8┙ columns (2 if Nb < 8 else 3)
Row 3 is rotated left 3 + ┕Nb / 7┙ columns (3 if Nb < 7 else 4)
3. MixColumn is applied to every column.
4. The round key is Xor'ed.
Inverse Round
1. The Inverse S-box is applied to each octet in the state.
2. No action on Row 0 of the state.
Row 1 is rotated right 1 octet.
Row 2 is rotated right 2 + ┕Nb / 8┙ columns (2 if Nb < 8 else 3)
Row 3 is rotated right 3 + ┕Nb / 7┙ columns (3 if Nb < 7 else 4)
3. InvMixColumn is applied to every column.
4. The modified round key is Xor'ed.
Links
http://www.bletchleypark.net/crypt/aes_header.txt
http://www.bletchleypark.net/crypt/aes_cpp.txt
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
http://csrc.nist.gov/encryption/aes/aesfact.html
http://csrc.nist.gov/encryption/aes/rijndael
http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf