Cryptology ePrint Archive: Report 2006/288

Predicting Secret Keys via Branch Prediction

Onur Aciicmez and Jean-Pierre Seifert and Cetin Kaya Koc

Abstract: This paper presents a new software side-channel attack - enabled by the branch prediction capability common to all modern high-performance CPUs. The penalty payed (extra clock cycles) for a mispredicted branch can be used for cryptanalysis of cryptographic primitives that employ a data-dependent program flow. Analogous to the recently described cache-based side-channel attacks our attacks also allow an unprivileged process to attack other processes running in parallel on the same processor, despite sophisticated partitioning methods such as memory protection, sandboxing or even virtualization. We will discuss in detail several such attacks for the example of RSA, and experimentally show their applicability to real systems, such as OpenSSL and Linux. More specifically, we will present four different types of attacks, which are all derived from the basic idea underlying our novel side-channel attack. Moreover, we also demonstrate the strength of the branch prediction side-channel attack by rendering the obvious countermeasure in this context (Montgomery Multiplication with dummy-reduction) as useless. Although the deeper consequences of the latter result make the task of writing an efficient and secure modular expeonentiation (or scalar multiplication on an elliptic curve) a challenging task, we will eventually suggest some countermeasures to mitigate branch prediction side-channel attacks.

Category / Keywords: public-key cryptography / Branch Prediction, Modular Exponentiation, Montgomery Multiplication, RSA, Side Channel Analysis, Simultaneous Multithreading, Trusted Computing

Publication Info: Currently under the review process of CT-RSA conference

Date: received 23 Aug 2006, last revised 25 Aug 2006

Contact author: aciicmez at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20060825:160427 (All versions of this report)

Short URL: ia.cr/2006/288

Discussion forum: Show discussion | Start new discussion