## 3 Attacks on AES
### AES Fundamentals  
The AES algorithm is explained in [46]. It is a symmetric block cipher that operates with data in blocks of 16 bytes. Both encryption and decryption behave similarly. They repeatedly apply a round transformation on the state, denoted \(S\). The number of iteration rounds, \(N_{r}\), depends on the size of the key: 10 rounds for 128-bits, 12 rounds for 192-bits and 14 rounds for 256-bits. The encryption process is depicted in Figure 1. In each round, the algorithm uses a different round key \(K^{r}\), which is obtained from the algorithm key using a known and fixed scheme. Once a round key is known, there is a straight forward algorithm to recover the same amount of bits of the encryption key. Consequently, to obtain a 256-bit AES key, we need to obtain at least two consecutive round keys.  
AES arranges both round key and the data in form of a 4 \(\times\) 4 matrix of byte elements. If we follow the terms used in [46], we can denote \(S^{r},0\leq r\leq N_{r}\) the input state to round \(r\). Each of its byte elements is then denoted as \(S^{r}_{i,j},0\leq i<4,0\leq j<4\). \(i\) indicates the row of the state and \(j\) the columns. We use only one subindex \(j\) to refer to a column of the state \(S_{j}\). Considering a plaintext block \(p_{0}p_{1}p_{2}\ldots p_{15}\), the elements of the initial state \(S^{0}\) of the algorithm are \(S^{0}_{i,j}=p_{i+4j}\).  
The normal round transformation in the encryption process consists of four steps denoted: SubBytes, ShiftRows, MixColumns and AddRoundKey, being SubBytes the only non-linear transformation. SubBytes is an S-box \(S_{RD}\) applied to the elements of the state. ShiftRows is an element transposition that rotates the rows of the state \(i\) positions to the left. MixColumns operates on the state column by column. The operation is a matrix multiplication of a 4 \(\times\) 4 known matrix and each of four the original columns. AddRoundKey is the addition (bitwise XOR in GF(2)) of the elements of the state with the corresponding element of the round key.  
Figure 1: Diagram of the AES encryption process.  
All these steps have an inverse step, which are used in the decryption process: InvSubBytes (using S-box \(S_{RD}^{-1}\)), InvShiftRows (rotating to the right), InvMixColumns (multiplying by the inverse matrix) and AddRoundKey. The normal round transformation is applied in all but the first and last rounds. The first round applies only the AddRoundKey step. The last round is a normal round without the MixColumns step.  
The decryption algorithm can be implemented by applying the inverses of the steps in a reverse order, being InvSubBytes the last step of each round excepting the last one. It is preferable to perform the non-linear step first in typical implementations. In [46], the authors presented the Equivalent Decryption Algorithm, with a sequence of steps equal to the encryption, by switching the order of application of InvSubBytes and InvShiftRows (the order is indifferent) and InvMixColumns and AddRoundKey. The round key of all but the first and last rounds needs to be adapted for this purpose, by applying the InvMixColumns step to it.  
The key fact to understand the attack against AES-256 is that the state \(S^{r}\) can be reached in the \(r\) round of the plaintext encryption process or in the \(N_{r}+1-r\) round of the ciphertext decryption process.