Revisiting Prime+Prune+Probe: Pitfalls and Remedies

Abstract

Randomizing the mapping of memory addresses to cache locations is a promising approach for protecting computer systems against cache attacks. Multiple randomized caches have been proposed recently, with the aim of preventing adversaries from creating eviction sets - collections of addresses that compete with target memory addresses on cache space. However, Purnal et al. (IEEE SP 2021) demonstrated the Prime+ Prune+ Probeattack, which allows attackers to efficiently build generalized eviction sets, enabling target memory address eviction with a high probability. As the complexity of constructing eviction set is a key factor in randomized cache design, the Prime+prune+probe attack significantly reduces the security bounds of these randomizing designs. Since the Prime+prune+probe attack is probabilistic, generalized eviction sets often get stuck after repeated use, making them ineffective for typical cache attack settings. Prior works have noticed this behavior and proposed mitigation approaches. These approaches are based on evicting members of the eviction set from the cache, either probabilistically, using random memory accesses, or directly, using dedicated flush instructions. However, these proposals do not analyze the effectiveness of the techniques or evaluate their success. In this work we revisit Prime+prune+probe and analyze it in light of the possibility of eviction sets getting stuck. We observe that flushing does not behave as anticipated in realistic cache architectures, where invalid cache lines are filled first before evicting other lines. We further propose a new technique for allowing repeated attacks - combining random noise with flushing. We conduct an in-depth analysis of all discussed techniques and compare their complexity attacking an AES T-table implementation. We find that combining probabilistic eviction with flushing outperforms the traditional approaches by a factor of two, allowing attackers to increase the granularity and observe victim processes even better than in prior works.