article

Efficient Cache Attacks on AES, and Countermeasures

Authors:

Dag Arne Osvik,

Adi ShamirAuthors Info & Claims

Journal of Cryptology, Volume 23, Issue 1

Pages 37 - 71

Published: 01 January 2010 Publication History

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.

References

[1]

M. Abadi, M. Burrows, M. Manasse, T. Wobber, Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5(2), 299-327 (2005).

Digital Library

[2]

O. Aciiç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. Aciiç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]

O. Aciiç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].

[5]

O. Aciiçmez, Ç.K. Koç, J.-P. Seifert, On the power of simple branch prediction analysis . IACR Cryptology ePrint Archive, report 2006/351 (2006).

[6]

O. Aciiç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.

[7]

O. Aciiç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.

[8]

O. Aciiç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.

[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]

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.

[12]

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.

[13]

E. Biham, A. Shamir, Differential cryptanalysis of DES-like Cryptosystems. J. Cryptol. 4(1), 3-72 (1991).

Digital Library

[14]

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.

[15]

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.

[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]

J. Daemen, V. Rijmen, The Design of Rijndael: AES--The Advanced Encryption Standard (Springer, Berlin, 2001). ISBN 3-540-42580-2.

[21]

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.

[22]

O. Goldreich, R. Ostrovsky, Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431-473 (1996).

Digital Library

[23]

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.

[24]

W.-M. Hu, Lattice scheduling and covert channels, in IEEE Symposium on Security and Privacy (IEEE, New York, 1992), pp. 52-61.

[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.

[27]

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.

Digital Library

[28]

S. Kent et al., RFC 4301 through RFC 4309 . NetworkWorking Group Request for Comments. http://rfc. net/rfc4301.html etc. (2005).

[29]

R.E. Kessler, M.D. Hill, Page placement algorithms for large real-indexed caches. ACM Trans. Comput. Syst. 10(4), 338-359 (1992).

Digital Library

[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]

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.

[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]

T. Lindholm, F. Yellin, The Java Virtual Machine Specification , 2nd edn. (Prentice Hall, New York, 1999).

[34]

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.

[35]

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.

[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]

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.

Digital Library

[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]

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.

[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.

Digital Library

[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]

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.

[46]

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.

[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]

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.

[52]

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.

[53]

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.

[54]

M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D.A. Osvik, B. de Weger, Short chosenprefix 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/.

[55]

Trusted Computing Group, Trusted Computing Group: Home . Web site, http://www. trustedcomputinggroup.org.

[56]

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.

[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.

[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]

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.

[63]

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.

[64]

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.

Cited By

Peters MGaudin NThoma JLapôtre VCotret PGogniat GGüneysu TQuek TGao DZhou JCardenas A(2024)On The Effect of Replacement Policies on The Security of Randomized Cache ArchitecturesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637677(483-497)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637677
Mahmud FKim SChawla HKim ETsai CMuzahid A(2023)Attack of the Knights:Non Uniform Cache Side Channel AttackProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627199(691-703)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627199
Ghaniyoun MBarber KXiao YZhang YTeodorescu RSolihin YHeinrich M(2023)TEESec: Pre-Silicon Vulnerability Discovery for Trusted Execution EnvironmentsProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589070(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589070
Show More Cited By

Efficient Cache Attacks on AES, and Countermeasures

Recommendations

Cache attacks and countermeasures: the case of AES
CT-RSA'06: Proceedings of the 2006 The Cryptographers' Track at the RSA conference on Topics in Cryptology

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-...
Related-key rectangle attacks on reduced AES-192 and AES-256
FSE'07: Proceedings of the 14th international conference on Fast Software Encryption

This paper examines the security of AES-192 and AES-256 against a related-key rectangle attack. We find the following new attacks: 8-round reduced AES-192 with 2 related keys, 10-round reduced AES-192 with 64 or 256 related keys and 9-round reduced AES-...
One-Sided Countermeasures for Side-Channel Attacks Can Backfire
WiSec '18: Proceedings of the 11th ACM Conference on Security & Privacy in Wireless and Mobile Networks

Side-channel attacks are currently one of the most powerful attacks against implementations of cryptographic algorithms. They exploit the correlation between the physical measurements (power consumption, electromagnetic emissions, timing) taken at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 23, Issue 1

January 2010

120 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 2010 International Association for Cryptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

100
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peters MGaudin NThoma JLapôtre VCotret PGogniat GGüneysu TQuek TGao DZhou JCardenas A(2024)On The Effect of Replacement Policies on The Security of Randomized Cache ArchitecturesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637677(483-497)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637677
Mahmud FKim SChawla HKim ETsai CMuzahid A(2023)Attack of the Knights:Non Uniform Cache Side Channel AttackProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627199(691-703)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627199
Ghaniyoun MBarber KXiao YZhang YTeodorescu RSolihin YHeinrich M(2023)TEESec: Pre-Silicon Vulnerability Discovery for Trusted Execution EnvironmentsProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589070(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589070
Schlüter TChoudhari AHetterich LTrampert LNemati HIbrahim ASchwarz MRossow CTippenhauer NMeng WJensen CCremers CKirda E(2023)FetchBench: Systematic Identification and Characterization of Proprietary PrefetchersProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623124(975-989)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623124
Ge JLi YZheng YLiu YHabib S(2022)More Secure Collaborative APIs resistant to Flush-Based Cache Attacks on Cortex-A9 Based Automotive SystemProceedings of the 6th ACM Computer Science in Cars Symposium10.1145/3568160.3570227(1-9)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3568160.3570227
Lang FWang WMeng LLin JWang QLu L(2022)MoLE: Mitigation of Side-channel Attacks against SGX via Dynamic Data Location EscapeProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3568002(978-988)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3568002
Thoma JGüneysu T(2022)Write Me and I’ll Tell You Secrets – Write-After-Write Effects On Intel CPUsProceedings of the 25th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3545948.3545987(72-85)Online publication date: 26-Oct-2022
https://dl.acm.org/doi/10.1145/3545948.3545987
Zhang RBond MZhang YEgger BSmith A(2022)Cape: compiler-aided program transformation for HTM-based cache side-channel defenseProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction10.1145/3497776.3517778(181-193)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3497776.3517778
Kietzmann PBoeckmann LLanzieri LSchmidt TWählisch M(2021)A Performance Study of Crypto-Hardware in the Low-end IoTProceedings of the 2021 International Conference on Embedded Wireless Systems and Networks10.5555/3451271.3451279(79-90)Online publication date: 20-Feb-2021
https://dl.acm.org/doi/10.5555/3451271.3451279
Brotzman RZhang DKandemir MTan G(2021)SpecSafe: detecting cache side channels in a speculative worldProceedings of the ACM on Programming Languages10.1145/34855065:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485506
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents