research-article

New attacks and defense for encrypted-address cache

Author:

Moinuddin K. QureshiAuthors Info & Claims

ISCA '19: Proceedings of the 46th International Symposium on Computer Architecture

Pages 360 - 371

https://doi.org/10.1145/3307650.3322246

Published: 22 June 2019 Publication History

Abstract

Conflict-based cache attacks can allow an adversary to infer the access pattern of a co-running application by orchestrating evictions via cache conflicts. Such attacks can be mitigated by randomizing the location of the lines in the cache. Our recent proposal, CEASER, makes cache randomization practical by accessing the cache using an encrypted address and periodically changing the encryption key. CEASER was analyzed with the state-of-the-art algorithm on forming eviction sets, and the analysis showed that CEASER with a Remap-Rate of 1% is sufficient to tolerate years of attack.

In this paper, we present two new attacks that significantly push the state-of-the-art in forming eviction sets. Our first attack reduces the time required to form the eviction set from O(L²) to O(L), where L is the number of lines in the attack. This attack is 35x faster than the best-known attack and requires that the Remap-Rate of CEASER be increased to 35%. Our second attack exploits the replacement policy (we analyze LRU, RRIP, and Random) to form eviction set quickly and requires that the Remap-Rate of CEASER be increased to more than 100%, incurring impractical overheads.

To improve the robustness of CEASER against these attacks in a practical manner, we propose Skewed-CEASER (CEASER-S), which divides the cache ways into multiple partitions and maps the cache line to be resident in a different set in each partition. This design significantly improves the robustness of CEASER, as the attacker must form an eviction set that can dislodge the line from multiple possible locations. We show that CEASER-S can tolerate years of attacks while retaining a Remap-Rate of 1%. CEASER-S incurs negligible slowdown (within 1%) and a storage overhead of less than 100 bytes for the newly added structures.

References

[1]

D. J. Bernstein, "Cache-timing attacks on AES," tech. rep., 2005.

[2]

Z. Wang and R. B. Lee, "New cache designs for thwarting software cache-based side channel attacks," in 34th Annual International Symposium on Computer Architecture (ISCA), 2007.

Digital Library

[3]

L. Domnitser, A. Jaleel, J. Loew, N. Abu-Ghazaleh, and D. Ponomarev, "Non-monopolizable caches: Low-complexity mitigation of cache side channel attacks," ACM Trans. Archit. Code Optim., vol. 8, Jan. 2012.

Digital Library

[4]

V. Kiriansky, I. Lebedev, S. Amarasinghe, S. Devadas, and J. Emer, "DAWG: A Defense Against Cache Timing Attacks in Speculative Execution Processors," in 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct 2018.

[5]

Z. Wang and R. B. Lee, "A novel cache architecture with enhanced performance and security," in 41st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pp. 83--93, 2008.

Digital Library

[6]

M. Qureshi, "CEASER: Mitigating Conflit-Based Cache Attacks via Encrypted-Address and Remapping," in 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct 2018.

[7]

F. Liu, Y. Yarom, Q. Ge, G. Heiser, and R. B. Lee, "Last-level cache side-channel attacks are practical," in 2015 IEEE Symposium on Security and Privacy, pp. 605--622, May 2015.

Digital Library

[8]

A. Jaleel, K. B. Theobald, S. C. Steely, Jr., and J. Emer, "High performance cache replacement using re-reference interval prediction (rrip)," in Proceedings of the 37th Annual International Symposium on Computer Architecture, ISCA '10, (New York, NY, USA), pp. 60--71, ACM, 2010.

Digital Library

[9]

A. Seznec, "A case for two-way skewed-associative caches," in Annual International Symposium on Computer Architecture (ISCA), 1993.

Digital Library

[10]

S. Sardashti, A. Seznec, and D. A. Wood, "Skewed compressed caches," in Annual IEEE/ACM International Symposium on Microarchitecture, 2014.

Digital Library

[11]

E. Quiñones, E. D. Berger, G. Bernat, and F. J. Cazorla, "Using randomized caches in probabilistic real-time systems," in 21st Euromicro Conference on Real-Time Systems, ECRTS 2009, Dublin, Ireland, 2009.

