Personal computers are mostly used by a single person or shared between a group of users that trust each other, in cloud computing users usually do not trust each other: the owner of one process may have a great interest in the encryption keys used by a process owned by another user. Since the OS provides separate address space for each process, it may seem that the attacker has no way to steal the key. Turns out the attack may be practical.
To understand how the attack works we need to recall how memory is accessed by a program: Before requesting data from a memory chip, processor checks whether the data was recently accessed and saved in the cache. If the data is in the local cache, it can be accessed hundred times faster than otherwise. To make the implementation easier, the cache is designed in such a way that each memory location is allowed to be cached only in few places: to check that a memory location is cached, only these few places need to be checked.
Software implementations of the AES cipher commonly employ a look-up table. Which places in this table are accessed depends on which data is encrypted and which key is used. If an attacker, by accessing memory in his address space and checking how long it takes, can deduce what parts of the look-up table were accessed, he may deduce the key.
Cache-based side-channel attacks (SCA) against AES are known for a long time, what is new is the practicality of the attack:
[Our] spy process neither needs to learn the plain- or ciphertexts involved, nor their probability distributions in order [to] recover the secret key.
We describe how besides the key also the plaintext can be recovered without knowing the ciphertexts at all
We have a fully working implementation of our attack techniques against the 128-bit AES implementation of OpenSSL 0.9.8n on Linux. It is highly efficient and is able to recover keys in realtime. More precisely, it consists of two phases: in an [observation] phase, which lasts about 2.8 seconds on our test machine, about 100 encryptions have to be monitored. Then, an offline analysis phase, lasting about 3 minutes recovers the key.
Usually, implementing a counter-measure for SCA makes implementation slower, fortunately, the new processors give us a good way to prevent the attack and improve the performance simultaneously: AES Instruction Set (an extension to the x86 instruction set architecture for microprocessors from Intel and AMD) is already used by many software packages.
