×

On the incomparability of cache algorithms in terms of timing leakage. (English) Zbl 1489.68045

Summary: Modern computer architectures rely on caches to reduce the latency gap between the CPU and main memory. While indispensable for performance, caches pose a serious threat to security because they leak information about memory access patterns of programs via execution time.
In this paper, we present a novel approach for reasoning about the security of cache algorithms with respect to timing leaks. The basis of our approach is the notion of leak competitiveness, which compares the leakage of two cache algorithms on every possible program. Based on this notion, we prove the following two results:
First, we show that leak competitiveness is symmetric in the cache algorithms. This implies that no cache algorithm dominates another in terms of leakage via a program’s total execution time. This is in contrast to performance, where it is known that such dominance relationships exist.
Second, when restricted to caches with finite control, the leak-competitiveness relationship between two cache algorithms is either asymptotically linear or constant. No other shapes are possible.

MSC:

68M25 Computer security
68M07 Mathematical problems of computer architecture
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: arXiv

References:

[1] [ACPS12]M´ario Alvim, Kostas Chatzikokolakis, Catuscia Palamidessi, and Geoffrey Smith. Measuring information leakage using generalized gain functions. In Computer Security Foundations Symposium (CSF), 2012 IEEE 25th, pages 265-279. IEEE, 2012.
[2] [AK06]Onur Acıi¸cmez and C¸ etin Ko¸c. Trace-driven cache attacks on AES. Information and Communications Security, pages 112-121, 2006.
[3] [ASK07]Onur Acıi¸cmez, Werner Schindler, and C¸ etin K. Ko¸c. Cache based remote timing attack on the AES. In Cryptographers Track at the RSA Conference, pages 271-286. Springer, 2007.
[4] [AZMM04] Hussein Al-Zoubi, Aleksandar Milenkovic, and Milena Milenkovic. Performance evaluation of cache replacement policies for the spec cpu2000 benchmark suite. In Proceedings of the 42nd annual Southeast regional conference, pages 267-272. ACM, 2004.
[5] [Bel66]Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, 5(2):78-101, 1966.
[6] [Ber05]DanielBernstein.Cache-timingattacksonAES.http://cr.yp.to/antiforgery/ cachetiming-20050414.pdf, 2005.
[7] [CHM07]David Clark, Sebastian Hunt, and Pasquale Malacaria. A static analysis for quantifying information flow in a simple imperative language. JCS, 15(3):321-371, 2007.
[8] [CKR17]Pablo Ca˜nones, Boris K¨opf, and Jan Reineke. Security analysis of cache replacement policies. In POST, pages 189-209. Springer, 2017.
[9] [CS10]Michael R. Clarkson and Fred B. Schneider. Hyperproperties. Journal of Computer Security, 18(6):1157-1210, 2010.
[10] [DKMR15] Goran Doychev, Boris K¨opf, Laurent Mauborgne, and Jan Reineke. CacheAudit: a tool for the static analysis of cache side channels. ACM Transactions on Information and System Security
[11] [FKL+91]Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. · Zbl 0753.68018
[12] [GBK11]David Gullasch, Endre Bangerter, and Stephan Krenn. Cache games - bringing access-based cache attacks on AES to practice. In SSP, pages 490-505. IEEE, 2011.
[13] [HL17]Zecheng He and Ruby B. Lee. How secure is your cache against side-channel attacks? In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, pages 341-353. ACM, 2017.
[14] [HM10]Jonathan Heusser and Pasquale Malacaria. Quantifying information leaks in software. In ACSAC, pages 261-269. ACM, 2010. · Zbl 1189.68059
[15] [KB07]Boris K¨opf and David Basin. An Information-Theoretic Model for Adaptive Side-Channel Attacks. In Proc. 14th ACM Conference on Computer and Communications Security (CCS ’07), pages 286-296, New York, NY, USA, 2007. ACM.
[16] [KGG+18] Paul Kocher, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. Spectre attacks: Exploiting speculative execution. arXiv preprint arXiv:1801.01203, 2018.
[17] [LSG+18]Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown. arXiv preprint arXiv:1801.01207, 2018.
[18] [LYG+15]Fangfei Liu, Yuval Yarom, Qian Ge, Gernot Heiser, and Ruby B. Lee. Last-level cache side-channel attacks are practical. In SSP, pages 605-622. IEEE, 2015.
[19] [NMS09]James Newsome, Stephen McCamant, and Dawn Song. Measuring channel capacity to distinguish undue influence. In PLAS, pages 73-85. ACM, 2009.
[20] [OST06]Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: the case of AES. In CT-RSA, pages 1-20. Springer, 2006. · Zbl 1125.94326
[21] [RG08]Jan Reineke and Daniel Grund. Relative competitive analysis of cache replacement policies. In LCTES, pages 51-60, New York, NY, USA, June 2008. ACM.
[22] [Sch18]Felix Schr¨oder. Security of cache replacement policies under side-channel attacks. 2018.
[23] [Smi09]Geoffrey Smith. On the foundations of quantitative information flow. In FoSSaCS, pages 288-302. Springer, 2009. · Zbl 1234.68101
[24] [ST85]Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985.
[25] [TOL+11]Mohit Tiwari, Jason Oberg, Xun Li, Jonathan Valamehr, Timothy E. Levin, Ben Hardekopf, Ryan Kastner, Frederic T. Chong, and Timothy Sherwood. Crafting a usable microkernel, processor, and I/O system with strict and provable information flow security. In ISCA, pages 189-200. ACM, 2011.
[26] [YF14]Yuval Yarom and Katrina Falkner. FLUSH+RELOAD: A high resolution, low noise, L3 cache side-channel attack. In USENIX, pages 719-732. USENIX Association, 2014.
[27] [ZL14]Tianwei Zhang and Ruby B. Lee. New models of cache architectures characterizing information leakage from cache side channels. In Proceedings of the 30th Annual Computer Security Applications Conference, pages 96-105. ACM, 2014.
[28] [ZWSM15] Danfeng Zhang, Yao Wang, G. Edward Suh, and Andrew C. Myers. A hardware design language for timing-sensitive information-flow security. In ASPLOS, pages 503-516. ACM, 2015.
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.