Last-Level Cache Side-Channel Attacks Are Feasible in the Modern Public Cloud

Two programs sharing a cloud server share the CPU's last-level cache, and by filling a cache set with its own data and later checking what got evicted (Prime+Probe), one tenant can watch which memory a neighbor touches and read out its secrets — a classic attack that everyone, including Amazon's own security documentation, believed was impractical in a real cloud because the noise from thousands of other tenants would drown the signal; this paper (Illinois and Tel Aviv) shows it works anyway, with new techniques that build the crucial "eviction sets" in minutes instead of an estimated 14 hours under noise (using the L2 cache as a cheap pre-filter and binary search instead of brute force) and pull the secret out of the noise with frequency analysis — extracting a median 81% of an ECDSA signing key's nonce bits from a victim in Google's serverless cloud in 19 seconds, and proving to defenders that noise is not a defense.

The argument in one glance

Problem

Tenants share a cache, and a shared cache leaks secrets

In a public cloud, many customers' workloads run on the same physical machine and share the CPU's last-level cache (LLC). That sharing is a channel: with PRIME+PROBE, a malicious tenant fills a chosen cache set with its own data, lets a victim tenant run, then measures how long its data takes to reload — if the reload is slow, the victim evicted it, meaning the victim accessed that cache set. Repeated over time, this reveals which memory regions the victim touches, and for cryptographic code whose memory accesses depend on secret bits, that access pattern leaks the secret. It is a well-known attack, but it had only ever been demonstrated in quiet, controlled laboratory machines. The open question — and cloud providers' public position — was whether it could possibly work in a real, noisy, production cloud.
What people did

Assume the cloud's noise makes it impractical

The prevailing assumption was that production multi-tenancy is its own defense. A real cloud host runs thousands of workloads that constantly churn the shared cache, so any single victim's access is buried in a torrent of unrelated background activity. Cloud vendors said as much: Amazon's EC2 security documentation explicitly asserted that such LLC Prime+Probe attacks were infeasible in the wild. The reasoning was that the noise, the hidden physical-address mapping, the short lifetimes of serverless functions, and the complexity of modern cache hierarchies together made the attack a lab curiosity, not a real threat.
Why it fell short

Nobody had actually tried it in the cloud — and the prerequisite step collapses under noise

The trouble with "noise makes it impractical" is that it was an assumption, not a measurement. Actually attempting the attack in a production cloud exposes exactly where the difficulty is: the very first step, building an EVICTION SET — a small group of addresses that all map to the same cache set, needed to reliably fill and monitor that set — falls apart in noise. On Google Cloud Run, background LLC accesses run about 40x higher than in a lab (11.5 versus 0.29 accesses per millisecond per set), and with tens of thousands of possible cache sets and only a roughly one-hour function lifetime, the state-of-the-art eviction-set algorithms degrade catastrophically: their success rate drops from about 98% in the lab to 39-56% in the cloud, and constructing the sets for the whole system would take an estimated 14.6 hours — far longer than any victim runs. So the attack does not fail because it is impossible; it fails because one algorithmic step is not robust to noise. Which raises the real question: can that step be made robust?
This paper's idea

Make the eviction-set step noise-robust, and pull the signal out with structure

This paper (University of Illinois and Tel Aviv University — Zhao, Morrison, Fletcher, Torrellas) shows the attack IS feasible in the modern public cloud, by making its bottleneck robust. Two algorithmic ideas rebuild eviction sets under noise. L2-DRIVEN FILTERING uses the fact that the L2 cache's set-index bits are a subset of the LLC's, so two addresses that are not congruent in the cheap-to-test L2 cannot be congruent in the LLC — a cheap necessary-condition filter that prunes candidate addresses roughly 16x before the expensive LLC test. A BINARY-SEARCH pruning algorithm exploits that "the smallest set of addresses that can evict the target" is monotone, replacing quadratic group testing with logarithmic search, and parallel probing shrinks the measurement window so noise has less chance to corrupt it. Together they build all the eviction sets in about 2.4 minutes at 99.1% success. Then FREQUENCY ANALYSIS isolates the victim's periodic secret access from the aperiodic noise. The end result, framed as a warning to defenders: a median 81% of an ECDSA nonce's bits extracted from a victim in Google Cloud Run in 19 seconds — noise is not a defense.

Why this problem is worth solving

For anyone defending cloud infrastructure, the gap between “shown in a lab” and “works in production” is the whole ballgame — a threat that only materializes in quiet, controlled conditions can be treated as theoretical, while one that survives real-world noise demands mitigation. The mechanism at issue is the

