International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A Formal Analysis of Prefetching in Profiled Cache-Timing Attacks on Block Ciphers

Chester Rebeiro
Debdeep Mukhopadhyay
DOI: 10.1007/s00145-021-09394-z
Search ePrint
Search Google
Abstract: Formally bounding side-channel leakage is important to bridge the gap between theory and practice in cryptography. However, bounding side-channel leakages is difficult because leakage in a cryptosystem could be from several sources. Moreover, the amount of leakage from a source may vary depending on the implementation of the cipher and the form of attack. To formally analyze the security of a cryptosystem, it is therefore essential to consider each source of leakage independently. This paper considers data prefetching, which is used in most modern day cache memories to reduce miss penalty. We build a framework that would help computer architects theoretically gauge the impact of a data prefetcher in time-driven cache attacks early in the design phase. The framework computes leakage due to the prefetcher using a metric that is based on the Kullback–Leibler transformation. We use the framework to analyze two commonly used prefetching algorithms, namely sequential and arbitrary-stride prefetching. These form the basis of several other prefetching algorithms. We also demonstrate its use by designing a new prefetching algorithm called even–odd prefetcher that does not have leakage in time-driven cache attacks.
  title={A Formal Analysis of Prefetching in Profiled Cache-Timing Attacks on Block Ciphers},
  journal={Journal of Cryptology},
  author={Chester Rebeiro and Debdeep Mukhopadhyay},