Cryptology ePrint Archive: Report 2015/1191

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

Chester Rebeiro and Debdeep Mukhopadhyay

Abstract: Formally bounding side-channel leakage is important to bridge the gap between the theory and practice in cryptography. However, bounding side-channel leakages is difficult because leakage in a crypto-system 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 crypto-system against a form of attack, 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 the miss penalty. To the best of our knowledge, we show for the first time that micro-architectural features like prefetching is a major source of leakage in profiled cache-timing attacks. We further quantify the leakage due to important data prefetching algorithms, namely sequential and arbitrary-stride prefetching. The analytical results, with supported experimentation, brings out interesting facts like the effect of placement of tables in memory and the cipher’s implementation on the leakage in profiled cache-timing attacks.

Category / Keywords: foundations / quantifying information leakage, formal modeling, cache memories, data prefetching, profiled cache-timing attacks

Original Publication (with major differences): Journal of Cryptology

Date: received 13 Dec 2015, last revised 7 Jun 2021

Contact author: chetrebeiro at gmail com

Available format(s): PDF | BibTeX Citation

Note: submitted to the Journal of Cryptology (in June 2011)

Version: 20210607:124821 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]