Prime+Probe — a side channel with nothing shared

FLUSH+RELOAD is precise, but it has a prerequisite that often doesn't hold: shared memory with the victim. Across VMs on a cloud host, or a victim that maps nothing of yours, there's no line to clflush. Prime+Probe removes the requirement entirely — it spies on the cache through contention rather than sharing.

the cache is a grid of sets#

A set-associative cache splits into sets; each address maps to one set, and a set holds W lines (a W-way cache). Access a set's worth of your own addresses — an eviction set of W lines that all map to the same set — and you've filled it, displacing whatever was there. That's the entire lever.

1
2
3
4

set k:  [ way0 ][ way1 ][ way2 ] ... [ way W-1 ]
prime:  fill all W ways with attacker lines
victim: touches an address mapping to set k  ->  evicts one attacker line
probe:  re-access the W lines; the evicted one is now a slow miss

prime, wait, probe#

1
2
3
4
5

PRIME   access every line in the eviction set for set k   (fill the set)
WAIT    let the victim execute
PROBE   re-access the eviction set, timing each line:
          all fast      -> victim did NOT use set k
          one+ slow     -> victim evicted your line -> it USED set k

A slow probe means the victim accessed some address that maps to set k. You don't learn which address (that's the resolution you trade away versus FLUSH+RELOAD), but a pattern of busy sets over time is plenty to fingerprint an AES T-table access, an exponentiation step, or a keystroke.

the hard part: building eviction sets#

You need W addresses that collide in the target set. In L1 that's easy — the set index comes from virtual-address bits you control. In the last-level cache, where cross-core spying happens, it's hard: the LLC is physically indexed and sliced (Intel's undocumented hash spreads addresses across slices), so you don't know which addresses collide. You find eviction sets empirically:

• allocate a large buffer (huge pages help — they fix the low physical bits);
• use timing to group-test addresses into colliding sets (an address belongs to a candidate set if accessing the set slows its reload);
• prune each set down to exactly the W lines that evict the target.

1
2
3
4
5
6

candidates = huge_page_buffer_lines()
evset = []
for line in candidates:
    if access_then_time(evset + [line]) > THRESHOLD:   # adding it causes eviction
        evset.append(line)
        if len(evset) == W: break                       # W = associativity

1
2

set 3: BUSY  set 7: idle  set 11: BUSY ...  -> AES key byte candidates
segfault{i_never_touched_your_memory}

where it fits#

• No sharing required — the reason Prime+Probe, not FLUSH+RELOAD, is the tool for cross-VM and cross-tenant cloud attacks.
• Coarser but broader — set-level, noisier, and the eviction-set work is real, but it reaches victims that share nothing mappable.
• The substrate for bigger attacks — LLC Prime+Probe is the covert channel many cross-core Spectre and Rowhammer setups build on.

The two cache attacks are a resolution/reach trade: FLUSH+RELOAD when you share a page and want exact lines; Prime+Probe when you share nothing and can live with "which set." Between them they cover almost every situation where two security domains land on the same cache — which, on modern hardware, is nearly all of them.