52 Things: Number 17: Describe and compare the round structure of DES and AES.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.In this week, we describe and compare the round structure of DES and AES. 

Both DES and AES are examples of iterated block ciphers. The block ciphers obtain their security by repeated use of a simple round function. The round function takes an n-bit block and returns an n-bit block, where n is the block size of the overall cipher. The number of rounds r can either be a variable or fixed. As a general rule increasing the number of rounds will increase the level of security of the block cipher. Each use of the round function employs a round key k_i (where 1 ≤ i ≤ r) derived from the main secret key k, using an algorithm called a key schedule. To allow decryption, for every round key the function implementing the round must be invertible, and for decryption the round keys are used in the opposite order that they were used for encryption. In DES the functions needed to implement the round function are not invertible, but the whole round is invertible. For AES (Rijndael) not only is the whole round function invertible but every function used to create the round function is also invertible. 
More particularly, the DES cipher is a variant of the basic Feistel cipher. The interesting property of a Feistel cipher is that the round function is invertible regardless of the choice of the function in the box marked F. To see this notice that each encryption round is given by:

L_i = R_i-1

R_i = L_i-1 ⊕ F(K_i,R_i-1).

Hence, the decryption can be performed via:

R_i-1 = L_i

L_i-1 = R_i ⊕ F(K_i,L_i).

This way we can choose any function for the function F, and we will still obtain an encryption function which can be inverted using the secret key. The same code/circuitry can be used for the encryption and decryption functions. We only need to use the round keys in the reverse order for decryption. As a variant of the Feistel cipher design, DES includes the following distinct characteristics:

• the number of rounds r is 16,
• the block length n is 64 bits,
• the key length is 56 bits,
• the round keys K₁,...,K₁₆ are each 48 bits
• before and after the main Feistel iteration a permutation is performed.

In summary the DES cipher operates on 64 bits of plaintext in the following manner:

• Perform an initial permutation.
• Split the blocks into left and right half.
• Perform 16 rounds of identical operations (Festal cipher). In each round the, the F function consists of the following six stages:
• Expansion Permutation: The right half of 32 bits is expanded and permuted to 48 bits.
• Round Key Addition: The 48-bit output from the expansion permutation is XORed with the round key, which is also 48 bits in length.
• Splitting: The resulting 48-bit value is split into eight lots of six-bit values.
• S-Box: Each six-bit value is passed into one of eight different S-Boxes (Substitution Box) to produce a four-bit result. Each S-Box is a look-up table of four rows and sixteen columns. The six input bits specify which row and column to use. Bits 1 and 6 generate the row number, whilst bits 2, 3, 4 and 5 specify the column number. The output of each S-Box is the value held in that element in the table.
• P-Box: We now have eight lots of four-bit outputs which are then combined into a 32-bit value and permuted to form the output of the function F.
• Join the half blocks back together.
• Perform a final permutation.

The DES key schedule takes the 56-bit key, which is actually input as a bitstring of 64 bits comprising of the key and eight parity bits, for error detection. It first permutes the bits of the key (which takes a 64-bit input and produces a 56-bit output, hence discarding the parity bits). The output of this permutation, called PC-1 in the literature, is divided into a 28-bit left half C₀ and a 28-bit right half D₀. Now for each round we compute:

C_i=C_i−1 ≪ p_i
D_i=D_i−1 ≪ p_i

where x ≪ p_i means perform a cyclic shift on x to the left by p_i positions. Finally the two portions C_i and D_i are joined back together and are subject to another permutation, called PC-2, to produce the final 48-bit round key.
Note that a key length of 56 bits is insufficient for many modern applications, hence often one uses DES by using three keys and three iterations of the main cipher. Such a version is called Triple DES or 3DES. In 3DES the key length is equal to 168. There is another way of using DES three times, but using two keys instead of three giving rise to a key length of 112. In this two-key version of 3DES one uses the 3DES basic structure but with the first and third key being equal. However, two-key 3DES is not as secure as one might initially think.
More details on actual values (S-Boxes, P-Boxes and all Permutation tables) can be found in [1].

