Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache

Antoon Purnal; Ingrid Verbauwhede

REVIEW 2 major objections 6 minor 12 references

Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims ScatterCache's profiling cost drops from about $2^{25}$ to below $2^{10}$ victim accesses and that arbitrary cache collisions enable covert channels.

desk verdict Solid profiling generalization undercuts ScatterCache's security assumptions, but the scan step needs a fix and the covert channel claims are unsupported. read the letter →

arxiv 1908.03383 v1 pith:YK3GTJYA submitted 2019-08-09 cs.CR

Antoon Purnal , Ingrid Verbauwhede This is my paper · ORCID

classification cs.CR

keywords cache-basedtimingchannelsScatterCachePrime+Probeevictionsetprofilingcovertrandomizedarchitecturesrandomizationmicroarchitecturalattacks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

ScatterCache is a protected cache architecture that randomizes address-to-set mapping with a keyed cryptographic function, on the claim that eviction-set profiling is too expensive for practical Prime+Probe attacks. This note argues that under the same noise-free assumptions as the original ScatterCache analysis, the cost is much lower: a generalized profiling strategy reduces the required victim accesses from about $2^{25}$ to below $2^{10}$ for an 8-way cache with 11 index bits. It also argues that two cooperating processes can turn arbitrary cache collisions into a covert channel whose bandwidth lies between full-cache eviction and ordinary Prime+Probe. If these claims hold, ScatterCache's protection against contention-based timing channels is far weaker than its designers estimated.

What carries the argument

The load-bearing object is the pruned attacker address set. The attacker loads $k$ addresses, repeatedly re-reads them, and discards any address whose access latency is high until no further addresses are evicted; this leaves $k'$ addresses that are guaranteed to reside at different cache locations. Their count $k'$ sets the paper's central probability, $p = k'/(n_\text{ways} \cdot 2^{b_\text{indices}})$, which converts profiling effort from the original quadratic-to-linear cost in victim accesses. For covert channels, the equivalent machinery is collision search under collaboration: because any shared cache line between transmitter and receiver is usable, the birthday bound replaces second-preimage resistance as the relevant cost.

What would settle it

Run the paper's profiling procedure on a hardware or simulated ScatterCache with a deliberately noisy cache, for example a second process issuing random accesses, and measure whether pruning terminates and whether the victim-access count follows $n_\text{ways} \cdot 2^{b_\text{indices}} \cdot t / k'$; if interference prevents termination or inflates the count, the claimed reduction is not attainable outside the noise-free model.

Watch

Extended reading notes

Core claim

The central discovery is that ScatterCache's profiling difficulty is not intrinsic but an artifact of an overly restricted attack strategy. Instead of asking how many victim accesses are needed for each individual colliding address, the attacker floods the cache with $k$ of its own addresses, prunes away the ones evicted by internal collisions until $k'$ stable resident addresses remain, and then lets each victim access evict one of those $k'$ addresses with probability $p = k'/(n_\text{ways} \cdot 2^{b_\text{indices}})$. The expected number of victim accesses per colliding address is $1/p$, so the total for $t$ addresses is $n_\text{ways} \cdot 2^{b_\text{indices}} \cdot t / k'$, which is the original ScatterCache formula divided by $k'$; the original formula is recovered at $k' = 1$. For cooperating transmitter and receiver, the same pruning trick turns the harder second-preimage search for a specific victim address into a birthday-problem collision search, giving a covert channel whose bandwidth interpolates between full-cache eviction and ordinary Prime+Probe.

Load-bearing premise

The entire quantitative gain rests on the model being completely noise-free: no other processes, no systematic cache interference, and a reliable hit/miss distinction; the paper states this in Section 3 as a deliberate match to the original ScatterCache analysis. If real-world noise prevents the pruning step from terminating cleanly, the claimed victim-access reductions are not guaranteed.

Editorial extensions

If this is right

