Branch Prediction/Speculative Execution attacks have advanced from “fun thought-experiment” to “theoretical attack” to “realistic threat.”
We have only seen the tip of the iceberg of exploits (eg “Spectre”), and defending against them (1) will crush CPU performance and (2) is impossible in the general case until new CPUs are built with full process isolation.
(Hah, I bet you thought I would be giving you good advancements!)
The very, very short story:
Until 2017, when the Spectre paper was released, Software Engineers treated CPUs as Turing machines.
Deep down, we knew that CPUs were doing Fancy Shit to “fake” the simplicity of a Turing machine but still make CPUs Really Fast. CPUs cached some data in registers and speculatively executed branches. But there was a 100% impenetrable wall between “CPU optimization tricks” and “things we have to think about while writing code.”
Spectre blew a hundred-mile hole in that wall.
I am not going to go into deep detail on this class of exploits because (1) I’m not an expert, and will humiliate myself and (2) good resources have been written already. I recommend this one, which gives an an amazingly approachable description of the CPU architecture optimizations behind Spectre.
The 5,000 mile view is:
When I write and execute this code:
- if (a < my_variable) {
- z = my_array[some_array[y] *256 ];
- }
I expect the CPU to run commands in this order:
- evaluate “a < my_variable”
- if it is true, evaluate some_array[y] * 256
- look up the value in my_array
- assign that value to z
This is not always what happens. One of the fundamental advancements in processing over the past 50 years has been the sophisticated use of small but fast processor caches to hold “hot” data.
Think of “CPU cache vs main memory” as “keeping a pencil in your pocket” vs “keeping a pencil in a desk drawer.” You can only keep a few things in your pocket at a time — but you can get to them quickly. When you don’t need your pencil anymore — you put it back in the drawer, and fill your pocket with kleenexes or whatever instead.
Well, the CPU knows that main memory access is slow. So if “a < my_variable” is in main memory, but “some_array[y]” is in the cache, it might execute the latter command even before the first statement is evaluated as true.
- If the statement ends up being true: the return value of some_array[y] is used
- If the statement is false: the return value is ignored
If your process is the only process running on a CPU, the story ends there. But on modern computers, that is never true:
- On a cloud server, your physical CPU will be shared between Virtual Machines.
- On a consumer device, multiple programs are running at any given time. Most notably, browsers are running untrusted JavaScript, sharing CPU time with gmail and other sensitive programs.
Spectre outlines a wide class of attacks by which a second program can (1) trick the CPU into speculatively executing the branch above, and (2) within a completely separate program, use the fact that the CPU has displaced a cache line by loading my_array to then infer the internal state of the attacked program.
This is Very Bad. It is pretty close to the Worst Thing.
This attack is not isolated to any particular CPU. It is a vulnerability on practically every modern CPU, on every modern architecture. As Matt summarizes (from the post I linked above):
I consider this a fundamental revelation about how modern hardware and software work together. The fact that CPU caches can be used indirectly to learn about access patterns has been known for some time. The fact that CPU caches can be used as a side-channel to dump computer memory is astounding, both conceptually and in its implications.
It is also more-or-less unfixable without redesigning the underlying CPU architecture. Engineers have introduced changes to make the attacks harder, but fundamental chip redesigns will be necessary to fully mitigate the risk. And even these limited protections are not free:
the collective whack is ~15-16 percent on all Intel CPUs without Hyper-Threading disabled. Disabling increases the overall performance impact to 20 percent (for the 7980XE), 24.8 percent (8700K) and 20.5 percent (6800K).
[source]
There is no good news. This advance in software sophistication — using timing attacks to break through the abstractions provided by a modern CPU — will haunt us for decades:
- CPU performance is 10–20% throttled across the board by anti-Spectre patches.
- We have no confidence that there aren’t already viruses in the wild utilizing CPU cache side-channels to steal secrets.
Yay progress.