a technique for spying on another program’s memory accesses through a shared cache without any direct access to its data. The attacker first PRIMES a cache set by loading enough of its own data to fill that set, evicting whatever was there. It then waits while the victim executes. Finally it PROBES by re-accessing its own data and timing it: if a line reloads quickly, it was still cached (the victim did not touch that set); if it reloads slowly, it was evicted, meaning the victim accessed that set and displaced it. By monitoring which sets the victim touches over time, the attacker reconstructs the victim’s memory-access pattern — and when a cryptographic routine takes different code paths (and thus touches different memory) depending on the bits of a secret key, that pattern betrays the key

. The reason this had been dismissed for real clouds is that Prime+Probe’s signal is a timing difference of a few cycles, and a production host generates a deluge of unrelated cache activity that swamps it. The contribution here is less a new attack than a rigorous answer to an unexamined assumption — an answer with direct consequences for what defenders must actually protect against.

The place the difficulty concentrates, and the place the paper’s techniques live, is a preliminary step most descriptions gloss over: the

a group of memory addresses that the attacker controls, all of which map to the SAME cache set as the victim data of interest. It is the prerequisite for everything: to prime a set you must be able to fill it, and to fill a specific set you need enough of your own addresses that land in it — that is exactly an eviction set. But the mapping from an address to a cache set is determined by physical-address bits the attacker cannot see (and, on modern Intel chips, by an undocumented hash across cache slices), so the attacker must DISCOVER an eviction set empirically: take a large pool of candidate addresses and, through repeated timing tests, prune it down to a minimal set that reliably evicts the target. Each timing test is itself a noisy Prime+Probe measurement, so in a busy cloud the pruning is fighting the same noise the attack does — and with tens of thousands of cache sets to cover and a victim that runs for minutes, a slow or unreliable pruning procedure simply never finishes

. This is why prior methods, tuned for quiet labs, collapsed in the cloud: not because the physics changed, but because their search algorithm was not designed to be fast and robust under noise. Making that one algorithmic step noise-robust is what turns the attack from theoretical to demonstrated — which is precisely why understanding it matters for the defense.

What people did before, and where it broke

Lab demonstrations of LLC Prime+Probe. Show the attack on a quiet, single-tenant machine with known address mappings (often using huge pages). Clean and reproducible, but they establish nothing about a noisy, opaque, multi-tenant production host — the environment that actually matters.
Assuming production noise is a defense. Cloud vendors argued the attack is impractical in the wild because of background cache churn. But this was an untested assumption; the paper measures the noise (about 40x the lab) AND shows it can be overcome, refuting the claim.
Classic eviction-set construction (group testing, Prime+Scope). Prune a candidate pool by splitting it into groups and testing which can be removed. Works in the lab (about 98% success), but in the cloud its success drops to 39-56% and it slows 10-24x, because each noisy timing test can give a wrong answer and the algorithm has no cheap way to reduce the candidate pool first.
Relying on non-inclusive caches / Snoop Filters. Modern Intel server chips decouple private L2 from the shared LLC via a Snoop Filter, which was thought to complicate these attacks. But the paper targets the Snoop Filter itself as the leakage channel, so this is no protection.
The gap. No prior work established whether LLC side channels are feasible in a real public cloud, because no one had made the eviction-set step robust to production noise. This paper does, and demonstrates an end-to-end cross-tenant key-bit leak — turning an assumed non-threat into a measured one.

How the attack is made feasible

Prune the eviction-set search cheaply, beat the noise, and extract the periodic signal

Frame it as a real-environment feasibility question

Prime+Probe is known to work in a quiet lab; the open question is whether it survives a production cloud's noise. The paper measures the real noise (about 40x the lab) and asks whether the attack's bottleneck — eviction-set construction — can be made robust to it, rather than assuming noise is protective.
↓ →
Pre-filter candidates with a cheap L2 necessary condition new

On these Intel chips, the L2 cache's set-index bits are a SUBSET of the LLC's, so two addresses that are not congruent in L2 cannot be congruent in the LLC. Testing L2 congruence is cheap, so the attacker builds one L2 eviction set and uses it to discard most candidate addresses before the expensive LLC test — a necessary-condition filter that cuts the candidate pool about 16x.
↓ →
Prune the survivors by binary search over a monotone test new

The classic method splits candidates into groups and tests removals, costing on the order of the associativity squared times the pool size. Instead, the paper observes that "the smallest prefix of candidates that can evict the target" is monotone — a prefix either can evict or cannot — so binary search finds that tipping point in logarithmic tests, dropping the cost to roughly the pool size times its logarithm.
↓ →
Shrink the measurement window with parallel probing new

