Systematic Analysis of Randomization-based
Protected Cache Architectures
Antoon Purnal* , Lukas Giner† , Daniel Gruss† , and Ingrid Verbauwhede**

imec-COSIC, KU Leuven

Abstract—Recent secure cache designs aim to mitigate sidechannel attacks by randomizing the mapping from memory
addresses to cache sets. As vendors investigate deployment ofthese caches, it is crucial to understand their actual security.
In this paper, we consolidate existing randomization-based secure caches into a generic cache model. We then comprehensively
analyze the security of existing designs, including C EASER -S
and S CATTER C ACHE, by mapping them to instances of thismodel. We tailor cache attacks for randomized caches using anovel P RIME +P RUNE +P ROBE technique, and optimize it using
burst accesses, bootstrapping, and multi-step profiling. P RIME +P RUNE +P ROBE constructs probabilistic but reliable eviction
sets, enabling attacks previously assumed to be computationallyinfeasible. We also simulate an end-to-end attack, leaking secrets
from a vulnerable AES implementation. Finally, a case study of
C EASER -S reveals that cryptographic weaknesses in the randomization algorithm can lead to a complete security subversion.
Our systematic analysis yields more realistic and comparable
security levels for randomized caches. As we quantify how
design parameters influence the security level, our work leads toimportant conclusions for future work on secure cache designs.

I. I NTRODUCTION
Caches reduce the latency for memory accesses with highlocality. This is crucial for performance but also an inherent
side channel that has been exploited in many microarchitecturalattacks, e.g., on cryptographic implementations [3], [34], [54],[14], user input [40], [33], [12], [32], system secrets [13], [16],[9], covert channels [27], [11], [30], and transient-execution
attacks like Spectre [19], [6], [4] and Meltdown [23], [47].
Due to the limited size of the cache, some addresses arebound to be allocated to the same cache set, i.e., they arecongruent and contend for the same resources. While some
attacks are enabled by the attacker’s capability to flush cachelines, others work purely with this cache contention. The basic
building block for measuring cache contention is the eviction
set, a set of congruent addresses. Accessing the addresses inthis eviction set brings the cache into a known state. Measuring
how long this takes, tells the attacker whether some process
worked on congruent addresses since the last eviction.
To mitigate contention-based attacks, the cache hardware canbe augmented to so-called protected cache architectures. One
line of work reduces interference through better isolation [41],[17], [50], [55], [56], [24], [18], [42], or partial isolation (e.g.,
locking cache lines) [51], [8]. Another promising line of work is
randomized cache architectures [51], [52], [21], [25], [26], [45],[38], [39], [53], which randomize the otherwise predictable
mapping of memory addresses to cache sets. Several recently† Graz University of Technology

Randomized
Ideal-casemapping Section V-VI security
Section VIII

Section VII

Real-world
security

Rekeying condition

Fig. 1: Security argument for randomized caches.

proposed randomized caches [45], [38], [39], [53] evaluate a
dedicated hardware mapping to perform the randomization on
the fly. Consequently, these architectures only slightly change
the interface to the outside, and can maintain efficient andscalable sharing of caches. However, even if the randomized
mapping is (cryptographically) unpredictable, there are cachecollisions due to the limited size of the cache. Hence, existing
proposals incorporate some notion of rekeying, i.e., renewing
randomization at runtime. This limits the temporal window inwhich eviction sets can be used for an attack.
While randomized cache architectures show promise to
thwart eviction-based cache attacks with reasonable overhead,supporting them with quantified security claims (a default for
cryptographic algorithms) is challenging. Figure 1 depicts theestablished security argument. The randomized mapping is used
as a trust anchor for security in ideal attack conditions, yieldinga (conservative) estimate for the rekeying condition. Currently,
the security transfer from the randomization mapping to idealcase security is not well-understood, which we highlight byimproving state-of-the-art attacks by orders of magnitude.
Assuming that system activity increases the attack complexity,
ideal-case security implies real-world security. However, it isunclear to which extent the rekeying condition can be relaxed.
The high interest in these novel cache designs and theirseeming relevance to mitigate a growing list of attacks motivates
the following fundamental questions of this paper:
Can we accurately compare security levels for randomized
caches? How realistic are security levels reported for secure
randomized caches? Do secure randomized caches provide
substantially higher security levels than regular caches?
In this paper, we systematically cover the attack surface ofrandomization-based protected caches. We consolidate existing
proposals into a generic randomized cache model, and identify
attacker objectives in such caches. We then analyze this model,
resulting in a comprehensive and parametrized analysis, serving
as a baseline for future secure caches and their analysis.
We present P RIME +P RUNE +P ROBE (PPP), a technique tofind probabilistic but reliable eviction sets in randomized caches.
Improving the approach by Werner et al. [53], PPP dramaticallyoutperforms traditional eviction, turning infeasible attacks (e.g.,

> 1030 accesses) into feasible ones (e.g., < 107 accesses).
We also analyze security under complicating system effects,
e.g., noise and multiple victim accesses, culminating withsuccessful key recovery from a vulnerable AES implementation.
Latency constraints associated with the cache hierarchy haveinspired designers to invent new [38], [45] or repurpose existing [45] low-latency structures for the randomization mapping.
Security arguments then rely on their alleged unpredictability.
We falsify this assumption for C EASER -S, and propose that
future designs use mappings that resist extensive cryptanalysis.
Contributions. In summary, our main contributions are:
• We consolidate existing proposals into a generic randomized
cache architecture model.
• We derive a comprehensive and parametrized analysis of
all computation-based randomized cache architectures. We
improve noise-free attacks by several orders of magnitude.
• We analyze non-ideal effects in profiling on randomized
caches, and demonstrate the first end-to-end attack.
• We study the security requirements of the core randomized
mapping and show that the security of C EASER -S can becompletely subverted, even with frequent rekeying.
Outline. Section II provides background. Section III presents
our generalized cache model. Section IV generalizes contentionbased attacks for randomized caches. Section V presents
ideal-case eviction set construction, Section VI describes
optimizations, and Section VII considers aggravating systemeffects. Section VIII shows how exploiting internals cancompletely subvert security guarantees. Section IX discusses
results and compares existing proposals. Section X concludes.
II. BACKGROUND
A. Caches and Cache Hierarchies
CPUs hide memory latency using caches to buffer data
expected to be used in the near future. Caches are organized incache lines. In a directly mapped cache, each memory address
can be cached by exactly one of the cache lines, determinedby a fixed address-based mapping. If a memory address can becached in any cache line, the cache is called fully-associative.
If a memory address can only be cached in a (fixed) subset
of cache lines, the cache is called set-associative. Addresses
mapping to the same set are called congruent. Upon a cacheline fill request, a replacement policy determines which cacheline in the set is replaced. The so-called cache line tag uniquely
identifies a cached address. CPU caches can be virtually or
physically indexed and tagged, i.e., cache (set) index and thecache line tag are derived from the virtual or physical address.
CPUs have multiple cache levels, with the lower levels being
faster and smaller than the higher levels. If all cache lines froma cache A are required to be also present in a cache B, cache
B is called inclusive with respect to cache A. If a cache line
can only reside in one of two cache levels at the same time, thecaches are called exclusive. If the cache is neither inclusive nor
exclusive, it is called non-inclusive. The last-level cache (LLC)
is often inclusive to lower-level caches and shared across coresto enhance the performance upon transitioning threads between
cores and to simplify cache coherency and lookups.

The L1 cache is often considered the lowest level cache. It is
usually virtually indexed and physically tagged. All higher-level
caches are usually physically indexed and physically tagged.
Again for performance, the last-level cache today is typicallycomposed of multiple independent slices, e.g., one slice perphysical or logical core. Each (physical) address maps to oneof the slices. After selecting the slice, the cache (set) index
is selected as described before. The slices are interconnected,
e.g., by a ring bus, allowing all cores to access all last-level
cache lines. The mapping from physical addresses to slices has
been reverse-engineered for certain microarchitectures [28]. In
this work, we focus on the complete mapping function which
combines the mapping from addresses to slices, sets, and lines.
B. Cache Attacks
Caches reduce the latency of memory accesses with temporalor spatial locality, e.g., recent memory accesses. An attacker canobserve the latency and make deductions, e.g., on other recent
memory accesses. The first cache attacks deduced cryptographic
secrets by observing the execution time [20], [35], [46], [3]. The
best techniques today are F LUSH +R ELOAD [54] and P RIME +P ROBE [34]. F LUSH +R ELOAD flushes an address, then waits,
and by reloading determines whether the victim accessed itin the meantime. While F LUSH +R ELOAD requires a flush
instruction to remove a cache line from all cache levels, E VICT +R ELOAD [12] uses cache contention. Both F LUSH +R ELOAD
and E VICT +R ELOAD only work on (read-only) memory shared
between attacker and victim. P RIME +P ROBE [34] overcomes
this limitation. P RIME +P ROBE measures cache contention
instead of memory latency. The attacker fills (primes) a subsetof the cache (e.g., a slice, a set, a line) and measures (probes)
how long it takes. The time to fill the subset is higher if a
victim replaces an attacker cache line with a congruent address.
Mounting P RIME +P ROBE requires information about how
addresses map to cache lines, which can be gained implicitly
in certain scenarios. This is trivial for the L1 cache and, hence,
the first P RIME +P ROBE attacks targeted the L1 cache [36],[34]. More recently, P RIME +P ROBE attacks were mounted on
last-level caches [27], [33], [29], [22], [30].
Cache attacks based on cache contention generally consist of
two phases. In the profiling phase, the attacker finds a so-called
eviction set, a set of addresses with a high degree of contention
in a subset of the cache. In the exploitation phase, the attacker
accesses this eviction set to bring the cache into a known state.
For E VICT +R ELOAD, the attacker uses it to evict an entire
cache set (including a target address) and to later on reload thetarget address to determine whether it has been accessed in themeantime. P RIME +P ROBE works similarly, except that it does
not reload the target address but accesses the eviction set again
to measure contention caused by victim memory accesses.
Early approaches for finding eviction sets were based on
knowing addresses and their congruence, and simply collected a
set of such addresses. With address information unavailable, theattacker instead starts with a set of addresses, large enough to
be a superset of an eviction set with high probability. Elements
are removed from this set until it has minimal size. Recently,this eviction set reduction has been improved from quadratic
to linear complexity in the size of the initial set [49], [39].
C. Randomized Cache Architectures
State-of-the-art randomized cache architectures replace predictable address-to-index mappings with deterministic but
random-looking mappings. The original proposals considera software-managed look-up table, whereas newer designs
compute the randomized mapping on-the-fly in hardware.
1) Table-based architectures: RPCache [51] uses a permutation table to randomize the mapping from memory addresses
to cache lines. Occasionally updating the permutation aims to
mitigate statistical attacks. Random-fill cache [25] issues cache
fill requests to random addresses in spatial proximity insteadof the accessed ones. Table-based architectures face scalability
issues, which are especially prohibitive for last-level caches.
2) Computation-based architectures: Recent designs (T IME S ECURE C ACHE [45], C EASER [38], [39], S CATTER C ACHE [53]) cope with this scalability problem by computing
the mapping in hardware instead of storing it. This computation
should have very low latency. Given their flexibility andscalability, computation-based designs are proposed for lastlevel caches, which have the largest latency budget and areimportant to protect as they are usually shared across cores.
3) Cache partitions: Algorithmic advances in eviction set
construction [49], [39] have shown that only randomizing thememory address is insufficient to protect against contentionbased cache attacks. As a key insight, C EASER -S and S CAT TER C ACHE partition the cache and use the randomized mapping
to derive a different cache-set index in each of these partitions.
Not only does this significantly raise the bar for finding eviction
sets, but it also hinders using them in the exploitation phase.
4) Rekeying: Even if the mapping from address to cache set
in each partition is unpredictable, the attacker can, over time,
still identify sets of addresses contending in the cache. Thus,
randomized caches rely on rekeying, i.e., sampling a new key
to refresh the randomization. Selecting an appropriate rekeying
condition marks an important security-performance trade-off.
5) Security analysis: Computation-based randomized caches
show promise to mitigate cache-based side-channel attacks.
Although all proposals come with first-party security analyses,
they currently lack a systematic and complete analysis (thatwe rely on and know, e.g., for cryptographic schemes).