For an 8-way set-associative cache with 11 index bits, an eviction set of 275 colliding addresses can be profiled in under five seconds at $k=8000$, rather than the roughly 38 hours estimated in the original analysis.
The original ScatterCache victim-access effort is a worst case of the generalized formula, so randomized caches that rely on that formula must re-derive their security margins for every $k' > 1$.
Two cooperating processes can communicate through ScatterCache at a rate between full-cache eviction and ordinary Prime+Probe, trading bit-error rate against bandwidth through the attack parameters $f$ and $s$.
Because the attack uses only hit/miss timing and pruning, the same profiling strategy transfers to other randomized cache mappings that are analyzed under the same noise-free assumptions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: the birthday-style collision shortcut likely applies to other keyed randomization defenses, such as encrypted-index caches, so defenders should estimate collision-search cost whenever processes can collaborate.
Inference: the pruning step could probably be made noise-tolerant by replacing its clean termination criterion with a statistical threshold, but the paper does not demonstrate this; testing that variant would be a natural next step.
Inference: since the attack never breaks the index derivation function itself, changing the cryptographic key or the cipher cannot close the channel; a defense would have to prevent an attacker from keeping many addresses resident at once.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

You should know two things about this note. First, it makes a real improvement to Prime+Probe profiling against ScatterCache: by using k attacker addresses and pruning to k', the expected victim-access count drops from nways^2 * 2^b * t to nways * 2^b * t / k'. Second, the covert channel section is a sketch, not a demonstration; there are no bit-error rates, bandwidths, or simulator outputs. The profiling result is the reason to read it.

What is genuinely good: the derivation is self-contained, matches the stated noise-free model, and the simulation checks out in the paper's own table. It correctly generalizes the original ScatterCache analysis (k=1 recovers it) and it challenges a published defense under the defense's own assumptions. That is fair and useful. The use of birthday-style collisions for covert channels is a natural extension and worth exploring, though it is not quantified here.

The biggest soft spot is step (iii) of Section 4. The text says the attacker accesses the full set of k' addresses again and stores any address with high latency as victim-evicted. That is wrong as written. When the attacker reloads the first slow address, that reload can evict another, not-yet-scanned attacker address; that second address will then also appear slow. For nways=8, bindices=11, k=8000, the numbers in the paper imply roughly a 32% chance per successful iteration that the reload hits a surviving attacker address, and about 16% of iterations produce at least one false positive. The paper never says to stop at the first miss, and never accounts for collateral evictions. A stop-at-first-miss rule would likely fix the profiling, but the text needs to say so, and the claimed t=275 reliability should be re-checked.

Other soft spots are minor. No code or data is released, so "experimentally validated" is hard to verify; the table is nearly unreadable in the arXiv version; and the covert channel section gives no quantitative results at all. The noise-free assumption is inherited from ScatterCache, so it is not a flaw by itself, but it does mean the practical claims are not yet tested.

Who should read this: anyone working on randomized cache defenses or cache side channels. It deserves a serious referee, not a desk reject. A referee should ask for the simulator, for numeric covert-channel results, and for a precise statement of the scan rule in step (iii).

My recommendation: send it out, with a request for revision on those points.

Referee Report

2 major / 6 minor

Summary. This short note analyzes the security of the ScatterCache randomized cache architecture in a noise-free model matching the original ScatterCache security analysis. The first contribution is a more efficient Prime+Probe profiling method: instead of using a single attacker address per trial, the attacker populates a set of k addresses, prunes them to a collision-free set of k' addresses, and then repeatedly triggers the victim access and scans for evicted addresses. The paper derives the expected number of victim accesses as Av = nways * 2^bindices * t / k', a reduction from the original nways^2 * 2^bindices * t by a factor of nways * k'. For the concrete 8-way, 11-index-bit example with k=8000, the paper claims the victim access count for t=275 drops from roughly 2^25 to below 2^10. The second contribution is a covert channel scheme for probabilistic caches that exploits arbitrary collisions between collaborating transmitter and receiver processes. The paper reports simulation-based validation for the profiling method and states that both phases of the covert channel were simulated, but provides no quantitative results for the covert channel.

