Title: ScatterCache: Thwarting Cache Attacks via Cache Set Randomization Abstract: Cache side-channel attacks can be leveraged as a building block in attacks leaking secrets even in the absence of software bugs. Currently, there are no practical and generic mitigations with an acceptable performance overhead and strong security guarantees. The underlying problem is that caches are shared in a predictable way across security domains. In this paper, we eliminate this problem. We present ScatterCache, a novel cache design to prevent cache attacks. ScatterCache eliminates fixed cache-set congruences and, thus, makes eviction-based cache attacks unpractical. For this purpose, ScatterCache retrofits skewed associative caches with a keyed mapping function, yielding a security-domain-dependent cache mapping. Hence, it becomes virtually impossible to find fully overlapping cache sets, rendering current eviction-based attacks infeasible. Even theoretical statistical attacks become unrealistic, as the attacker cannot confine contention to chosen cache sets. Consequently, the attacker has to resort to eviction of the entire cache, making deductions over cache sets or lines impossible and fully preventing high-frequency attacks. Our security analysis reveals, that even in the strongest possible attacker model (noise-free), the construction of a reliable eviction set for Prime+Probe in an 8-way ScatterCache with 16384 lines requires observation of at least 33.5 million victim memory accesses as compared to fewer than 103 on commodity caches. ScatterCache requires hardware and software changes, yet is minimally invasive on the software level and is fully backward compatible with legacy software while still improving the security level over state-of-the-art caches. Finally, our evaluations show that the runtime performance of software is not curtailed and our design even outperforms state-of-the-art caches for certain realistic workloads.