Fig. 2: Computation-based randomized cache model

the atomic unit of the mapping from addresses to cache sets isthe cache line, for which we assume a generic size of 2o bytes(i.e., o line offset bits). The model makes abstraction of theline offset bits, as they do not contribute to the randomization.
In accordance with traditional caches, processes cannot
monitor the data in the cache directly, nor can they infer
to which cache way a certain memory address is allocated.
The only interface available is the access latency when reading
specific addresses, i.e., it is low in case of a cache hit and highin case of a miss. In some practical cases, an attacker mightalso have access to flush semantics. However, our attacks do not
rely on it and we thus assume it to be disabled architecturally.
1) Generic model: Figure 2 depicts our generic computationbased randomized cache, featuring the following components:
1 The memory address a is the primary input to therandomization design. a is either a physical or virtual address,
impacting the degree of control an attacker has over a.
2 The key K captures the design’s entropy (unpredictability).
3 The security domain separator s optionally differentiates
the randomization for processes in different threat domains.
4 The randomized mapping RK (a, s) is the core of thearchitecture. It is a pseudorandom mapping, i.e., deterministic
but random-looking, for which the algorithmic description is
publicly known, but the key K is not (Kerckhoff’s principle).
The LLC slicing function can be encapsulated in R (i.e., one
randomized cache), or not (i.e., per-slice randomized caches).
5 The randomized cache is divided into P partitions, where
1 ≤ P ≤ nw . An input address a has, in general, a different
index in each of these partitions. To accommodate this, R has
to supply P · b pseudorandom bits. We assume P divides nw .
6 When caching a, one of the partitions is truly randomly
selected, and the corresponding cache-set index in this partition
is determined based on the pseudorandom output of R. Then,
III. G ENERIC R ANDOMIZED C ACHE M ODEL
one of the cache lines in this set is replaced by a, adhering to the
In this section, we present a generic randomized cache model replacement policy within the partition. We consider randomthat covers all proposed computation-based randomized caches replacement (RAND) and least-recently used (LRU). Under
to this date. We use it to cover the attack surface of randomized attack, several stateful policies can degenerate to LRU [10].
caches systematically. In later sections, we will quantify the 7 The rekeying period T denotes the condition for entropy
influence of each parameter on the residual attack complexity. renewal. It should be strict enough to maintain high security,and loose enough to maintain high performance.
A. Randomization-based Protected Cache Model
2) Instantiating Caches: Table I shows how existing designs
Although some protected cache designs fix the cache instantiate this model. The key K can be a cryptographic key
configuration, we consider a generic nw -way set-associative (C EASER -S, S CATTER C ACHE), a set of cryptographic keys, orcache with 2b sets (i.e., b index bits). Then, let N = nw · 2b selection of a random permutation (T IME -S ECURE C ACHE).
denote the number of cache lines. As with traditional caches, T IME -S ECURE C ACHE (T SC) implements domain separation

TABLE I: Instantiating the generic model for existing cache designs.
DesignUnprotected
T SC [45]C EASER [38]C EASER -S [39]S CATTER C ACHE [53]

K

s

P

R

∅
keys / select
key
key
key

∅
RKs (a)∅?
RK (a, s)

1
1
1
2-4
nw

slice + bits
HashRP / RM
L LBC
L LBC
Q ARMA [1]with a per-process key, S CATTER C ACHE via additional input
to the mapping, and C EASER -S mentions it without implementation details. Traditional unprotected caches, C EASER, and
T SC all have one single partition. In S CATTER C ACHE, P = nw
(the maximum), whereas C EASER -S recommends 2 ≤ P ≤ 4.
The rekeying condition T can use, e.g., the wall-clock time,
the number of accesses to the cache, or more complex policies.
3) Software Simulator: We implement our model as a C++
randomized LLC simulator, which we parametrize and use to
obtain all experimental results in this work. For simulation
purposes, many well-analyzed cryptographic primitives can beused for RK . We use AES because of its hardware support.

Fig. 3: Generalized eviction sets are based on partial congruence(nw = 6, P = 3, b = log2 8 = 3)

RK to the cache architecture (cf. Figure 1). It allows selecting
a conservative rekeying condition for a specific design. Besides
its general applicability, it also covers some practical settings.
For instance, trusted execution environments like Intel SGX
are subject to precise control over victim execution [31], i.e.,
precisely stepping to a single instruction (e.g., a memory access)and even repeating it an arbitrary number of times [48], [43].

B. Attacker Models
We now systematically cover the attack surface of randomized caches and define relevant attacker models in such caches.
Leveraging a provable security methodology from cryptog- IV. E XPLOITING C ONTENTION ON R ANDOMIZED C ACHES
raphy, we propose to analyze the randomized mapping R ( 4 )This section introduces generalized eviction to overcome
separately from how it is used. On the one hand, we consider the challenges introduced by randomized caches. Next, it
black-box attacks, which assume that R behaves ideally. In this generalizes traditional attacker objectives to randomized caches.
case, processes cannot efficiently recover K, find inputs to RK
that produce output collisions, or infer any information about A. Generalizing Eviction
cache set indices in one partition based on observations in
1) Full congruence: In an eviction set for a traditional cache,another. On the other hand, we also consider shortcut attacks
every
address ai in this set is fully congruent with x. Hence,that exploit R directly. Physical side-channel attacks on R (e.g.,
ifxiscurrently cached, each ai has the potential to evict it.
using power consumption) are out of scope for this work but
Inarandomized cache, an attacker can theoretically still
can be addressed orthogonally with established approaches [7].
find
a
set
of addresses that collide with the target address x
We further assume full attacker control over input addressin
every
partition.
However, the probability for a randomlya ( 1 ) as the mapping R should dissolve any attacker control
selectedaddresstobe fully congruent with x is 2−bP , i.e., it
regardless of the input. The key K ( 2 ) is considered full
entropy (e.g., generated by a TRNG). If security domains ( 3 ) plummets exponentially with P . Already for P ≥ 2, relying on
are supported, we assume that an attacker cannot obtain the full congruence to construct eviction sets is highly impractical.
2) Partial congruence: To overcome the full congruencesame identifier s as the victim. The attacker cannot observe theoutput of R ( 5 ) directly, but only gather metadata about it by problem, one can also try to evict a target address x based
measuring cache contention. Finally, the attacker cannot modify on partial congruence. This approach, introduced by Werner
the rekeying condition ( 7 ) (e.g., it is enforced in hardware). et al. [53] for special case P = nw , constructs an eviction set
In line with Figure 1, we consider the following three attacks: using addresses congruent with the target in one partition only.
To understand eviction with partial congruence in general,
Aideal In an ideal black-box attack, the mapping R is considered to behave ideally, and the system is completely noise-free. consider Figure 3, where the attacker wants to evict a target x
The victim performs only a single memory access, exactly the in a toy randomized cache with 6 ways (nw = 6), 8 sets (b = 3)
one the attacker wants to observe later (cf. Sections V and VI). and 3 partitions (P = 3). Assume the attacker has found sets ofAnonid In a non-ideal black-box attack, Aideal is extended addresses G1 , G2 , G3 , satisfying that all elements in Gi arewith aggravating system assumptions, and serves to study the congruent with x in partition i but not in the other partitions.
Eviction based on partial congruence is probabilistic. If
increase in attack complexity with respect to Aideal , e.g., noisex is allocated to partition i, it could be evicted by Gi . An
and multiple victim accesses (cf. Section VII).
Ashort In a shortcut attack, internals of the mapping R are element in Gi can only contribute to evicting x when it isexploited to find eviction sets much faster than in the black-box also assigned to partition i; this assignment is truly random(i.e., not pseudorandom). In what follows, we let a generalized
case, i.e., a shortcut is found (cf. Section VIII).
Existing analyses [39], [53] study attacker Aideal , as it eviction set G for a target address x denote the supersetofSP
describes the transfer of security properties from the mapping addresses that collide with x in one partition: G = i=1 Gi .

TABLE II: Generalized eviction set size for several instances.
RP

RAND

LRU

pe
[%]
50
90
95
50
90
95

nw = 4
P =2
P =4
6
18
22
6
14
16

12
36
44
12
36
44

P =2

nw = 8
P =4

P =8

P =2

12
36
46
14
24
26

24
72
92
28
60
72

48
144
184
48
144
184

22
72
94
30
42
46

nw = 16
P = 4 P = 16
44
144
188
60
100
116

176
576
752
176
576
752

