## 3 Attacks on AES
### Information Processing
#### 3.3.2 Attack on AES-256
The key of the first decryption round is exactly the same as the key used in the last round of the encryption, previously obtained using the non-access cache attack and targeting the last round (Algorithm 2). As we know both input data (ciphertext) and round key, we can perform the first round of the decryption algorithm and obtain the state of round 1, \(\text{D}^{1}\). Applying the \(\texttt{Td}\)-tables on the state, we calculate an intermediate value of Round 1, \(\text{IV}^{1}\). At this point, if we perform the AddRoundKey, the next step of the decryption algorithm, the result would be \(D^{2}\), which can be transformed into the encryption \(S^{13}\) state, as explained using Equation (2b). In the T-table implementation, the state (including \(S^{N_{r}-1}\) or \(S^{13}\) for AES256) is used as index to access the Te tables. Note that not accessing a cache line holding one entry of the table also indicates which indexes of the table are not being used, which is similar to indicating which values of the state can be discarded. Then, we apply Equation (2a) to transform the discarded values for state \(S^{N_{r}-1}\) to discarded values for state \(D^{2}\). After this transformation, we have information on both sides of the  
Figure 4: Relation between encryption, straight decryption and equivalent decryption. AddRoundKey in round 1 of the decryption sequence. We can vote to discard possible values of the decryption round key. We vote to those values, which, once the decryption state is transformed into the encryption state, would lead to a memory access on the unused lines. The least voted value for each byte is the decryption round key. Both the encryption and decryption keys are related and one can be obtained from the other applying the InvMixColumns operation, or an equivalent operation depending on the direction of the conversion. As a result of this information processing, we know two consecutive round keys; that is, the full AES-256 key. This algorithm could be applied recursively for the whole encryption/decryption process, as the cache information is applicable to the whole encryption. Using this encryption-by-decryption cache attack on AES-256, we obtain the key with fewer than 10,000 samples in the best scenario. We provide further details in Section 4. ```
0:\(\overline{X}_{0}\), \(\overline{X}_{1}\), \(\overline{X}_{2}\), \(\overline{X}_{3}\), \(\overline{S}^{N_{t}+1}\) and \(\mathbf{K}^{N_{t}}\)\(\triangleright\) Information about the accesses, ciphertext and last round key. 0:\(\mathbf{Kd}_{ij}^{1}\)\(\triangleright\) Secret decryption key values
1:\(\mathbf{Kd}^{0}\) = \(\mathbf{K}^{N_{t}}\)
2:for\(l\) = 0 to 256 do
3: CKd\({}_{ij}^{1}\)\([l]\) = 0; \(\triangleright\) Initialization of the candidates array
4:endfor
5:for\(t\) = 0 to number of encryptions do
6:if\(\overline{X}_{i}\)\([t]\) == 0 then
7: D\({}^{0}\) = \(\overline{S}^{N_{t}+1}\)\([t]\);
8: D\({}^{1}\) =D\({}^{0}\)\(\oplus\)\(\mathbf{Kd}^{0}\);
9:for\(j\) = 0 to 4 do
10:\(\mathbf{IV}_{j}^{1}\)=\(\mathbf{Td}_{0}\)\(\left[D_{0,j}^{1}\right]\)\(\oplus\)\(\mathbf{Td}_{1}\)\(\left[D_{1,j-1}^{1}\right]\)\(\oplus\)\(\mathbf{Td}_{2}\)\(\left[D_{2,j-2}^{1}\right]\)\(\oplus\)\(\mathbf{Td}_{3}\)\(\left[D_{3,j-3}^{1}\right]\)\(\triangleright\) Obtain intermediate value
11:endfor
12:for\(l\) = 0 to n do\(\triangleright\) n stands for the number of entries that a cache line holds
13: CKd\({}_{ij}^{1}\) = \(\left[\mathbf{IV}_{ij}^{1}\oplus S_{RD}\)\([l]\right]\) ++; \(\triangleright\) Vote for discard key candidate
14:endfor
15:endif
16:endfor
17:return argmin(CKd\({}_{ij}^{1}\)); \(\triangleright\) The candidate with the fewest votes for discard is the secret key. ```  
**Algorithm 3** Recovery algorithm for key byte \(\mathbf{Kd}_{i,j}^{1}\).