52 Things: Number 43: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for 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. This week we consider what can be done to mitigate the thread of side-channels against AES implementations...
Sidechannel defences: Why?
For a modern cryptographic scheme to be taken seriously, we generally require some form of security justification. In the case of AES, we believe it acts like a random permutation if the adversary doesn't know the key. However, if the adversary has side-channel information, it is possible that this is no longer the case. So, what can we do about it?  Ideally we would create an implementation that is completely impervious to side-channel attacks. However, this effectively means the implementation must sit in total isolation, with absolutely no output streams - which makes it rather pointless!
Perhaps we can make sure that whatever we do, it doesn't matter if the AES implementation leaks information through side channels? This leads to the field of leakage resilient cryptography, which is a very strong security requirement indeed. As such, schemes secure in these conditions (of which there are very few) tend to be drastically less efficient than those which avoid (/ignore) the problem. Since trade-offs must always be made in design, in practice we tend to use schemes that assume AES doesn't leak any information, and combine them with implementations that contain defences against some of the simpler side-channel attacks. The hope is that this pushes the attack cost beyond the value of the information secured and so (even though they could) no adversary will bother attacking the system because it is no longer viable.

Some Basic Defences
So, with that in mind, let us consider a couple of basic defences against some of the less sophisticated side-channel attacks. As pointed out in the question, these techniques may be easily bypassed, so think of this post as explaining the general concept, rather than providing any sensible suggestions!

Attack: Timing Attack
Weakness: Some implementations run in different times depending on their inputs. As such, by observing how long the system takes to respond one learns something about the key/inputs.
Defence: Constant time implementations. As the title says, the best defence against a timing attack is to make sure the implementation takes constant time, and most implementations will be constant-time nowadays. This might not be too hard in hardware, but in software it can be very difficult indeed, because the microcode (the internal programming of the processor) is generally a trade secret and open to change.

Attack: Power Analysis (DPA,SPA)
Weakness: The power usage of some implementations is correlated with the key material, often due to the hamming distance when storing values. For more information, read the blog from two weeks ago.
Defence (1): Masking Rather than using the AES Sbox directly, one applies a mask to the input value, and looks this up in a masked Sbox (which is effectively the Sbox with its values reordered to accommodate the mask).  Then, even though the attacker may be able to detect correlations between certain internal variables, these are all masked, and do not [directly] correspond to the key material as they had previously. More complex masking schemes will be more complex to instantiate, but lead to better resistance to attack.
Defence (2): Shuffling To conduct a power analysis attack, the attacker uses the fact they know the internal structure of the AES scheme. If we shuffle the order of the S-boxes in our implementation (by some secret permutation), the adversary will not know how their readings correspond to the internal key materials. A variation on this is the deliberate use of non-determinism, allowing the processor to reorder certain collections of instructions on it's own.


Attack: Cache-flooding
Weakness: Implementations using lookup-tables (eg for the SBox) will be more or less efficient if the appropriate cells are already in the processors cache. By pushing most of the lookup table out of the cache, an attacker can observe whether the appropriate cells are called, leaking information. Can also be observed as a timing attack or by power analysis if the cost of loading the cache can be observed.
Defence: Dont use lookup tables on secret data! The simplest defence in this list - if you don't want to leak information about which lookup entries have been used, don't use lookup tables. In the case of AES this is reasonable, because the AES Sbox can actually be computed as a simple function on the input byte. This would be much less practical with (for example) the DES Sbox, which does not have this structure.

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/