Ideas to Think About

This week was fall break for Princeton (which coincided with Hurricane Sandy. It's amazing that Princeton can plan its academic calendar around natural disasters). The week before that, Eva and I met with Professor Ruby Lee and Professor Cuff to discuss some approaches to tackling this project. I will present some of these here. 

From Professor Lee's perspective, there are four main questions we should be asking in this project:

1. How do we make the cache-timing side-channel attacks go faster?
2. What are the root causes that allow this attack to work?
3. How can we defend against these attacks?
4. What kinds of quantitative metrics can we use to measure the amount of information leakage? 

(If you don't know what the cache-timing side-channel attack is, see post below titled Project Description.)

The question that I would most like to answer for this project is the fourth one. (Eva and I also currently believe it is the easiest one to answer). We can narrow down question 4 to the following: What is the equivocation of the key given a set of N timing data?

Professor Cuff gave us some ideas about how we can answer this. He suggested that for the attack, we assume that only the plaintext and the timing data is known. If we assume that the attacker knows both the plaintext and ciphertext, then given infinite resources the attacker will be able to figure out the key. This would create a degenerate problem. Professor Cuff also suggested that we look into ideas of hypothesis testing. Particularly, he recommended using Sanov's theorem.

I am currently looking into some of the ideas Professor Cuff proposed. Looking at the problem through hypothesis testing is makes sense, since for any variation of the cache-timing attack, the attacker needs to decide between possible key distributions at some point. Therefore, using some already developed theories in hypothesis testing, we may be able to find some kind of bound on the amount of information leaked. 

If we were analyzing the first-round-attack variation of the cache-timing attack, then we can break down the problem by only looking at 4 bit segments (or nibbles) at a time. Then for each key nibble, we would only have to try 16 hypotheses to determine the key nibble. This is much more tractable than trying hypotheses on the whole length of the key, which would be 2^128 hypotheses. 

Don't have a good brain teaser question for this week. I'll try to find one for a later post.

For those not familiar with cryptography, note that the plaintext is the input to a encryption system and the output is the ciphertext. The key determines what the ciphertext will be. The goal of the most cipher attacks is to try to extract the key. Now, given the plaintext and the resulting ciphertext, the key is uniquely determined. However, calculating the key from the just plaintext and ciphertext is too computationally intensive to be feasible.