AES cache-timing attacks and nonce-based operation modes

Question

As I understand it, AES cache-timing attacks exploit the execution time variations due to cache hits/misses, especially the ones depending on the SBox look-up tables which are key-related.

To mount such an attack, does an attacker need to have knowledge of the algorithm input? If so, are such attacks still relevant against operation modes such as CCM or GCM where the input nonce has a specific format and might be not transmitted (at least a part of it)?

In the paper of Daniel J. Bernstein one can read:

By considering table lookups in (e.g.) the last AES round, develop an attack that works with highly structured AES inputs (as in, e.g., counter mode) rather than random-looking AES inputs (as in, e.g., CBC).

Have related works been published yet?

Answer 1

There are multiple ways you can get the key in attacking AES.

Let's say you have the known cipher-text, $ct$, and a list of all S-box lookups used in the last round of AES (maybe from a cache-attack).

We know that $ct$ is equal to $k \oplus y$, where $y$ is the intermediate state after the last S-box computation.

Now, we can go through each byte of $ct$, and for each byte $ct_i$ we attempt a possible key value $k_i$ for each value 0x00-0xff. Then we can get a possible $y_i = ct_i \oplus k_i$. If we run an inverse S-box computation on this $y_i$ and it is contained in the list of S-box lookups we received earlier, then we know that this $k_i$ is a possible byte for the key $k$.

If we do this operation many times through many runs of AES, then we can develop a table of possible $k_i$ values for each byte in $k$. We can use the mode of each key byte $k_i$ to build our correct key $k$. The accuracy of this attack obviously increases with more runs of AES.

As seen in this attack, you do not need to know the input of AES, only the output $ct$ and some last-round S-box information.

Hope this helps.