Each pruning test is a noisy timing measurement, and a long test window lets background accesses corrupt it (a sequential test spanning 4.6 milliseconds saw about 53 stray accesses). Issuing the probe accesses in parallel to exploit memory-level parallelism shrinks the window to about 135 microseconds, cutting the chance of noise-induced false positives, with backtracking to recover from the few that slip through.
↓ →
Locate the leaking set by its periodicity, not its magnitude new

The victim's secret-dependent access recurs every loop iteration, so it is PERIODIC, while the cloud noise is aperiodic. Applying power spectral density analysis (Welch's method) to each monitored set, the attacker sees sharp spectral peaks at the crypto loop's frequency only on the set the victim actually touches — identifying the target set at 94.1% success where raw access counts are hopeless.
↓ →
Read the secret bits from timing, at high resolution new

With the target set found, parallel probing monitors it at fine time resolution and detects the victim's access at 84.1% at the crypto loop's cadence (versus 15.4% and 6.0% for prior probe methods). Each iteration's presence or absence of a mid-loop access to the target set reveals whether the corresponding secret nonce bit was 0 or 1.

Demonstrated cross-tenant on Google Cloud Run (a serverless/FaaS platform) against a deprecated OpenSSL 1.0.1e ECDSA implementation on Intel Skylake-SP/Cascade Lake-SP servers, with co-location assumed from prior work. Presented as a threat assessment for defenders.

The idea

An assumption is not a measurement — test the threat in the real environment. The whole paper turns on refusing to accept that “the cloud is too noisy for this attack” without checking. Prior work showed Prime+Probe in quiet labs; vendors extrapolated that production noise made it safe; nobody measured. When the authors actually attempt it in Google Cloud Run, they find the noise is real (about 40x the lab) but that it defeats only ONE algorithmic step — eviction-set construction — which can be redesigned to be robust. This is the measure-in-the-real-conditions-not-the-controlled-ones discipline the site keeps sharpening: the PCIe-collectives page measures bandwidth under real contention because isolated numbers lie, the accelerator- characterization page derives guidelines from real workloads. Here it carries a security-specific edge — noise is not a defense, and a mitigation believed sufficient because it was never truly tested is not a mitigation at all. The contribution is the rigor of closing an untested gap between lab and reality.

Use a cheap necessary condition to prune an expensive search. The first technique is a clean algorithmic idea with nothing security- specific about it. Finding addresses congruent in the LLC is expensive and noisy, but LLC-congruence REQUIRES L2-congruence (because the L2 set-index bits are a subset of the LLC’s), and testing L2-congruence is cheap. So the attacker applies the cheap necessary- condition test first, discarding the roughly 15/16 of candidates that cannot possibly be LLC-congruent, and only runs the expensive test on the survivors. This is the prune-the-search-with-a-cheap-filter discipline the site rewards — the compiler-autotuning page pruning its configuration space with constraints, the memory-allocation page using a solver to prune infeasible branches early — where a cheap test that can only rule things OUT (never in) collapses the work the expensive test must do. The nesting of cache index bits is exactly the structure that makes such a filter exist.

Exploit structure to beat noise — monotonicity for a fast search, periodicity to find the signal. Two of the techniques recover a clean result from a noisy one by leaning on structure. The pruning uses MONOTONICITY: because a larger prefix of candidate addresses can only be more likely to evict the target, the smallest evicting prefix can be found by binary search in logarithmic time instead of quadratic group testing — the same exploit-a-monotone-property-to-search-fast move the site just met in the concurrent-graph and collectives pages. The target-set identification uses PERIODICITY: the victim’s secret access repeats with the crypto loop, so a frequency-domain analysis (power spectral density) shows a sharp peak exactly where the periodic signal is, while the aperiodic noise spreads across the spectrum — the same recover-the-signal-from-noise-by-its-structure move the noisy- quantum page makes when it exploits that errors cluster in Hamming space. In both, a structural property (monotone eviction, periodic access) is the lever that turns an intractable noisy problem into a tractable one.

Why noise was believed to be a defense, and why it is not

Closing the gap between the lab and the cloud

Assessing LLC side-channel feasibility in a production cloud. Numbers from the paper's Google Cloud Run measurements.

Step 1 of 5

The lab result

On a quiet, single-tenant machine, Prime+Probe works cleanly: eviction sets build at about 98% success, the timing signal is clear, and secret-dependent memory accesses are readable. This is what prior work demonstrated, and what made the attack well known.

