Erkay SAVAŞ, Cemal YILMAZ, Ali Can ATICI

Cache-timing attacks without a profiling phase

Theoretically secure cryptographic algorithms can be vulnerable to attacks due to their implementation flaws.Bernstein’s attack is a well-known cache-timing attack that uses execution times as the side-channel. The major drawbackof this attack is that it needs an identical target machine to perform its profiling phase where the attacker models thecache timing-behavior of the target machine. This assumption makes the attack unrealistic in many circumstances. Inthis work, we present an effective method to eliminate the profiling phase. We propose a methodology to model the cachetiming-behavior of the target machine by trying hypothetical cache behaviors exhaustively. Our implementation resultsshow that the proposed nonprofiled Bernstein’s attack has comparable (and better in some test instances) performanceto the original attack with the profiling phase.

PDF

___

[1] Kocher PC. Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. In: The 16th Annual International Cryptology Conference on Advances in Cryptology; 18–22 August 1996; Santa Barbara, CA, USA. Berlin, Germany: Springer. pp. 104-113.
[2] Kocher PC, Jaffe J, Jun B. Differential power analysis. In: The 19th Annual International Cryptology Conference on Advances in Cryptology; 15–19 August 1999; Santa Barbara, CA, USA. Berlin, Germany: Springer. pp. 388-397.
[3] Gandolfi K, Mourtel C, Olivier F. Electromagnetic analysis: concrete results. In: Cryptographic Hardware and Embedded Systems - CHES; 14–16 May 2001; Paris, France. Berlin, Germany: Springer. pp. 251-261.
[4] Aciicmez O, Koc CK, Seifert J. Predicting secret keys via branch prediction. In: Topics in Cryptology - CT-RSA; 5–9 February 2007; San Francisco, CA, USA. Berlin, Germany: Springer. pp. 225-242.
[5] Mowery K, Keelveedhi S, Shacham H. Are AES x86 cache timing attacks still feasible? In: Cloud Computing Security Workshop; 16–18 October 2012; Raleigh, NC, USA. New York, NY, USA: ACM. pp. 19-24.
[6] Reberio C, Mukhopadhyay D. Micro-architectural analysis of time-driven cache attacks: quest for the ideal implementation. IEEE T Comput 2015; 64: 778-790.
[7] D. J. Bernstein. Cache timing attacks on AES. http://cr.yp.to/antiforgery/cachetiming-20050414.pdf.
[8] AES Standard. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf.
[9] Kelsey J, Schneier B, Wagner D, Hall C. Side channel cryptanalysis of product ciphers. J Comput Secur 2000; 8: 141-158.
[10] Tromer E, Osvik DA, Shamir A. Efficient cache attacks on AES, and countermeasures. J Cryptol 2009; 23: 37-71.
[11] Aciicmez O, Koc CK. Trace-driven cache attacks on AES (short paper). In: 8th International Conference on Information and Communications Security; 4–7 December 2006; Raleigh, NC, USA. Berlin, Germany: Springer. pp. 112-121.
[12] Tsunoo Y, Saito T, Suzaki T, Shigeria M, Miyauchi H. Cryptanalysis of DES implemented on computers with cache. In: Cryptographic Hardware and Embedded Systems - CHES; 8–10 September 2003; Cologne, Germany. Berlin, Germany: Springer. pp. 62-76.
[13] Chiappetta M, Savaş E, Yılmaz C. Real time detection of cache-based side-channel attacks using hardware performance counters. Appl Soft Comput 2016; 49: 1162-1174.
[14] Neve M. Cache-based vulnerabilities and SPAM analysis. PhD, Université Catholique de Louvain, Louvain, Belgium, 2006.
[15] Atici AC, Yilmaz C, Savas E. An approach for isolating the sources of information leakage exploited in cache-based side-channel attacks. In: 7th International Conference on Software Security and Reliability - Companion (SERE-C); 18–20 June 2013; Washington, DC, USA. Washington, DC, USA: IEEE. pp. 74-83.
[16] Bonneau J, Mironov I. Cache-collision timing attacks against AES. In: Cryptographic Hardware and Embedded Systems - CHES; 10–13 October 2006; Yokohama, Japan. Berlin, Germany: Springer. pp. 201-215.
[17] Spreitzer R, Gerard B. Towards more practical time-driven cache attacks. In: Information Security Theory and Practice. Securing the Internet of Things - WISTP; 30 June–2 July 2014; Heraklion, Crete, Greece. Berlin, Germany: Springer. pp. 24-39.
[18] Spreitzer R, Plos T. On the applicability of time-driven cache attacks on mobile devices. In: 7th International Conference, Network and System Security; 3–4 June 2013; Madrid, Spain. Berlin, Germany: Springer. pp. 656-662.
[19] Lipp M, Gruss D, Spreitzer R, Maurice C, Mangard S. ARMageddon: cache attacks on mobile devices. In: 25th USENIX Security Symposium; 10–12 August 2016; Austin, TX, USA. Berkeley, CA, USA: USENIX Association. pp. 549-564.
[20] Spreitzer R, Plos T. Cache-access pattern attack on disaligned AES T-tables. In: 4th International Workshop on Constructive Side-Channel Analysis and Secure Design, COSADE; 6–8 March 2013; Paris, France. Berlin, Germany: Springer. pp. 200-214.
[21] Bogdanov A, Eisenbarth T, Paar C, Wienecke M. Differential cache-collision timing attacks on AES with applications to embedded CPUs. In: Topics in Cryptology - CT-RSA; 1–5 March 2010; San Francisco, CA, USA. Berlin, Germany: Springer. pp. 235-251.
[22] Gallais JF, Kizhvatov I, Tunstall M. Improved trace-driven cache-collision attacks against embedded AES implementations. In: 11th International Workshop on Information Security Applications, WISA; 24–26 August 2010; Jeju Island, Korea. Berlin, Germany: Springer. pp. 243-257.
[23] Gülmezoğlu B, İnci MS, Irazoqui G, Eisenbarth T, Sunar B. Cross-VM cache attacks on AES. IEEE T Comput Syst 2016; 2: 211-222.
[24] Gülmezoğlu B, İnci MS, Irazoqui G, Eisenbarth T, Sunar B. A faster and more realistic flush+reload attack on AES. In: 6th International Workshop on Constructive Side-Channel Analysis and Secure Design - COSADE; 13–14 April 2015; Berlin, Germany. New York, NY, USA: Springer-Verlag New York. pp. 111-126.
[25] Irazoqui G, İnci MS, Eisenbarth T, Sunar B. Fine grain cross-VM attacks on Xen and VMware. In: IEEE Fourth International Conference on Big Data and Cloud Computing; 3–5 December 2014; Sydney, Australia. Washington, DC, USA: IEEE. pp. 737-744.
[26] Irazoqui G, Eisenbarth T, Sunar B. S$A: A shared cache attack that works across cores and defies VM sandboxing - and its application to AES. In: IEEE Symposium on Security and Privacy; 18–20 May 2015; San Jose, CA, USA. Washington, DC, USA: IEEE. pp. 591-604.
[27] Irazoqui G, İnci MS, Eisenbarth T, Sunar B. Wait a Minute! A fast, cross-VM attack on AES. In: 17th International Symposium on Research in Attacks, Intrusions and Defenses - RAID; 17–19 September 2014; Gothenburg, Sweden. Switzerland: Springer. pp. 299-319.
[28] Weiß M, Heinz B, Stumpf F. A cache timing attack on AES in virtualization environments. In: Financial Cryptography and Data Security Conference; 27 February–March 2 2012; Kralendijk, Bonaire. Berlin, Germany: Springer. pp. 314-328.
[29] Jiang ZH, Fei Y. A novel cache bank timing attack. In: IEEE/ACM International Conference on Computer-Aided Design - ICCAD; 13–16 November 2017; Irvine, CA, USA. Piscataway, NJ, USA: IEEE. pp. 139-146.
[30] Moghimi A, Irazoqui G, Eisenbarth T. CacheZoom: How SGX amplifies the power of cache attacks. In: Cryptographic Hardware and Embedded Systems - CHES; 25–28 September 2017; Taipei, Taiwan. Berlin, Germany: Springer. pp. 69-90.
[31] Ashokkumar C, Giri RP, Menezes B. Highly efficient algorithms for AES key retrieval in cache access attacks. In: IEEE European Symposium on Security and Privacy; 21–24 March 2016; Saarbrücken, Germany. Washington, DC, USA: IEEE. pp. 261-275.
[32] Irazoqui G, Eisenbarth T, Sunar B. Cross processor cache attacks. In: 11th Asia Conference on Computer and Communications Security; 30 May–03 June 2016; Xi’an, China. New York, NY, USA: ACM. pp. 353-364.
[33] Gullasch D, Bangerter E, Krenn S. Cache games - bringing access-based cache attacks on AES to practice. In: 32nd IEEE Symposium on Security and Privacy; 22–25 May 2011; Oakland, CA, USA. Washington, DC, USA: IEEE. pp. 490-505.
[34] Reberio C, Mondal M, Mukhopadhyay D. Pinpointing cache timing attacks on AES. In: 23rd International Conference on VLSI Design; 3–7 January 2010; Bangalore, India. Washington, DC, USA: IEEE. pp. 306-311.