SBN

An accessible overview of Meltdown and Spectre, Part 2

This is the second half of our blog post on the Meltdown an Spectre vulnerabilities, describing Spectre Variant 1 (V1) and Spectre Variant 2 (V2). If you have not done so already, please review the first blog post for an accessible review of computer architecture fundamentals. This blog post will start by covering the technical details of Spectre V1 and Spectre V2, and conclude with a discussion of how these bugs lurked undetected for so long, and what we think the future holds.

Like Meltdown, the Spectre vulnerabilities rely on speculative execution and timing side channels to read memory without proper permission. The difference between Meltdown and Spectre is the method of operation and the potential impact — more computers are vulnerable to Spectre. Meltdown works by taking advantage of an asynchronous permissions check, and affects affects only Intel processors. Spectre works by tricking the branch predictor (Figure 1), and affects almost every processor released in the last 25 years.

Figure 1: How branch misprediction leads to speculative execution. When the branch predictor makes an incorrect guess about the destination of a conditional branch, some instructions are speculatively executed. The execution of these instructions is undone, but their effects on the cache remain. Spectre causes the branch predictor to guess wrong and speculatively execute a carefully chosen set of instructions.

Figure 1: How branch misprediction leads to speculative execution. When the branch predictor makes an incorrect guess about the destination of a conditional branch, some instructions are speculatively executed. The execution of these instructions is undone, but their effects on the cache remain. Spectre causes the branch predictor to guess wrong and speculatively execute a carefully chosen set of instructions.

Spectre (Variant 1)

The first variant of Spectre allows a program to read memory that it should not have the ability to read. Spectre V1 attacks are possible because of the confluence of two optimizations: branch prediction and speculative execution. A Spectre V1 attack tricks the branch predictor (for conditional branches) into skipping security checks and speculatively executing instructions in the wrong context. The effects of these speculatively executed instructions are visible via a cache timing side-channel.

Technical Details

Let’s walk through a hypothetical example. Even though the steps seem complex, they are quite possible to execute in a web browser via JavaScript — see the Spectre paper’s working proof of concept. The following example assumes a Spectre attack delivery via JavaScript in a web browser. That isn’t a requirement. Spectre can work on all kinds of programs, not just web browsers. Also, some specifics are omitted for brevity and clarity.

  1. First we’ll create two large memory allocations. We’ll call one leaker and the other reader. In JavaScript, these can be created with ArrayBuffers, a structure used for storing binary data (like pictures). The leaker allocation will be used for the cache timing side-channel. The reader allocation only exists to train the branch predictor. The arrays we allocated have a fixed length. It is only legal to read items from the array starting at zero (the first element) and ending before the array length (the last element). So for a 256 byte array, the valid items are numbered 0 to 255. This range of the first to last element is called the array bounds.
  2. Next we start training the branch predictor. A Spectre attack relies on grooming the branch predictor to guess that certain security checks always pass. In this specific case, we are going to make the branch predictor guess that the values read out of reader are always in bounds. JavaScript checks bounds on array reads; an out of bounds read will fail and cause the program to stop working. Array bounds are (currently!) checked via branch instructions. For this part of the Spectre attack, we will repeatedly read in bounds values from reader. Recall that the processor assumes current behavior is predictive of future behavior. If branches are always taken (or not taken), then the branch predictor will be trained to expect that same behavior.
  3. Next we ensure that no part of leaker is cached. This is also possible to do in JavaScript. We avoid the details for brevity.
  4. Now that the preparation is out of the way, let’s get to the core Spectre V1 flaw. We will read an out of bounds element from reader. Let’s call this value secret. Because we read secret from outside the array bounds, it can, by definition, be any chosen memory location. The read of secret will temporarily succeed even though there is a bounds check that logically prevents it from ever happening. It succeeds only speculatively, because the branch predictor has been primed to assume that the bounds check will succeed. At this point the countdown also starts for the processor to discover the mispredicted branch and un-execute the mispredicted instructions.
  5. Next, we use the value of secret as an index to read an element from reader (i.e., reader[secret]). This action will be speculatively executed and cause that element of reader to be cached. At this point, the branch predictor can correct itself and un-execute all speculatively executed instructions.
  6. By measuring the time to read every element of secret, it is possible to determine which element was cached. The index of the cached element will be the value of secret, a value the program was not permitted to read. For example, if reader[42] was cached, the value of secret would be 42.
  7. The attack can now be repeated to read more bytes. The bandwidth of this channel is estimated at 10 KB/s.

See Figure 2 for a graphical representation of the reader and secret data memory locations at Step 4.

