On the power of simple branch prediction analysis

By Onur Aciiçmez, Ç. Koç, Jean-Pierre Seifert. ACM Asia Conference on Computer and Communications Security, 2007

301 citations recorded by the source corpus.

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 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 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.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/55520e5f45a94a332097b750afd730ef57dd9168

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

Citations in the corpus

BranchScope: A New Side-Channel Attack on Directional Branch Predictor (2018, background): “Previous work has specifically targeted the BTB to create side channels [1, 3, 21, 36].”
FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack (2014, background): “In particular, the code is likely to be vulnerable to Branch Prediction Analysis [3].”
Yet another MicroArchitectural Attack:: exploiting I-Cache (2007, methodology): “On simultaneous multi-threading systems, the spy routine does not even need to interrupt the cipher execution and can observe it “on-the-fly” as done in [32, 1].”
Inferring Fine-grained Control Flow Inside SGX Enclaves with Branch Shadowing (2016, background): “, the LBR) or measuring branch misprediction penalty [3, 12, 13].”
Last-Level Cache Side-Channel Attacks are Practical (2015, methodology): “This technique has been used for attacks against several processor caches, including the L1 data cache [28, 31, 34, 47], L1 instruction cache [1, 2, 4] and the branch prediction cache [3].”
HomeAlone: Co-residency Detection in the Cloud via Side-Channel Analysis (2011, unknown): “Besides the data cache, other architectural side channels have been exploited in cryptanalysis; as mentioned above, these include the instruction cache [4], the branch target cache [6], [7], and shared functional units [46], [9].”
A Hardware Design Language for Timing-Sensitive Information-Flow Security (2015, background): “Attacks have also been shown that exploit timing channels arising from other components: instruction and data caches [2], branch predictors and branch target buffers [3], and shared functional units [44].”
CacheZoom: How SGX Amplifies The Power of Cache Attacks (2017, background): “The Flush+Reload is constrained by the memory deduplication requirement.”
Cross-VM side channels and their use to extract private keys (2012, background): “The attacker program monitors usage of a shared architectural component to learn information about the key, e.g., the data cache [36,43], instruction cache [1,2], ﬂoating-point multiplier [5], or branch-prediction cache [3].”
Raccoon: Closing Digital Side-Channels through Obfuscated Execution (2015, background): “Some application-level information leaks are beyond the application’s control, for example, an adversary reading a victim’s secrets through the /proc ﬁlesystem [13], or a victim’s ﬂoating point registers that are not cleared on a context switch [2].”