A Simplified Model

Recap: We are trying to analysis the cache-timing side-channel attack which is used to extract the key from AES encryption. What happens is that as each plaintext is encrypted, the attacker can measure the time it takes the cipher to complete the encryption. Since AES encryption uses table look-ups, the algorithm will need to make calls to the cache. Since there can be cache-hits and cache-misses, the values which are looked up will have some relationship with the times it takes to look up the each value in the cache. We can use this information to extract the key. 

There are may different ways an attacker can used the timing information. We will focus on one model at a time. The current model we will look at is the first round model described by Bonneau's paper[1]. In this post, I will explain some of the ideas I have to simplify this model in order to make the problem easier to analyze. 

Now, since we are looking at the first round attack, we will the making the following assumption. If two look-ups that occur in the first round look up the same index, then the second of these look-ups is likely to have a cache hit. Therefore if, two of the same indices are looked-up in the first round, then the total time will on average be shorter than if all the values looked-up are different. 

So let us specifically consider two different indices being looked-up in the first round, say indices i_0 and i_1. If we know that i_0 = i_1, then we can figure out certain bits of the key. We we want to figure out, if given timing data, whether we can infer if i_0 = i_1.

The problem is, there will be other cache-hits and cache-misses that occur in other look-ups, so it is very hard to tell if i_0 = i_1. However, what we can do is model the times that come from the other look-ups as noise. We can approximate the distribution of the timing data for one encryption, given that i_0 = i_1 and that i_0 != i_1.

To do this, let us make certain assumptions on the system doing the encryption. We will suppose that the time for each encryption, excluding the time it takes to process the cache-hits and misses, is the same each time. We will assume that each cache-hit takes a fixed H time units to process, and each miss takes a fixed M time units to process (not true in hierarchy memory models). Let M - H = D. Therefore the distribution of any encryption is in step sizes of D. In this situation, the timing data can exactly tell us the number of misses. 

We know that there are 160 table look-ups in AES encryption. So, here we can model the distribution of timing data as a Bernoulli distribution, setting the probability of a cache-miss to be P. Even though 160 is a small number, the Bernoulli distribution can be approximated by a Gaussian. Depending on if i_0 = i_1 or i_0 != i_1, we have slightly different distributions, and we can use these distributions to do hypothesis testing and to find the probability of error given a number of samples. 

However, we made many assumptions in the model, which may not correctly model how a system would behave in the real world. We will need to look into these assumptions some more.

Okay, here is a brain teaser for this post. This is a USAMTS problem from some years ago.

Suppose that you have 14 coins, which all have a unique year written on them so that they can be distinguished. Now, only 7 of these coins are real. The other 7 are fake. Suppose real coins weigh 1 gram and fake coins weigh .9999 grams. You only have a strange futuristic scale to weigh these coins. The scale will compare two groups of coins and tell you which group is heavy. If the two groups are the same, then the scale returns all your coins. However, if one group is heavier than the other, the scale still tells you which group is heavier, but then the scale takes one coin uniformly at random from the heavier group and keeps it as payment. How can you use this scale to determine and keep in your possession one real coin. 


References:
[1] Bonneau, J., & Mironov, I. (2006). Cache-collision timing attacks against AES. Lecture Notes in Computer Science series 4249, 201-215.