International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Power of Simple Branch Prediction Analysis

Authors:
Onur Aciicmez
Çetin Kaya Koç
Jean-Pierre Seifert
Download:
URL: http://eprint.iacr.org/2006/351
Search ePrint
Search Google
Abstract: Very recently, a new software side-channel attack, called Branch Prediction Analysis (BPA) attack, has been discovered and also demonstrated to be practically feasible on popular commodity PC platforms. While the above recent attack still had the flavor of a classical timing attack against RSA, where one uses many execution-time measurements under the same key in order to statistically amplify some small but key-dependent timing differences, we dramatically improve upon the former result. We prove that a carefully written spy-process running simultaneously with an RSA-process, is able to collect during one \emph{single} RSA signing execution almost all of the secret key bits. We call such an attack, analyzing the CPU's Branch Predictor states through spying on a single quasi-parallel computation process, a \emph{Simple Branch Prediction Analysis (SBPA)} attack --- sharply differentiating it from those one relying on statistical methods and requiring many computation measurements under the same key. The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA against side-channel attacks are, in the context of SBPA attacks, totally useless. Additional to that very crucial security implication, targeted at such implementations which are assumed to be at least statistically secure, our successful SBPA attack also bears another equally critical security implication. Namely, in the context of simple side-channel attacks, it is widely believed that equally balancing the operations after branches is a secure countermeasure against such simple attacks. Unfortunately, this is not true, as even such ``balanced branch'' implementations can be completely broken by our SBPA attacks. Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor. Thus, we conclude that SBPA attacks are much more dangerous than previously anticipated, as they obviously do not belong to the same category as pure timing attacks.
BibTeX
@misc{eprint-2006-21842,
  title={On the Power of Simple Branch Prediction Analysis},
  booktitle={IACR Eprint archive},
  keywords={implementation / Branch Prediction, Modular Exponentiation, RSA, Side Channel Analysis, Simultaneous Multithreading, Trusted Computing},
  url={http://eprint.iacr.org/2006/351},
  note={Currently under review process onur.aciicmez@gmail.com 13475 received 18 Oct 2006, last revised 23 Nov 2006},
  author={Onur Aciicmez and Çetin Kaya Koç and Jean-Pierre Seifert},
  year=2006
}