Digital Library

[12]

V. Young, C. Chou, A. Jaleel, and M. Qureshi, "Accord: Enabling associativity for gigascale dram caches by coordinating way-install and way-prediction," in 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pp. 328--339, 2018.

[13]

D. A. Osvik, A. Shamir, and E. Tromer, "Cache attacks and countermeasures: The case of aes," in The Cryptographers' Track at the RSA Conference on Topics in Cryptology, 2006.

Digital Library

[14]

C. Percival, "Cache missing for fun and profit," in The Technical BSD Conference, 2005.

[15]

How Much Will It Cost To Sniff Out The Spies? (Riddler Nation at FiveThirtyEight.com on Oct 5, 2018). https://fivethirtyeight.com/features/how-much-will-it-cost-to-sniff-out-the-spies/.

[16]

M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, and J. Emer, "Adaptive insertion policies for high performance caching," in Proceedings of the 34th Annual International Symposium on Computer Architecture, ISCA '07, (New York, NY, USA), pp. 381--391, ACM, 2007.

Digital Library

[17]

C.-J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely, Jr., and J. Emer, "Ship: Signature-based hit predictor for high performance caching," in Proceedings ofthe 44th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-44, (New York, NY, USA), pp. 430--441, ACM, 2011.

Digital Library

[18]

V. Young, C.-C. Chou, A. Jaleel, and M. Qureshi, "Ship++: Enhancing signature-based hit predictor for improved cache performance," in The 2nd Cache Replacement Championship (CRC-2 Workshop in ISCA 2017), 2017.

[19]

S. M. Khan, Y. Tian, and D. A. Jimenez, "Sampling dead block prediction for last-level caches," in 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, 2010.

Digital Library

[20]

A. Jain and C. Lin, "Back to the future: Leveraging belady's algorithm for improved cache replacement," in 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA), 2016.

Digital Library

[21]

S. Beamer, K. Asanovic, and D. A. Patterson, "The GAP benchmark suite," CoRR, vol. abs/1508.03619, 2015.

[22]

T. Sherwood, E. Perelman, G. Hamerly, and B. Calder, "Automatically characterizing large scale program behavior," SIGOPS Oper. Syst. Rev., vol. 36, pp. 45--57, Oct. 2002.

Digital Library

[23]

P. Vila, B. Kopf, and J. F. Morales, "Theory and practice of finding eviction sets," in 2019 2019 IEEE Symposium on Security and Privacy (SP), pp. 695--710, may 2019.

[24]

F. Liu, Q. Ge, Y. Yarom, F. Mckeen, C. Rozas, G. Heiser, and R. B. Lee, "CATalyst: Defeating last-level cache side channel attacks in cloud computing," in IEEE International Symposium on High Performance Computer Architecture (HPCA), 2016.

[25]

T. Kim, M. Peinado, and G. Mainar-Ruiz, "STEALTHMEM: System-level protection against cache-based side channel attacks in the cloud," in 21st USENIX Security Symposium, 2012.

Digital Library

[26]

Z. He and R. B. Lee, "How secure is your cache against side-channel attacks?," in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 341--353, ACM, 2017.

Digital Library

[27]

M. Yan, R. Sprabery, B. Gopireddy, C. Fletcher, R. Campbell, and J. Torrellas, "Attack directories, not caches: Side channel attacks in a non-inclusive world," in IEEE Symposium on Security and Privacy (S&P), 2019.

[28]

P. Kocher, D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom, "Spectre attacks: Exploiting speculative execution," ArXiv e-prints, Jan. 2018.

[29]

M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg, "Meltdown," ArXiv e-prints, Jan. 2018.

[30]

J. Van Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens, M. Silberstein, T. F. Wenisch, Y. Yarom, and R. Strackx, "Foreshadow: Extracting the keys to the intel sgx kingdom with transient out-of-order execution," in 27th USENIX Security Symposium USENIX Security 18), USENIX Association, 2018.

Digital Library

[31]

M. Yan, J. Choi, D. Skarlatos, A. Morrison, C. W. Fletcher, and J. Torrellas, "Invisispec: Making speculative execution invisible in the cache hierarchy," in 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct 2018.

