AES [20] is a well-known block cipher that supports block lengths of 128-bits and key lengths of 128,192, and 256 bits. The AES algorithm consists of identical operations, i.e., rounds. The number of rounds depends on the key length; 10 rounds for 128-bit key, 12 rounds for 192-bit key and 14 rounds for 256-bit key. The AES encrypts the input, referred to as a plaintext, to the output, referred to as ciphertext after the desired number of rounds. The 128-bit input plaintext is represented as 4 x 4 matrix of input bytes, where each column is a separate word. Each round comprises the following four basic transformations, except for the last round, which omits MixColumns

• SubBytes (SB) is a nonlinear substitution operation. Each input byte to the SubBytes operation is replaced by another byte using one-byte substitution table, referred as S-box. This replacement is a one-to-one mapping.

• ShiftRows (SR) is the byte-wise permutation. The second, the third, and the fourth row of the matrix is cyclically shifted by one, two, and three positions to the left, respectively.

• MixColumns (MC) is a four-byte mixing operation. A linear transformation is applied to every column in the matrix, where each input byte in a column affects all the four bytes in the same column.

• AddRoundKeys (ARK) is XORing the state with the round key. Each output byte of the MixColumns operation is XORed with the corresponding key byte.

Figure 6.7 shows the structure of first round of AES, which contains an extra key XORing operation at the beginning. The intermediate results of every round is stored in the round registers.

Fig. 6.7 First round of AES: pi is the plaintext byte, ki is the initial key byte, qi is the SR output byte, ki is the round key byte, and ri is the round output byte

6.3.2.1 Differential Properties of AES [21]

In AES S-box, for an input X and the input difference a, the output difference в is represented as

For a given (a, в) pair, there could be no, two, or four solutions for X [22]. In the case of two solutions, they will be 8, and 8 ® a, where 8 is any nonzero solution for equation (6.1). In case of four solutions, they will be 8, 8 ® a, 0 and a.

Lemma 1 For a given input X and two nonzero differences a_{t}and aj, the output differences в and вj are

For any value X, в and ej are distinct.

Proof We prove this by contradiction. Let as assume that there is a value x of X for which вг = в j. Let’s define y = x ® a j. Then, we have two equations

)

where в = вj implies that x and y are the two solutions of Eq. (6.1) where в = в = в j and a = a_{t}. Then either y = x ® a_{t} ,or x and y must be zero and a_{t} or vice versa. In either case, a j = a_{t} contradicting our assumption. Therefore, в and вj must be distinct. ?