Deconstructing new cache designs for thwarting software cache-based side channel attacks

ABSTRACT

Software cache-based side channel attacks present a serious tthreat to computer systems. Previously proposed countermeasures were either too costly for practical use or only effective against particular attacks. Thus, a recent work identified cache interferences in general as the root cause and proposed two new cache designs, namely partition-locked cache (PLcache) and random permutation cache(RPcache), to defeat cache-based side channel attacks by eliminating/obfuscating cache interferences. In this paper, we analyze these new cache designs and identify significant vulnerabilities and shortcomings of those new cache designs. We also propose possible solutions and improvements over the original new cache designs to overcome the identified shortcomings.

REFERENCES

• 1: O. Aciçmez and Ç. K. Koç. Microarchitectural Attacks and Countermeasures. Chapter in "Cryptographic Engineering" by Ç. K. Koç, Springer, ISBN 0387718168, to be published in November 2008.
• 2: Onur Aciiçmez, Yet another MicroArchitectural Attack:: exploiting I-Cache, Proceedings of the 2007 ACM workshop on Computer security architecture, November 02-02, 2007, Fairfax, Virginia, USA [doi>10.1145/1314466.1314469]
• 3: Onur Aciiçmez , Çetin Kaya Koç , Jean-Pierre Seifert, On the power of simple branch prediction analysis, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1266999]
• 4: O. Aciçmez, Ç. K. Koç, and J.-P. Seifert. Predicting Secret Keys via Branch Prediction. Topics in Cryptology | CT-RSA 2007, The Cryptographers' Track at the RSA Conference 2007, M. Abe, editor, pages 225--242, Springer-Verlag, Lecture Notes in Computer Science series 4377, 2007.
• 5: Onur Aciicmez , Jean-Pierre Seifert, Cheap Hardware Parallelism Implies Cheap Security, Proceedings of the Workshop on Fault Diagnosis and Tolerance in Cryptography, p.80-91, September 10-10, 2007 [doi>10.1109/FDTC.2007.4]
• 6: O. Aciçmez, W. Schindler, and Ç. K. Koç. Cache Based Remote Timing Attack on the AES. Topics in Cryptology | CT-RSA 2007, The Cryptographers' Track at the RSA Conference 2007, M. Abe, editor, pages 271--286, Springer-Verlag, Lecture Notes in Computer Science series 4377, 2007.
• 7: Onur Aciiçmez , Werner Schindler , Çetin K. Koç, Improving Brumley and Boneh timing attack on unprotected SSL implementations, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102140]
• 8: Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197, 2001. Available at http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
• 9: AMD. Lightweight Profiling Proposal, AMD, July 2007. Available at: http://developer.amd.com/assets/HardwareExtensionsforLeightweightProfilingPublic20070720.pdf
• 10: D. J. Bernstein. Cache-timing attacks on AES. Technical Report, 37 pages, April 2005.
• 11: J. Bonneau and I. Mironov. Cache-Collision Timing Attacks against AES. Cryptographic Hardware and Embedded Systems | CHES 2006, L. Goubin and M. Matsui, editors, pages 201--215, Springer-Verlag, Lecture Notes in Computer Science series 4249, 2006.
• 12: David Brumley , Dan Boneh, Remote timing attacks are practical, Proceedings of the 12th conference on USENIX Security Symposium, p.1-1, August 04-08, 2003, Washington, DC
• 13: D. Burger and T.M. Austin. The Simplescalar Tool Set Version 2.0. Technical Report, Computer Science Department, University of Wisconsin-Madison, 1997.
• 14: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 15: S. Gueron. Advanced Encryption Standard (AES) Instructions Set. Technical Report, 35 pages, Intel Corporation, April 2008. Available at: http://softwarecommunity.intel.com/isn/downloads/intelavx/AES-Instructions-Set WP.pdf
• 16: M. Neve and J.-P. Seifert. Advances on Access-driven Cache Attacks on AES. 13th International Workshop on Selected Areas of Cryptography | SAC'06, E. Biham and A. M. Youssef, editors, pages 147--162, Springer, Lecture Notes in Computer Science series 4356, 2007.
• 17: OpenSSL Montgomery Exponentiation Side-Channel Local Information Disclosure Vulnerability. http://www.securityfocus.com/bid/25163/ 2007.
• 18: OpenSSL Timing Attack RSA Private Key Information Disclosure Vulnerability. http://www.securityfocus.com/bid/7101/ 2003.
• 19: D. A. Osvik, A. Shamir, and E. Tromer. Cache Attacks and Countermeasures: The Case of AES. Topics in Cryptology | CT-RSA 2006, The Cryptographers' Track at the RSA Conference 2006, D. Pointcheval, editor, pages 1--20, Springer-Verlag, Lecture Notes in Computer Science series 3860, 2006
• 20: D. Page. Theoretical Use of Cache Memory as a Cryptanalytic Side-Channel. Technical Report CSTR-02--003, Department of Computer Science, University of Bristol, June 2002.
• 21: D. Page. Partitioned Cache Architecture as a Side Channel Defence Mechanism. Cryptography ePrint Archive, Report 2005/280, August 2005.
• 22: C. Percival. Cache missing for fun and profit. BSDCan 2005, Ottawa, 2005.
• 23: Dawn Xiaodong Song , David Wagner , Xuqing Tian, Timing analysis of keystrokes and timing attacks on SSH, Proceedings of the 10th conference on USENIX Security Symposium, p.25-25, August 13-17, 2001, Washington, D.C.
• 24: K. Tiri, O. Aciçmez, M. Neve, and F. Andersen. An Analytical Model for Time-Driven Cache Attacks. 14th International Workshop on Fast Software Encryption | FSE 2007, A. Biryukov, editor, pages 399--413, Springer, Lecture Notes in Computer Science series 4593, 2007.
• 25: Zhenghong Wang , Ruby B. Lee, New cache designs for thwarting software cache-based side channel attacks, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Security

Keywords:
cache architecture, cache attack, cryptanalysis, microarchitectural analysis, side-channel analysis, timing attack