## 3 Attacks on AES
### Information Processing
#### 3.3.2 Attack on AES-256  
The attack against AES-256 comes as an extension of the previously explained attack on the last round of an encryption. There are no further assumptions than in the previous case. The setup and measurement collection steps are exactly the same for both attacks, and only the information processing phase is different since it includes an extra step. We retrieve 128 bits of the key using Algorithm 2 and use the guessed 128 bits of the key and the same information that has already been used (non-accesses and ciphertext) to derive the remaining 128 unknown bits of the key. We similarly use information about the non-used cache lines to discard key values until we obtain the key. This is possible because this information refers to the whole encryption and, as previously stated, if a cache line has not been accessed within an encryption, it has not been accessed in any of its rounds. Note that the probability of non-accessing one line when performing an AES-256 encryption, which is a function of the number of rounds, and is given by Equation (1), is 2.69% (14 rounds). Consequently, the attack on AES-256 would require more samples to successfully guess the whole key. In this case, about 1 out of 37 samples carries useful information. This means we need to collect at least the same number of useful samples than in the previous case. The key to understand the attack is to understand the equivalence between encryption and decryption. Using the decryption algorithm, we transform the data referring to the encryption process in a way that it is possible to easily derive the round key discarding its possible values. For this reason, we call this approach encryption-by-decryption attack (EBD). If we analyze the AES encryption process, we see that the output of each round is used as an index to access the \(\mathsf{T}\)-tables in the next round after a ShiftRows operation. Taking into account the valuable information of the unused cache lines, it is possible to figure out which are the state values that are not possible before the penultimate round, \(S^{Nr-1}\). That is, if a cache line has not been accessed, all the state values that would have forced an access to this line can be discarded. Once we know the last round key, it is straightforward to obtain the input to that round (\(S^{Nr-1}\)) only taking into the account the encryption function. However, because of the MixColumns operation which is performed in all the previous rounds (except for the initial one), the certainty about the non-usage of a cache line of one table and the knowledge of the encryption function are not enough to obtain information about the key of these rounds. However, if we use the decryption function and take into the account the equivalence between encryption and decryption, we can transform our data so we can derive information about a state of the decryption function, which is equivalent to the \(S^{Nr-1}\) state in the encryption function. Figure 4 shows with dotted lines the instants where equivalent decryption and encryption algorithms have the same values. According to the figure, we establish a bidirectional relation between an encryption state \(S^{r}\) and a decryption state \(D^{N_{r}+1-r}\) using SubBytes and ShiftRows steps. Figure 3: Key byte possible values with their associated discarding scores. The relations are defined in Equations (2a) and (2b). These relations and the knowledge of the values which are not possible in the state \(S^{Nr-1}\) give us the values which are not possible in the state \(D^{2}\). Since the value of what we call intermediate value \(\text{IV}^{1}\) can be easily obtained from the decryption function, our scenario is similar to the previous one (\(D^{2}_{i,j}=IV^{1}_{i,j}\oplus\text{CK}d^{1}_{i,j}\)). \[D^{N_{r}+1-r}=\texttt{ShiftRows}(S_{RD}(S^{r})) \tag{2a}\] \[S^{r}=S_{RD}(\texttt{InvShiftRows}(D^{N_{r}+1-r})) \tag{2b}\]  
Algorithm 3 shows how to obtain the correct candidates for the round key of decryption algorithm Round 1 (the second round).