Figure 2: A hypothetical layout of reader and some secret data in computer memory. Because computer memory is laid out linearly, it is possible to access any part of it in terms of a positive or negative index into reader. Access to reader should be limited by its bounds, 0 to 255. If bounds checks are bypassed, even by a few speculatively executed instructions, it is possible to access memory without proper permission.

Figure 2: A hypothetical layout of reader and some secret data in computer memory. Because computer memory is laid out linearly, it is possible to access any part of it in terms of a positive or negative index into reader. Access to reader should be limited by its bounds, 0 to 255. If bounds checks are bypassed, even by a few speculatively executed instructions, it is possible to access memory without proper permission.

What is the impact?

Spectre (Variant 1) is a really big deal to desktop, laptop, and mobile users. It lets websites break security and isolation guarantees built into web browsers like Chrome, IE, and Firefox. As an example, Spectre could allow a website open in one tab to read passwords you are typing into a different tab, or allow an ad on a checkout page to read the credit card number you are typing.

Spectre is equally devastating for cloud providers and internet companies. A lot of the code powering your favorite websites relies on isolation guarantees provided by programming languages. Spectre renders those guarantees into good intentions. Application hosting providers have to re-evaluate their security architecture, rebuild a lot of core code (with performance loss), or both.

There is no generic fix for Variant 1. Affected software has to be re-compiled to avoid using vulnerable code patterns. However, exploitation of the vulnerability can be made more difficult. This is the path taken by web-browser vendors so far. They have removed high-resolution timers (necessary to determine if something was cached) and are actively working to avoid using vulnerable code patterns.

What should I do?

Update your browser, operating system, and BIOS to the latest version. All browser vendors have released mitigations for Spectre vulnerabilities.

All major cloud providers have deployed mitigations. You as a customer should have nothing to worry about moving forward.

Spectre (Variant 2)

The second variant of Spectre allows a program to read memory that it should not have access to, regardless of whether the memory is part of the same program, another program, or the core operating system.

Like Spectre V1, Spectre V2 also relies on abusing branch prediction, speculative execution, and cache timing side-channels. Whereas V1 tricks the conditional branch predictor, V2 tricks the indirect branch predictor. The indirect branch predictor is indifferent to privilege changes, including from user to kernel, from program to program, and even from a virtual machine (think cloud computing instance) to hypervisor (the cloud control plane). For those reasons, Spectre V2 attacks can happen across most if not all privilege levels provided by modern processors.

Technical Details

Out of the three published attacks, Spectre V2 attacks are the most complex. To explain a Spectre V2 attack, we are going to describe a simplified version outlined in the Google Project Zero blog. Many technical details will be omitted with the hope of providing a more accessible understanding of the attack.

The Spectre V2 attack described here reads privileged hypervisor memory from a guest virtual machine. Google Project Zero demonstrated that this attack works with real software running on real processors.

First, a quick refresher about indirect branches and the indirect branch predictor. Indirect branches tell a processor to start executing instructions at some new location. This location can be stored in memory. If that location is not cached, the processor would have to pause a very long time (relative to instruction execution speed) while waiting to find out where to get instructions. The indirect branch predictor guesses where the processor would go next, so the processor doesn’t have to wait. If the guess turns out to be wrong, the processor un-executes some instructions and goes back to the correct place. If the guess turns out to be correct, the program runs much faster. Processors are very good at guessing correctly, so this usually results in a big speedup.

Time for the first Spectre V2 concept: the indirect branch predictor works by keeping a history of recently executed branches in the Branch History Buffer (BHB), sometimes called the Branch History Table, because previous branch decisions are typically indicative of future branch decisions (Figure 3). As with Meltdown and Spectre V1, by carefully measuring how long some branch operations take, it is possible to “read” the BHB and determine the location of previously executed instructions — even if those instructions were executed at a different privilege level or in a different program.

Figure 3: The branch history buffer is used to predict the target of indirect branches, so that the processor can execute them faster. When an indirect branch executes, an entry is written into the table. The table has limited space, and is indexed based on branch address. Because of this limitation, it is possible to “poison” the branch predictor and make it guess an attacker-chosen address for any indirect branch. In this hypothetical prediction example, any branch at an address ending in 045C would have the same predicted destination.

Figure 3: The branch history buffer is used to predict the target of indirect branches, so that the processor can execute them faster. When an indirect branch executes, an entry is written into the table. The table has limited space, and is indexed based on branch address. Because of this limitation, it is possible to “poison” the branch predictor and make it guess an attacker-chosen address for any indirect branch. In this hypothetical prediction example, any branch at an address ending in 045C would have the same predicted destination.

