Single Trace Attack Against RSA Key Generation in Intel SGX SSL

ABSTRACT

Microarchitectural side-channel attacks have received significant attention recently. However, while side-channel analyses on secret key operations such as decryption and signature generation are well established, the process of key generation did not receive particular attention so far. Especially due to the fact that microarchitectural attacks usually require multiple observations (more than one measurement trace) to break an implementation, one-time operations such as key generation routines are often considered as uncritical and out of scope. However, this assumption is no longer valid for shielded execution architectures, where sensitive code is executed - in the realm of a potential attacker - inside hardware enclaves. In such a setting, an untrusted operating system can conduct noiseless controlled-channel attacks by exploiting page access patterns. In this work, we identify a critical vulnerability in the RSA key generation procedure of Intel SGX SSL (and the underlying OpenSSL library) that allows to recover secret keys from observations of a single execution. In particular, we mount a controlled-channel attack on the binary Euclidean algorithm (BEA), which is used for checking the validity of the RSA key parameters generated within an SGX enclave. Thereby, we recover all but 16 bits of one of the two prime factors of the public modulus. For an 8192-bit RSA modulus, we recover the remaining 16 bits and thus the full key in less than 12 seconds on a commodity PC. In light of these results, we urge for careful re-evaluation of cryptographic libraries with respect to single trace attacks, especially if they are intended for shielded execution environments such as Intel SGX.

References

