Technique allows full recovery of 2048-bit RSA key stored in Amazon’s EC2 service.
Piercing a key selling point of commercial cloud computing services, computer scientists have devised a hack that allows an attacker using Amazon’s EC2 platform to steal the secret cryptographic keys of other users.
The proof-of-concept attack is significant because Amazon Web Services and many other cloud service providers already blocked a previous key-recovery attack on co-located virtual machines that was unveiled in 2009. The paper was one of the first to highlight the security risks that come when someone uses the same physical piece of hardware as an advanced attacker. Cloud providers and makers of cryptography and virtual-machine software patched many of the weaknesses that made the attack possible. As a result, many of the techniques that gave the 2009 attack a high degree of accuracy are no longer possible.
Now a separate team of researchers has constructed a new method for recovering the full private key used in a modern implementation of the widely used RSA crypto system. Like the 2009 work, the new research implements a CPU cache attack across two Amazon accounts that happen to be located on the same chip or chipset. They recently used their technique to allow one Amazon instance to recover the entire 2048-bit RSA key used by a separate instance, which they also happened to control. The newer technique works by probing the last level cache (LLC) of the Intel Xeon processor chipsets used by Amazon computers.
In a recently published paper, the scientists wrote:
This work presents a full key recovery attack on a modern implementation of RSA in a commercial cloud and explores all steps necessary to perform such an attack. In particular, the work first revisits the co-location problem. Our experiments show that the co-location techniques presented in  have been addressed by AWS and no longer are a significant indicator for co-location. In addition, we present new techniques that show that co-location is still detectable in 2015 by using other shared resources such as LLCs. Once co-located, we exploit the LLC to recover the secret key of a modern sliding-window exponentiation based implementation of RSA, across cores and without relying on deduplication. We expand beyond the techniques presented in [two papers published earlier this year] and show that a detailed study of the LLC structure of the targeted processor yields a much more efficient attack. In particular, we reverse engineer the LLC non-linear slice selection algorithm of Intel Xeon E5- 2670 v2 chipset, which is dominant on Amazon EC2. Finally, we present several techniques necessary for a cache attack to succeed in a public cloud. Most notably, we present methods to filter noise from the observed leakage at two levels: (i) by using an alignment filter to reduce temporal noise introduced by co-residing processes and the OS, (ii) by rejecting false detections using a threshold technique on the aligned traces. Finally we present an error correction algorithm that exploits dependencies between the public key and the observed private key to remove remaining errors and to recover error free RSA keys.
The attack relies on side channel analysis in which attackers extract a secret decryption key based on clues leaked by electromagnetic emanations, data caches, or other manifestations of a targeted cryptographic system. The side channel exploited came from a table lookup in Libgcrypt/gnupgp crypto library, which has since been patched. Other crypto apps and libraries likely contain the same weakness Libgcrypt did, so the attack remains viable. Such hacks require a large amount of expertise and quite possibly a fair amount of luck, since the attackers must run their code on the same piece of hardware storing the targeted RSA key. That means it’s unlikely the exploit will be actively used in the near future.
Still, the technique is sure to concern lawyers and security professionals, particularly those who are required to comply with government-mandated cryptography certifications or federal privacy laws such as the Health Insurance Portability and Accountability Act. The researchers presented several methods for preventing the attack, mainly by deploying stronger isolation in public cloud services.