Das Paper „Revisiting Prime+Prune+Probe: Pitfalls and Remedies“ von Moritz Peters, Florian Stolz, Jan Philipp Thoma, Tim Güneysu und Yuval Yarom wurde für die ACSAC 2025 akzeptiert.
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+PROBE attack, which allows attackers to efficiently build generalized eviction sets, which evict the target memory address 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, based on evicting members of the eviction set from the cache, using either probabilistically, by random memory accesses, or directly, using dedicated flush instructions. However, these techniques are not accompanied by an analysis of their effectiveness or any evaluation of their success.
In this work we revisit the analysis of the PRIME+PRUNE+PROBE in light of the possibility of eviction sets getting stuck. We first observe that flushing does not behave as anticipated in realistic cache architectures where invalid cache lines are filled first before evicting other lines. We also 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 run with higher granularity, being able to observe victim processes even better than before.