in the lab the cache is nearly idle — about 0.29 background accesses per millisecond per set
with known address mappings (huge pages), even eviction-set construction is straightforward

Why it works

The attack was only assumed impractical in the cloud, never measured → the paper attempts it in Google Cloud Run and finds noise defeats only the eviction-set step → the question becomes whether that one step can be made robust, not whether the attack is possible.
Finding LLC-congruent addresses is expensive and noisy, but requires L2-congruence which is cheap to test → an L2 necessary-condition filter discards ~15/16 of candidates first → the expensive LLC search runs on a pool about 16x smaller.
The smallest evicting prefix of candidates is monotone → binary search finds it in logarithmic tests instead of quadratic group testing → eviction-set construction drops from an estimated 14.6 hours to about 2.4 minutes at 99.1% success.
A long timing test lets background noise corrupt it → parallel probing shrinks the window from 4.6 milliseconds to ~135 microseconds → false positives fall enough that backtracking can recover, making the search robust to cloud noise.
The victim’s secret access is periodic while noise is aperiodic → frequency (power-spectral-density) analysis isolates the leaking set by its spectral peak → the target set is found at 94.1% and its bits read at 84.1% where raw magnitudes fail.

What it costs (scope, and the defensive reading)

The target is deprecated, but the technique is general. The victim is OpenSSL 1.0.1e, long end-of-life and since replaced by constant-time code; the point is not that exact library but that the eviction-set and signal-extraction techniques are architecture- agnostic against ANY code whose memory accesses depend on secret bits.
Intel server chips, specific mapping. The L2-filter and the Snoop-Filter targeting are demonstrated on Skylake-SP and Cascade Lake-SP; ARM and AMD use different cache hashing and would need adapted techniques, though the underlying ideas transfer.
Co-location is assumed, not solved here. The attack presumes the attacker already shares a host with the victim; the paper leans on prior work for achieving that, so defenders should treat co-location as achievable rather than a barrier.
The victim must actually leak and be observable. Truly constant-time code — no secret-dependent branches, loads, or loop counts — does not leak through this channel, and an asynchronous or rarely-triggered victim complicates the synchronization the attack needs.
This is a feasibility result, not a key recovery demonstrated end to end. It extracts 81% of nonce bits; converting those to a full private key via lattice methods is standard but not carried out here — the contribution is proving the leak is practical, which is what defenders need to know.

The evaluation

An end-to-end cross-tenant attack on a vulnerable ECDSA implementation (OpenSSL 1.0.1e) in Google Cloud Run, on Intel Skylake-SP and Cascade Lake-SP servers, measuring eviction-set construction time and success against prior methods, target-set identification, bit-detection rate, and end-to-end nonce extraction, with co-location assumed.

Building eviction sets: lab versus noisy cloud

Property	Quiet lab (prior work)	Prior methods in the cloud	This work's techniques
Eviction-set success rate
Time to cover the whole system
Candidate pruning
Noise handling	Little noise to handle
Feasible in a FaaS lifetime?	n/a (lab)

The attack's feasibility hinges entirely on the eviction-set step: prior methods that work in the lab need an estimated 14.6 hours in the cloud, while the L2 necessary-condition filter, monotone binary search, and parallel probing bring it to 2.4 minutes at 99.1% success — enough to run the full attack inside a serverless function's lifetime, refuting the claim that cloud noise makes LLC side channels impractical.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is a threat-assessment result, and its scope should be read precisely. The victim (OpenSSL 1.0.1e) is long deprecated and modern libraries use constant-time arithmetic; the enduring claim is that the eviction-set and signal-extraction TECHNIQUES are architecture- agnostic against any secret-dependent memory-access pattern, not that this exact library is at large. The demonstration is on Intel Skylake-SP/Cascade Lake-SP, and the L2-filter and Snoop-Filter targeting would need adaptation on ARM or AMD. It assumes co-location is already achieved (leaning on prior work) and that the victim is observable and synchronizable; truly constant-time code that makes no secret-dependent branch, load, or loop leaks nothing through this channel. And it extracts 81% of nonce bits rather than demonstrating a full key recovery — the standard lattice step to a private key is noted but not performed. None of this softens the core message for defenders — that LLC Prime+Probe attacks, long assumed impractical in production because of noise, are in fact feasible once the eviction-set step is made noise-robust (cheap L2 pre-filtering, monotone binary search, parallel probing) and the periodic secret signal is separated from aperiodic noise by frequency analysis; so multi-tenant noise is not isolation, and the real mitigations are constant-time code, cache partitioning, core isolation, and aggressive serverless timeouts.