3) Eviction probability: Given a target x to evict, we now
derive the eviction probability pe as a function of the size |G|of the generalized eviction set G. We assume that G contains
an equal share for every partition, i.e., |Gi | = |G|P , (1 ≤ i ≤ P ).
This assumption holds probabilistically in practice, and we willshow how it can be met deterministically in Section VI-B.
For replacement policy RAND, the eviction probability
generalizes the expression by Werner et al. [53]. Regardlessof the partition in which x resides, |G|P addresses in G could
evict it, each with probability n−1
w . Consequently, we have:

An arbitrary eviction set (normally the easiest to construct [49]) is a set of memory addresses that, when accessed,
has a high probability that at least one of its elements isevicted from the cache. Although this objective has proven to
be useful in traditional caches, e.g., for covert channels [30], its
generalization to randomized caches with P > 1 and security
domains does not seem to map to any known adversarial goals.
Takeaway: Generalize eviction to avoid full congruence.
Rely on partially congruent addresses to efficiently (butprobabilistically) measure contention in randomized caches.
V. C ONSTRUCTING G ENERALIZED E VICTION S ETS

The generalized eviction set G is the primitive at hand for
attacking randomized caches. Once G has been constructed,
contention-based attacks like P RIME +P ROBE are also possible
in randomized caches, although with a larger set and lower

 |G|
1
P
success probability (cf. Section IV-A). The major hurdle is thepe,RAND (|G|) = 1 − 1 −nw
profiling attack stage, i.e., constructing G itself. Purnal and
For LRU, evicting x requires the attacker to evict the full set Verbauwhede [37] performed an initial study of this problem.
in the partition in which x currently resides. This corresponds
This section is concerned with the construction of G for ato the event that at least nPw out of the |G|P addresses for thetarget address x, using the capabilities of the black-box attack
designated partition are actually mapped to this partition. It is Aideal (cf. Section III-B). We focus on the general case of a
described by the complement of the cumulative binomial with target x that is not attacker-accessible (cf. Section IV-B), as the|G|nw
1
and success probability
security domain separator s lifts most attack objectives fromp trials, P −1 successes P:|G| nw1
pe,LRU (|G|) = 1 − binom,−1,
the accessible to the non-accessible case. We will later show thePPP
optimizations that can be applied should they be accessible. Ournw−1 |G| −iP
X  |G|   1 i 
1PP
novel profiling approach is generically applicable and efficient,
· 1−
=1−
i
P
P
i=0
improving state-of-the-art methods by orders of magnitude.
Conversely, selecting the eviction probability pe fixes |G|,
Conventionally, eviction sets are constructed by reducing
presented in Table II for different cache configurations and pe . a large set of addresses to a smaller set while maintaining ahigh eviction rate. This traditional top-down approach is highly
B. Generalizing Attacker Objectives
effective for P = 1, but both the size of its initial set and its
We now generalize eviction set objectives from traditional reduction step are strongly hindered by partitioning the cache
to randomized caches and evaluate their utility.
(P > 1). We cope with the sheer infeasibility of reducing the
A targeted eviction set for an address x is a set of addresses initial set by adopting a new bottom-up approach: The attacker
that, when accessed, evicts x from the cache with high starts from an empty set and incrementally adds addresses forprobability. The complexity and utility of this objective depends which cache contention with the target address was observed.
on the capability of the attacker to access the target address x.
When measuring contention with a target x that is not
The attacker can access x if it is an in-process address attacker-accessible, the only available procedure is to prepareor resides in memory shared between attacker and victim. By the cache state, wait for victim execution, and observe changes
accessing x directly, the attacker can measure its access latency. in the cache state. Finding a generalized eviction set G thenThis objective is useful even in randomized caches, e.g., for comprises several iterations of this procedure. A successful
E VICT +R ELOAD side- and covert channels or to trigger direct iteration is one that catches an access to x, and the success
DRAM accesses for eviction-based Rowhammer [2], [10].
probability of an iteration is the catching probability pc .
In the other case, the attacker does not learn the access
Takeaway: Adopt a bottom-up strategy to construct G.
latency of x, and victim accesses to x are needed for constructing eviction sets. It is the primary attack vector for randomized
In partitioned randomized caches, detecting contention iscaches, as it represents the general scenario where x is notmuch more efficient than detecting absence of contention.
accessible by the attacker (unshared memory), or accessible tothe attacker but decoupled in the cache for different security
domains. In addition to the previous objectives, generalized A. Generic Prime+Prune+Probeeviction sets in this setting are useful, e.g., for P RIME +P ROBE
To maximize the probability of catching a victim access to x
side- and covert channels, or to extend transient execution in a given iteration, we develop a specialized P RIME +P ROBE,
windows by evicting branch condition values from the cache. tailored for finding eviction sets in randomized caches.

lishes pc for several configurations. We distinguish whether x
is cached (denoted pc,c ), vs. not cached (denoted pc,n ).
1) Target is not cached (pc,n ): After prime and prune,
Catching probabilityRPpc,n (not cached)pc,c (cached)
the victim access to x caches it in a random partition, and RKnw
P
pseudorandomly determines the cache set within this partition.
nw  i2 ·k0i ·(N −k0 )nw −i
k0
RAND
nw
N
i
n2
w ·N
i=1
For RAND, x evicts an attacker address with probability equalp(P −1)+11LRU≈ 1−binom(k, nPw −1, P ·2
≈ pc,n · c,n P
b)to the coverage of the cache after pruning (i.e., pc,n = k 0 /N ).
For LRU, x evicts an attacker address if there are at least
1) Prime+Prune+Probe: An iteration begins with a prime nPw addresses in the attacker set that were mapped to the same
step, where the attacker accesses a set of k addresses, loading cache partition and set of x during prime and prune.
It can be approximated (and lower-bounded) by the comthem into the cache. For k > 1, there can be cache contention
within this set. Thus, as a key step to eliminate false positives, plement of the cumulative binomial with k trials, nPw − 1
the prune step iteratively re-accesses the set. This forces successes and binomial success probability (P · 2b )−1 , i.e.,
all self-evicted addresses to be cached again, at a potentially pc,n = 1− binom(k, nPw −1, P 1·2b ). In practice, due to selfdifferent location than before. The prune step terminates as evictions during pruning, the actual number of binomial trials
soon as no more self-evictions occur when accessing the set. is slightly higher than k, resulting in increased pc,n .
2) Target is cached (pc,c ): Catching an access to a cached
If there are still self-evictions after a few iterations, pruning
becomes more aggressive and additionally discards all addresses target x requires both evicting x and detecting its reintroduction
with high access latency (i.e., those evicted by another attacker in the cache, resulting in a penalty on pc . The probabilities
address). Upon termination of the prune step, the attacker has pc,c (exact for RAND, approximate for LRU) are derived ina set of k 0 ≤ k known addresses guaranteed to reside in the Appendix B and collected in Table III. The penalty is maximal
00cache. Let mpr denote the total number of pruning iterations. for k = 1, being nw (RAND) or P (LRU), and decreases with kNow, the attacker triggers the victim to perform the access of as prime/prune implicitly evict an increasing cache portion.
Appendix C complements the theoretical analysis withinterest (i.e., access x, as in conventional P RIME +P ROBE). This
memory access evicts one attacker address with probability empirical validation. It also explores the relation between pc
0pc , which depends both on the attack parameter k and the and k , and the penalty on pc for a cached target.
randomized cache parameters (cf. Section V-B). In the probe
Takeaway: Add pruning to P RIME +P ROBE profiling.
step, the attacker accesses the set of k 0 addresses again, adding
Pruning enables testing more than one guess per iteration.
addresses with high latency to G (i.e., victim evicted them).
It improves profiling for RAND and is essential for LRU.
In P RIME +P RUNE +P ROBE (PPP), the prune step is crucial
TABLE III: Catching probability pc as a function of cache and attack
instance, and whether the target address is cached or not.

and noise-absorbing. Without it, the attacker cannot distinguish
VI. O PTIMIZATIONS FOR P RIME +P RUNE +P ROBE
evictions due to victim accesses from those by the priming set.
By pruning, the attacker completely removes these false posiThis section describes optimizations of P RIME +P RUNE +tives. Appendix A experimentally relates pruning parameters P ROBE for (A) total cache accesses and (B) victim invocations.
k, k 0 and mpr for different cache configurations.
We then evaluate PPP strategies on a range of cache instances.
The P RIME +P RUNE +P ROBE procedure is repeated until
A. Optimizing for total cache accesses
enough accesses are caught and added to G. This constitutes
1) Burst Accesses: As derived, the catching probability pc,cthe bottom-up approach; G is not the result of shrinking a(target already cached) holds at the start of constructing thelarge initial set. Instead, it is built from the ground up.
2) Penalty for being cached: In case the target address x is generalized eviction set G. As the elements of G have explicitly
already cached, a single PPP iteration must both evict x and been observed to collide with x, they can be accessed in burst
before the PPP iteration, essentially implementing a targetedcatch the access to x when it is reloaded into the cache.
The attacker can either (1) first evict x probabilistically, by eviction of x. As profiling progresses and G grows, the burst
accessing many different addresses or other techniques; (2) becomes more successful, and the penalty for a cached target
apply PPP as-is, tolerating a suboptimal catching probability shrinks, hence pc,c → pc,n asymptotically. The burst accesspc . These strategies trade off the success probability of one optimization thus hides the caching penalty. It applies to both
iteration (pc ) with its execution time (number of accesses). In RAND and LRU, but the latter can be accelerated even more.
2) Bootstrapping: A PPP iteration for LRU succeeds ifwhat follows, we consider both a cached and uncached x. Anyprime/prune
fill the full set for x in the designated partition.
profiling strategy then has higher pc than when the target isAs
Gcontends
with x, we add G as bootstrapping elements
always cached, and lower pc than when it is never cached.
to the PPP set. Thus, filling the full set becomes more likely.
However, if a victim access to x evicts a bootstrapping
B. Catching Probability pc
element instead of a PPP guess, the iteration is wasted: G was
The catching probability pc is the success rate of one P RIME + already known to contend with x. This issue can be resolved by
P RUNE +P ROBE iteration and depends on the randomized cache relying on LRU statefulness. Adding G at the end of the PPP(nw , b, P , policy RP) and attack parameter k 0 . Table III estab- set ensures that PPP evictions precede bootstrapping evictions.

Bootstrapping implicitly implements burst accesses, andworks very well for LRU. However, it is unattractive for RAND.
Takeaway: Use elements in G to accelerate finding more.
Burst accesses hide caching penalty effectively as G grows.
Bootstrapping increases pc by helping to fill the LRU set.
B. Optimizing for victim invocations

