Computing Discussions 2018-01-12 Meltdown & Spectre

class: center, middle

Computing Discussions  
# Meltdown & Spectre

<img src="img/meltdown.svg" alt="Meltdown Logo" width="200px" height="200px"> 
<img src="img/spectre.svg" alt="Spectre Logo" width="200px" height="200px">

Friday January 12th 2018  
by Oliver Stueker

---
class: center, middle

## They must be bad, they even have logos!

<img src="img/meltdown.svg" alt="Meltdown Logo" width="200px" height="200px"> 
<img src="img/spectre.svg" alt="Spectre Logo" width="200px" height="200px">

.footnote[Logos from  <https://meltdownattack.com> & <https://spectreattack.com> used under CC0.]
---

# Outline

1. Introduction
1. Scalar processors
1. Super-scalar processors
1. Out-of-order processors
1. Branch prediction
1. Speculation
1. Cache
1. Side channel
1. Putting it all together
1. What's at risk?
1. Conclusion
1. Links

.small[
This presentation draws heavily from "Why Raspberry PI isn’t vulnerable to Spectre or Meltdown"
by Eben Upton (Raspberry Pi Founder)  
<https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>
]

---
class: split-70

## Introduction

.column[
* The Spectre and Meltdown vulnerabilities are design flaws in processors (CPUs)
* Software and Firmware (BIOS) updates are being released.
* But the root problem can only been fixed by new hardware.
* Intel CPUs are susceptible to both Spectre and Meltdown.
* AMD CPUs are only a bit better off (immune against Meltdown)
* many (but not all) ARM CPUs (Smart-phones, Tablets, ...) are affected as well.
]

---
class: split-60

## What is a scalar processor?

.column[
* We use this code as an example.
* It is simple enough that each statement roughly 
  corresponds to a single machine instruction.
* A *scalar* processor would process each instruction
  sequentially.
* Examples: 
    * x86 processors up to 486, 
    * ARM1176 core used in Raspberry Pi 1 and RasPi Zero.
]

.column[
Pseudo code (Example):
```python
t = a+b
u = c+d
v = e+f
w = v+g
x = h+i
y = j+k
```
]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
class: split-60

## What is a super-scalar processor?

.column[
* One can make a processor faster by:
    - increasing clock speed (MHz/GHz)
    - performing several things at once
* *Super-scalar* processors have pipelines (pipes)
  that can process independent instructions
  at the same time.
* A dependent instruction needs to wait.
* These pipes are multiple integer- and/or floating-point-units
  within the same CPU(core).
* Examples:
    * Intel Pentium
    * ARM Cortex-A7 and Cortex-A53 cores used in 
    RasPi 2 and RasPi 3 
]

.column[
```python
# processor tries to 
# execute as:

t, u = a+b, c+d
v, w = e+f, v+g  # dep!
x, y = h+i, j+k

# because of dependency
# it has to execute as:
t, u = a+b, c+d
v    = e+f      # idle!
w, x = v+g, h+i
y    = j+k
```
]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
class: split-60

## What is an out-of-order processor?

.column[
* To keep all pipelines filled CPUs can re-order
  waiting instructions to resolve dependencies.
* These 6 instructions can be processed in just 3 cycles!
* Examples:
    * Intel Pentium 2
    * AMD K5
    * Many recent ARM cores Cortex-A9, -A15, -A17 & -A57
      that are base of many Smart-phones & tablets.
]

.column[
```python
# CPU reorders:
t = a+b
u = c+d
v = e+f
x = h+i #!
w = v+g #!
y = j+k

# and executes as:
t, u = a+b, c+d
v, x = e+f, h+i
w, y = v+g, j+k
```
]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
class: split-60

## What is branch prediction?
.column[
* Real programs use conditionals (e.g. `if`/`else`) 
  and loops (e.g. `for` or `while`)
* The next instruction to process often depends on 
  evaluating a condition.
* In order to avoid *stalls* a processor can *guess*
  which instruction is next and already fetch it.
* A *branch predictor* helps by making an educated guess
  based on statistics of often a particular branch was taken.
* An attacker can mis-train a branch predictor to make poor choices.
]

.column[
```python
t = a+b
u = t+c
v = u+d
if v:
   w = e+f
   x = w+g
   y = x+h
```
]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
class: split-60

## What is Speculative Execution?

.column[
* Modern processors can speculate whether an instruction
  will be called upon.
* Speculative execution evaluates instructions that are likely
  to be needed next in order to keep 'pipes' busy  
  (*Use it or loose it!*).
* The branch predictor is used to choose the most likely path through
  the program.
* If the execution was unnecessary, the results are discarded
  instead of being committed to memory (RAM).  
* To the program it would seem the instructions never happened.  
  What could go wrong with that?
]

.column[
```python
# this code:
t = a+b
u = t+c
v = u+d
if v:
   w = e+f
   x = w+g
   y = x+h

# could be executed as:
 t, w_ = a+b, e+f
 u, x_ = t+c, w_+g
 v, y_ = u+d, x_+h
 if v:
    w, x, y = w_, x_, y_

# in case v is False,
# results are discarded.
```
]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
class: split-60

## What is a cache?
.column[
* On modern computers it takes ~100ns to get data from RAM.
* That's 200 clock cycles on a 2GHz CPU.
* Cache is small but very fast memory close to the CPU.
    * L1 cache, size:  32-64KB, latency: 0.5-1ns,  
      within each CPU core
    * L2 cache, size: 256KB, latency: 4-7ns,  
      sometimes shared by two cores
    * L3 cache, size: 2-40MB, latency: 50ns,  
      usually shared by all CPU cores
]

.column[

```python
# without cache:
a = mem[0] # 100ns
b = mem[1] # 100ns
# takes 200ns

# with cache:
a = mem[0]  # 100ns
# copy mem[0:15] to cache
b = mem[1]  # 1ns
# mem[1] is in the cache

# takes 101ns
```

]

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>  
with info from: <https://software.intel.com/en-us/articles/memory-performance-in-a-nutshell>  
and <https://gist.github.com/jboner/2841832>
]
---
class: split-60

