Noise-Free Security Assessment of Eviction Set Construction Algorithms with Randomized Caches
Source abstract
Abstract
Cache timing attacks, i.e., a class of remote side-channel attack, have become very popular in recent years. Eviction set construction is a common step for many such attacks, and algorithms for building them are evolving rapidly. On the other hand, countermeasures are also being actively researched and developed. However, most countermeasures have been designed to secure last-level caches and few of them actually protect the entire memory hierarchy. Cache randomization is a well-known mitigation technique against cache attacks that has a low-performance overhead. In this study, we attempted to determine whether address randomization on first-level caches is worth considering from a security perspective. In this paper, we present the implementation of a noise-free cache simulation framework that enables the analysis of the behavior of eviction set construction algorithms. We show that randomization at the first level of caches (L1) brings about improvements in security but is not sufficient to mitigate all known algorithms, such as the recently developed Prime–Prune–Probe technique. Nevertheless, we show that L1 randomization can be combined with a lightweight random eviction technique in higher-level caches to mitigate known conflict-based cache attacks.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Security and Verification in Computing · Cloud Data Security Solutions · Advanced Memory and Neural Computing
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
CEA, LETI MINATEC Campus, University Grenoble Alpes, 38054 Grenoble, France
CNRS, Grenoble INP, TIMA, University Grenoble Alpes, 38000 Grenoble, France
References (65)
Show source-provided references
1. Kocher, P., Horn, J., Fogh, A., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., and Prescher, T. (2019, January 16–18). Spectre attacks: Exploiting speculative execution. Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), New York, NY, USA.10.1109/SP.2019.00002 ↗
2. Lipp, M., Schwarz, M., Gruss, D., Prescher, T., Haas, W., Mangard, S., Kocher, P., Genkin, D., Yarom, Y., and Hamburg, M. (2020). Meltdown, Association for Computing Machinery (ACM).10.1145/3357033 ↗
3. Lipp, M., Gruss, D., Spreitzer, R., Maurice, C., and Mangard, S. (2016, January 10–12). Armageddon: Cache attacks on mobile devices. Proceedings of the 25th USENIX Security Symposium, Austin, TX, USA.
4. Bernstein, D.J. (2005). Cache-Timing Attacks on AES, CiteSeer.
5. Percival, C. (2005). Cache Missing for Fun and Profit, BSDCan.
6. Yarom, Y., and Falkner, K. (2014, January 20–22). FLUSH + RELOAD: A high resolution, low noise, L3 cache side-channel attack. Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA.
7. Dessouky, G., Frassetto, T., and Sadeghi, A.R. (2020, January 12–14). HybCache: Hybrid side-channel-resilient caches for trusted execution environments. Proceedings of the 29th USENIX Security Symposium, Austin, Virtual, Online.
8. Kiriansky, V., Lebedev, I., Amarasinghe, S., Devadas, S., and Emer, J. (2018, January 20–24). DAWG: A defense against cache timing attacks in speculative execution processors. Proceedings of the Annual International Symposium on Microarchitecture, MICRO, Fukuoka, Japan.10.1109/MICRO.2018.00083 ↗
9. Gruss, D., Lettner, J., Schuster, F., Ohrimenko, O., Haller, I., and Costa, M. (2017, January 16–18). Strong and efficient cache side-channel protection using hardware transactional memory. Proceedings of the 26th USENIX Security Symposium, Vancouver, BC, Canada.
10. Liu, F., Ge, Q., Yarom, Y., Mckeen, F., Rozas, C., Heiser, G., and Lee, R.B. (2016, January 12–16). Catalyst: Defeating last-level cache side channel attacks in cloud computing. Proceedings of the International Symposium on High-Performance Computer Architecture, Barcelona, Spain.10.1109/HPCA.2016.7446082 ↗
11. Wang, Y., Ferraiuolo, A., Zhang, D., Myers, A.C., and Suh, G.E. (2016, January 5–9). SecDCP: Secure dynamic cache partitioning for efficient timing channel protection. Proceedings of the 53rd Annual ACM IEEE Design Automation Conference, Austin, TX, USA.10.1145/2897937.2898086 ↗
12. Zhou, Z., Reiter, M.K., and Zhang, Y. (2016, January 24–28). A software approach to defeating side channels in last-level caches. Proceedings of the 23rd ACM Conference on Computer and Communications Security, Vienna, Austria.10.1145/2976749.2978324 ↗
13. Kim, T., Peinado, M., and Mainar-Ruiz, G. (2012, January 8–10). StealthMem: System-level protection against cache-based side channel attacks in the cloud. Proceedings of the 21st USENIX Security Symposium, Bellevue, WA, USA.
14. Sanchez, D., and Kozyrakis, C. (2011, January 4–8). Vantage: Scalable and efficient fine-grain cache partitioning. Proceedings of the 38th Annual International Symposium on Computer Architecture, ISCA’11, San Jose, CA, USA.10.1145/2000064.2000073 ↗
15. Wang, Z., and Lee, R.B. (2007, January 9–13). New cache designs for thwarting software cache-based side channel attacks. Proceedings of the 34th Annual International Symposium on Computer Architecture, ISCA’07, San Diego, CA, USA.10.1145/1250662.1250723 ↗
16. Jaamoum, A., Hiscock, T., and Di Natale, G. (2021, January 1–5). Scramble Cache: An Efficient Cache Architecture for Randomized Set Permutation. Proceedings of the 2021 Design, Automation and Test in Europe Conference and Exhibition (DATE), Grenoble, France.10.23919/DATE51398.2021.9473919 ↗
17. Brutus: Refuting the security claims of the cache timing randomization countermeasure proposed in ceaser10.1109/LCA.2020.2964212 ↗
18. Song, W., Li, B., Xue, Z., Li, Z., Wang, W., and Liu, P. (2021, January 24–27). Randomized Last-Level Caches Are Still Vulnerable to Cache Side-Channel Attacks! But We Can Fix It. Proceedings of the 42nd IEEE Symposium on Security and Privacy, San Francisco, CA, USA.10.1109/SP40001.2021.00050 ↗
19. Werner, M., Unterluggauer, T., Giner, L., Schwarz, M., Gruss, D., and Mangard, S. (2019, January 14–16). Scattercache: Thwarting cache attacks via cache set randomization. Proceedings of the 28th USENIX Security Symposium, Santa Clara, CA, USA.
20. Qureshi, M.K. (2018, January 20–24). CEASER: Mitigating conflict-based cache attacks via encrypted-address and remapping. Proceedings of the Annual International Symposium on Microarchitecture, MICRO, 51st Annual IEEE/ACM, Fukuoka, Japan.10.1109/MICRO.2018.00068 ↗
21. Newcache: Secure cache architecture thwarting cache side-channel attacks10.1109/MM.2016.85 ↗
22. Liu, F., and Lee, R.B. (2014, January 13–17). Random fill cache architecture. Proceedings of the Annual International Symposium on Microarchitecture, MICRO, 47th Annual IEEE/ACM, Cambridge, UK.10.1109/MICRO.2014.28 ↗
23. Wong, H. (2022, January 22). Intel Ivy Bridge Cache Replacement Policy. Available online: http://blog.stuffedcow.net/2013/01/ivb-cache-replacement.
24. High performance cache replacement using re-reference interval prediction (RRIP)10.1145/1816038.1815971 ↗
25. Maurice, C., Le Scouarnec, N., Neumann, C., Heen, O., and Francillon, A. (2015, January 2–4). Reverse engineering Intel last-level cache complex addressing using performance counters. Proceedings of the 18th International Symposium on Research in Attacks, Intrusions, and Defenses, Kyoto, Japan.10.1007/978-3-319-26362-5_3 ↗
26. Acıiçmez, O., Brumley, B.B., and Grabher, P. (2010, January 17–20). New results on instruction cache attacks. Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010, Santa Barbara, CA, USA.10.1007/978-3-642-15031-9_8 ↗
27. Acıiçmez, O., and Schindler, W. (2008, January 8–11). A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL. Proceedings of the Cryptographers’ Track at the RSA Conference, San Francisco, CA, USA.
28. Efficient cache attacks on AES, and countermeasures10.1007/s00145-009-9049-y ↗
29. Gruss, D., Maurice, C., Wagner, K., and Mangard, S. (2016, January 7–8). Flush + Flush: A fast and stealthy cache attack. Proceedings of the 13th International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, San Sebastian, Spain.10.1007/978-3-319-40667-1_14 ↗
30. Disselkoen, C., Kohlbrenner, D., Porter, L., and Tullsen, D. (2017, January 16–18). Prime + Abort: A Timer-Free High-Precision L3 Cache Attack using Intel TSX. Proceedings of the 26th USENIX Security Symposium, Vancouver, BC, USA.
31. Liu, F., Yarom, Y., Ge, Q., Heiser, G., and Lee, R.B. (2015, January 18–20). Last-level cache side-channel attacks are practical. Proceedings of the 36th IEEE Symposium on Security and Privacy, San Jose, CA, USA.10.1109/SP.2015.43 ↗
32. Neve, M., and Seifert, J.P. (2006, January 17–18). Advances on access-driven cache attacks on AES. Proceedings of the 13th International Workshop on Selected Areas in Cryptography, Montreal, QC, Canada.
33. Osvik, D.A., Shamir, A., and Tromer, E. (2006, January 13–17). Cache attacks and countermeasures: The case of AES. Proceedings of the Cryptographers’ Track at the RSA Conference, San Jose, CA, USA.10.1007/11605805_1 ↗
34. Gulmezouglu, B., Inci, M.S., Irazoqui, G., Eisenbarth, T., and Sunar, B. (2015, January 13–14). A faster and more realistic flush + reload attack on AES. Proceedings of the International Workshop on Constructive Side-Channel Analysis and Secure Design, Berlin, Germany.10.1007/978-3-319-21476-4_8 ↗
35. Irazoqui, G., Eisenbarth, T., and Sunar, B. (2015, January 18–20). S$A: A shared cache attack that works across cores and defies VM sandboxing—And its application to AES. Proceedings of the 36th IEEE Symposium on Security and Privacy, San Jose, CA, USA.10.1109/SP.2015.42 ↗
36. Gras, B., Razavi, K., Bosman, E., Bos, H., and Giuffrida, C. (March, January 26). ASLR on the Line: Practical Cache Attacks on the MMU. Proceedings of the NDSS Conference, San Diego, CA, USA.
37. Gruss, D., Maurice, C., Fogh, A., Lipp, M., and Mangard, S. (2016, January 24–28). Prefetch side-channel attacks: Bypassing SMAP and kernel ASLR. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.10.1145/2976749.2978356 ↗
38. Jang, Y., Lee, S., and Kim, T. (2016, January 24–28). Breaking kernel address space layout randomization with intel tsx. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.10.1145/2976749.2978321 ↗
39. Hund, R., Willems, C., and Holz, T. (2013, January 4–8). Practical timing side channel attacks against kernel space ASLR. Proceedings of the 2013 IEEE Symposium on Security and Privacy, Berlin, Germany.10.1109/SP.2013.23 ↗
40. Aciiçmez, O. (2007, January 2). Yet another microarchitectural attack: Exploiting I-cache. Proceedings of the 2007 ACM Workshop on Computer Security Architecture, Fairfax, VA, USA.10.1145/1314466.1314469 ↗
41. Gras, B., Razavi, K., Bos, H., and Giuffrida, C. (2018, January 15–17). Translation leak-aside buffer: Defeating cache side-channel protections with {TLB} attacks. Proceedings of the 27th USENIX Security Symposium, Berkeley, CA, USA.
42. Aciiçmez, O., Koç, Ç.K., and Seifert, J.P. (2007, January 20–22). On the power of simple branch prediction analysis. Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, Singapore.10.1145/1229285.1266999 ↗
43. (2022, January 22). How to Use the Kernel Samepage Merging Feature (Linux Kernel). Available online: https://www.kernel.org/doc/Documentation/vm/ksm.txt.
44. Non-monopolizable caches: Low-complexity mitigation of cache side channel attacks10.1145/2086696.2086714 ↗
45. Page, D. (2022, January 22). Partitioned Cache Architecture as a Side-Channel Defence Mechanism. IACR Cryptol. ePrint Arch. Available online: https://eprint.iacr.org/2005/280.
46. Shi, J., Song, X., Chen, H., and Zang, B. (2011, January 27–30). Limiting cache-based side-channel in multi-tenant cloud using dynamic page coloring. Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems and Networks Workshops, Northwest Washington, DC, USA.10.1109/DSNW.2011.5958812 ↗
47. (2022, January 22). Intel® 64 and IA-32 Architectures, Software Developer’s Manual, Volume 2. Available online: https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-vol-3b-part-2-manual.pdf.
48. Vila, P., Köpf, B., and Morales, J.F. (2019, January 19–23). Theory and practice of finding eviction sets. Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP.2019.00042 ↗
49. Zhang, Y., Juels, A., Reiter, M.K., and Ristenpart, T. (2012, January 16–18). Cross-VM side channels and their use to extract private keys. Proceedings of the 2012 ACM Conference on Computer and Communications Security, Raleigh, NC, USA.10.1145/2382196.2382230 ↗
50. Kayaalp, M., Abu-Ghazaleh, N., Ponomarev, D., and Jaleel, A. (2016, January 5–9). A high-resolution side-channel attack on last-level cache. Proceedings of the 53rd Annual Design Automation Conference, Austin, TX, USA.10.1145/2897937.2897962 ↗
51. A survey of microarchitectural side-channel vulnerabilities, attacks and defenses in cryptography10.1145/3456629 ↗
52. Winter is here! A decade of cache-based side-channel attacks, detection & mitigation for RSA10.1016/j.is.2020.101524 ↗
53. Purnal, A., Giner, L., Gruss, D., and Verbauwhede, I. (2021, January 24–27). Systematic analysis of randomization-based protected cache architectures. Proceedings of the 42th IEEE Symposium on Security and Privacy, Virtual.10.1109/SP40001.2021.00011 ↗
54. Van Der Veen, V., Fratantonio, Y., Lindorfer, M., Gruss, D., Maurice, C., Vigna, G., Bos, H., Razavi, K., and Giuffrida, C. (2016, January 24–28). Drammer: Deterministic rowhammer attacks on mobile platforms. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.
55. (2022, January 22). Transparent Hugepage Support (Linux Kernel). Available online: https://www.kernel.org/doc/Documentation/vm/transhuge.txt.
56. Genkin, D., Pachmanov, L., Tromer, E., and Yarom, Y. (2018, January 2–4). Drive-by key-extraction cache attacks from portable code. Proceedings of the International Conference on Applied Cryptography and Network Security, Leuven, Belgium.10.1007/978-3-319-93387-0_5 ↗
57. Wang, D., Qian, Z., Abu-Ghazaleh, N., and Krishnamurthy, S.V. (2019, January 2–6). Papp: Prefetcher-aware prime and probe side-channel attack. Proceedings of the 56th Annual Design Automation Conference, Las Vegas, NV, USA.10.1145/3316781.3317877 ↗
58. Qureshi, M.K. (2019, January 22–26). New attacks and defense for encrypted-address cache. Proceedings of the 2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA), Phoenix, AZ, USA.10.1145/3307650.3322246 ↗
59. Zhang, T., and Lee, R.B. (2014, January 8–12). New models of cache architectures characterizing information leakage from cache side channels. Proceedings of the 30th Annual Computer Security Applications Conference, New Orleans, LA, USA.10.1145/2664243.2664273 ↗
60. Demme, J., Martin, R., Waksman, A., and Sethumadhavan, S. (2012;, January 9–13). Side-channel vulnerability factor: A metric for measuring information leakage. Proceedings of the International Symposium on Computer Architecture, Portland, OR, USA.10.1109/ISCA.2012.6237010 ↗
61. Purnal, A., and Verbauwhede, I. (2019). Advanced profiling for probabilistic Prime + Probe attacks and covert channels in ScatterCache. arXiv.
62. Saileshwar, G., and Qureshi, M. (2021, January 11–13). MIRAGE: Mitigating Conflict-Based Cache Attacks with a Practical Fully-Associative Design. Proceedings of the 30th USENIX Security Symposium, Virtual, Online.
63. Qureshi, M.K., Thompson, D., and Patt, Y.N. (2005, January 4–8). The V-Way cache: Demand-based associativity via global replacement. Proceedings of the 32nd IEEE International Symposium on Computer Architecture (ISCA’05), Madison, WI, USA.
64. Tan, Q., Zeng, Z., Bu, K., and Ren, K. (2020, January 23–26). PhantomCache: Obfuscating Cache Conflicts with Localized Randomization. Proceedings of the NDSS Symposium, San Diego, CA, USA.10.14722/ndss.2020.24086 ↗
65. Bao, C., and Srivastava, A. (2015, January 18–21). 3D integration: New opportunities in defense against cache-timing side-channel attacks. Proceedings of the 33rd IEEE International Conference on Computer Design (ICCD), New York, NY, USA.10.1109/ICCD.2015.7357114 ↗