the guess g, then probes S. If accessing an element of S isslow, say ak , we add g to the candidate pool for ak . Every
iteration has pc = Nc , and there are ≈ c + 1 attacker accesses
per iteration, (i.e., very little pruning, and probe overlaps with
the next prime). The expected number of attacker accesses toobtain one element for the candidate pool hence is E[Aa ] ≈ N .
2) Optimizing Step 2 for LRU: For LRU, reverse PPP iseven more effective. Again, let S = {a1 , a2 , . . . , ac } be the set
from Step 1, and let g denote a random address guess.
Assume the attacker primes the cache with S, prunes it, andobserves self-evictions. For LRU, this implies that S filled
a full cache set ( nPw lines). In this case, the attacker does
reverse P RIME +P RUNE +P ROBE, where one iteration consistsof prime and prune with S, accessing g, and probe with
S. If accessing an element of S is slow in the probe step, say
ak , we add g to the candidate pool for ak . This approach has
pc = P 1·2b , and there are ≈ c+1 accesses per iteration, resulting
in expected number of attacker accesses E[Aa ] ≈ (c+1)·P ·2b .
Importantly, as g collides with multiple ak in S, it very
likely collides with x and can directly be added to S. Thus,
it immediately grows eviction set G without accesses by thevictim, bypassing Step 3. However, it can only be started
if priming S has observed self-evictions. Interleaving it with
Step 1 implicitly generates new attempts at this precondition.
3) Flexibility of the Framework: The three-step framework
flexibly instantiates randomized caches and attack scenarios.
If the victim program is tiny and executes continuously, allprofiling time is spent in Step 1. The shares of Step 2 andStep 3 grow as soon as the victim program becomes the bottleneck in any way. Finally, if x is attacker-accessible, reverse
PPP from Step 2 is used immediately. The framework alsoenables splitting G based on the partition of contention withx, making the eviction probabilities (Section IV-A) exact.

We now explicitly minimize the required victim accesses
Av . This is relevant, e.g., for long victim programs or cases
where victim runs are limited. We decouple it as Av = pcc ,relating it to accesses c needed to be caught (i.e., successful
iterations), and to pc (i.e., success probability of one iteration).
Section V already maximized denominator pc with P RIME +P RUNE +P ROBE. We now independently minimize numerator c,forming a flexible profiling framework to globally optimize Av .
It first preselects candidate addresses that have higher catchingprobabilities. The framework comprises three steps:
Step 1. Use P RIME +P RUNE +P ROBE to find, for every
partition i, one address ai that collides with x in that partition.
Step 2. For each ai , construct a candidate pool withaddresses that collide with it in at least one partition.
Step 3. Resume P RIME +P RUNE +P ROBE with the obtained
candidate pools instead of randomly selected addresses.
The first step simply constructs a smaller G with PPP.
Assume it needs to continue until G contains at least one
element for every partition. The expected accesses to catch isthen given by the coupon collector problem in statistics, with
one set of P coupons: E[c] = P (1 + 1/2 + · · · + 1/P ).
The second step finds addresses that contend with the ai
obtained in Step 1, instead of profiling x directly. As the ai
are attacker-accessible, their access latency can be measured,and no victim accesses are required. Addresses that contend
with ai also contend with x with probability ≥ P −1 , which is
Takeaway: Use elements in G to reduce victim accesses.
much more likely than a randomly selected address (≈ 2−b ).
Filtering candidate addresses based on contention with G
The third step resumes PPP for target x with candidate pools
allows to (partially) refrain from victim invocations.
for the ai . Every iteration accesses the pools, prunes, triggers
access to x, and probes. For sufficiently large candidate pools,
C. Evaluation of profiling strategies
pc ≈ 1, significantly reducing Av as compared to Step 1.
Conceptually, the first and third step are similar in nature.
Figure 4 depicts victim and total cache accesses for the
They can also be independently accelerated, as in Section VI-A. presented profiling strategies, obtained from simulated proWe now explore the complexity and acceleration opportuni- filing runs (cf. Section III-A3). We observe a mostly linear
ties of Step 2. As the access latency of the targets ai can progression in constructing G. One exception is reverse PPP,
be measured, catching probabilities can increase, and there is where the construction of the candidate pools does not grow G
no penalty if the ai are already cached. We again distinguish immediately (jump), but accelerates the profiling that follows.
between replacement policies, and measure the complexity in
Optimizations like burst accesses and bootstrapping improve
attacker accesses Aa (as there are no victim accesses).
both total and victim accesses. In contrast, probabilistic full1) Optimizing Step 2 for RAND: We propose to construct cache evictions and three-step profiling incur a trade-off
the candidate pool through reverse P RIME +P RUNE +P ROBE. between total accesses and victim invocations. Of course, one
Let S = {a1 , a2 , . . . , ac } be the starting set obtained in Step can freely interpolate between these extreme strategies.
1. The elements of S are now the targets instead of the victim
D. Influence of randomized cache instanceaddress x. Every iteration tries one random address guess g.
P RIME +P RUNE +P ROBE (PPP) primes the cache with k1) Sets, ways and partitions: Both profiling and exploitation
guesses and observes eviction by the target. R EVERSE PPP in randomized caches are influenced by the parameters of theinstead primes the cache with the targets S, prunes, accesses instance. We investigate the effectiveness of PPP on several

Fig. 4: Effort of profiling strategies for RAND (top) and LRU (bottom), measured as total (left) and victim (right) cache accesses, averaged for 104 simulated
profiling runs. Cache instances are denoted RP(nw , b, P ). k is fixed to N
(RAND) and 3N(LRU) to isolate the influence of the strategy. Pruning becomes2
4
aggressive from the sixth iteration, if not already terminated. Full evictions between PPP iterations, if performed, use 2N addresses for LRU and 3N for RAND.

instances for RAND and LRU. Figure 5 captures our findings, TABLE IV: Rekeying periods T to ensure that the success rate to construct G
with pe ≥ 95% is upper-bounded by 1/2{8,12,16,24,32} . The cache instanceagain based on simulation (cf. Section III-A3).
is RAND(16, 13, 16) and all accesses are counted as cache hits (e.g., 10 ns)
Larger caches resist better against PPP. Increasing cacheb
T for profilingT /2 for profilingways (nw ) seems to compare favorably to increasing sets (2 ).
Success Rate
T
time
T
time
While the latter only proportionally prolongs profiling and−8240N≈ 10 sec
80N≈ 20 sec
does not affect exploitation, the former inhibits both profiling
2−1229N≈ 2.5 min58N
≈ 5 minand exploitation. In particular, |G| increases for the same
−16
2
22N
≈ 30 min
44N≈ 60 minexploitation pe , and profiling is prolonged as |G| increases
2−32
9N≈ 2 years
18N≈ 4 years
while the accesses per element of G stay roughly the same.
Similarly, for the same cache dimensions (nw , b), both PPP to catch at the very least m ≥ pe P victim accesses toprofiling and exploitation suffer from increased partitioning P . different partitions. Indeed, an attack with pe > m has inferredP
Especially for RAND, there is no indication from our ideal-case information about partitions for which no memory access has
analysis why one should not opt for maximal partitioning.
been caught. By contradiction with A , it cannot exist.
In general, we find that PPP can be hindered by tuning
Beyond Aideal , we further contrive the setting in favor of thecache sets, ways, and partitions, but not to the point where it attacker. We consider strongly idealized pruning (i.e., k 0 = k andbecomes infeasible. What really works is limiting the cache mpr = 1), and a permanently uncached target (i.e., pc = pc,n ).
access budget for the attacker (i.e., a strict rekeying condition). Furthermore, we scope the algorithm as catching a single access
2) Rekeying period: The difference between the profiling in m partitions, neglecting the necessary expansion to full G.
state of the art and rekeying period T is the design’s security
A perfectly ideal P RIME +P RUNE +P ROBE iteration thenmargin. Although tempting, setting T just low enough to thwart requires k accesses for prime, k for prune, 1 for the victim
known techniques does not account for potential improvements. access, and k to probe. Assuming the attacker somehow
As an example to obtain (very) conservative rekeying periods, manages to combine probe of one iteration with prime of
we now leverage the security of RK to derive minimal the next, we use 2k+1 accesses per iteration as lower bound.
complexities to construct generalized eviction sets of certain
We outline the idea for a randomized cache with random
quality, i.e., with a lower bound on eviction probability pe replacement. The only degree of freedom in the idealized PPP(e.g., pe ≥ 90%). We use the following central assumptions:is the number of addresses k in the prime step. Indeed, theirk
A RK is indistinguishable from a random function.
order or frequency does not impact the cache coverage N.
B Victim addresses of interest are not attacker-accessible.
Given a rekeying period of T cache accesses, the probability
C The eviction probability pe for G is lower-bounded.
of observing at least one access in at least m distinct partitions
As the target is not accessible to the attacker ( B ), she can is (using a generalization of the birthday problem in statistics):
 T
only infer accesses with PPP (cf. Section V-A1): bring cache
T −i
2k+1  T  i
P  Xll l − r
2k+1
X
k
(N
−
k)
P
 X
r
i
2k+1
max 
(−1)
(
) 
in known state, wait for victim execution, and probe.
T
k
i
l
r
P
2k+1
r=0
i=m
l=m
N
To achieve an eviction rate pe ( C ), the profiling needs

Fig. 5: Influence of randomized cache parameters, for RAND (left) and LRU (right). To isolate the influence of the instance, profiling strategies are fixed toburst accesses and k = N
for RAND, and bootstrapping and k = 3N
for LRU. Instances are indicated as (nw , b, P ), and positioned for mean profiling effort
2
4(y-axis, log scale), and eviction set size for exploitation (x-axis, log scale). Vertical lines span the 5-95th percentiles (ranges indicated) over 103 simulated runs.

Conversely, Table IV captures rekeying periods T that upperbound the fraction of successful rekeying periods. Pessimistically assuming that every memory access is a cache hit, it
gives an expected continuous profiling time of having one
successful construction of G within the rekeying period. As
the obtained G is only useful for one period, Table IV also
includes the case where half of it is used for exploitation. Notethat these minimal efforts strongly depend on m, and henceon the quality of G that can be tolerated for exploitation ( C ).

