International Association for Cryptologic Research

International Association
for Cryptologic Research


Onur Aciiçmez

Affiliation: Samsung Electronics


New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures
Software based side-channel attacks allow an unprivileged spy process to extract secret information from a victim (cryptosystem) process by exploiting some indirect leakage of ``side-channel'' information. It has been realized that some components of modern computer microarchitectures leak certain side-channel information and can create unforeseen security risks. An example of such MicroArchitectural Side-Channel Analysis is the Cache Attack --- a group of attacks that exploit information leaks from cache latencies. Public awareness of Cache Attack vulnerabilities lead software writers of OpenSSL (version 0.9.8a and subsequent versions) to incorporate countermeasures for preventing these attacks. In this paper, we present a new and yet unforeseen side channel attack that is enabled by the recently published Simple Branch Prediction Analysis (SBPA) which is another type of MicroArchitectural Analysis. We show that modular inversion --- a critical primitive in public key cryptography --- is a natural target of SBPA attacks because it typically uses the Binary Extended Euclidean algorithm whose nature is an input-centric sequence of conditional branches. Our results show that SBPA can be used to extract secret parameters during the execution of the Binary Extended Euclidean algorithm. This poses a new potential risk to crypto-applications such as OpenSSL, which already employs Cache Attack countermeasures. Thus, it is necessary to develop new software mitigation techniques for BPA and incorporate them with cache analysis countermeasures in security applications. To mitigate this new risk in full generality, we apply a security-aware algorithm design methodology and propose some changes to the CRT-RSA algorithm flow. These changes either avoid some of the steps that require modular inversion, or remove the critical information leak from this procedure. In addition, we also show by example that, independently of the required changes in the algorithms, careful software analysis is also required in order to assure that the software implementation does not inadvertently introduce branches that may expose the application to SBPA attacks. These offer several simple ways for modifying OpenSSL in order to mitigate Branch Prediction Attacks.
Yet Another MicroArchitectural Attack: Exploiting I-cache
Onur Aciicmez
MicroArchitectural Attacks (MA), which can be considered as a special form of Side-Channel Analysis, exploit microarchitectural functionalities of processor implementations and can compromise the security of computational environments even in the presence of sophisticated protection mechanisms like virtualization and sandboxing. This newly evolving research area has attracted significant interest due to the broad application range and the potentials of these attacks. Cache Analysis and Branch Prediction Analysis were the only types of MA that had been known publicly. In this paper, we introduce Instruction Cache (I-Cache) as yet another source of MA and present our experimental results which clearly prove the practicality and danger of I-Cache Attacks.
A Major Vulnerability in RSA Implementations due to MicroArchitectural Analysis Threat
Onur Aciicmez Werner Schindler
Recently, Aciicmez, Koc, and Seifert have introduced new side-channel analysis types,namely Branch Prediction Analysis (BPA) and Simple Branch Prediction Analysis (SBPA), which take advantage of branch mispredictions occur during the operations of cryptosystems [4, 5]. Even more recently, Aciicmez has developed another attack type, I-cache analysis, which exploits the internal functionalities of instruction/trace caches [1]. These MicroArchitectural Analysis (MA) techniques, more specifically SBPA and I-cache Analysis, have the potential of disclosing the entire execution flow of a cryptosystem as stated in [4, 1]. Our focus of interest in this paper is that these attacks can reveal whether an extra reduction step is performed in each Montgomery multiplication operation. First Walter et. al. and then Schindler developed attacks on RSA, which result in total break of the system if the occurrences of extra reduction steps can be determined with a reasonable error rate [39, 30, 29]. These attacks may be viewed as theoretical in the sense that neither Walter et. al. nor Schindler implemented actual attacks on real systems but instead they assumed that side-channel information obtained via power and timing analysis would reveal such occurrences of extra reduction step. In this paper we adjusted the attack from [30] to the current OpenSSL standard and put this attack into practice, proving its practicality via MA. The second part of the attack exploits the previously gathered information on the required extra reductions in an optimal way, using advanced stochastic methods as the formulation and analysis of stochastic processes. Our results show the feasibility of compromising current RSA implementations such as OpenSSL. After we shared our result with OpenSSL development team, they included a patch into the stable branch ([45]), which allows users to compile an OpenSSL version that is resistent against our attack ([46]). In particular, this patch will affect the upcoming version of 0.9.8f. We also contacted the US CERT who informed software vendors. The US CERT assigned the vulnerability explained in this paper CVE name CVE-2007-3108 and CERT vulnerability number VU#724968, and they issued a vulnerability note ([47–49]). We point out that this publication appeared in accordance with the OpenSSL development team. Several countermeasures have been developed and employed in widely used cryptographic libraries like OpenSSL to mitigate such side-channel analysis threats. However the current implementations still do not provide sufficient protection against MicroArchitectural Analysis, despite of all the sophisticated mitigation techniques employed in these implementations. In this paper, we will show that one can completely break the RSA implementation of the current OpenSSL version (v.0.9.8e) even if the most secure configuration, including all of the countermeasures against side-channel and MicroArchitectural analysis, is in place. We have only analyzed OpenSSL, thus we currently do not know the strength of other cryptographic libraries. Other libraries and software products need to be thoroughly analyzed and appropriately modified if it is necessary. At least, developers of the current software applications that rely on OpenSSL RSA implementation need to update their products based on the recent OpenSSL changes. Our results indicate that MicroArchitectural Analysis threatens at least 60% of the internet traffic worldwide and the current systems should be analyzed thoroughly to evaluate their overall strength against MicroArchitectural Analysis ([44]). We will eventually discuss appropriate countermeasures that must be employed in security systems.
Trace-Driven Cache Attacks on AES
Onur Ac\i{}i\c{c}mez Çetin Kaya Koç
Cache based side-channel attacks have recently been attracted significant attention due to the new developments in the field. In this paper, we present efficient trace-driven cache attacks on a widely used implementation of the AES cryptosystem. We also evaluate the cost of the proposed attacks in detail under the assumption of a noiseless environment. We develop an accurate mathematical model that we use in the cost analysis of our attacks. We use two different metrics, specifically, the expected number of necessary traces and the cost of the analysis phase, for the cost evaluation purposes. Each of these metrics represents the cost of a different phase of the attack.
Predicting Secret Keys via Branch Prediction
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.
On the Power of Simple Branch Prediction Analysis
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.

Program Committees

CHES 2015
CHES 2014