## What is a side channel?

From Wikipedia:

> … a side-channel attack is any attack based on information gained from the 
> physical implementation of a cryptosystem, rather than brute force or theoretical
> weaknesses in the algorithms.
>
> For example, timing 
> information, power consumption, electromagnetic leaks or even sound can provide 
> an extra source of information, which can be exploited to break the system.

Spectre and Meltdown are side-channel attacks which deduce the contents of a memory location which should not normally be accessible by using timing to observe whether another, accessible, location is present in the cache.

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/> and Wikipedia]
---
## Putting it all together (1)

Combining speculation and caching can permit a Meltdown-like attack:

```python
t = a+b
u = t+c
v = u+d
if v:
   w = kern_mem[address]   # if we get here, fault
   x = w&0x100
   y = user_mem[x]
```

If the branch predictor can be tricked to believe v is true,  
a Super-scalar CPU with 2 pipelines will process as:

```python
t, w_ = a+b, kern_mem[address]
u, x_ = t+c, w_&0x100
v, y_ = u+d, user_mem[x_]

if v:
   # fault
   w, x, y = w_, x_, y_      # we never get here
```

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
## Putting it all together (2)

So if we:

1. clear the cache that user_mem is not in it,
2. train the predictor to predict v will be `True`,
3. make sure that eventually v is `False`
4. run the following code:

```python
t, w_ = a+b, kern_mem[address]
u, x_ = t+c, w_&0x100
v, y_ = u+d, user_mem[x_]

if v:
   # fault
   w, x, y = w_, x_, y_      # we never get here
```

* The fault (error) in the `if` branch will never be reached,
however a chunk of the **`user_mem`** array will be in the cache.
* Which part is cached depends on the value of **`kern_mem[address]`**.
* We can now check how fast we can access any a chunk of **`user_mem`**
  and conclude whether it was cached (fast) or not (slow).

.footnote[Adapted from: <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>]
---
## What's at risk?

* Meltdown:
    * A user on a system can ex-filtrate secret data from system memory 
      (e.g. encryption keys, passwords, data being processed by other users).
    * Even malicious code running in one Virtual Machine (VirtualBox or in the 
      cloud) can even steal data from other VMs or the host computer.
* Spectre:
    * A malicious program can possibly
      read data from other programs, e.g.:
      * a JavaScript in a browser tab from other browser tabs 
        (think credit card information, emails)
      * passwords from a password-manager

---
## However

* The real Meltdown exploit is substantially more complex than this.
  * The data however needs to be inside the memory (RAM) and not just on hard-disk.
  * It takes some time to reconstruct all the memory of a machine.
  * The specifics need to be adjusted to the a particular CPU model.

* Updates to the OS core (Kernel Updates) can protect against Meltdown.
* Updates to programs (browsers, compilers) can protect against Spectre.
* These updates will make our computers slower.

---
## Conclusion

* Computers have been designed to work as fast as possible,
but not as secure as possible.

* What the code describes is not exactly what will happen in the CPU.

* The physical implementation can be exploited to read data from regions of
  the memory that a (user) process is not supposed to see.

* This will haunt us for may years! It will take time until more secure 
  processors are developed and available to buy and even longer until insecure
  systems are retired.
  
* Security researcher have now a new angle to find unrelated, but similar attack vectors.

---
# Links:

1. <https://meltdownattack.com> & <https://spectreattack.com>
2. <http://blog.cyberus-technology.de/posts/2018-01-03-meltdown.html>  
3. <https://googleprojectzero.blogspot.ca/2018/01/reading-privileged-memory-with-side.html>
4. <https://www.raspberrypi.org/blog/why-raspberry-pi-isnt-vulnerable-to-spectre-or-meltdown/>

---
class: center, middle
![xkcd #1938 Meltdown and Spectre](https://imgs.xkcd.com/comics/meltdown_and_spectre.png)  
.footnote[Source: <https://xkcd.com/1938/>]
???
New zero-day vulnerability: In addition to rowhammer, it turns out lots of servers are vulnerable to regular hammers, too.