×

Efficient cache attacks on AES, and countermeasures. (English) Zbl 1181.94106

Summary: 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.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Software:

OpenSSL; Serpent
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abadi, M.; Burrows, M.; Manasse, M.; Wobber, T., Moderately hard, memory-bound functions, ACM Trans. Internet Technol., 5, 2, 299-327 (2005) · doi:10.1145/1064340.1064341
[2] 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
[3] 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]
[4] Acıiçmez, O.; Koç, Ç. K., Trace driven cache attack on AES (short paper), Proc. International Conference on Information and Communications Security (ICICS) 2006, 112-121 (2006), Berlin: Springer, Berlin
[5] 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)
[6] Acıiçmez, O.; Koç, Ç. K.; Seifert, J.-P., Predicting secret keys via branch prediction, Proc. RSA Conference Cryptographers Track (CT-RSA) 2007, 225-242 (2007), Berlin: Springer, Berlin · Zbl 1177.94125
[7] Acıiçmez, O.; Schindler, W.; Koç, Ç. K., Cache based remote timing attack on the AES, Proc. RSA Conference Cryptographers Track (CT-RSA) 2007, 271-286 (2007), Berlin: Springer, Berlin · Zbl 1177.94126
[8] Acıiçmez, O.; Seifert, J.-P., Cheap hardware parallelism implies cheap security, Proc. Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC) 2007, 80-91 (2007), New York: IEEE, New York
[9] 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
[10] D.J. Bernstein, Cache-timing attacks on AES. Preprint (2005). http://cr.yp.to/papers.html#cachetiming
[11] Bertoni, G.; Zaccaria, V.; Breveglieri, L.; Monchiero, M.; Palermo, G., AES power attack based on induced cache miss and countermeasure, Proc. International Conference on Information Technology: Coding and Computing (ITCC’05), 586-591 (2005), New York: IEEE, New York
[12] Biham, E., A fast new DES implementation in software, Proc. Fast Software Encryption (FSE) 1997, 260-272 (1997), Berlin: Springer, Berlin · Zbl 1385.94014
[13] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like Cryptosystems, J. Cryptol., 4, 1, 3-72 (1991) · Zbl 0729.68017 · doi:10.1007/BF00630563
[14] Blum, M.; Evans, W.; Gemmell, P.; Kannan, S.; Naor, M., Checking the correctness of memories, Proc. Conference on Foundations of Computer Science (FOCS) 1991, 90-99 (1991), New York: IEEE, New York
[15] Bonneau, J.; Mironov, I., Cache-collision timing attacks against AES, Proc. Cryptographic Hardware and Embedded Systems (CHES) 2006, 201-215 (2006), Berlin: Springer, Berlin
[16] 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
[17] 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
[18] 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
[19] J. Daemen, V. Rijmen, AES Proposal: Rijndael, version 2, AES submission (1999). http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
[20] Daemen, J.; Rijmen, V., The Design of Rijndael: AES—The Advanced Encryption Standard (2001), Berlin: Springer, Berlin · Zbl 1065.94005
[21] Dwork, C.; Goldberg, A.; Naor, M., On memory-bound functions for fighting spam, Proc. CRYPTO’2003, 426-444 (2003), Berlin: Springer, Berlin · Zbl 1122.94415
[22] Goldreich, O.; Ostrovsky, R., Software protection and simulation on oblivious RAMs, J. ACM, 43, 3, 431-473 (1996) · Zbl 0885.68041
[23] Hu, W.-M., Reducing timing channels with fuzzy time, Proc. IEEE Computer Society Symposium on Research in Security and Privacy, 8-20 (1991), New York: IEEE, New York
[24] Hu, W.-M., Lattice scheduling and covert channels, IEEE Symposium on Security and Privacy, 52-61 (1992), New York: IEEE, New York
[25] 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
[26] 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 · Zbl 1290.94102
[27] Kelsey, J.; Schneier, B.; Wagner, D.; Hall, C., Side channel cryptanalysis of product ciphers, Proc. 5th European Symposium on Research in Computer Security, 97-110 (1998), Berlin: Springer, Berlin · Zbl 1487.94125
[28] S. Kent et al., RFC 4301 through RFC 4309. Network Working Group Request for Comments. http://rfc.net/rfc4301.html etc. (2005)
[29] Kessler, R. E.; Hill, M. D., Page placement algorithms for large real-indexed caches, ACM Trans. Comput. Syst., 10, 4, 338-359 (1992) · doi:10.1145/138873.138876
[30] 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
[31] Könighofer, R., A fast and cache-timing resistant implementation of the AES, Proc. RSA Conference Cryptographers Track (CT-RSA) 2008, 187-202 (2008), Berlin: Springer, Berlin · Zbl 1153.68373
[32] 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
[33] Lindholm, T.; Yellin, F., The Java Virtual Machine Specification (1999), New York: Prentice Hall, New York
[34] Matsui, M., How far can we go on the x64 processors?, Proc. Fast Software Encryption (FSE) 2006, 341-358 (2006), Berlin: Springer, Berlin
[35] Matsui, M.; Nakajima, J., On the power of bitslice implementation on Intel Core2 processor, Proc. Cryptographic Hardware and Embedded Systems (CHES) 2007, 121-134 (2007), Berlin: Springer, Berlin
[36] 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)
[37] Microsoft Corp., Next-generation secure computing base. Web page, http://www.microsoft.com/resources/ngscb
[38] Naor, M.; Rothblum, G. N., The complexity of online memory checking, Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2005, 573-584 (2005), New York: IEEE, New York
[39] National Institute of Standards and Technology, Advanced Encryption Standard (AES), FIPS PUB 197 (2001)
[40] National Institute of Standards and Technology, Secure Hash Standard (SHS), FIPS PUB 180-2 (2002)
[41] Neve, M.; Seifert, J.-P., Advances on access-driven cache attacks on AES, Proc. Selected Areas in Cryptography (SAC’06), 147-162 (2006), Berlin: Springer, Berlin · Zbl 1161.94421
[42] 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
[43] OpenVPN Solutions LLC, OpenVPN—an Open Source SSL VPN Solution by James Yonan. Web site, http://openvpn.net
[44] 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
[45] Osvik, D. A.; Shamir, A.; Tromer, E., Cache attacks and countermeasures: the case of AES, Proc. RSA Conference Cryptographers Track (CT-RSA) 2006, 1-20 (2006), Berlin: Springer, Berlin · Zbl 1125.94326
[46] Oswald, E.; Mangard, S.; Pramstaller, N.; Rijmen, V., A side-channel analysis resistant description of the AES S-box, Proc. Fast Software Encryption (FSE) 2005, 413-423 (2005), Berlin: Springer, Berlin · Zbl 1140.94366
[47] 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
[48] D. Page, Defending against cache-based side-channel attacks. Information Security Technial Report, vol. 8, issue 8 (2003)
[49] 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
[50] C. Percival, Cache missing for fun and profit. BSDCan 2005, Ottawa (2005). See http://www.daemonology.net/hyperthreading-considered-harmful
[51] Rebeiro, C.; Selvakumar, D.; Devi, A. S.L., Bitslice implementation of AES, Proc. Cryptology and Network Security (CANS) 2006, 203-212 (2006), Berlin: Springer, Berlin · Zbl 1307.94089
[52] Rudra, A.; Dubey, P. K.; Jutla, C. S.; Kumar, V.; Rao, J. R.; Rohatgi, P., Efficient Rijndael encryption implementation with composite field arithmetic, Proc. Cryptographic Hardware and Embedded Systems (CHES) 2001, 171-184 (2001), Berlin: Springer, Berlin · Zbl 1012.94544
[53] Schramm, K.; Paar, C., Higher Order Masking of the AES, Proc. RSA Conference Cryptographers Track (CT-RSA) 2006, 208-225 (2006), Berlin: Springer, Berlin · Zbl 1125.94330
[54] 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/ · Zbl 1252.94098
[55] Trusted Computing Group, Trusted Computing Group: Home. Web site, http://www.trustedcomputinggroup.org
[56] Tsunoo, Y.; Saito, T.; Suzaki, T.; Shigeri, M.; Miyauchi, H., Cryptanalysis of DES implemented on computers with cache, Proc. Cryptographic Hardware and Embedded Systems (CHES) 2003, 62-76 (2003), Berlin: Springer, Berlin
[57] 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
[58] 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
[59] University of Cambridge Computer Laboratory, The Xen virtual machine monitor. Web site, http://www.cl.cam.ac.uk/research/srg/netos/xen · Zbl 1213.68154
[60] 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)
[61] VMware Inc., VMware: virtualization, virtual machine & virtual server consolidation. Web site, http://www.vmware.com
[62] Yang, J.; Goodman, J., Symmetric key cryptography on modern graphics hardware, Proc. Asiacrypt 2007, 249-264 (2007), Berlin: Springer, Berlin · Zbl 1153.94438
[63] Zhuang, X.; Zhang, T.; Lee, H.-H. S.; Pande, S., Hardware assisted control flow obfuscation for embedded processors, Proc. International Conference on Compilers, Architectures and Synthesis for Embedded Systems, 292-302 (2004), New York: ACM, New York
[64] Zhuang, X.; Zhang, T.; Pande, S., HIDE: An Infrastructure for Efficiently protecting information leakage on the address bus, Proc. Architectural Support for Programming Languages and Operating Systems, 82-84 (2004), New York: ACM, New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.