To profile the cache addresses of interest, we propose a
two-phase approach. First, we collect a superset of addresses
containing colliding addresses for all static and dynamic cachelines. Second, we obtain disjoint sets of addresses from thesuperset, each with colliding addresses for one target.
The attacker distinguishes static and dynamic accesses by theproperty that dynamic accesses are statistically performed lessoften than static accesses, which are always performed. With
the assumption from the beginning of this section, we consider
a scenario where an attacker controls, e.g., via input, which
VII. L IFTING I DEALIZING A SSUMPTIONS
dynamic accesses the victim performs in any given execution.
This
control can be exerted positively (i.e., a dynamic access is
In this section, we explore for the first time the morealwaysperformed for a specific input) as well as negatively (i.e.,
challenging attack Anonid with complicating system activityadynamic
access is never performed for a specific input). The(cf. Section IV), as opposed to the commonly assumed Aideal .
latterscenario
repeatedly calls the victim with inputs that cause
We start with a victim program performing more memory acitto
accessallbut one address. Thus, it can be separated fromcesses than of interest to the attacker and present an end-to-end
thesuperset,as
all other addresses in it are accessed eventually.
attack on a vulnerable AES implementation. We then quantify
Ingeneral,any
manipulation of access probabilities in thethe influence of random noise on P RIME +P RUNE +P ROBE.
victimcanbeobserved.
This approach describes a stronger
The central assumption is that the attacker wants to profile
attacker,astargetedaddresses
can be distinguished from others
specific addresses of the victim and that the access probability
in
both
the
dynamic
andstaticset in the same step.
of said addresses can be changed via inputs to the victim.
1) Implementation: In the following, we focus on maximum
partitioning P = nw , as non-random replacement policies likeIn the profiling phase, the attacker identifies addresses of LRU generally require special treatment but behave predictably.
interest in a victim program and distinguishes between them if We employ catching with intermediate full eviction. The
there are multiple, requiring disjoint eviction sets for each target. analysis of Section V-B1 applies. To generate distinct andFrom this perspective, we model the execution of victim code large eviction sets for our ntarget target addresses, we slightly
as a set of static and dynamic memory accesses. Static accesses modify the three-step approach described in Section VI-B. All
are performed regardless of the attacker’s input, i.e., code and experiments are obtained in simulation (cf. Section III-A3).
data accesses performed in all victim executions. Dynamic
To find sets of addresses ai , in Step 1, we first
accesses do not always occur, e.g., state- or input-dependent construct the previously described superset usingcode or data accesses.
P RIME +P RUNE +P ROBE (Section VI-B). Instead of only one
The attack targets are one or more addresses that are accessed victim memory access, all nstat static and ndyn dynamic
upon a certain event the attacker wants to spy on [12]. Like victim accesses are now observed by the attacker. To identify
Gruss et al. [12], we cannot distinguish addresses in the static a enough colliding addresses for all targets, we construct aset, as the cause-effect relationship is the same for all of them. superset of at least nw ·(nstat +ndyn ) addresses. The expected
Hence, for our attack, all targets are in the dynamic set.
amount of memory required to find a collision in a specificA. Multiple Victim Accesses

Cache Misses

2 · 107
1 · 107

TABLE V: End-to-end attack on T-table AES for different configurations(means over 100 runs). nslices = 8, b = 11. Where not shown, standard
deviations are < 0.5% of the mean.

victim cache lines
1
5
10
20

nw

0
0

0.1

0.2

0.3

0.4

0.5

Noise Level ν

Fig. 6: Cache misses for creating a superset with 3 · nw addresses per victim
cache line, as a function of noise ν for different numbers of total victim cachelines, k = 1000 (avg. over 100 runs). Instance is RAND(8, 9, 8)

way is cachesize, though higher confidence requires more. Wenw
can apply the coupon collector’s problem (cf. Section VI-B)w)
for an estimated factor of coupon(n, but as more addressesnwneed to be profiled, the probability to catch enough addresses
for all targets decreases. Consequently, this step requires anumber of repetitions, depending on the prime parameter k.
Next, we separate unwanted addresses from target addresses
within the superset. To this end, we call the victim with
inputs that exclude exactly one of the ntarget cache lines.
By repeatedly evicting the cache, calling the victim with therequired parameters, and measuring accesses in the superset,
we generate a histogram for all target addresses. After a certain
number of repetitions, addresses that are never evicted by thevictim are very likely to collide with the targeted address.
Repeating this process ntarget times, we get disjoint sets ofaddresses for each target cache line. Step 2 and Step 3
can be applied to these sets of addresses (ai ) to construct the
final generalized eviction sets like in the single-access case.
From our experiments (cf. Figure 6), we estimate that the
number of cache misses (the largest factor of the executiontime) increases sub-linearly with the total amount of accessesby the victim (nstat + ndyn ). This is because the catchingprobability pc increases with ntarget . The superset’s separation
depends linearly on ntarget and the overall size of the superset.
2) End-to-end Attack on AES T-Tables: We choose the 10
round T-tables implementation of AES in OpenSSL 1.1.0g as
an example, as it is a well-known target for cache attacks [3],[34], [44], [12]. We perform the One-Round Attack, describedby Osvik et al. [34], and thus recover 64 bits in the 16 upper
nibbles of the 16-byte key (see Appendix D).
The parameters for this attack are nstat = 27 and ndyn = 65.
With ntarget = 64, the 4 T-tables are a difficult attack target,
as the profiling time scales linearly with ntarget .
For profiling, we require AES runs that access all but
the target address, for each target. We can prepare 64 such
key/plaintext pairs offline. All AES runs are recorded as
memory access traces with the Intel PIN Tool [15] and injected
into the simulator (cf. Section III-A3) at the appropriate
times. Lacking more efficient eviction methods, we rely on
probabilistic full cache eviction. In total, eviction accounts for≈ 90% of all accesses during the attack, which in turn makes
the superset-splitting step of the profiling the largest contributor
to the overall runtime. Because we assume no restriction on
the number of encryptions, we do not perform Step 2 forthis attack, as pruning the generated candidate pools wouldP

policy misses [109 ] hits [109 ]#AES∅ collisions/addr. correct nibbles est. t [min]

12.03
2.78
3.21
46.27
4.69
7.85

56663
23682
26060
15707239192
66640

20.47 ± 3.61
15.52 ± 3.37
17.74 ± 7.53
37.91 ± 5.65
26.62 ± 5.85
26.99 ± 11.66

8 8n/a
8 2 RAND
8 2 LRU
16 16
n/a
16 2 RAND
16 2 LRU

3.59
2.25
1.75
9.25
3.91
2.63

15.90 ± 0.33
16.00 ± 0.00
15.94 ± 0.28
15.77 ± 0.45
15.93 ± 0.26
15.75 ± 0.51

1.58
0.63
0.78
6.89
1.32
2.60

also require the costly splitting phase. Instead, we see thatusing fewer colliding addresses for each target (cf. Table V)
still performs well. We can compensate for the lower detection
probability by increasing the number of encryptions during the
exploitation phase.
We use cache parameters from modern Intel processors: 8
slices (with a slicing function [28]) of 1 MB each, so eachslice is a randomized cache with nw = 8/16 and b = 11. We
run the same attack for P = nw = 8/16 and P = 2, withreplacement policies random and LRU. As seen in Table V,
the attack is generic enough for all configurations, without
special considerations for LRU. The variance in the numberof addresses found per target increases for P = 2, especiallyfor LRU, but since this specific attack sums over the hits on
different addresses, this effect is mitigated for the end result (seeAppendix D). For P = 2, we speed up the attack by reducing
the cache lines used for full cache eviction from 2N to 1.5N ,as well as reducing the superset size (cf. Section VI-D1).
This end-to-end implementation is not optimal, as there aremany parameters that could be optimized. Nonetheless, we cansee that cache attacks can still be executed in a reasonable
time frame. If we model the attack as a mixture of sequential
accesses for full cache evictions and timed random accesses
for the sets, we can calculate the average attack times shownin Table V. For this rough estimate, we use access times
measured on a real system with the same miss rates (i7-8700K@ 3.60GHz, sequential access:≈ 11.4c, timed (rdtsc) random
miss: ≈ 235c, hit: ≈ 222c).
Takeaway: Unpredictability requires key agility.
Frequent rekeying is essential to maintain the benefits ofrandomization, even in non-ideal conditions.

B. Influence of NoiseIn the ideal case (Aideal ), there is no noise from memory
accesses by the attacker process itself, nor the victim, or any
other process in the system (including the operating system).
Section VII-A already implicitly includes noise generated by
the victim’s code execution. We now additionally consider noise
introduced by other system activity. We make the simplifying
assumption that noise accesses are random and occur at a rateof ν random accesses for every attacker access.
Multiple steps of the (unmodified) profiling algorithm from
Section VI-B are affected by noise. Spurious memory accesses
during the prune step increase the number of pruning
iterations mpr significantly and reduce the size k 0 of thek0 , k =mpr , k =100
1000
nw · 2b−1

k’

100
1000
nw · 2b−1

1,000

100

50

mpr

2,000

0

0
0

0.1

0.2

0.3

0.4

0.5

Noise Level νand k0 as a function of noise ν, for various k (average

VictimCollisions [%]Fig. 7: Pruning mpr
over 100 runs). Instance is RAND(8, 9, 8)
80

k
100
1000
nw · 2b−1

60
40
0

0.1

0.2

0.3

0.4

Fig. 9: Differential propagation through CEASER’s LLBC. For brevity, we
introduce f [j◦i] (·) as shorthand for f [j] (f [i] (·)).

0.5

Noise Level ν

Fig. 8: Percentage of caught addresses in the superset that genuinely collidewith victim addresses in exactly one way, as a function of ν for various k(avg. over 100 runs). Instance is RAND(8, 9, 8)

accesses to multiple cache lines, all of them can be used for
detection. Attacks will mostly need to be asynchronous, which
necessitates some form of continuous monitoring. We leave an
investigation of practical implementations for future work.

