Seeds of SEED: A Side-Channel Resilient Cache Skewed by a Linear Function over a Galois Field

Abstract

Consider a set-associative cache with p ⁿ sets and p ⁿ ways where p is prime and n > 0. Furthermore, assume that the cache may be shared among p ⁿ mutually distrusting principals that may use the Prime+Probe side-channel attack against one another; architecturally, these principals occupy separate security domains (for example, separate processes, virtual machines, sandboxes, etc.). This paper shows that there exists a linear skewing of cache sets over the Galois field G p n that exhibits the following property: each cache set of each security domain intersects every cache set of every other security domain exactly once. Therefore, a random eviction from a single cache set in security domain A may be observed via Prime+Probe in any of security domain B’s cache sets. This paper characterizes this linear skewing and describes how it can be implemented efficiently in hardware.