1. Onur Aciiçmez. 2007. Yet Another MicroArchitectural Attack: : Exploiting ICache. In Computer Security Architecture Workshop -- CSAW. ACM, 11--18.
2. Onur Aciiçmez, Shay Gueron, and Jean-Pierre Seifert. 2007. New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures. In Cryptography and Coding -- IMA 2007 (LNCS), Vol. 4887. Springer, 185--203.
3. Onur Aciiçmez, Çetin Kaya Koç, and Jean-Pierre Seifert. 2007. On the Power of Simple Branch Prediction Analysis. In Asia Conference on Computer and Communications Security -- AsiaCCS 2007. ACM, 312--320.
4. Onur Aciiçmez and Werner Schindler. 2008. A Vulnerability in RSA Implementations Due to Instruction Cache Analysis and Its Demonstration on OpenSSL. In Topics in Cryptology -- CT-RSA 2008 (LNCS), Vol. 4964. Springer, 256--273.
5. Sarang Aravamuthan and Viswanatha Rao Thumparthy. 2007. A Parallelization of ECDSA Resistant to Simple Power Analysis Attacks. In Communication System Software and Middleware -- COMSWARE 2007. IEEE, 1--7.
6. Elaine Barker and Allen Roginsky (NIST). 2015. Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths. (2015). NIST Special Publication 800--131A, Revision 1.
7. Aurélie Bauer, Éliane Jaulmes, Victor Lomné, Emmanuel Prouff, and Thomas Roche. 2014. Side-Channel Attack against RSA Key Generation Algorithms. In Cryptographic Hardware and Embedded Systems -- CHES 2014 (LNCS), Vol. 8731. Springer, 223--241.
8. Daniel J. Bernstein. 2005. Cache-Timing Attacks on AES. Available online at http://cr.yp.to/antiforgery/cachetiming-20050414.pdf. (April 2005).
9. Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom. 2017. Sliding Right into Disaster: Left-to-Right Sliding Windows Leak. In Cryptographic Hardware and Embedded Systems -- CHES 2017 (LNCS), Vol. 10529. Springer, 555-- 576.
10. Dan Boneh. 1999. Twenty Years of Attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (1999), 203--213.
11. Ferdinand Brasser, Urs Müller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. 2017. Software Grand Exposure: SGX Cache Attacks Are Practical. In Workshop on Offensive Technologies -- WOOT 2017. USENIX Association.
12. Jo Van Bulck, Frank Piessens, and Raoul Strackx. 2017. SGX-Step: A Practical Attack Framework for Precise Enclave Execution Control. In System Software for Trusted Execution -- SysTEX 2017. ACM. In press.
13. Jo Van Bulck, Nico Weichbrodt, Rüdiger Kapitza, Frank Piessens, and Raoul Strackx. 2017. Telling Your Secrets without Page Faults: Stealthy Page Table-Based Attacks on Enclaved Execution. In USENIX Security Symposium 2017. USENIX Association, 1041--1056.
14. Sanchuan Chen, Xiaokuan Zhang, Michael K. Reiter, and Yinqian Zhang. 2017. Detecting Privileged Side-Channel Attacks in Shielded Execution with Déjà Vu. In Asia Conference on Computer and Communications Security -- AsiaCCS. ACM, 7--18.
15. Bart Coppens, Ingrid Verbauwhede, Koen De Bosschere, and Bjorn De Sutter. 2009. Practical Mitigations for Timing-Based Side-Channel Attacks on Modern x86 Processors. In IEEE Symposium on Security and Privacy -- S&P 2009. IEEE Computer Society, 45--60.
16. Intel Corporation. 2017. Intel Software Guard Extensions Developer Guide. https://software.intel.com/en-us/sgx-sdk/documentation. (2017).
17. Intel Corporation. 2017. Intel Software Guard Extensions (Intel SGX). https: //software.intel.com/en-us/sgx. (2017).
18. Intel Corporation. 2017. Using the Intel Software Guard Extensions (Intel SGX) SSL Library. https://software.intel.com/en-us/sgx/resource-library. (2017).
19. Thomas Finke, Max Gebhardt, and Werner Schindler. 2009. A New Side-Channel Attack on RSA Prime Generation. In Cryptographic Hardware and Embedded Systems -- CHES 2009 (LNCS), Vol. 5747. Springer, 141--155.
20. OpenSSL Software Foundation. 2017. OpenSSL -- Cryptography and SSL/TLS Toolkit. https://www.openssl.org/. (2017).
21. Yangchun Fu, Erick Bauman, Raul Quinonez, and Zhiqiang Lin. 2017. SGX-LAPD: Thwarting Controlled Side Channel Attacks via Enclave Verifiable Page Faults. In Recent Advances in Intrusion Detection -- RAID 2017 (LNCS), Vol. 10453. Springer, 357--380.
22. Cesar Pereida García and Billy Bob Brumley. 2017. Constant-Time Callees with Variable-Time Callers. In USENIX Security Symposium 2017. USENIX Association, 83--98.
23. Qian Ge, Yuval Yarom, David Cock, and Gernot Heiser. 2016. A Survey of Microarchitectural Timing Attacks and Countermeasures on Contemporary Hardware. Journal of Cryptographic Engineering (2016), 1--27.
24. Vinodh Gopal, James Guilford, Erdinc Ozturk, Wajdi Feghali, Gil Wolrich, and Martin Dixon. 2009. Fast and Constant-Time Implementation of Modular Exponentiation. In Embedded Systems and Communications Security -- ECSC 2009.
25. Johannes Götzfried, Moritz Eckert, Sebastian Schinzel, and Tilo Müller. 2017. Cache Attacks on Intel SGX. In European Workshop on System Security -- EUROSEC 2017. ACM, 2:1--2:6.
26. Shay Gueron. 2012. Efficient Software Implementations of Modular Exponentiation. J. Cryptographic Engineering 2 (2012), 31--43.
27. Marcus Hähnel, Weidong Cui, and Marcus Peinado. 2017. High-Resolution Side Channels for Untrusted Operating Systems. In USENIX Annual Technical Conference -- USENIX ATC 2017. USENIX Association, 299--312.
28. Matthew Hoekstra, Reshma Lal, Pradeep Pappachan, Vinay Phegade, and Juan del Cuvillo. 2013. Using Innovative Instructions to Create Trustworthy Software Solutions. In Hardware and Architectural Support for Security and Privacy -- HASP. ACM, 11.
29. American National Standards Institute. 1998. Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA). (1998).
30. Paul C. Kocher. 1996. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Advances in Cryptology -- CRYPTO 1996 (LNCS), Vol. 1109. Springer, 104--113.
31. Robert Könighofer. 2008. A Fast and Cache-Timing Resistant Implementation of the AES. In Topics in Cryptology -- CT-RSA 2008 (LNCS), Vol. 4964. Springer, 187--202.
32. Sangho Lee, Ming-Wei Shih, Prasun Gera, Taesoo Kim, Hyesoon Kim, and Marcus Peinado. 2017. Inferring Fine-grained Control Flow Inside SGX Enclaves with Branch Shadowing. In USENIX Security Symposium 2017. USENIX Association, 557--574.
33. Frank McKeen, Ilya Alexandrovich, Alex Berenzon, Carlos V. Rozas, Hisham Shafi, Vedvyas Shanbhogue, and Uday R. Savagaonkar. 2013. Innovative Instructions and Software Model for Isolated Execution. In Hardware and Architectural Support for Security and Privacy -- HASP. ACM, 10.
34. Alfred Menezes, Paul C. van Oorschot, and Scott A. Vanstone. 1996. Handbook of Applied Cryptography. CRC Press.
35. Ahmad Moghimi, Gorka Irazoqui, and Thomas Eisenbarth. 2017. CacheZoom: How SGX Amplifies the Power of Cache Attacks. In Cryptographic Hardware and Embedded Systems -- CHES 2017 (LNCS), Vol. 10529. Springer, 69--90.
36. Elaine Barker (NIST). 2016. Recommendation for Key Management, Part 1: General. (2016).
37. Colin Percival. 2005. Cache Missing for Fun and Profit. http://daemonology.net/ hyperthreading-considered-harmful/. (2005).
38. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. 1978. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21 (1978), 120--126.
39. Michael Schwarz, Samuel Weiser, Daniel Gruss, Clémentine Maurice, and Stefan Mangard. 2017. Malware Guard Extension: Using SGX to Conceal Cache Attacks. In Detection of Intrusions and Malware &Vulnerability Assessment -- DIMVA 2017 (LNCS), Vol. 10327. Springer, 3--24.
40. Jaebaek Seo, Byoungyoung Lee, Seong Min Kim, Ming-Wei Shih, Insik Shin, Dongsu Han, and Taesoo Kim. 2017. SGX-Shield: Enabling Address Space Layout Randomization for SGX Programs. In Network and Distributed System Security Symposium -- NDSS 2017. The Internet Society.
41. Ming-Wi Shih, Sangho Lee, Taesoo Kim, and Marcus Peinado. 2017. T-SGX: Eradicating Controlled-Channel Attacks Against Enclave Programs. In Network and Distributed System Security Symposium -- NDSS 2017. In press.
42. Shweta Shinde, Zheng Leong Chua, Viswesh Narayanan, and Prateek Saxena. 2015. Preventing Your Faults From Telling Your Secrets: Defenses Against Pigeonhole Attacks. arXiv ePrint Archive, Report 1506.04832 (2015).
43. Shweta Shinde, Zheng Leong Chua, Viswesh Narayanan, and Prateek Saxena. 2016. Preventing Page Faults from Telling Your Secrets. In Asia Conference on Computer and Communications Security -- AsiaCCS. ACM, 317--328.
44. J. Stein. 1967. Computational Problems Associated with Racah Algebra. J. Comput. Phys. 1 (1967), 397--405.
45. Raoul Strackx and Frank Piessens. 2016. Ariadne: A Minimal Approach to State Continuity. In USENIX Security Symposium 2016. USENIX Association, 875--892.
46. Raoul Strackx and Frank Piessens. 2017. The Heisenberg Defense: Proactively Defending SGX Enclaves against Page-Table-Based Side-Channel Attacks. CoRR abs/1712.08519 (2017).
47. Eran Tromer, Dag Arne Osvik, and Adi Shamir. 2010. Efficient Cache Attacks on AES, and Countermeasures. J. Cryptology 23 (2010), 37--71.
48. Camille Vuillaume, Takashi Endo, and Paul Wooderson. 2012. RSA Key Generation: New Attacks. In Constructive Side-Channel Analysis and Secure Design -- COSADE 2012 (LNCS), Vol. 7275. Springer, 105--119.
49. Wenhao Wang, Guoxing Chen, Xiaorui Pan, Yinqian Zhang, XiaoFeng Wang, Vincent Bindschaedler, Haixu Tang, and Carl A. Gunter. 2017. Leaky Cauldron on the Dark Land: Understanding Memory Side-Channel Hazards in SGX. In Conference on Computer and Communications Security -- CCS 2017. ACM, 2421-- 2434.
50. Yuan Xiao, Mengyuan Li, Sanchuan Chen, and Yinqian Zhang. 2017. STACCO: Differentially Analyzing Side-Channel Traces for Detecting SSL/TLS Vulnerabilities in Secure Enclaves. In Conference on Computer and Communications Security -- CCS 2017. ACM, 859--874.
51. Yuanzhong Xu, Weidong Cui, and Marcus Peinado. 2015. Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems. In IEEE Symposium on Security and Privacy -- S&P 2015. IEEE Computer Society, 640--656.
52. Yuval Yarom and Katrina Falkner. 2014. FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack. In USENIX Security Symposium 2014. USENIX Association, 719--732.
53. Yuval Yarom, Daniel Genkin, and Nadia Heninger. 2016. CacheBleed: A Timing Attack on OpenSSL Constant Time RSA. In Cryptographic Hardware and Embedded Systems -- CHES 2016 (LNCS), Vol. 9813. Springer, 346--367.

Index Terms

• Security and privacy

  • Cryptography

  • Software and application security