Now for the second Spectre V2 concept: The branch predictor is shared among all programs running on a processor. Branches executed in one program change how the indirect branch predictor guesses in another program. By executing a carefully chosen series of branches, you can “write” the BHB, and force the branch predictor to guess a location you chose for a future indirect branch — even if that indirect branch will be executed at a different privilege level. This is analogous to Spectre V1, but using indirect branches instead of conditional branches.

The steps described for Google Project Zero’s Spectre V2 attack are less detailed because there isn’t a good way to condense the required information. Each step described below is extremely involved and difficult to accomplish properly. The described scenario is one where a cloud computing instance reads memory contents of the cloud control plane (Linux-KVM, specifically). That memory contains private information about what every other cloud computing instance on that physical machine is doing, including private user data, software source code, encryption keys, etc.

Attack Preparation

  1. First, allocate a large block of memory that will be used for the cache-timing side channel. Per our previous convention, we’ll call this block reader.
  2. To leak out data via speculative execution, we will need some way to force the hypervisor to read a byte of privileged memory first, and to use that byte to access reader. This code pattern may be hard to find, but luckily we can cheat. The KVM hypervisor is a part of the Linux kernel, and the Linux kernel includes a feature that runs custom programs to quickly deal with network traffic. This feature is called the eBPF interpreter. We can use the eBPF interpreter to create the code pattern we need in the hypervisor. To do that, we’ll need to:
    1. Find the eBPF interpreter in the hypervisor, and
    2. Supply some code to the eBPF interpreter, which we’ll call ebpf_code.
  3. Because Spectre V2 relies on tricking the indirect branch predictor, we need to know the location of an indirect branch in the hypervisor. We’ll call this indirect_branch.
  4. The hypervisor has a different view of computer memory than our program in the cloud instance. Because we’ll be leaking memory from the hypervisor, we’ll need to find out where in hypervisor-land reader, ebpf_code, indirect_branch and the eBPF interpreter are located.
  5. To find these items, we will need to know the location of some code in the hypervisor. We can’t simply read hypervisor code. We lack the proper privileges. Instead, we leak out code locations via the BHB. How? We’ll ask the hypervisor to do some normal operations on behalf of the cloud instance. In the course of these operations, the hypervisor executes indirect branches, the locations of which will be stored in the BHB. We then “read” the BHB to identify these code locations.
  6. Once we know some code locations in the hypervisor, with some math and multiple repeated attempts we can find where in hypervisor-land reader, ebpf_code, indirect_branch and the eBPF interpreter reside (Figure 4).
Figure 4: A simplified diagram of how a cloud computing system would look after completing Step 6 of this attack description. The attacker has gathered all information they need to conduct the attack, but the key part is still to come.

Figure 4: A simplified diagram of how a cloud computing system would look after completing Step 6 of this attack description. The attacker has gathered all information they need to conduct the attack, but the key part is still to come.

Attack Execution

  1. We ensure that no part of reader is cached.
  2. Time for the magic! We execute a series of indirect branches that write new entries into the BHB. These branches and their targets are set up to trick the indirect branch predictor into guessing that indirect_branch points to the eBPF interpreter (Figure 5).
Figure 5: This is the core of the Spectre V2 attack: specially crafted indirect branches can trick the Branch History Buffer into predicting an attacker-chosen speculative destination for an indirect branch. In this case, an indirect branch in the hypervisor is set to speculatively point to the eBPF interpreter code instead of its original location.

Figure 5: This is the core of the Spectre V2 attack: specially crafted indirect branches can trick the Branch History Buffer into predicting an attacker-chosen speculative destination for an indirect branch. In this case, an indirect branch in the hypervisor is set to speculatively point to the eBPF interpreter code instead of its original location.

Leaking Secrets

  1. We set up processor state so that if it were to start executing the eBPF interpreter, then the interpreter would run ebpf_code, which would in turn read a byte of hypervisor memory and use that byte to access a part of reader.
  2. We ask the hypervisor to perform an innocuous action that is guaranteed to trigger indirect_branch. A complex chain of events now happens:
    1. The processor will guess indirect_branch points to the eBPF interpreter.
    2. The processor will start speculatively executing the eBPF interpreter. Also, the countdown starts until the processor knows it guessed the wrong branch target.
    3. The eBPF interpreter will execute instructions provided by ebpf_code, which will:
      1. Read a byte of hypervisor memory.
      2. Use that byte to access a piece of reader.
      3. Cause that piece of reader to be cached.
    4. The processor figures out it executed the wrong branch, and un-executes every instruction speculatively executed thus far. However, a piece of reader is now in the cache (Figure 6).
  3. As with Meltdown and Spectre V1, we time access to every piece of reader and identify which piece is read much faster than the others. The index of that piece is the value of the byte we read from hypervisor memory.
  4. We can repeat this process to read more bytes, although with less setup since we can skip the Attack Preparation steps.
