listen to this article:
One is often asked as a Professor to explain some complex aspect of security in an easy way. This week I saw an interesting talk which explained cache attacks via means of cookery. So let me share this with you.
Imagine you are involved in a cookery contest with someone, as it is cryptography we will call this other person Alice. You both have an assistant who can go get items for you as you cook. The kitchen in which the competition is being held has a single small fridge and cupboard. The rules of the competition are as follows. You both have to cook a dish, and your assistant can be told to go get ingredients for you. The assistant will go get the ingredients from the fridge or cupboard, but if they do not find the ingredients there then they need to go fetch them from the shop. Clearly going to the shop takes longer than going to the fridge and cupboard. If after your assistant returns from the shop they find the fridge or cupboard full, they are allowed to chuck stuff in the fridge and cupboard into the bin so as to make space.
You decide that it would help your chances of winning if you knew what dish Alice was cooking before the “big reveal” at the end of the competition. So the first thing you do is send your assistant to the shop with a list of everything you need for your recipe. Suppose you are making beef stew so you ask for meat, potatoes, carrots, onions, etc. The assistant goes to the shop and puts the ingredients into the fridge and cupboard, but you ask the assistant not to buy any onions.
You suspect that Alice is either going to make beef stew or pancakes. If it is beef stew you know you are going to have to try harder to win, but you think Alice’s pancakes are not that good. So if Alice chooses to make pancakes you can be more relaxed.
As you cook you require the onions to chop. So you ask your assistant to go get the onions from the cupboard. Now two things can happen. If they return quickly, which means they did not need to go to the shop, then you know Alice is making a recipe with onions in it. Because the only way onions could have got into the cupboard would have been if her assistant had put some there. On the other hand, if they return slowly then they must have gone to the shop, so either Alice’s assistant never bought onions in the first place, or the onions they bought have already been used by Alice. Repeating this process we can try and figure out what Alice is cooking.
This is the basics of a cache attack. The fridge/cupboard is the local memory store on the microprocessor (the cache), whereas the shop is the main memory (the RAM). In a cache attack, we measure the time difference between fetching data, just as we measured in the scenario above the time it took for our assistant to fetch the ingredients.
In the security literature, you will also find a term related to cache attacks, called “Flush-and-Reload”. We can see this in action in our kitchen example above as follows. Now suppose you ask your assistant to go buy 100 bottles of milk for use later. They dutifully go to the shop, buy the bottles and return to the kitchen. They find that the fridge has not enough space for 100 bottles of milk, so they put the contents of the fridge into the bin, and place your bottles in the fridge. Around ten minutes later you ask for some eggs, and the assistant returns very quickly. This means the fridge had eggs in it. So at this point, you know that Alice sends her assistant to get some eggs in those ten minutes. What we did was “flush” the fridge’s contents by filling it with milk, and then we saw that getting eggs was quicker than it should have been. Which led us to conclude that Alice had in the meantime requested some eggs.
Of course, this analogy, like all analogies, is not quite correct. But I hope it helps explain some things about these types of attacks. Let us know if you have other cool every-day analogies for complex ideas in computer security.