The discovery of a high-impact side-channel attack is bad news for vulnerable systems, as it affects their design in an unexpected way. Side channel-attacks have been studied for virtual machines with very limited success up to now. Co-hosting servers with different security requirements does not feel right (it’s better to be safe than sorry: just don’t do it!). Still, extracting keys across such a side channel is intuitively highly unlikely. Even so, this paper shows how it can be done.

The side channel the authors use is neither new nor unexpected: the processor cache. A first hurdle is that the cache channel only leaks information if very short time intervals can be inspected. They needed to reduce the observation granularity down to what is required for meaningful measurements. Using inter-processor interrupts makes that possible.

Even then, there is significant noise as the attack is executed on real-life software and operating systems. The authors assume knowledge of the software on the victim virtual machine (VM), so that they can train a classification engine that will detect the interesting parts and at the same time eliminate noise. In this study, a private key is the target. Using the private key leads to recognizable and different code sequences whether the key has a 0 or a 1 in a given position: square for a 0, and square and multiply for a 1. Analyzing a code fragment via its cache use results in a sequence of multiply, square, or unknown operations. This is the raw data that is collected multiple times and is used to construct the key.

The first component in the chain producing the key from the basic trace data is a multiclass support vector machine. The next component uses hidden Markov models. Finally, the results are post-processed using domain knowledge. The outcome can best be described as strings with known elements and unknown positions. These strings are then aligned to form the full sequence of interest. In this paper, that result is a sequence of 1, 0, or unknown bits. The remaining unknowns are detected via brute force. The authors succeeded in ending with a very limited search space (less than 10,000 tries), with data obtained from just a few hours of data collection.

The paper highlights the risks of shared environments convincingly. It also provides novel ideas for exploiting side channels and other partial, unreliable data leaks.