resulting set. The probe step samples noise in addition to the
VIII. S HORTCUT ATTACKS
collisions with the targeted victim cache line.
Figure 7 and Figure 8 show both effects. Though the
In this section, we consider attack Ashort and draw attention
unmodified prune step terminates, the resulting set size k 0 to the soundness of the randomized mapping by achieving
can be seen to decrease quickly with ν, while the number shortcuts during a case study on C EASER and C EASER -S.
of pruning iterations mpr increases. Hence, with noise, theIn particular, we demonstrate how weaknesses in their
attacker could explore the PPP parameter space in favor of common randomized mapping allow us to reliably constructa smaller k. Figure 8 also shows a faster decrease in correct eviction sets without any memory accesses. We first describe
collisions for higher k, while the cost of pruning grows.
Low-Latency Block Cipher (LLBC), the C EASER-specific
Alternatively, the attacker can consider early-aborting prun- implementation of the mapping RK . Drawing inspiration froming, i.e., terminating prune before it is entirely free of misses. differential cryptanalysis, we show how input differences
Indeed, a large part of the pruning iterations are no longer due propagate through the LLBC, and we derive an expression
to self-evictions, but due to sampling noise. The false positives for precomputing address differences that systematically yield
introduced by the early-abort are then removed in a later stage. cache set collisions, independent of key, partition, and address.
The separation phase from Section VII-A is effective at
We describe the attack first for C EASER [38] before tackling
filtering false positives caused by noise during PPP, since static the generalized and improved C EASER -S [39].
victim accesses, dynamic victim accesses, and false positives
exhibit different behavior in the separation phase. In contrast to A. Low-Latency Block Cipher in C EASER (-S)
static or dynamic accesses, false positives occur only in some
C EASER instantiates RK by encrypting the input address
runs, leading to multiple runs with 0 accesses. Hence, they a with a custom LLBC with 40-bit blocks and 80-bit key. In
appear in more than one set in the end and can be removed. particular, it divides the input address in two equally sized (leftFigure 6 shows the total number of cache misses for the right) chunks a = (L || R) and produces an output encrypted
generation of supersets for victims of different total sizes address RK (a) = (L’|| R’). From this output, the lowermost(nstat +ndyn ). These supersets contain exactly 3 · nw · (nstat + b bits determine the cache set index: s = bRK (a)cb = bR’cb .
ndyn ) addresses that collide with victim cache lines in exactly
The encryption proceeds as a keyed four-stage Feistel
one way. They additionally contain non-colliding addresses network (depicted in Figure 9). Each stage instantiates a roundintroduced by noise and self-eviction in the proportion shown function F (X, K), taking 40-bit input (20 bit X and 20 bit
in Figure 8, which is removed during separation. We can see K) and producing 20-bit output (Y ). In each round function,that the number of cache misses (and by extension, the runtime) 20 intermediary bits Wi are first computed as Wi = Si (X, K),
for this step grows approximately linearly with noise.
where Si defines exclusive or (xor) of 20 input bits (out of40). The Wi are shifted with a bit-permutation P to obtain Y .
C. Infrequent victim events
In C EASER, the round functions are randomly sampled,
In the case where an event in the victim happens only once fixed at design time, and explicitly different in every stage.
or a limited number of times (e.g., user input), the probe set Let F [r] denote the round function for stage r, and K [r] theG needs to be large enough to achieve a very high detection 20-bit subkey for this stage. Describe the bit-permutation withprobability, which places more weight on accurate profiling i ← P (i), i.e., a bit at position P (i) moves to position i.
compared to VII-A2. On the other hand, when events trigger Next, let Xi and Ki denote the indices from resp. X and K [r]that are xored to obtain intermediary bit Wi = Si (X, K).
The round function output is Y = (Y0 ||Y1 ||...||Y19 ) =(WP (0) ||WP (1) ||...||WP (19) ). The round function F [r] thus[r]comprises 20 functions Fi (X,X
K [r] ) eachXcomputing one Yi :[r]

Yi = Fi (X, K

[r]

)=

[r]

Xj +

j∈XP (i)

Kk

(1)

0

k∈KP (i)B. Constructing and Using the Shortcut
The outcome of the shortcut is a set of addresses ai thatcollides in the cache with a target address a, i.e., RK (ai ) =RK (a). The attacker could attempt this shortcut by recovering
the mapping key K, granting the shortcut for the lifetime of
the key. Our approach, in contrast, is fully key-independent.
It is a restricted take on chosen-plaintext attacks, where therestriction stems from being embedded in a cache. Specifically,
the adversary can choose a set of plaintexts to RK (i.e., input
addresses ai ), but does not observe any cryptographic output.
We rephrase the shortcut as a differential problem, i.e., tofinding a set of ∆a satisfying RK (a+∆a) = RK (a). Matchingwith the Feistel topology, we denote the input difference ∆a =(∆L ||∆R ) and the output difference (∆L0 ||∆R0 ). Achieving
the shortcut is then equivalent to finding pairs ∆L and ∆R , notboth zero, that result in the same set index bits: b∆R0 cb = 0b .
1) ∆−Propagation: We derive the propagation first throughthe round function F [r] , then the full LLBC. Let+denote GF (2)addition (bitwise xor). As a well-known cryptanalytic fact,
differences propagate unaffected through addition. Let ∆X and∆Y denote differences at the input and output of F [r] . Stateddifferently, if Y = F [r] (X, K [r] ) and Y 0 = F [r] (X+∆X , K [r] ),then ∆Y = Y 0 +Y . Now compute the i-th output bit ∆Y,i :
[r]

[r]

[r]

[r]

∆Y,i = Yi + Yi = Fi (X + ∆X , K ) + Fi (X, K )
X
X
[r]
[r]
=
(Xj + ∆X,j + Xj ) +(Kk + Kk )j∈XP (i)X=

k∈KP (i)[r]∆X,j = fi (∆X )j∈XP (i)If we let ∆Y = f [r] (∆X ), then f [r] captures the effect ofround function F [r] on an input difference ∆X . Similar to F [r]before, f [r] is an umbrella for 20 functions:∆Y = f

[r]

[r]

[r]

0

RK (a) = RK (a + ∆a) ⇒ RK 0 (a + ∆a) = RK 0 (a )Observing the linearity in the entire cipher (particularly in the
SBoxes Si , supposed to be non-linear), we draw inspirationfrom differential cryptanalysis to bypass RK altogether.

03) Implications: The shortcut does not require knowledge of
key K, and is even completely independent of K. Furthermore,
it is also independent of the input a. Although in general
RK (a) 6= RK 0 (a), eviction sets constructed for key K 0 and
input a0 are still eviction sets for any other (K, a) pair:[r](∆X ) = (f0 (∆X ) || f1 (∆X ) || ... || f19 (∆X ))Note that f [r] only depends on the input difference ∆X .
Crucially, it is independent of both X itself and the key K.
2) Shortcut Equation: Armed with the ∆-propagation
through round functions F [r] , Figure 9 shows our probability
1 differential trail through C EASER’s full LLBC, yielding an
expression for output difference ∆0R . This expression, which we
dub the S HORTCUT E QUATION, describes ∆a = (∆L ||∆R ) satisfying output collision: b∆0R cb = 0b ⇒ RK (a) = RK (a+∆a).
A straightforward way to find solutions to this equation
fixes (say) ∆L and tests variable ∆R for equality. The
expected offline complexity for each ∆a = (∆L , ∆R ) is 2b−1
evaluations of the shortcut equation. Since very often b < 20, thenaı̈ve computation is very practical. As the shortcut equation
describes twenty linear equations over GF (2), one could also
algebraically determine a compact expression for ∆L and ∆R .

(2)

This follows from the key-independence of the S HORTCUTE QUATION. Hence, rekeying does not invalidate eviction
sets constructed using the shortcut. This has the devastatingconsequence that, as soon as the ∆a have been precomputed
offline, the attacker can construct arbitrary eviction sets for any
target a with zero cache accesses, completely bypassing RK .
4) Extension to C EASER -S: C EASER -S implements partitions with P parallel LLBC instances with different keys. By
Equation (2), collision in one partition implies collision in
all partitions. Thus, our shortcut equally impacts C EASER -S,
allowing easy construction of fully congruent eviction sets.
5) Mitigation: At the very least, the LLBC rounds shouldincorporate non-linear SBox layers. This spot mitigation thwarts
the presented shortcut, but more subtle attacks could remain.
Takeaway: Do not overestimate the mapping’s security.
Shortcut attacks can be fundamentally eliminated by arandomization mapping that resists formal cryptanalysis.
IX. D ISCUSSION
In this section, we relate and compare the contributions inthis paper to the most closely related work, as well as provide
specific recommendations and directions for future work.
A. Prime+Prune+Probe on specific designs
Our generic model for computation-based randomized caches
permits to instantiate existing designs, extend their security
analysis, and compare them in terms of profiling effort.
We consider an 8 MB cache with 16 ways (nw ) and 13
index bits (b) (i.e., N = 131 072). We assume a non-accessible
target address (e.g., by enabling security domain separation s).
Although we consider Aideal (cf. Section III-B), i.e., we are able
to pinpoint one target access of interest, victim execution timecannot be neglected. Therefore, we assume a modestly-sized
victim program, performing 1 000 accesses per invocation.
Figure 10 shows total cache accesses to profile a generalized
eviction set G with pe = 90%. For each instance we use
P RIME +P RUNE +P ROBE and optimize for total cache accesses.
1) Single-partition caches: Randomized caches with P = 1(C EASER, T SC) can be treated as traditional caches without
adversary control over physical addresses. They require extremely frequent rekeying, given that fully congruent eviction
sets (i.e., pe = 100%) can be obtained with the efficient topdown profiling approach [49], [39].
2) C EASER -S: First-party C EASER -S analysis [39] only
considers fully congruent eviction. As fully congruent addresses
are extremely scarce, it is completely infeasible for larger P .
We instantiate the model to C EASER -S2 (resp. C EASER S4) by setting P = 2 (resp. P = 4) and replacement policy

not investigated, T SC risks shortcuts due to absence of
cryptographic structure. Shortcuts in S CATTER C ACHE are only
possible by significant cryptanalytic advances for Q ARMA [1].

Fig. 10: Complexity (Aideal ) to construct a fully congruent or generalized(pe = 90% or pe = 50%) eviction set. Randomized caches are monolithic 8 MB
(nw = 16, b = 13, N = 131 072 lines). Cost metric is total cache accesses;
victim runtime is modeled with 1 000 accesses. Fully congruent eviction
assumes initial set (before reduction) of 2N . PPP uses the best-performing
strategy (cf. Section VI-C), with k = N(RAND) or k = 3N
(LRU).
2
4