Significance. If the profiling reduction is correct, it materially weakens the security guarantees claimed for ScatterCache, since eviction-set construction is several orders of magnitude cheaper than originally estimated. The derivation of Av is clean, self-contained, and parameter-free apart from the attack-set size k, and the simulation results reported in Table 1 are broadly consistent with the formula. The covert channel idea is also interesting, as it turns the birthday-paradox effect into a communication primitive, but as presented it is only a sketch. The lack of any bit-error-rate, bandwidth, or comparison data means the paper's second advertised contribution is not yet substantiated. The noise-free assumption is explicitly inherited from the original ScatterCache analysis, which is reasonable, though it limits direct practical applicability.

major comments (2)

[§5 (Covert channels)] The covert channel contribution is not quantitatively supported. The text states "We have successfully simulated both the profiling and transmission phase of the described covert channel attack" (Discussion, §5), but no bit error rates, bandwidth figures, threshold values, or comparisons to full-cache eviction are reported anywhere in the manuscript. The abstract claims the approach "significantly outperforms known covert channels (e.g. full-cache eviction)", yet the only evidence is an unquantified statement of successful simulation. This is load-bearing because the second contribution is advertised as a demonstration, not merely as a possibility result. The authors should either add a concrete evaluation (BER as a function of d, s, f, and cache parameters; achieved bandwidth against a baseline) or substantially temper the claims in the abstract and conclusion.
[§4, step (iv) and Eq. (1)] The expected victim-access formula Av = t/p does not account for the fact that the same attacker address can be evicted and identified more than once. The procedure re-primes the same k' addresses each iteration; if the victim evicts an address that was already stored in a previous iteration, that iteration does not add a new colliding address. To obtain t distinct colliding addresses, the expected number of successful evictions should include a coupon-collector factor, or the authors must specify that identified addresses are excluded from subsequent scans (in which case p decreases over time and Av is higher than t/p). For the headline parameters (k'=5305, t=275) the discrepancy is about 2%, so the qualitative claim survives, but the derivation as written is not exact. The manuscript should either state the additional assumption or correct the formula.

minor comments (6)

[§4, step (iii)] The scan in step (iii) would benefit from an explicit statement that the pruning step guarantees the k' addresses are pairwise non-colliding in every cache way, so that reloading a slow address cannot evict a not-yet-scanned attacker address. This resolves the apparent ambiguity about collateral evictions and makes the procedure unambiguous for implementers.
[Table 1] Table 1 is very difficult to parse in the current formatting; rows and columns run together, and some entries appear to be missing or merged. The table should be reformatted so that each parameter (nways, bindices, k, mpr, k', p, Av, Aa/Av, amiss, time) is clearly separated.
[§4, step (ii)] The sentence "The expected value of the cache coverage with the coupon collector problem gives an estimate of this p" is vague. The connection between the coupon-collector problem and the stated probability p = k'/(nways * 2^bindices) should be spelled out or removed.
[§5, transmission phase] The threshold d is introduced but no guidance is given on how it should be set, apart from a generic comment that its optimal value may be greater than zero. A concrete analysis or even a simulated example would help the reader understand the trade-off between false positives and false negatives.
[General] No simulation code or raw data is provided, so the results are not independently reproducible. For a paper that relies on simulation evidence, at least a reference implementation or a detailed statistical description of the simulator would strengthen the work.
[§5, profiling phase, step (iv)] The text says "each transmitter address collides with at least one victim address" but in the covert-channel setting the collision is with the receiver's addresses, not a victim's. This appears to be a typo and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the improved profiling bound follows directly from the stated probabilistic cache model and is not fitted to data.

full rationale

The paper's central claim is a probabilistic reduction in profiling effort: with k' pruned attacker addresses, the probability that a victim access evicts one of them is p = k'/(nways * 2^bindices), and the expected number of victim accesses to collect t colliding addresses is therefore Av = t/p = nways * 2^bindices * t / k'. This is derived directly from the model assumptions (pseudorandom IDF, random replacement, noise-free cache) rather than fitted to measurements or renamed from an existing result. The original ScatterCache expression is recovered as the k' = 1 limit with the factor c, which is a consistency check, not a circular step. The authors cite the original ScatterCache paper [11] for the baseline analysis and for the t = 275 exploitation parameter, but these citations are not self-citations and do not carry the load of the new derivation; the new bound is supported by the paper's own equations and by simulation. The paper explicitly states its noise-free assumption, matching the original analysis, and identifies noisy environments as future work, which is a stated limitation rather than an input disguised as a prediction. The reviewer's identified scan-order false-positive issue is a correctness concern about the attack procedure, not a circularity of the derivation, so it does not affect the circularity score. Overall, the derivation is self-contained and no load-bearing step reduces to its own inputs by construction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or system entities. Its quantitative claims depend on attacker-chosen parameters (k and d) and on the stated noise-free, pseudorandom-IDF, and random-replacement assumptions. No data fitting is used.

free parameters (2)

attack set size k = 8000 (example used in the runtime estimate)
Chosen by the attacker; larger k reduces victim accesses but increases attacker accesses, so it is a trade-off parameter, not fitted to data.
covert channel threshold d = not specified
Determined ahead of time as an attack parameter to balance false positives; the paper does not give a method to set it.

assumptions (4)

domain assumption The IDF is a perfectly pseudorandom function (no cryptanalytic attacks).
Stated in Section 3 under 'Cryptographic unit (IDF)' and matches the ScatterCache analysis.
domain assumption The cache uses a random replacement policy.
Stated in Section 3 under 'Cache properties'.
domain assumption The system is noise-free; no other processes or systematic effects influence the cache.
Stated in Section 3 under 'Noise-free model'.
standard math Birthday and coupon-collector probability bounds apply.
Used in Sections 4 and 5 to estimate collisions and expected events.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache." pith.science (2026). https://pith.science/paper/YK3GTJYA

@misc{pith2026190803383,
  author       = {Pith},
  title        = {Pith review of: Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YK3GTJYA}},
  note         = {Machine review of arXiv:1908.03383}
}