The AES (Rijndael) algorithm, unlike DES, is a block cipher that does not rely on the basic design of the Feistel cipher. However, AES does have a number of similarities with DES. It uses a repeated number of rounds to obtain security and each round consists of substitutions and permutations, plus a key addition phase. AES in addition has a strong mathematical structure, as most of its operations are based on arithmetic in the field F₂⁸ . However, unlike DES the encryption and decryption operations are distinct.
AES identifies 32-bit words with polynomials in F₂⁸[X] of degree less than four. AES is a parametrized algorithm in that it can operate on block sizes of 128, 192 or 256 bits. It can also accept keys of size 128, 192 or 256 bits. For each combination of block and key size a different number of rounds is specified.
To make our discussion simpler we shall consider the simpler, and probably more used, variant which uses a block size of 128 bits and a key size of 128 bits, in which case 10 rounds are specified. AES operates on an internal four-by-four matrix (S(4,4)) of bytes, called the state matrix, which is usually held as a vector of four 32-bit words, each word representing a column. Each round key is also held as a four-by-four matrix [1]. The AES round function operates using a set of four operations:

• SubBytes: There are two types of S-Boxes used in Rijndael: One for the encryption rounds and one for the decryption rounds, each one being the inverse of the other. For the encryption S-Box each byte s = [s₇,...,s₀] of the state matrix is taken in turn and considered as an element of F₂⁸. The S-Box can be mathematically described in two steps:

1. The multiplicative inverse in F₂⁸ of s is computed to produce a new byte x = [x₇, . . . , x₀].
2. The bit-vector x is then mapped, via an affine F2 transformation [1], to a new bit-vector y. The new byte is given by y. The decryption S-Box is obtained by first inverting the affine transformation and then taking the multiplicative inverse.

• ShiftRows: The ShiftRows operation in AES performs a cyclic shift on the state matrix. Each row is shifted by different offsets [1]. The inverse of the ShiftRows operation is simply a similar shift but in the opposite direction. The ShiftRows operation ensures that the columns of the state matrix ‘interact’ with each other over a number of rounds.
• MixColumns: The MixColumns operation ensures that the rows in the state matrix ‘interact’ with each other over a number of rounds; combined with the ShiftRows operation it ensures each byte of the output state depends on each byte of the input state [1].
• AddRoundKey: The round key addition is particularly simple. One takes the state matrix and XORs it, byte by byte, with the round key matrix. The inverse of this operation is clearly the same operation.

The AES algorithm can be described using the pseudo-code:

AddRoundKey(S, K0) 
for i = 1 to 9 do 
      SubBytes(S) 
      ShiftRows(S) 
      MixColumns(S) 
      AddRoundKey(S, Ki) 
end 
SubBytes(S) 
ShiftRows(S) 
AddRoundKey(S, K10)

The message block to encrypt is assumed to be entered into the state matrix S. The output encrypted block is also given by the state matrix S.
The AES key schedule makes use of a round constant which we shall denote by: 

RC_i = xⁱ (mod x⁸ + x⁴ + x³ + x + 1)

We label the round keys as (W_4i, W_4i+1, W_4i+2, W_4i+3) where i is the round. The initial main key is first divided into four 32-bit words (k₀, k₁, k₂, k₃). The round keys are then computed as algorithm below, where RotBytes is the function which rotates a word to the left by a single byte, and SubBytes applies the Rijndael encryption S-Box to every byte in a word [1].

W₀ =K₀,W₁ =K₁,W₂ =K₂,W₃ =K₃ 
for i = 1 to 10 do 
      T = RotBytes(W_4i−1) 
      T = SubBytes(T) 
      T = T ⊕ RC_i 
      W_4i = W_4i−4 ⊕ T 
      W_4i+1 = W_4i−3 ⊕ W_4i 
      W_4i+2 = W_4i−2 ⊕ W_4i+1 
      W_4i+3 = W_4i−1 ⊕ W_4i+2 
end
References: [1] http://www.cs.bris.ac.uk/~nigel/Crypto_Book/