Pablo Cañones ; Boris Köpf ; Jan Reineke - On the Incomparability of Cache Algorithms in Terms of Timing Leakage

lmcs:4665 - Logical Methods in Computer Science, March 5, 2019, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:21)2019
On the Incomparability of Cache Algorithms in Terms of Timing LeakageArticle

Authors: Pablo Cañones ; Boris Köpf ; Jan Reineke

    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.


    Volume: Volume 15, Issue 1
    Published on: March 5, 2019
    Accepted on: January 14, 2019
    Submitted on: July 4, 2018
    Keywords: Computer Science - Cryptography and Security

    Consultation statistics

    This page has been seen 1158 times.
    This article's PDF has been downloaded 484 times.