Figure 6: A visualization of how secrets can be leaked in a Spectre V2 attack. The eBPF interpreter speculatively executes attacker-specified eBPF code which will read a secret value and use it to access reader. The effects of speculative execution can be observed via a cache-timing side channel.

Figure 6: A visualization of how secrets can be leaked in a Spectre V2 attack. The eBPF interpreter speculatively executes attacker-specified eBPF code which will read a secret value and use it to access reader. The effects of speculative execution can be observed via a cache-timing side channel.

Again, the steps described above are greatly simplified to show the general concepts and some of the exciting trickery involved in a working Spectre V2 attack. Each step is very complex on its own (i.e., one does not simply “read” the BHB).

What is the impact?

This is very bad news for everyone — no matter if you are a cloud provider, an internet company, or just a citizen of the web. The impact combines the worst parts of Spectre (Variant 1) with the worst parts of Meltdown. Unlike Variant 1, there is no proof of concept that targets web browsers, but the possibility can’t be ruled out.

The news for cloud providers is worse. There is a proof-of-concept exploit that breaks the strongest isolation mechanisms used to separate tenants on cloud computing systems. Also, not only Intel, but processors from various vendors across multiple CPU architectures are vulnerable to Variant 2.

There are multiple mitigations available, each of which has some performance cost. Processor vendors have updates available that tune how their processors work to lessen the impact. When that is not possible, software can be re-compiled to avoid using indirect branch instructions. We have not been able to find reliable numbers for the performance penalty of these fixes, but they are certainly not zero and must be paid in addition to the penalties for fixing Meltdown.

What should I do?

Update your operating system and firmware (i.e., BIOS or UEFI) to the latest version. The latest operating systems and BIOS updates will mitigate the most serious instances of Variant 2 either via processor microcode updates, workarounds to control indirect branch predictor behavior, or recompilation to avoid indirect branches.

All major cloud providers have deployed mitigations. You as a customer should have nothing to worry about.

How Did This Happen?

So how did a fundamental computer design flaw go unnoticed for the past 25 years? The answer has two parts: our fundamental assumptions about computing have changed, and the many hints about these security implications weren’t put together in a working proof-of-concept until now.

When speculative execution made its consumer processor debut in the 90s, the way we used computers was different. Most machines were single user, and the most popular operating systems of the day — Windows 9x and Mac OS Classic — lacked memory protection. You didn’t need Spectre or Meltdown to read (or even write!) another application’s memory — you could just do it. In that environment, the performance gains were real, and the security implications weren’t.

Nowadays, multi-tenant cloud computing, whether using virtual machines or containers, powers a huge part of the web. It is a regular occurrence for web browsers to download and run untrusted code (i.e. JavaScript) that is meant to be sandboxed from other untrusted code (i.e. other tabs you have open). In this environment, leaking information from one isolated memory compartment to another (e.g. between browser tabs) is a huge problem.

There have been numerous hints that speculative execution could lead to leaks of privileged information. The Google Project Zero blog post cites multiple sources (including one by our very own Sophia D’Antoine) that insinuate the problem. Multiple, independent researchers identified and reported the Spectre and Meltdown vulnerabilities, and others were very close. There is, however, a big difference between thinking there may be a problem and writing a proof-of-concept showing the problem is real. The work done by the researchers reporting this issue was fantastic. I hope this blog post shows just how difficult it was.

Conclusion

We hope you have a better understanding of how Meltdown and Spectre work at a technical level, their impact, and the available mitigations. This blog post was written to be accessible to someone without a computer architecture background, and we sincerely hope we succeeded. To our more technical readers, the Meltdown and Spectre papers, and the Project Zero blog post are better sources for the gory details.

Looking forward, micro-architectural attacks on computing platforms are going to be an exciting area of computer security. Because so many deployed platforms are vulnerable to Meltdown and Spectre, micro-architectural attacks will continue to be relevant and dangerous for many years to come.

*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored by Artem Dinaburg. Read the original post at: https://blog.trailofbits.com/2018/03/22/an-accessible-overview-of-meltdown-and-spectre-part-2/