abstract

Timing channels in cache hierarchies are an important enabler in many microarchitectural attacks. ScatterCache (USENIX 2019) is a protected cache architecture that randomizes the address-to-index mapping with a keyed cryptographic function, aiming to thwart the usage of cache-based timing channels in microarchitectural attacks. In this note, we advance the understanding of the security of ScatterCache by outlining two attacks in the noise-free case, i.e. matching the assumptions in the original analysis. As a first contribution, we present more efficient eviction set profiling, reducing the required number of observable victim accesses (and hence profiling runtime) by several orders of magnitude. For instance, to construct a reliable eviction set in an 8-way set associative cache with 11 index bits, we relax victim access requirements from approximately $2^{25}$ to less than $2^{10}$ . As a second contribution, we demonstrate covert channel profiling and transmission in probabilistic caches like ScatterCache. By exploiting arbitrary collisions instead of targeted ones, our approach significantly outperforms known covert channels (e.g. full-cache eviction).

Figures

Figures reproduced from arXiv: 1908.03383 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Preprint available at http://cr.yp.to/papers.html# cachetiming (2005)

Bernstein, D.J.: Cache-timing attacks on AES. Preprint available at http://cr.yp.to/papers.html# cachetiming (2005)

work page 2005
[2]

In: Cryptographers’ track at the RSA conference

Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Cryptographers’ track at the RSA conference. pp. 1–20. Springer (2006)

work page 2006
[3]

In: 2019 IEEE Symposium on Security and Privacy (2019)

Kocher, P., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., Prescher, T., Schwarz, M., Yarom, Y.: Spectre attacks: Exploiting speculative execution. In: 2019 IEEE Symposium on Security and Privacy (2019)

work page 2019
[4]

In: 27th USENIX Security Symposium

Lipp, M., Schwarz, M., Gruss, D., Prescher, T., Haas, W., Fogh, A., Horn, J., Mangard, S., Kocher, P., Genkin, D., Yarom, Y., Hamburg, M.: Meltdown: Reading kernel memory from user space. In: 27th USENIX Security Symposium. pp. 973–990 (2018)

work page 2018
[5]

In: 23rd USENIX Security Symposium

Yarom, Y., Falkner, K.: Flush+ reload: a high resolution, low noise, l3 cache side-channel attack. In: 23rd USENIX Security Symposium. pp. 719–732 (2014)

work page 2014
[6]

In: International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment

