## 3 Attacks on AES
### Information Processing  
This final step is common for all the attacks. In this stage, our approach differs from previous attack strategies. Traditional approaches for the considered attacks take into account if the data stored in the monitored cache line has been used by the victim. In contrast, we consider the opposite situation, i.e., the victim has not used that data. Our approach is based on the following observations:  
* Whenever the retrieved information shows that the victim has used the considered data, they could have been used during the last round or during any of the remaining ones. Thus, whenever the data are used in a different round, this approach introduces \"noise\". On the other hand, if a monitored cache line has not been accessed during the encryption, neither has it been accessed in the last round nor in any other round. * Speculative execution of pieces of code, or prefetching of the data that the processor believes are going to be used in the near future, may involve that the attacker sees in the cache data that have not been used by the victim (false positive). Nonetheless, to obtain a false positive in the non-access approach, the data have to be used during the last round of the encryption and then flushed away by other process during the short period of time after the end of the encryption and before the recovering step. * Each non-access sample reduces the key search space discarding up to \(n^{4}\) key values (\(n\) equals to 16 table entries stored in the cache line, which are used to obtain 4 output bytes). Thus, we obtain information from each of the samples. In contrast, when considering accesses, only when one candidate value towers over the rest, the retrieved information is useful to retrieve the secret key. * The information obtained this way is more likely to be applicable to all the rounds of an encryption, or at least to the penultimate round, as it refers to the whole encryption, so we can use this information to retrieve longer keys (192 or 256 bits). We have seen in Section 3.2 that each table Te is accessed four times during each round. Therefore, the probability of not accessing a concrete cache line within an encryption is provided by Equation (1), where \(n\) represents the number of table entries a cache line can hold, and \(N_{r}\) the number of rounds of the algorithm. Particularly, in our case, where the size of a cache line is 64 bytes, \(n\) is 16 (each entry of  
Figure 2: Timing information obtained when attacking AES in the Reload and Probe steps in our test machine. The threshold is shown in red. Te has 32-bits) and the number of rounds (\(N_{r}\)) for AES-128 is 10. Consequently, the probability of not accessing the cache line is 7.5%. This means that one of each fourteen encryptions performed gives us useful information. \[Pr[no\ access\ Te_{i}]=\left(1-\frac{n}{256}\right)^{N_{r}+4} \tag{1}\]  
As stated before, we focus on the last round of the encryption process. This round includes SubBytes, ShiftRows and AddRoundKey operations. Referred to the last round input state and the T-tables, we can express an output element by \(S_{i,j}^{N_{r}+1}=K_{i,j}^{N_{r}}\oplus\mathtt{Te}_{i+2}\left[s_{i,j+i}^{N_{ r}}\right]\). When a cache line has not been used during the encryption, we can discard all the key values which, given an output byte, would have had to access any of the Te-table entries hold in the mentioned cache line. For example, given a ciphertext byte \"0F\" and a cache line holding \"01\", \"AF\", \"B4\", and \"29\", if this line remains unused after performing the encryption, we discard the key byte values 0F\(\oplus\)01, 0F\(\oplus\)AF, 0F\(\oplus\)B4 and 0F\(\oplus\)29. As shown in Section 3.2, the same table is used to obtain all the elements of the row of the output state. This means each \(\mathtt{Te}_{i}\) table also discards the \(K_{i,j}\) values with the same \(i\) value independently of the \(j\) index. A general description of the key recovery algorithm for the last round key is provided in Algorithm 2.