B. Future Work
Our work serves as a baseline to which future secure cachedesigns, and their analysis, could be compared. This paper also
shows the importance of cryptanalytic resistance of the corerandomization mapping. Stringent latency constraints could
inspire new designs in the space of low-latency cryptography.
The rekeying period may be varied for different security levels. This can be transparently implemented through frequently
and unpredictably updating s for high-security processes (e.g.,
enclaves), while refreshing K in larger intervals for regularprocesses. We also propose heuristic-based rekeying, invalidating eviction sets upon observation of certain microarchitectural
events (e.g., many LLC cache misses or PPP signatures). It
should be noted that rapid rekeying only mitigates attacks inscope for randomized caches, i.e., potential cache-contention
channels that do not target set contention might remain.
The gap between our conservative rekeying periods (Section VI-D2) and PPP profiling in practice is quite large. Future
work could explore closing this gap by improving profiling,
relaxing theoretical bounds, or a combination of both.

LRU. While C EASER -S could accomodate several policies (e.g.,
LRU, RRIP, . . . ) [39], we believe LRU leads to an accurate
security assessment. Indeed, many stateful replacement policies
can be degraded to LRU with some repeated accesses [10].
X. C ONCLUSION
In what follows, we assume the problems from Section VIII
Analyzing the residual attack surface of randomized cache
to be fixed. There are three proposed C EASER -S instances,architectures is a complex undertaking. In this work, we havewith rekeying periods resp. 100N , 200N and 1000N . We
established a generic framework to jointly analyze all existingobserve that P RIME +P RUNE +P ROBE consistently obtains highcomputation-based randomized caches. We showed that, similar
quality generalized eviction sets within the rekeying period of
to cryptanalysis, randomized cache designs must be subjected
the 1000N -instance. While prior profiling techniques succeed
to systematic analysis to gain confidence in their security. In
on average once every 68 years [39], PPP on C EASER -S2
this effort, we have contributed on three main fronts.
has average complexity of ≈ 320N , leaving on average 68%
First, we have advanced the profiling state of the art forof every rekeying period available for exploitation. The more
randomization-based secure caches. We developed novel attack
conservative designs (100N, 200N ) resist PPP for the majority
techniques for such caches, including P RIME +P RUNE +P ROBE
of rekeying periods, though with considerably reduced security
and optimizations like bootstrapping and multi-step profiling.
margin. We observe an extreme gap between PPP and previous
Second, we have started bridging the gap between the usually
idealized estimates, easily exceeding 20 orders of magnitude
assumed ideal attack and complicating effects like noise andfor P = 4 and 50 orders of magnitude for P = 8 (not displayed).
multiple victim accesses. We have simulated an end-to-end
3) S CATTER C ACHE: First-party analysis [53] already con- attack, leaking AES keys from a vulnerable implementation.
siders generalized eviction. Their approach can be seen as a
Finally, we have falsified the implicit assumption that any
corner case of PPP, i.e., using k = 1 (cf. Section V).
randomized mapping successfully results in a secure cache.
We instantiate S CATTER C ACHE by setting P = nw = 16,
ACKNOWLEDGMENTS
implicitly with replacement RAND. Optimized for total accesses,
PPP improves profiling with three orders of magnitude for the
We would like to thank the anonymous reviewers and ourconsidered configuration. The main contribution of PPP is that shepherd, David Kohlbrenner, for their valuable feedback.
it requires much fewer victim invocations, as it permits to test This work was supported in part by the European Researchmany addresses in parallel (k  1). While S CATTER C ACHE Council (ERC) under the EU Horizon 2020 research anddoes not specify a rekeying frequency, our results indicate that innovation programme (grant agreements No 681402 and No
it should be determined more conservatively than expected.
695305). It was also supported by the CyberSecurity Research4) Shortcuts: With a case study on C EASER -S, we show Flanders VR20192203 and the Research Council KU Leuven
with devastating consequences that the security of the ran- C16/15/058. Antoon Purnal is funded by an FWO fellowship.
domization should not be taken for granted, even if its output Additional funding was provided by a generous gift from Intel.
is not directly observable. A similar study was conducted Any opinions, findings, and conclusions or recommendations
in concurrent work [5]. Instantiating a sound cryptographic expressed in this paper are those of the authors and do notalgorithm thwarts all shortcuts but affects performance. Though necessarily reflect the views of the funding parties.

R EFERENCES[1] R. Avanzi, “The QARMA block cipher family. almost MDS matrices overrings with zero divisors, nearly symmetric even-mansour constructions
with non-involutory central rounds, and search heuristics for low-latencys-boxes,” in IACR ToSC, 2017.
[2] Z. B. Aweke, S. F. Yitbarek, R. Qiao, R. Das, M. Hicks, Y. Oren, andT. Austin, “ANVIL: Software-based protection against next-generation
Rowhammer attacks,” ACM SIGPLAN Notices, 2016.
[3] D. J. Bernstein, “Cache-timing attacks on aes,” 2005.
[4] A. Bhattacharyya, A. Sandulescu, M. Neugschwandtner, A. Sorniotti,
B. Falsafi, M. Payer, and A. Kurmus, “SMoTherSpectre: exploiting
speculative execution through port contention,” in CCS, 2019.
[5] R. Bodduna, V. Ganesan, P. SLPSK, K. Veezhinathan, and C. Rebeiro,“Brutus: Refuting the security claims of the cache timing randomization
countermeasure proposed in CEASER,” in IEEE CA Letters, 2020.
[6] C. Canella, J. Van Bulck, M. Schwarz, M. Lipp, B. Von Berg, P. Ortner,
F. Piessens, D. Evtyushkin, and D. Gruss, “A Systematic Evaluationof Transient Execution Attacks and Defenses,” in USENIX Security
Symposium, 2019.
[7] S. Chari, C. S. Jutla, J. R. Rao, and P. Rohatgi, “Towards soundapproaches to counteract power-analysis attacks,” in CRYPTO, 1999.
[8] M. Green, L. Rodrigues-Lima, A. Zankl, G. Irazoqui, J. Heyszl, andT. Eisenbarth, “AutoLock: Why Cache Attacks on ARM Are Harder
Than You Think,” in USENIX Security Symposium, 2017.
[9] D. Gruss, C. Maurice, A. Fogh, M. Lipp, and S. Mangard, “Prefetch
Side-Channel Attacks: Bypassing SMAP and Kernel ASLR,” in CCS,
2016.
[10] D. Gruss, C. Maurice, and S. Mangard, “Rowhammer.js: A Remote
Software-Induced Fault Attack in JavaScript,” in DIMVA, 2016.
[11] D. Gruss, C. Maurice, K. Wagner, and S. Mangard, “Flush+Flush: A
Fast and Stealthy Cache Attack,” in DIMVA, 2016.
[12] D. Gruss, R. Spreitzer, and S. Mangard, “Cache Template Attacks:
Automating Attacks on Inclusive Last-level Caches,” in USENIX Security
Symposium, 2015.
[13] R. Hund, C. Willems, and T. Holz, “Practical Timing Side Channel
Attacks against Kernel Space ASLR,” in S&P, 2013.
[14] M. S. Inci, B. Gulmezoglu, G. Irazoqui, T. Eisenbarth, and B. Sunar,“Cache Attacks Enable Bulk Key Recovery on the Cloud,” in CHES,
2016.
[15] Intel Corporation, “Pin - A Dynamic Binary Instrumentation
Tool,”
https://software.intel.com/en-us/articles/
pin-a-dynamic-binary-instrumentation-tool.
[16] Y. Jang, S. Lee, and T. Kim, “Breaking Kernel Address Space Layout
Randomization with Intel TSX,” in CCS, 2016.
[17] T. Kim, M. Peinado, and G. Mainar-Ruiz, “StealthMem: system-levelprotection against cache-based side channel attacks in the cloud,” in
USENIX Security Symposium, 2012.
[18] V. Kiriansky, I. Lebedev, S. Amarasinghe, S. Devadas, and J. Emer,“DAWG: A Defense Against Cache Timing Attacks in Speculative
Execution Processors,” MICRO, 2018.
[19] P. Kocher, J. Horn, A. Fogh, D. Genkin, D. Gruss, W. Haas, M. Hamburg,
M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom, “Spectre
Attacks: Exploiting Speculative Execution,” in S&P, 2019.
[20] P. C. Kocher, “Timing Attacks on Implementations of Diffe-Hellman,
RSA, DSS, and Other Systems,” in CRYPTO, 1996.
[21] J. Kong, O. Acıiçmez, J.-P. Seifert, and H. Zhou, “Hardware-software
integrated approaches to defend against software cache-based side channel
attacks,” in HPCA, 2009.
[22] M. Lipp, D. Gruss, R. Spreitzer, C. Maurice, and S. Mangard, “ARMageddon: Cache Attacks on Mobile Devices,” in USENIX Security
Symposium, 2016.
[23] M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh,
J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg,“Meltdown: Reading Kernel Memory from User Space,” in USENIX
Security Symposium, 2018.
[24] F. Liu, Q. Ge, Y. Yarom, F. Mckeen, C. Rozas, G. Heiser, and R. B.
Lee, “Catalyst: Defeating last-level cache side channel attacks in cloudcomputing,” in HPCA, 2016.
[25] F. Liu and R. B. Lee, “Random Fill Cache Architecture,” in MICRO,
2014.
[26] F. Liu, H. Wu, K. Mai, and R. B. Lee, “Newcache: Secure
cache architecture thwarting cache side-channel attacks,” IEEE