Cited By

Fan HWang WWang YWang XGao Y(2024)Cache attacks on subkey calculation of BlowfishJournal of Computer Security10.3233/JCS-23005232:2(165-191)Online publication date: 9-Apr-2024
https://doi.org/10.3233/JCS-230052
Zhang JChen CCui JLi K(2024)Timing Side-Channel Attacks and Countermeasures in CPU MicroarchitecturesACM Computing Surveys10.1145/3645109Online publication date: 7-Feb-2024
https://doi.org/10.1145/3645109
Ramkrishnan KMcCamant SZhai AYew PQuek TGao DZhou JCardenas A(2024)Non-Fusion Based Coherent Cache Randomization Using Cross-Domain AccessesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3645011(186-202)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3645011
Show More Cited By

Recommendations

New cache designs for thwarting software cache-based side channel attacks
ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture

Software cache-based side channel attacks are a serious new class of threats for computers. Unlike physical side channel attacks that mostly target embedded cryptographic devices, cache-based side channel attacks can also undermine general purpose ...
Adaptive Caches as a Defense Mechanism Against Cache Side-Channel Attacks
ASHES'19: Proceedings of the 3rd ACM Workshop on Attacks and Solutions in Hardware Security Workshop

Side-channel attacks exploit architectural features of computing systems and algorithmic properties of applications executing on these systems to steal sensitive information. Cache side-channel attacks are more powerful and practical compared to other ...
Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '19: Proceedings of the 46th International Symposium on Computer Architecture

June 2019

849 pages

ISBN:9781450366694

DOI:10.1145/3307650

General Chair:
Srilatha (Bobbie) Manne
Microsoft
,
Program Chairs:
Hillery Hunter
IBM
,
Erik Altman
IBM Research

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

In-Cooperation

IEEE-CS\DATC: IEEE Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ISCA '19

Sponsor:

SIGARCH

ISCA '19: The 46th Annual International Symposium on Computer Architecture

June 22 - 26, 2019

Arizona, Phoenix

Acceptance Rates

ISCA '19 Paper Acceptance Rate 62 of 365 submissions, 17%;

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
843
Total Downloads

Downloads (Last 12 months)121
Downloads (Last 6 weeks)22

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan HWang WWang YWang XGao Y(2024)Cache attacks on subkey calculation of BlowfishJournal of Computer Security10.3233/JCS-23005232:2(165-191)Online publication date: 9-Apr-2024
https://doi.org/10.3233/JCS-230052
Zhang JChen CCui JLi K(2024)Timing Side-Channel Attacks and Countermeasures in CPU MicroarchitecturesACM Computing Surveys10.1145/3645109Online publication date: 7-Feb-2024
https://doi.org/10.1145/3645109
Ramkrishnan KMcCamant SZhai AYew PQuek TGao DZhou JCardenas A(2024)Non-Fusion Based Coherent Cache Randomization Using Cross-Domain AccessesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3645011(186-202)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3645011
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
Saxena AMathur SQureshi MTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Rubix: Reducing the Overhead of Secure Rowhammer Mitigations via Randomized Line-to-Row MappingProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640404(1014-1028)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640404
Zhao ZMorrison AFletcher CTorrellas JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Last-Level Cache Side-Channel Attacks Are Feasible in the Modern Public CloudProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640403(582-600)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640403
Bhatla ANavneet Panda B(2024)The Maya Cache: A Storage-efficient and Secure Fully-associative Last-level Cache2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00013(32-44)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00013
Li ZXue ZSong W(2024)Feasibility Analysis and Performance Optimization of the Conflict Test Algorithms for Searching Eviction SetsInformation Security and Cryptology – ICISC 202310.1007/978-981-97-1238-0_12(214-232)Online publication date: 8-Mar-2024
https://doi.org/10.1007/978-981-97-1238-0_12
Zhang ZTao MO'Connell SChuengsatiansup CGenkin DYarom YCalandrino JTroncoso C(2023)BunnyHopProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620647(7321-7337)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620647
De Meulemeester JPurnal AWouters LBeckers AVerbauwhede ICalandrino JTroncoso C(2023)SPECTREMProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620589(6293-6310)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620589
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents