Paper 2006/288

Predicting Secret Keys via Branch Prediction

Onur Aciicmez, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Currently under the review process of CT-RSA conference
Keywords
Branch PredictionModular ExponentiationMontgomery MultiplicationRSASide Channel AnalysisSimultaneous MultithreadingTrusted Computing
Contact author(s)
aciicmez @ eecs oregonstate edu
History
2006-08-25: revised
2006-08-24: received
See all versions
Short URL
https://ia.cr/2006/288
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/288,
      author = {Onur Aciicmez and Jean-Pierre Seifert and Cetin Kaya Koc},
      title = {Predicting Secret Keys via Branch Prediction},
      howpublished = {Cryptology ePrint Archive, Paper 2006/288},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/288}},
      url = {https://eprint.iacr.org/2006/288}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.