How do cache-timing attacks determine the secret keys of encryption algorithms?

In cache-timing attacks like prime+probe, attacking programs are able to discover the addresses of a victim program's data in main memory. These attacks are often used to determine the secret keys used by encryption algorithms like AES, but are unable to directly access the victim's data.

So my question is, how can the attacker infer the secret key just by knowing the addresses of the victim's data? Can someone please describe this process?

Thank you!

how can the attacker infer the secret key just by knowing the addresses of the victim's data?

Usually, another condition is required: that the address of the victim's data varies according to the secret key. Then knowing the address (thru observation of the cache) leaks something about the key.

In the question and the above, "the victim's data" needs not be data that the victim aims to encrypt, decrypt, or use as key. It often is something else manipulated as part of the encryption or decryption; like, part of a constant table being fetched during the encryption.

For example, in a naive implementations of AES using a 256-byte table to implement the SubBytes step, such leak can happen on the first round because the address of a byte fetched in the table is the XOR of the first plaintext byte and the first key byte, plus the table's base address.

Detailing: that step of AES encryption can be coded as blk0 = sbox[ blk0 ^ key0 ] where blk0 and key0 are byte variables, and sbox is a table of 256 bytes. In this, blk0 could be the first byte of an IV thus public, and the low-order byte of the address of the first byte of sbox would typically be determinable from the code. The address of the byte read in sbox is the quantity (blk0 ^ key0 ) + sbox that's internally computed and presented to the cache subsystem as address. Gaining knowledge of that address is enough to find key0.

Typically, the information learned at each step of a cache-timing attack is tiny and only indirectly related to the key. But millions of tiny leak can be correlated and lead to full key extraction.

Actually attacks get complicated, but these are the main ideas. I recommend reading Daniel J. Bernstein's Cache-timing attacks on AES.

• Isn't it more about T tables and rows of the cache? Fill the cache, wait for encryption, and see what is missing in your cache. Besides in the wild life, it is almost impossible to execute. All attacks in general assume that the attacker is alone with the victim. And the real issue is the co-location with the shared hardware if the victim is using a shared hardware. Commented Jul 14 at 22:07
• @kelalaka there are many variations of cache timing attacks. Some empty the cache and then see what is loaded; some fill the cache and then see what is evicted Please note that any amount of random interference can be reduced by running the attack many times and calculating averages. Commented Jul 15 at 20:37
• @StackExchangeSupportsIsrael yes. Now assume there is more than one entity doing constant encryption, What will you see? I just want to see one wild example. Commented Jul 15 at 21:01
• @kelalaka Since the attacker is spamming your system with garbage data to decrypt, they will see mostly the statistics of their own data, mixed with some random interference coming from the decryption of valid data. Commented Jul 15 at 21:03
• @scha: No. As part of AES encryption of something (not an address), some memory is read at an address that depends on the secret key. Information about that address yields information about the key.
– fgrieu
Commented Jul 16 at 5:47

Here is an attack that supposedly works against certain ARM processors: We want the hardware as fast as possible. If you load a cache line from memory, the processor scans the data in the cache line and looks for things that look like pointers. If your data contains pointers, then there is a good chance that your code will soon load the data pointed to. To make this faster, the processor loads the data pointed to into cache earlier. If the data is used, your code runs faster.

However, this pre-loading affects other processes. Data used by another process may have been removed from cache. So another process may be able to detect what happened. That’s the critical information: Another process may be malware. so you have malware that may be happen to detect that your cache line contains pointers.

That’s very, very little information. so it might require lots of statistics and guess work to recover encrypted data.📊

• Your wrote; "the processor scans the data in the cache line and looks for things that look like pointers. If your data contains pointers, then there is a good chance that your code will soon load the data pointed to. To make this faster, the processor loads the data pointed to into cache earlier. If the data is used, your code runs faster". That would invalidate a standard assumption made in devising security code: that among memory activities only accesses (including branches) to addresses dependent on secret data can create a timing side-channel. Any link?
– fgrieu
Commented Jul 15 at 6:55
• I believe this is referring to the recently discovered Go.Fetch vulnerability, which affects most of Apple's M series CPUs as well as, presumably, some Intel and AMD ones. The feature being exploited is "data-dependent memory prefetch". Commented Jul 15 at 7:26