google/security-researchEste projeto hospeda avisos de segurança e suas provas de conceito relacionadas a pesquisas conduzidas no Google que impactam código não pertencente ao Google.
This repository contains proof of concept for page table side channels, implemented in two ways:
Both were discussed in the VUSec's AnC paper, though only the first one was implemented (Prime+Probe was deemed impractical). After we conducted our own experiments (described here), a similar research was afterwards independently published in the Peek-a-Walk paper.
The point of the PoC is to guess the secret pointer that is accessed by the victim - either for its own sake (e.g. to break ASLR), or as part of a larger exploit (where secret data is encoded as a pointer).
To build the code, run make. To cross-compile for
ARM, run CROSS=aarch64-linux-gnu- make. You will now have two binaries:
anc and
eviction_anc. The recommended way to run them is:
taskset -a -c 0 ./anc $RANDOM
$RANDOM is a seed for the internal PRNG - you can generally reuse it
if you want reproducibility. However, some of the modern ARM CPUs have
fairly advanced prefetchers with state persisting for many seconds,
and across new processes - so for those, reusing seed is discouraged
to avoid unrelated effects.
We ran the code on Intel, AMD, and ARM CPUs.
On Intel and AMD both work (though anc on AMD might be somewhat unreliable);
on most ARMs - only anc does (eviction_anc might return partial results).
When you run anc, you should see a line like this at the bottom:
TRUE: 0x6585903b62af [4230]
GUESS: 0x6585903b6280 [4230] (OK)
The OK indicates that the secret pointer has been guessed correctly
(up to a few last bits, which are unknown). If you see BAD, the exploit
failed.
When you run eviction_anc, you should see something like this at the end:
Best guesses: 01 03 1c 16 17 (order unknown)
True values: 17 16 03 1c 01
If the two lines contain the same values (potentially in a different order), the exploit succeeded.
Both x86 and ARM use page walks to find page's physical address. This is illustrated by the following diagram from AMD64 Architecture Programmer's Manual:
When an address is loaded, actually about five loads from main memory can be performed: first the top level table's entry pointing to the lower level table start, then one of that table's entries is loaded and so on.
Crucially, each of these hidden, intermediate loads goes through the processor cache hierarchy - and can be cached, e.g. in L1D. The attacker can then use one of the well-known cache side channels to leak the accessed pointer address, since the L1D signal is directly connected to the bits in the address. Here's a helpful diagram for ARM with 4kB pages (from Linux docs):
+--------+--------+--------+--------+--------+--------+--------+--------+
|63 56|55 48|47 40|39 32|31 24|23 16|15 8|7 0|
+--------+--------+--------+--------+--------+--------+--------+--------+
| | | | | |
| | | | | v
| | | | | [11:0] in-page offset
| | | | +-> [20:12] L3 index
| | | +-----------> [29:21] L2 index
| | +---------------------> [38:30] L1 index
| +-------------------------------> [47:39] L0 index
+-------------------------------------------------> [63] TTBR0/1
Confusingly, ARM uses L0 to refer to the top level, while AMD reverses the numbering. For the rest of this write-up we'll use ARM terminology.
The page walk as described above only occurs if the translation result is not cached in TLB, or other paging-structure caches. See e.g. this presentation for good introduction. For our attack, the TLB and paging-structure caches are not needed; in fact, they get in way of our job - so as one of the steps, we try to clear them.
Implemented in anc.c.
We can split an address into a sequence of page table entry indexes, L0:L1:L2:L3:P - for example 1:2:3:4:5. Then let's say we hypothetically run the following sequence of loads and flushes:
load a:b:c:d:e ; attacker controlled
flush everything
load a:b:X:Y:Z ; secret!
load a:b:c:d:e ; attacker controlled
The first load will of course perform the whole page table walk, and
the secret load will do that as well. However, the secret load will leave
L0[a] and L1_a[b] entries cached, making the final load's page table
walk faster (as it will reuse these two entries, and only slowly load the
rest).
This leads to a simple (at least in principle) algorithm of leaking the address:
addr = 0
for level in 0..4:
best_t, best_addr = inf, -1
for i in 0..512:
guess = addr
guess.level_bits[level] = i
mmap(guess)
flush everything
call victim to load secret pointer
t = time_access(guess)
best_t, best_addr = min((best_t, best_addr), (t, guess))
addr = best_addr
return addr
In short, we brute force all possible indexes at the top page table and check accessing which is fastest; then we repeat for the lower levels.
In practice, there are some optimizations (e.g. we only mmap each guess once - before the loop; and we time access to all guesses after the secret pointer is loaded just once).
However, there are still some complications, and unstated details.
In the pseudocode we have an enigmatic flush everything statement. This
is supposed to make sure the secret load is fully uncached at all levels
so that we can differentiate the touched cachelines from the untouched ones.
Additionally, we need it to be uncached also in the TLB.
Since page tables are not directly accessible from userspace, we cannot use
instructions such as x86 clflush. Instead, we use cache contention to evict
them. At the program start, we allocate a large number of pages. Then the
eviction step just loads all of them in succession.
The eviction pages are placed at mostly random locations in order to put as much cache pressure as possible. However, if we did this naively, we would expect all top-level page table entries to be cached after the eviction step (as our random pointers were caching random L0 entries in the course of loading). To remedy that, we choose one L0 entry to be "sacrificed": all eviction pages will be allocated under that L0 index. Other indexes won't be cached (just as we wanted); we'll have to adjust the algorithm to ignore that special index (for L0 only). This makes our algorithm fail if the secret pointer was under that index (though in principle this condition could be detected by repeating the algorithm with a different chosen L0 index for eviction pages).
There is a lot of noise in the system, and the timing difference is very small (~single-digit cycles - or sub-cycle in some cases!). The noise can be mostly averaged out by repeating the experiment thousands of times, and averaging the measured time.