Gruss, D., Maurice, C., Wagner, K., Mangard, S.: Flush+ ﬂush: a fast and stealthy cache attack. In: International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. pp. 279–299. Springer (2016)

work page 2016
[7]

In: 2015 IEEE Symposium on Security and Privacy

Liu, F., Yarom, Y., Ge, Q., Heiser, G., Lee, R.B.: Last-level cache side-channel attacks are practical. In: 2015 IEEE Symposium on Security and Privacy. pp. 605–622. IEEE (2015)

work page 2015
[8]

ACM SIGARCH Computer Architecture News 35(2), 494–505 (2007)

Wang, Z., Lee, R.B.: New cache designs for thwarting software cache-based side channel attacks. ACM SIGARCH Computer Architecture News 35(2), 494–505 (2007)

work page 2007

Show all 12 references

[9]

In: Pro- ceedings of the 41st annual IEEE/ACM International Symposium on Microarchitecture

Wang, Z., Lee, R.B.: A novel cache architecture with enhanced performance and security. In: Pro- ceedings of the 41st annual IEEE/ACM International Symposium on Microarchitecture. pp. 83–93. IEEE Computer Society (2008)

2008
[10]

In: 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)

Qureshi, M.K.: Ceaser: Mitigating conﬂict-based cache attacks via encrypted-address and remapping. In: 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). pp. 775–

2018
[11]

In: 28th USENIX Security Symposium (2019)

Werner, M., Unterluggauer, T., Giner, L., Schwarz, M., Gruss, D., Mangard, S.: SCATTERCACHE: Thwarting Cache Attacks via Cache Set Randomization. In: 28th USENIX Security Symposium (2019)

2019
[12]

In: In- ternational Conference on Detection of Intrusions and Malware, and Vulnerability Assessment

Maurice, C., Neumann, C., Heen, O., Francillon, A.: C5: cross-cores cache covert channel. In: In- ternational Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. pp. 46–64. Springer (2015)

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Preprint available at http://cr.yp.to/papers.html# cachetiming (2005)

Bernstein, D.J.: Cache-timing attacks on AES. Preprint available at http://cr.yp.to/papers.html# cachetiming (2005)

work page 2005

[2] [2]

In: Cryptographers’ track at the RSA conference

Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Cryptographers’ track at the RSA conference. pp. 1–20. Springer (2006)

work page 2006

[3] [3]

In: 2019 IEEE Symposium on Security and Privacy (2019)

Kocher, P., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., Prescher, T., Schwarz, M., Yarom, Y.: Spectre attacks: Exploiting speculative execution. In: 2019 IEEE Symposium on Security and Privacy (2019)

work page 2019

[4] [4]

In: 27th USENIX Security Symposium

Lipp, M., Schwarz, M., Gruss, D., Prescher, T., Haas, W., Fogh, A., Horn, J., Mangard, S., Kocher, P., Genkin, D., Yarom, Y., Hamburg, M.: Meltdown: Reading kernel memory from user space. In: 27th USENIX Security Symposium. pp. 973–990 (2018)

work page 2018

[5] [5]

In: 23rd USENIX Security Symposium

Yarom, Y., Falkner, K.: Flush+ reload: a high resolution, low noise, l3 cache side-channel attack. In: 23rd USENIX Security Symposium. pp. 719–732 (2014)

work page 2014

[6] [6]

In: International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment

Gruss, D., Maurice, C., Wagner, K., Mangard, S.: Flush+ ﬂush: a fast and stealthy cache attack. In: International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. pp. 279–299. Springer (2016)

work page 2016

[7] [7]

In: 2015 IEEE Symposium on Security and Privacy

Liu, F., Yarom, Y., Ge, Q., Heiser, G., Lee, R.B.: Last-level cache side-channel attacks are practical. In: 2015 IEEE Symposium on Security and Privacy. pp. 605–622. IEEE (2015)

work page 2015

[8] [8]

ACM SIGARCH Computer Architecture News 35(2), 494–505 (2007)

Wang, Z., Lee, R.B.: New cache designs for thwarting software cache-based side channel attacks. ACM SIGARCH Computer Architecture News 35(2), 494–505 (2007)

work page 2007