Micro, vol. 36, no. 5, pp. 8–16, Sep. 2016. [Online]. Available:
https://doi.org/10.1109/MM.2016.85[27] F. Liu, Y. Yarom, Q. Ge, G. Heiser, and R. B. Lee, “Last-Level Cache
Side-Channel Attacks Are Practical,” in S&P, 2015.
[28] C. Maurice, N. Le Scouarnec, C. Neumann, O. Heen, and A. Francillon,“Reverse Engineering Intel Complex Addressing Using Performance
Counters,” in RAID, 2015.
[29] C. Maurice, C. Neumann, O. Heen, and A. Francillon, “C5: Cross-Cores
Cache Covert Channel,” in DIMVA, 2015.
[30] C. Maurice, M. Weber, M. Schwarz, L. Giner, D. Gruss, C. A. Boano,
S. Mangard, and K. Römer, “Hello from the Other Side: SSH over
Robust Cache Covert Channels in the Cloud,” in NDSS, 2017.
[31] A. Moghimi, G. Irazoqui, and T. Eisenbarth, “Cachezoom: How SGX
amplifies the power of cache attacks,” in CHES, 2017.
[32] J. Monaco, “SoK: Keylogging Side Channels,” in S&P, 2018.
[33] Y. Oren, V. P. Kemerlis, S. Sethumadhavan, and A. D. Keromytis, “TheSpy in the Sandbox: Practical Cache Attacks in JavaScript and Their
Implications,” in CCS, 2015.
[34] D. A. Osvik, A. Shamir, and E. Tromer, “Cache attacks and countermeasures: The case of aes,” in CT-RSA, 2006.
[35] D. Page, “Theoretical use of cache memory as a cryptanalytic sidechannel,” Cryptology ePrint Archive, Report 2002/169, 2002.
[36] C. Percival, “Cache missing for fun and profit,” in BSDCan, 2005.
[37] A. Purnal and I. Verbauwhede, “Advanced Profiling for Probabilistic
Prime+Probe Attacks and Covert Channels in ScatterCache,” in arXiv
1908.03383, 2019.
[38] M. K. Qureshi, “CEASER: Mitigating Conflict-based Cache Attacks via
Encrypted-address and Remapping,” in MICRO, 2018.
[39] ——, “New Attacks and Defense for Encrypted-address Cache,” in ISCA,
2019.
[40] T. Ristenpart, E. Tromer, H. Shacham, and S. Savage, “Hey, You, Get off
of My Cloud: Exploring Information Leakage in Third-party Compute
Clouds,” in CCS, 2009.
[41] D. Sanchez and C. Kozyrakis, “Vantage: scalable and efficient fine-graincache partitioning,” in ISCA, 2011.
[42] S. Sari, O. Demir, and G. Kucuk, “Fairsdp: Fair and secure dynamic
cache partitioning,” in International Conference on Computer Scienceand Engineering (UBMK), 2019.
[43] D. Skarlatos, M. Yan, B. Gopireddy, R. Sprabery, J. Torrellas, and C. W.
Fletcher, “MicroScope: Enabling Microarchitectural Replay Attacks,” in
ISCA, 2019.
[44] R. Spreitzer and T. Plos, “Cache-access pattern attack on disaligned aes
t-tables,” in COSADE, 2013.
[45] D. Trilla, C. Hernandez, J. Abella, and F. J. Cazorla, “Cache Side-channel
Attacks and Time-predictability in High-performance Critical Real-time
Systems,” in DAC, 2018.
[46] Y. Tsunoo, T. Saito, and T. Suzaki, “Cryptanalysis of DES implemented
on computers with cache,” in CHES, 2003.
[47] J. Van Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens,
M. Silberstein, T. F. Wenisch, Y. Yarom, and R. Strackx, “Foreshadow:
Extracting the Keys to the Intel SGX Kingdom with Transient Out-oforder Execution,” in USENIX Security Symposium, 2018.
[48] J. Van Bulck, F. Piessens, and R. Strackx, “SGX-Step: A Practical Attack
Framework for Precise Enclave Execution Control,” in SysTEX, 2017.
[49] P. Vila, B. Köpf, and J. F. Morales, “Theory and Practice of Finding
Eviction Sets,” in S&P, 2019.
[50] R. Wang and L. Chen, “Futility scaling: High-associativity cachepartitioning,” in MICRO, 2014.
[51] Z. Wang and R. B. Lee, “New cache designs for thwarting software
cache-based side channel attacks,” in ISCA, 2007.
[52] ——, “A novel cache architecture with enhanced performance andsecurity,” in MICRO, 2008.
[53] M. Werner, T. Unterluggauer, L. Giner, M. Schwarz, D. Gruss, and
S. Mangard, “SCATTERCACHE: Thwarting Cache Attacks via Cache
Set Randomization,” in USENIX Security Symposium, 2019.
[54] Y. Yarom and K. Falkner, “FLUSH+RELOAD: A High Resolution, Low
Noise, L3 Cache Side-channel Attack,” in USENIX Security Symposium,
2014.
[55] D. Zhang, Y. Wang, G. E. Suh, and A. C. Myers, “A hardware design
language for timing-sensitive information-flow security,” ACM Sigplan
Notices, vol. 50, no. 4, pp. 503–516, 2015.
[56] Z. Zhou, M. K. Reiter, and Y. Zhang, “A software approach to defeatingside channels in last-level caches,” in CCS, 2016.

2) Least recently used (LRU): For LRU, we derive anapproximation for pc,c . We have that P [E] = pc,n . Assume
that x is cached in partition Pl , and let PR be the randomvariable denoting the partition to which x is reloaded.
nw
X
P [D|E] =P [D, PR = Pi |E] (law of total probability)i=1= P [D, PR = Pl |E] +X

P [D, PR = Pi |E]

i6=lFig. 11: Empirical k0 and mpr (means over 105 runs) for different k. Cache
instances are denoted RP(nw , b, P ). The prune step becomes aggressivefrom the sixth iteration, if not already terminated.

A PPENDIX
A. Relation between k. k 0 and mpr
Figure 11 experimentally (cf. Section III-A3) relates pruning
parameters k, k 0 and mpr for different cache instances.
It shows that the prune step does not shrink the initial set
that much (k 0 ≈ k), unless k is very large.
We also observe that instances with stateful replacement
policy (LRU) require fewer pruning iterations mpr than thosewith random replacement. Furthermore, they generally end up
with a larger set after pruning (k 0 ).

= P [D|PR = Pl , E] · P [Pl |E] +X
P [D|PR = Pi , E] · P [PR = Pi |E](conditional)

i6=l

1 X
1
+
pc,n ·
PP
i6=lConsequently, we obtain the expression from Table III:pc,n (P − 1) + 1
pc,c = P [D] ≈ pc,n ·P≈1·

C. Theoretical vs. experimental catching probabilities

Figure 12 presents experimental and visual support for the
analysis in Section V-B. Since the attacker cannot directly
set k 0 , we choose k as the independent variable in Figure 12.
However, recall that in Table III, the catching probabilities pc
are described in terms of k 0 for RAND, i.e., after pruning, and
B. Penalty for a cached target
in terms of k for LRU, i.e., before pruning. The reason is that
We now derive the catching probability for a target address the prune step does not allow concise statistical modeling.
x that is already cached. Recall that, to detect an access to x,
Hence, for RAND, we approximate k 0 with k, noting that thethe attacker must first evict it from the cache, and detect its exact pc in terms of k 0 becomes an upper bound in terms of k.
reintroduction in the cache. Let E denote the event that the We observe theory to match practice very well for k ≤ 0.6N , asP RIME +P RUNE +P ROBE iteration successfully evicts x from k ≈ k 0 (cf. Appendix A). The upper bound becomes noticeable
the cache, and D the event that probe detects an access to x for very large k, exactly because k 0 and k diverge.
e = 0 we have thatwhen it is reloaded. Given that P [D, E]
For LRU, the theoretical expressions were derived as a lower
bound(cf. Section V-B1). It is a good approximation for low
pc,c = P [D] = P [D, E] = P [D|E] · P [E]k. For larger k, although prune does not eliminate a lotof elements (cf. Appendix A), it increases pc significantly
1) Random replacement: We have that P [E] = pc,n (k 0 ). because addresses that were evicted and reintroduced have
Recall that for RAND, the target x has nw potential cache lines another attempt at hitting the correct cache set and partition.
to which it can be mapped. Let I denote the number of thoseIn principle, one can also choose k > N to increase pc
locations that the P RIME +P RUNE +P ROBE iteration occupies. beyond those depicted in Figure 12, all the way to pc ≈ 1.
nw
X
However, for such a configuration, the prune step becomes
P [D|E] =P [D, I = i|E] (law of total probability)
excessive, both for RAND and LRU. It will require a large
i=0
number of non-aggressive iterations to avoid shrinking k 0 toonwX
fast (cf. Appendix A), followed by many aggressive iterations=
P [D|E, I = i] · P [I = i|E]) (conditional)
until there are no more self-evictions. As a result, the cache
i=0naccesses needed to terminate the prune step are significant.
w
X i P [E|I = i] · P [I = i]=·(Bayes’ rule)n
P [E]D. Known-Plaintext AES T-Tables Attack
i=0 w

0i
0 nw −i−k )We implement the ”One-Round Attack” proposed by Osviknw
iX· niw k (NN
nw
i
=
· nw
(binomial pmf) et al. [34]. Because their work already describes the attackn
P [E]in detail, we only add a high-level overview here and discuss
i=0 w
Consequently, we obtain the expression from Table III:
implications for our cache model.
nw 
Xnw i2 · k 0i · (N − k 0 )nw −i
In the T-tables implementation of 128-bit AES, each of thepc,c = P [D] =2 · N nw
first 9 rounds accesses all 4 T-tables 4 times each. Per round,
i
n
w
i=1
one access is made for each key byte and plaintext byte pair

key nibble candidate(a) RAND (P = 16)
key byte ki
Fig. 13: Result of the AES T-tables attack. Columns normed to the highest
value. The partial key can be read from left to right by the darkest field ineach column. Pictured: Key=0x00102030405060708090a0b0c0d0e0f0(b) LRU (P = 2)(c) LRU (P = 4)
Fig. 12: Catching probabilities for cached and uncached targets in theory andpractice. Experimental results obtained from simulating a standalone 8MB
randomized cache (nw = 16, b = 13), averaged over 105 runs. The prune
step becomes aggressive from the sixth iteration, if not already terminated.

pi ⊕ ki to table Tj , j ≡ i mod 4, i ∈ [0..15]. T-tables consistof 256 entries of 4 bytes each, but as cache lines are typically
64 bytes in size, we can consider them arrays of 16 entries
each, addressed by the upper nibble of pi ⊕ ki . Thus entries
Tj [dpi ⊕ ki e4 ] will always be accessed in round 1, while otherentries may be accessed in later rounds. This produces thestatistical difference we exploit.
We construct a matrix M of 16 × 16 bins, where columns
represent the key byte position i, and rows the upper key nibble
candidate dki e4 . Because of the table association mentioned
before, table Tj produces columns M∗,i . We now measureaccesses to our probe sets Aj,l , l ∈ [0..15] for all 16 addressesof each table, and simply add the resulting amount of missesfrom each probe set to a bin for each plaintext byte: M [l ⊕pi , i] += misses(Aj,l ). The key nibbles are now the highest
value in each column. Depending on the size and quality ofthe probe sets, this takes several thousand random plaintexts.
Figure 13 shows the matrix for a successful attack.
The noteworthy part for our attack is that, for uniformly
distributed random plaintexts, each table address contributes
equally to each bin in the appropriate columns of M . For thisreason, this attack absorbs differences in probe set sizes.