Abstract
We describe several software side-channel attacks based on inter-process leakage through the state of the CPU’s memory cache. This leakage reveals memory access patterns, which can be used for cryptanalysis of cryptographic primitives that employ data-dependent table lookups. The attacks allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing, and virtualization. Some of our methods require only the ability to trigger services that perform encryption or MAC using the unknown key, such as encrypted disk partitions or secure network links. Moreover, we demonstrate an extremely strong type of attack, which requires knowledge of neither the specific plaintexts nor ciphertexts and works by merely monitoring the effect of the cryptographic process on the cache. We discuss in detail several attacks on AES and experimentally demonstrate their applicability to real systems, such as OpenSSL and Linux’s dm-crypt encrypted partitions (in the latter case, the full key was recovered after just 800 writes to the partition, taking 65 milliseconds). Finally, we discuss a variety of countermeasures which can be used to mitigate such attacks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abadi, M. Burrows, M. Manasse, T. Wobber, Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5(2), 299–327 (2005)
O. Acıiçmez, Yet another microarchitectural attack: exploiting I-cache, in IACR Cryptology ePrint Archive, report 2007/164 (2007). http://eprint.iacr.org/2007/164
O. Acıiçmez, Ç.K. Koç, Trace driven cache attack on AES. IACR Cryptology ePrint Archive, report 2006/138 (2006). http://eprint.iacr.org/2006/138; full version of [4]
O. Acıiçmez, Ç.K. Koç, Trace driven cache attack on AES (short paper), in Proc. International Conference on Information and Communications Security (ICICS) 2006. Lecture Notes in Computer Science, vol. 4296 (Springer, Berlin, 2006), pp. 112–121. Short version of [3]
O. Acıiçmez, Ç.K. Koç, J.-P. Seifert, On the power of simple branch prediction analysis. IACR Cryptology ePrint Archive, report 2006/351 (2006)
O. Acıiçmez, Ç.K. Koç, J.-P. Seifert, Predicting secret keys via branch prediction, in Proc. RSA Conference Cryptographers Track (CT-RSA) 2007. Lecture Notes in Computer Science, vol. 4377 (Springer, Berlin, 2007), pp. 225–242
O. Acıiçmez, W. Schindler, Ç.K. Koç, Cache based remote timing attack on the AES, in Proc. RSA Conference Cryptographers Track (CT-RSA) 2007. Lecture Notes in Computer Science, vol. 4377 (Springer, Berlin, 2007), pp. 271–286
O. Acıiçmez, J.-P. Seifert, Cheap hardware parallelism implies cheap security, in Proc. Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC) 2007 (IEEE, New York, 2007), pp. 80–91
R.J. Anderson, E. Biham, L.R. Knudsen, Serpent: A Proposal for the Advanced Encryption Standard. AES submission (1998). http://www.cl.cam.ac.uk/~rja14/serpent.html
D.J. Bernstein, Cache-timing attacks on AES. Preprint (2005). http://cr.yp.to/papers.html#cachetiming
G. Bertoni, V. Zaccaria, L. Breveglieri, M. Monchiero, G. Palermo, AES power attack based on induced cache miss and countermeasure, in Proc. International Conference on Information Technology: Coding and Computing (ITCC’05) (IEEE, New York, 2005), pp. 586–591
E. Biham, A fast new DES implementation in software, in Proc. Fast Software Encryption (FSE) 1997. Lecture Notes in Computer Science, vol. 1267 (Springer, Berlin, 1997), pp. 260–272
E. Biham, A. Shamir, Differential cryptanalysis of DES-like Cryptosystems. J. Cryptol. 4(1), 3–72 (1991)
M. Blum, W. Evans, P. Gemmell, S. Kannan, M. Naor, Checking the correctness of memories, in Proc. Conference on Foundations of Computer Science (FOCS) 1991 (IEEE, New York, 1991), pp. 90–99
J. Bonneau, I. Mironov, Cache-collision timing attacks against AES, in Proc. Cryptographic Hardware and Embedded Systems (CHES) 2006. Lecture Notes in Computer Science, vol. 4249 (Springer, Berlin, 2006), pp. 201–215
E. Brickell, G. Graunke, M. Neve, J.-P. Seifert, Software mitigations to hedge AES against cache-based software side channel vulnerabilities. IACR Cryptology ePrint Archive, report 2006/052 (2006). http://eprint.iacr.org/2006/052
E. Brickell, G. Graunke, J.-P. Seifert, Mitigating cache/timing attacks in AES and RSA software implementations, in RSA Conference 2006, San Jose, session DEV-203 (2006). http://2006.rsaconference.com/us/cd_pdfs/DEV-203.pdf
A. Canteaut, C. Lauradoux, A. Seznec, Understanding cache attacks. Research report RR-5881, INRIA, April 2006. http://www-rocq.inria.fr/codes/Anne.Canteaut/Publications/RR-5881.pdf
J. Daemen, V. Rijmen, AES Proposal: Rijndael, version 2, AES submission (1999). http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
J. Daemen, V. Rijmen, The Design of Rijndael: AES—The Advanced Encryption Standard (Springer, Berlin, 2001). ISBN 3-540-42580-2
C. Dwork, A. Goldberg, M. Naor, On memory-bound functions for fighting spam, in Proc. CRYPTO’2003. Lecture Notes in Computer Science, vol. 2729 (Springer, Berlin, 2003), pp. 426–444
O. Goldreich, R. Ostrovsky, Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)
W.-M. Hu, Reducing timing channels with fuzzy time, in Proc. IEEE Computer Society Symposium on Research in Security and Privacy (IEEE, New York, 1991), pp. 8–20
W.-M. Hu, Lattice scheduling and covert channels, in IEEE Symposium on Security and Privacy (IEEE, New York, 1992), pp. 52–61
Intel Corp., Intel IXP42X Product Line of Network Processors and IXC1100 Control Plane Processor Developer’s Manual. Order Number 252480-006US (2006). http://www.intel.com/design/network/manuals/252480.htm
E. Käsper, P. Schwabe, Faster and Timing-Attack Resistant AES-GCM. IACR Cryptology ePrint Archive, report 2009/129 (2009). http://eprint.iacr.org/2009/129
J. Kelsey, B. Schneier, D. Wagner, C. Hall, Side channel cryptanalysis of product ciphers, in Proc. 5th European Symposium on Research in Computer Security. Lecture Notes in Computer Science, vol. 1485 (Springer, Berlin, 1998), pp. 97–110
S. Kent et al., RFC 4301 through RFC 4309. Network Working Group Request for Comments. http://rfc.net/rfc4301.html etc. (2005)
R.E. Kessler, M.D. Hill, Page placement algorithms for large real-indexed caches. ACM Trans. Comput. Syst. 10(4), 338–359 (1992)
F. Koeune, J.-J. Quisquater, A timing attack against Rijndael. Technical Report CG-1999/1, Université catholique de Louvain, http://www.dice.ucl.ac.be/crypto/tech_reports/CG1999_1.ps.gz
R. Könighofer, A fast and cache-timing resistant implementation of the AES, in Proc. RSA Conference Cryptographers Track (CT-RSA) 2008. Lecture Notes in Computer Science, vol. 4964 (Springer, Berlin, 2008), pp. 187–202
C. Lauradoux, Collision attacks on processors with cache and countermeasures, in Western European Workshop on Research in Cryptology (WEWoRC) 2005. Lectures Notes in Informatics, vol. P-74 (2005), pp. 76–85. http://www.cosic.esat.kuleuven.ac.be/WeWorc/allAbstracts.pdf
T. Lindholm, F. Yellin, The Java Virtual Machine Specification, 2nd edn. (Prentice Hall, New York, 1999)
M. Matsui, How far can we go on the x64 processors?, in Proc. Fast Software Encryption (FSE) 2006. Lecture Notes in Computer Science, vol. 4047 (Springer, Berlin, 2006), pp. 341–358
M. Matsui, J. Nakajima, On the power of bitslice implementation on Intel Core2 processor, in Proc. Cryptographic Hardware and Embedded Systems (CHES) 2007. Lecture Notes in Computer Science, vol. 4727 (Springer, Berlin, 2007), pp. 121–134
R.V. Meushaw, M.S. Schneider, D.N. Simard, G.M. Wagner, Device for and method of secure computing using virtual machines. US patent 6,922,774 (2005)
Microsoft Corp., Next-generation secure computing base. Web page, http://www.microsoft.com/resources/ngscb
M. Naor, G.N. Rothblum, The complexity of online memory checking, in Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2005 (IEEE, New York, 2005), pp. 573–584
National Institute of Standards and Technology, Advanced Encryption Standard (AES), FIPS PUB 197 (2001)
National Institute of Standards and Technology, Secure Hash Standard (SHS), FIPS PUB 180-2 (2002)
M. Neve, J.-P. Seifert, Advances on access-driven cache attacks on AES, in Proc. Selected Areas in Cryptography (SAC’06). Lecture Notes in Computer Science, vol. 4356 (Springer, Berlin, 2006), pp. 147–162
M. Neve, J.-P. Seifert, Z. Wang, A refined look at Bernstein’s AES side-channel analysis. in Proc. ACM Symposium on Information, Computer and Communications Security (2006), p. 369
OpenVPN Solutions LLC, OpenVPN—an Open Source SSL VPN Solution by James Yonan. Web site, http://openvpn.net
D.A. Osvik, A. Shamir, E. Tromer, Other people’s cache: Hyper Attacks on HyperThreaded processors. Fast Software Encryption (FSE) 2005 rump session, Feb. 2005
D.A. Osvik, A. Shamir, E. Tromer, Cache attacks and countermeasures: the case of AES, in Proc. RSA Conference Cryptographers Track (CT-RSA) 2006. Lecture Notes in Computer Science, vol. 3860 (Springer, Berlin, 2006), pp. 1–20
E. Oswald, S. Mangard, N. Pramstaller, V. Rijmen, A side-channel analysis resistant description of the AES S-box, in Proc. Fast Software Encryption (FSE) 2005. Lecture Notes in Computer Science, vol. 3557 (Springer, Berlin, 2005), pp. 413–423
D. Page, Theoretical use of cache memory as a cryptanalytic side-channel. Technical Report CSTR-02-003, Department of Computer Science, University of Bristol (2002). http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=1000625
D. Page, Defending against cache-based side-channel attacks. Information Security Technial Report, vol. 8, issue 8 (2003)
D. Page, Partitioned cache architecture as a side-channel defence mechanism. IACR Cryptology ePrint Archive, report 2005/280 (2005). http://eprint.iacr.org/2005/280
C. Percival, Cache missing for fun and profit. BSDCan 2005, Ottawa (2005). See http://www.daemonology.net/hyperthreading-considered-harmful
C. Rebeiro, D. Selvakumar, A.S.L. Devi, Bitslice implementation of AES, in Proc. Cryptology and Network Security (CANS) 2006. Lecture Notes in Computer Science, vol. 4301 (Springer, Berlin, 2006), pp. 203–212
A. Rudra, P.K. Dubey, C.S. Jutla, V. Kumar, J.R. Rao, P. Rohatgi, Efficient Rijndael encryption implementation with composite field arithmetic, in Proc. Cryptographic Hardware and Embedded Systems (CHES) 2001. Lecture Notes in Computer Science, vol. 2162 (Springer, Berlin, 2001), pp. 171–184
K. Schramm, C. Paar, Higher Order Masking of the AES, in Proc. RSA Conference Cryptographers Track (CT-RSA) 2006. Lecture Notes in Computer Science, vol. 3860 (Springer, Berlin, 2006), pp. 208–225
M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D.A. Osvik, B. de Weger, Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Proc. CRYPTO 2009 (to be published). http://www.win.tue.nl/hashclash/rogue-ca/
Trusted Computing Group, Trusted Computing Group: Home. Web site, http://www.trustedcomputinggroup.org
Y. Tsunoo, T. Saito, T. Suzaki, M. Shigeri, H. Miyauchi, Cryptanalysis of DES implemented on computers with cache, in Proc. Cryptographic Hardware and Embedded Systems (CHES) 2003. Lecture Notes in Computer Science, vol. 2779 (Springer, Berlin, 2003), pp. 62–76
Y. Tsunoo, E. Tsujihara, K. Minematsu, H. Miyauchi, Cryptanalysis of block ciphers implemented on computers with cache, in Proc. International Symposium on Information Theory and Its Applications 2002 (2002), pp. 803–806
Y. Tsunoo, E. Tsujihara, M. Shigeri, H. Kubo, K. Minematsu, Improving cache attacks by considering cipher structure. Int. J. Inf. Secur. “Online First”, Springer, Nov. 2005
University of Cambridge Computer Laboratory, The Xen virtual machine monitor. Web site, http://www.cl.cam.ac.uk/research/srg/netos/xen
A.A. Veith, A.V. Belenko, A. Zhukov, A preview on branch misprediction attacks: using Pentium performance counters to reduce the complexity of timing attacks. CRYPTO’06 rump session (2006)
VMware Inc., VMware: virtualization, virtual machine & virtual server consolidation. Web site, http://www.vmware.com
J. Yang, J. Goodman, Symmetric key cryptography on modern graphics hardware, in Proc. Asiacrypt 2007. Lecture Notes in Computer Science, vol. 4833 (Springer, Berlin, 2007), pp. 249–264
X. Zhuang, T. Zhang, H.-H.S. Lee, S. Pande, Hardware assisted control flow obfuscation for embedded processors, in Proc. International Conference on Compilers, Architectures and Synthesis for Embedded Systems (ACM, New York, 2004), pp. 292–302
X. Zhuang, T. Zhang, S. Pande, HIDE: An Infrastructure for Efficiently protecting information leakage on the address bus, in Proc. Architectural Support for Programming Languages and Operating Systems (ACM, New York, 2004), pp. 82–84
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Lars R. Knudsen
Rights and permissions
About this article
Cite this article
Tromer, E., Osvik, D.A. & Shamir, A. Efficient Cache Attacks on AES, and Countermeasures. J Cryptol 23, 37–71 (2010). https://doi.org/10.1007/s00145-009-9049-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-009-9049-y