Cache Attacks: An Information and Complexity Theoretic Approach

In this paper, we present a formal analysis method of cache-based side-channel attacks by utilizing information and complexity theory. Although AES algorithm is chosen as the subject algorithm in the case study, the method is generic in the sense that it can be applied in many other algorithms that are subject to side-channel attacks. The adopted approach bases its analysis method on intermediate values used during the cryptographic computation observed via side-channels and explores the extent, to which the observations can be exploited in a successful attack. The method allows us to accurately estimate the feasibility of an attack strategy and compare efficiency of different attacks. Ultimate goal is to explore every attack possibility and estimate its corresponding feasibility to determine the optimal level of appropriate countermeasures. Using the method, we analyze four different cache-based attacks on AES and determine the complexity, feasibility, and strength of each attack. Our analysis demonstrates that second round-only attack on AES is feasible when the first and the last rounds are already protected.