[Cryptography] BranchScope: a new attack on branch predictors

[Henry Baker]

FYI --

https://arstechnica.com/gadgets/2018/03/its-not-just-spectre-researchers-reveal-more-branch-prediction-attacks/

As predicted, more branch prediction processor attacks are discovered

New attack focuses on a different part of the branch prediction system.

Peter Bright - Mar 26, 2018 10:15 pm UTC

Researchers from the College of William and Mary, Carnegie Mellon, the
University of California Riverside, and Binghamton University have
described a security attack that uses the speculative execution
features of modern processors to leak sensitive information and
undermine the security boundaries that operating systems and software
erect to protect important data.

http://www.cs.ucr.edu/~nael/pubs/asplos18.pdf

That probably sounds familiar.

The Spectre attacks, published earlier this year, take advantage of
the speculative execution features of modern processors to leak
sensitive information.  The new attack, named BranchScope by the
researchers, shares some similarity with variant 2 of the Spectre
attack, as both BranchScope and Spectre 2 take advantage of the
behavior of the processor's branch predictor.

With speculative execution, the processor runs ahead of where the
program actually is, and it tries to execute instructions before it
can be certain if those instructions will actually be run.  For
example, if a program tests whether two numbers are equal and does one
thing if they are and another thing if they aren't, the processor will
guess the outcome and speculatively execute the resulting action.  If
it later turns out that the processor guessed wrong, the speculative
results are thrown away and, at least in an abstract sense, it's as if
the bad guess never happened.  The processor picks up from where it
left off, performing the action that it should have taken instead.

The Spectre attacks as a whole occur because the processor doesn't
quite put things back the way they should be.  While the processor
does revert to its speculative execution correctly--if it didn't,
programs would simply stop working correctly--it doesn't quite do so
perfectly.  This is particularly noticeable when it comes to the
processor's cache: speculative execution can cause the processor to
load data into cache (or, alternatively, evict data from cache), and
these cache changes persist even if a bad speculation is made.
Carefully written software can detect these cache changes and use them
to infer secret information.

The processor's branch predictor is one of its core pieces of
speculative execution machinery.  While the branch predictors in the
latest processors are complex, in broad terms they operate in a
similar way.  The processor tracks the address of branch instructions,
whether the branch was taken or not, and if the branch is taken, the
address of the next instruction that should execute--that is, the
target of the branch.  The branch predictor provides two related
predictions: whether the branch is taken or not, and if it's taken,
what the target is.

BranchScope and Spectre 2 both take advantage of different parts of
the branch predictor.  Spectre 2 relied on a part called the Branch
Target Buffer (BTB)--the data structure within the processor that
records the branch target.  BranchScope, instead, leaks information
using the direction of the prediction--whether it's likely to be taken
or not--which is stored in the pattern history table (PHT).

The PHT keeps a kind of running score of recently taken branches to
remember if those branches were taken or not.  Typically, it's a
two-bit counter with four states: strongly taken, weakly taken, weakly
not taken, and strongly not taken.  Each time a branch is taken, the
counter's value is moved toward "strongly taken;" each time it's not
taken, it's moved toward "strongly not taken."  This design means that
an occasional mispredict won't change the result of the prediction: a
branch that's almost always taken will still predict as taken, even if
it's occasionally not actually taken.  Changing the prediction
requires two back-to-back mispredicts.  This design is proven to
provide better results than a one-bit counter that simply predicts a
branch based on what happened the last time it was taken.

For Spectre 2, an attacker primes the BTB, carefully executing branch
instructions so that the BTB has a predictable content with a target
instruction that will, if speculatively executed, disturb the
processor's cache in a detectable way.  The victim program then runs
and makes a branch.  The attacker then checks to see if the cache was
disturbed; the measurement of that disturbance leaks information.

In the new attack, an attacker primes the PHT and running branch
instructions so that the PHT will always assume a particular branch is
taken or not taken.  The victim code then runs and makes a branch,
which is potentially disturbing the PHT.  The attacker then runs more
branch instructions of its own to detect that disturbance to the PHT;
the attacker knows that some branches should be predicted in a
particular direction and tests to see if the victim's code has changed
that prediction.

The researchers looked only at Intel processors, using the attacks to
leak information protected using Intel's SGX (Software Guard
Extensions), a feature found on certain chips to carve out small
sections of encrypted code and data such that even the operating
system (or virtualization software) cannot access it.  They also
described ways the attack could be used against address space layout
randomization and to infer data in encryption and image libraries.

Spectre 2 has provoked both operating system and hardware changes,
with more hardware fixes planned.  The researchers suggest that a
similar combination of solutions would be needed for BranchScope; some
software can be modified to eliminate branches, and hardware could be
altered to partition the speculative execution data structures on the
processor so that one process could not attack another.

As with Spectre 2, it's not clear just how much software is truly
vulnerable to BranchScope attacks.  In both cases, attackers need the
ability to run code on a victim system, so these attacks will never be
used for initial entry into a system.  What they do, however, is
demonstrate that the isolation boundaries that have long been assumed
to exist are rendered somewhat permeable by the speculative execution
hardware that is essential to high-performance processors.  Moreover,
BranchScope shows that Spectre isn't the only avenue through which
this speculative execution can be exploited.

Fundamentally, the processor contains lots of internal states
(including registers, caches, branch predictor, store buffers, and
more) that speculative execution can modify.  The architectural
state--the parts directly exposed and manipulated by the processor's
published, documented instructions--is preserved properly by the
speculative hardware.  Attacks like Spectre and BranchScope exist
because the non-architectural state--the parts that represent
implementation details of the processor that may change from family to
family, and which aren't directly accessible to programs--isn't being
preserved fully.  Speculative execution (and the non-architectural
state it depends on) is designed to happen invisibly, with no
indication to the running program that it's occurring.

Attacks like Spectre 2 and BranchScope are the result.  It's likely to
be years before researchers have determined all the various ways in
which the speculative execution hardware can be used to leak
information this way, and it will be longer still before robust,
universal defenses are available to stop the attacks.

Peter is Technology Editor at Ars.  He covers Microsoft, programming
and software development, Web technology and browsers, and security.
He is based in Brooklyn, NY.

Email peter.bright at arstechnica.com // Twitter @drpizza
----------------
"[Speculation] attacks like Spectre and BranchScope exist
because the non-architectural state--the parts that represent
implementation details of the processor that may change from family to
family, and which aren't directly accessible to programs--isn't being
preserved fully."

The night is still young...