Background

Test the assumption for real, prune with a cheap filter, and exploit structure to beat noise

This paper sits in the site’s security-and-systems cluster and rhymes with several ideas covered elsewhere on this site. Its governing move is the measure-in-the-real-conditions discipline: an attack believed impractical because of production noise had never actually been tried there, so the contribution is testing the assumption and finding it false — the same real-environment rigor the PCIe-collectives page brings when it measures bandwidth under true contention rather than trusting isolated numbers, and the accelerator-characterization page brings when it derives guidelines from real workloads. Its first technique is a cheap-necessary-condition filter to prune an expensive search — L2-congruence is required for LLC-congruence and is cheap to test, so it discards most candidates before the costly test — the same prune-the-search-early discipline the compiler-autotuning page uses with constraints and the on-chip-memory-allocation page uses when its solver prunes infeasible branches. Its second and third techniques are exploit-a-structural-property-to-beat-noise: monotonicity turns quadratic group testing into logarithmic binary search, exactly the monotone-property-enables-fast-search move the concurrent-graph and collectives pages make, and periodicity lets frequency analysis pull the victim’s signal out of aperiodic noise, exactly the recover-the- signal-from-noise-by-its-structure move the noisy-quantum page makes exploiting that errors cluster in Hamming space. Even shrinking the measurement window with parallel probing to reduce noise exposure echoes the make-the-observation-fast-and-cheap discipline the tiered- memory and data-plane pages use to keep measurement from corrupting what it measures. The security lesson layered on top — that a defense assumed sufficient because it was never truly tested is not a defense — is the sharpest form of the site’s recurring warning against trusting a proxy or an assumption in place of a measurement.

If you remember only three things

1. In a multi-tenant cloud, tenants share the last-level cache, and a Prime+Probe side channel lets one tenant infer another's secret-dependent memory accesses — but these attacks had only been shown in quiet labs, and it was widely assumed (and asserted by cloud vendors) that production noise made them impractical; the assumption was never actually measured, and the real obstacle turns out to be a single step, building an EVICTION SET (addresses mapping to the same cache set), which prior algorithms cannot do reliably when background cache activity is about 40x the lab and would take an estimated 14.6 hours system-wide.
2. The paper makes that step noise-robust with two algorithmic ideas plus signal processing: an L2-driven filter exploits that L2 set-index bits are a subset of the LLC's, so L2-congruence is a cheap necessary condition that prunes candidates ~16x before the expensive LLC test; a binary-search pruning algorithm exploits that the smallest evicting address set is monotone, replacing quadratic group testing with logarithmic search, while parallel probing shrinks each noisy test window from 4.6 milliseconds to ~135 microseconds; and power-spectral-density (frequency) analysis isolates the victim's PERIODIC secret access from the aperiodic cloud noise, identifying the leaking cache set at 94.1%.
3. Together these build all eviction sets in ~2.4 minutes at 99.1% success (versus an estimated 14.6 hours for prior methods) and drive an end-to-end cross-tenant attack that extracts a median 81% of an ECDSA nonce's bits from a victim in Google Cloud Run in 19 seconds — enough for standard lattice cryptanalysis to recover the private key — refuting the vendor claim that LLC side channels are impractical in the wild. The defensive lessons: test threat assumptions in the real noisy environment rather than trusting them, because noise is not isolation; and the real mitigations are constant-time code, cache partitioning, core isolation, and aggressive serverless timeouts.

Check yourself

Check your understanding

1. Cloud vendors argued that production noise made LLC Prime+Probe attacks impractical. Predict why the paper treats this as the crux to investigate rather than a settled fact.
2. The first new technique filters candidate addresses using the L2 cache before running the expensive LLC test. Predict why testing L2 congruence first is a sound and powerful optimization.
3. To find the victim's leaking cache set amid heavy noise, the attacker does NOT look for the set with the most accesses; it applies frequency analysis to find a periodic signal. Predict why periodicity is the right thing to look for.
4. The paper's binary-search eviction-set algorithm replaces classic group testing, cutting the cost from roughly quadratic to roughly logarithmic in the candidate pool. Predict what property makes binary search valid here.

Sources

arXiv:2405.12469 — Last-Level Cache Side-Channel Attacks Are Feasible in the Modern Public Cloud (Extended Version) — ASPLOS 2024 (full text read via ar5iv).
ACM DL: Last-Level Cache Side-Channel Attacks Are Feasible in the Modern Public Cloud — published version.