BranchScope: A New Side-Channel Attack on Directional Branch Predictor

Abstract

We present BranchScope - a new side-channel attack where the attacker infers the direction of an arbitrary conditional branch instruction in a victim program by manipulating the shared directional branch predictor. The directional component of the branch predictor stores the prediction on a given branch (taken or not-taken) and is a different component from the branch target buffer (BTB) attacked by previous work. BranchScope is the first fine-grained attack on the directional branch predictor, expanding our understanding of the side channel vulnerability of the branch prediction unit. Our attack targets complex hybrid branch predictors with unknown organization. We demonstrate how an attacker can force these predictors to switch to a simple 1-level mode to simplify the direction recovery. We carry out BranchScope on several recent Intel CPUs and also demonstrate the attack against an SGX enclave.

References

1. O. Aciicmez, K. Koc, and J. Seifert. On the power of simple branch prediction analysis. In Symposium on Information, Computer and Communication Security (ASIACCS). IEEE, 2007.
2. O. Aciicmez, K. Koc, and J. Seifert. Predicting secret keys via branch prediction. In The cryptographers' track at the RSA conference, 2007.
3. Onur Aciiçmez, Shay Gueron, and Jean-Pierre Seifert. New branch prediction vulnerabilities in OpenSSL and necessary software countermeasures. In Cryptography and Coding, pages 185-203. Springer, 2007.
4. Thomas Allan, Billy Bob Brumley, Katrina Falkner, Joop Van de Pol, and Yuval Yarom. Amplifying side channels through performance degradation. In Proceedings of the 32nd Annual Conference on Computer Security Applications, pages 422-435. ACM, 2016.
5. Iosif Androulidakis and Gorazd Kandus. Feeling secure vs. being secure the mobile phone user case. In Global security, safety and sustainability&e-Democracy, pages 212-219. Springer, 2012.
6. Daniel J Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom. Sliding right into disaster: Left-to-right sliding windows leak. In International Conference on Cryptographic Hardware and Embedded Systems, pages 555-576. Springer, 2017.
7. Sarani Bhattacharya and Debdeep Mukhopadhyay. Fault Attack revealing Secret Keys of Exponentiation Algorithms from Branch Prediction Misses. Cryptology ePrint Archive, Report 2014/790, 2014.
8. David Brumley and Dan Boneh. Remote timing attacks are practical. Computer Networks, 48(5):701-716, 2005.
9. Jonathan Burket and Samantha Gottlieb. If-Conversion to Combat Control Flow-based Timing Attacks. 2014.
10. Youngsoo Choi, Allan Knies, Luke Gerke, and Tin-Fook Ngai. The impact of if-conversion and branch prediction on program execution on the intel® itanium processor. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 182-191. IEEE Computer Society, 2001.
11. Bart Coppens, Ingrid Verbauwhede, Koen De Bosschere, and Bjorn De Sutter. Practical mitigations for timing-based side-channel attacks on modern x86 processors. In Security and Privacy, 2009 30th IEEE Symposium on, pages 45-60. IEEE, 2009.
12. Victor Costan, Ilia A Lebedev, and Srinivas Devadas. Sanctum: Minimal Hardware Extensions for Strong Software Isolation. In USENIX Security Symposium, pages 857-874, 2016.
13. Jean-Francois Dhem, Francois Koeune, Philippe-Alexandre Leroux, Patrick Mestré, Jean-Jacques Quisquater, and Jean-Louis Willems. A practical implementation of the timing attack. In Smart Card Research and Applications, pages 167-182. Springer, 2000.
14. L. Domnitser, A. Jaleel, J. Loew, N. Abu-Ghazaleh, and D. Ponomarev. Non-Monopolizable Caches: Low-Complexity Mitigation of Cache Side-Channel Attacks. In ACM Transactions on Architecture and Code Optimization, Special Issue on High Performance and Embedded Architectures and Compilers, January 2012.
15. Marius Evers, Po-Yung Chang, and Yale N Patt. Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches. In ACM SIGARCH Computer Architecture News, volume 24, pages 3-11. ACM, 1996.
16. Dmitry Evtyushkin, Jesse Elwell, Meltem Ozsoy, Dmitry Ponomarev, Nael Abu Ghazaleh, and Ryan Riley. Iso-X: A flexible architecture for hardware-managed isolated execution. In Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, pages 190-202. IEEE Computer Society, 2014.
17. Dmitry Evtyushkin, Jesse Elwell, Meltem Ozsoy, Dmitry V Ponomarev, Nael Abu Ghazaleh, and Ryan Riley. Flexible hardware-managed isolated execution: Architecture, software support and applications. IEEE Transactions on Dependable and Secure Computing, 2016.
18. Dmitry Evtyushkin and Dmitry Ponomarev. Covert channels through random number generator: Mechanisms, capacity estimation and mitigations. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 843-857. ACM, 2016.
19. Dmitry Evtyushkin, Dmitry Ponomarev, and Nael Abu-Ghazaleh. Covert channels through branch predictors: a feasibility study. In Proceedings of the Fourth Workshop on Hardware and Architectural Support for Security and Privacy, page 5. ACM, 2015.
20. Dmitry Evtyushkin, Dmitry Ponomarev, and Nael Abu-Ghazaleh. Understanding and Mitigating Covert Channels Through Branch Predictors. ACM Transactions on Architecture and Code Optimization (TACO), 2015.
21. Dmitry Evtyushkin, Dmitry Ponomarev, and Nael Abu-Ghazaleh. Jump over ASLR: Attacking branch predictors to bypass ASLR. In Microarchitecture (MICRO), 2016 49th Annual IEEE/ACM International Symposium on, pages 1-13. IEEE, 2016.
22. Johannes Götzfried, Moritz Eckert, Sebastian Schinzel, and Tilo Müller. Cache Attacks on Intel SGX. 2017.
23. Daniel Gruss, Moritz Lipp, Michael Schwarz, Richard Fellner, Clémentine Maurice, and Stefan Mangard. KASLR is Dead: Long Live KASLR. In International Symposium on Engineering Secure Software and Systems, pages 161-176. Springer, 2017.
24. Daniel Gruss, Clémentine Maurice, Anders Fogh, Moritz Lipp, and Stefan Mangard. Prefetch side-channel attacks: Bypassing SMAP and kernel ASLR. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 368-379. ACM, 2016.
25. Daniel Gruss, Felix Schuster, Olya Ohrimenko, Istvan Haller, Julian Lettner, and Manuel Costa. Strong and Efficient Cache Side-Channel Protection using Hardware Transactional Memory. 2017.
26. D. Gullasch, E. Bangerter, and S. Krenn. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. In Security and Privacy (SP), 2011 IEEE Symposium on, pages 490-505, 2011.
27. Marcus Hähnel, Weidong Cui, and Marcus Peinado. High-Resolution Side Channels for Untrusted Operating Systems. In 2017 USENIX Annual Technical Conference (USENIX ATC 17), pages 299-312, Santa Clara, CA, 2017. USENIX Association.
28. Ralf Hund, Carsten Willems, and Thorsten Holz. Practical timing side channel attacks against kernel space ASLR. In Security and Privacy (SP), 2013 IEEE Symposium on, pages 191-205. IEEE, 2013.
29. Casen Hunger, Mikhail Kazdagli, Ankit Rawat, Alex Dimakis, Sriram Vishwanath, and Mohit Tiwari. Understanding contention-based channels and using them for defense. In High Performance Computer Architecture (HPCA), 2015 IEEE 21st International Symposium on, pages 639-650. IEEE, 2015.
30. Yeongjin Jang, Sangho Lee, and Taesoo Kim. Breaking kernel address space layout randomization with intel tsx. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 380-392. ACM, 2016.
31. Daniel A Jiménez and Calvin Lin. Dynamic branch prediction with perceptrons. In High-Performance Computer Architecture, 2001. HPCA. The Seventh International Symposium on, pages 197-206. IEEE, 2001.
32. Marc Joye and Sung-Ming Yen. The Montgomery powering ladder. In Cryptographic Hardware and Embedded Systems-CHES 2002, pages 291-302. 2002.
33. Mehmet Kayaalp, Dmitry Ponomarev, Nael Abu-Ghazaleh, and Aamer Jaleel. A high-resolution side-channel attack on last-level cache. In Design Automation Conference (DAC), 2016 53nd ACM/EDAC/IEEE, pages 1-6. IEEE, 2016.
34. Paul Kocher, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. Spectre Attacks: Exploiting Speculative Execution. ArXiv e-prints, January 2018.
35. Sangho Lee, Ming-Wei Shih, Prasun Gera, Taesoo Kim, Hyesoon Kim, and Marcus Peinado. Inferring fine-grained control flow inside SGX enclaves with branch shadowing. In Usenix Security Symposium, 2017.
36. Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown. ArXiv e-prints, January 2018.
37. Fangfei Liu, Qian Ge, Yuval Yarom, Frank Mckeen, Carlos Rozas, Gernot Heiser, and Ruby B Lee. Catalyst: Defeating last-level cache side channel attacks in cloud computing. In High Performance Computer Architecture (HPCA), 2016 IEEE International Symposium on, pages 406-418. IEEE, 2016.
38. Fangfei Liu, Yuval Yarom, Qian Ge, Gernot Heiser, and Ruby B Lee. Last-Level Cache Side-Channel Attacks are Practical. In 36th IEEE Symposium on Security and Privacy (S&P 2015), 2015.
39. Robert Martin, John Demme, and Simha Sethumadhavan. Timewarp: Rethinking timekeeping and performance monitoring mechanisms to mitigate side-channel attacks. ACM SIGARCH Computer Architecture News, 40(3):118-129, 2012.
40. Clémentine Maurice, Christoph Neumann, Olivier Heen, and Aurélien Francillon. C5: cross-cores cache covert channel. In International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, pages 46-64. Springer, 2015.
41. Scott McFarling. Combining branch predictors. Technical report, Technical Report TN-36, Digital Western Research Laboratory, 1993.
42. Frank McKeen, Ilya Alexandrovich, Alex Berenzon, Carlos V Rozas, Hisham Shafi, Vedvyas Shanbhogue, and Uday R Savagaonkar. Innovative instructions and software model for isolated execution. HASP@ISCA, 10, 2013.
43. Pierre Michaud, André Seznec, and Richard Uhlig. Trading conflict and capacity aliasing in conditional branch predictors. In ACM SIGARCH Computer Architecture News, volume 25, pages 292-303. ACM, 1997.
44. Ahmad Moghimi, Gorka Irazoqui, and Thomas Eisenbarth. CacheZoom: How SGX Amplifies The Power of Cache Attacks. arXiv preprint arXiv:1703.06986, 2017.
45. Thomaz Oliveira, Julio López, and Francisco Rodríguez-Henríquez. The Montgomery ladder on binary elliptic curves. Journal of Cryptographic Engineering, pages 1-18, 2017.
46. Erven Rohou, Bharath Narasimha Swamy, and André Seznec. Branch prediction and the performance of interpreters: don't trust folklore. In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, pages 103-114. IEEE Computer Society, 2015.
47. Michael Schwarz, Samuel Weiser, Daniel Gruss, Clémentine Maurice, and Stefan Mangard. Malware Guard Extension: Using SGX to Conceal Cache Attacks. arXiv preprint arXiv:1702.08719, 2017.
48. Hovav Shacham, Matthew Page, Ben Pfaff, Eu-Jin Goh, Nagendra Modadugu, and Dan Boneh. On the effectiveness of address-space randomization. In Proceedings of the 11th ACM conference on Computer and communications security (CCS), pages 298-307, 2004.
49. James E Smith. A study of branch prediction strategies. In Proceedings of the 8th annual symposium on Computer Architecture, pages 135-148. IEEE Computer Society Press, 1981.
50. Eric Sprangle, Robert S Chappell, Mitch Alsup, and Yale N Patt. The agree predictor: A mechanism for reducing negative branch history interference. In ACM SIGARCH Computer Architecture News, volume 25, pages 284-291. ACM, 1997.
51. Leif Uhsadel, Andy Georges, and Ingrid Verbauwhede. Exploiting hardware performance counters. In Fault Diagnosis and Tolerance in Cryptography, 2008. FDTC'08. 5th Workshop on, pages 59-67. IEEE, 2008.
52. Zhenghong Wang and Ruby B Lee. New cache designs for thwarting software cache-based side channel attacks. In ACM SIGARCH Computer Architecture News, volume 35, pages 494-505. ACM, 2007.
53. Johannes Winter. Trusted computing building blocks for embedded linux-based ARM trustzone platforms. In Proceedings of the 3rd ACM workshop on Scalable trusted computing, pages 21-30. ACM, 2008.
54. Yuanzhong Xu, Weidong Cui, and Marcus Peinado. Controlled-channel attacks: Deterministic side channels for untrusted operating systems. In Security and Privacy (SP), 2015 IEEE Symposium on, pages 640-656. IEEE, 2015.
55. Yuval Yarom and Naomi Benger. Recovering OpenSSL ECDSA Nonces Using the FLUSH+ RELOAD Cache Side-channel Attack. IACR Cryptology ePrint Archive, 2014:140, 2014.
56. Yuval Yarom and Katrina E Falkner. Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack. IACR Cryptology ePrint Archive, 2013:448, 2013.
57. Tse-Yu Yeh and Yale N Patt. Two-level adaptive training branch prediction. In Proceedings of the 24th annual international symposium on Microarchitecture, pages 51-61. ACM, 1991.

Index Terms

• Security and privacy

  • Security in hardware

    • Hardware attacks and countermeasures

      • Side-channel analysis and countermeasures

    • Hardware reverse engineering

  • Systems security

    • Information flow control