<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<a class="moz-txt-link-freetext" href="https://blog.acolyer.org/2018/01/15/meltdown/">https://blog.acolyer.org/2018/01/15/meltdown/</a><br>
<br>
<div class="moz-text-html" lang="x-unicode">
<p><a href="https://meltdownattack.com/meltdown.pdf">Meltdown</a>
Lipp et al., <em>2018</em></p>
<p>I’m writing this approximately one week ahead of when you get
to read it, so it’s entirely possible by this time that you’ve
already heard more than you can stand about Meltdown and
Spectre! Behind the news headlines though, there’s a lot of good
information in the accompanying papers, and I certainly wanted
to read them, so that’s what we’re going to be starting out with
this week.</p>
<blockquote>
<p> Meltdown breaks all security assumptions given by the CPU’s
memory isolation capabilities. We evaluated the attack on
modern desktop machines and laptops, as well as servers in the
cloud. Meltdown allows an unprivileged process to read data
mapped in the kernel address space… this may include physical
memory of other processes, the kernel, and in case of
kernel-sharing sandbox solutions (e.g., Docker, LXC) or Xen in
paravirtualization mode, memory of the kernel (or hypervisor)
and other co-located instances.
</p>
</blockquote>
<p>Depending on the capabilities of the target machine, it’s
possible to dump memory at up to 503 KB/s. There’s an
interesting footnote on the first page of the paper that says
“This attack was independently found by the authors of this
paper and Jann Horn from Google Project Zero.” Two independent
discoveries of the same vulnerability, which it turns out has
existed on Intel microarchitectures since 2010, certainly makes
you wonder how many other ‘discoveries’ of this there might have
been in the intervening period.</p>
<h3>You’re bang out-of-order</h3>
<p>(<em>That might be just a British expression, if it doesn’t
make sense to you, just ignore it!)</em>.</p>
<p>The roots of the problem go way back to 1967, when Tomasulo
first developed an algorithm to allow <em>out-of-order</em>
execution of instructions. Inside a CPU there are multiple
execution units. To keep things moving at pace, while the CPU is
busy executing the current instruction in one execution unit,
other units can run ahead, <em>speculatively</em> executing the
instructions that follow. The particular case of out-of-order
execution this paper concerns itself with is an instruction
sequence following a branch.</p>
<p>If we look inside a Skylake core, we’d find something like
this:</p>
<p><img
src="https://adriancolyer.files.wordpress.com/2018/01/meltdown-fig-1.jpeg?w=480"
alt=""></p>
<p>x86 instructions are fetched from memory by the front-end, and
decoded to micro-operations which are continuously sent to the
execution engine. The <em>reorder buffer</em> is responsible
for swizzling the registers so that instructions operating on
the same physical registers use the last logical value.
Execution units are connected via a common data bus, and if a
required operand is not immediately available then it’s possible
to listen on the bus and directly begin instruction execution
the moment it appears.</p>
<blockquote>
<p> Since CPUs usually do not run linear instruction streams,
they have branch prediction units that are used to obtain an
educated guess of which instruction will be executed next.
Branch predictors try to determine which direction of a branch
will be taken before its condition is actually evaluated.
Instructions that lie on that path and do not have any
dependencies can be executed in advance and their results
immediately used if the prediction was correct.
</p>
</blockquote>
<p>If the guess was wrong, the results can just be rolled back and
it’s as if they never happened. Or at least that’s the plan! But
as we all now know, unfortunately some traces do get left
behind…</p>
<blockquote>
<p> Although the instructions executed out of order do not have
any visible architectural effect on registers or memory, they
have microarchitectural side effects. During the out-of-order
execution, the referenced memory is fetched into a register
and is also stored in the cache. If the out-of-order execution
has to be discarded, the register and memory contents are
never committed. Nevertheless, the cached memory contents are
kept in the cache.
</p>
</blockquote>
<p>Consider the following simple example:</p>
<p>raise_exception()<br>
// the line below is never reached<br>
access(probe_array[data * 4096]);<br>
“<br>
Although we know the code on line 3 will never be reached, it
still might be speculatively executed. We’d like to know what
the value of <code>data</code> was during that execution. Since
we multiply <code>data</code> by 4096, every access to the
probe array is one memory page (4kB) apart: therefore each
unique value of data maps to a different unique page. If we
ensure that the probe array is not in cache (is <em>flushed</em>)
before the execution, then after the speculative execution, the
only page of the array that will (now) be in the cache is the
page indexed by the <code>data</code> value.</p>
<p>Now all we have to do is iterate over all of the 256 possible
values of the data byte and observe how many cycles it takes to
read each page of the probe array. This combination is known as
a ‘Flush+Reload’ cache side channel.</p>
<blockquote>
<p> Figure 4 shows the result of a Flush+Reload measurement
iterating over all pages, after executing the out-of-order
snipped with <code>data = 84</code>. Although the array
access should not have happened due to the exception, we can
clearly see that the index which would have been accessed is
cached. Iterating over all pages (e.g. in the exception
handler) shows only a cache hit for page 84.
</p>
</blockquote>
<p><img
src="https://adriancolyer.files.wordpress.com/2018/01/meltdown-fig-4.jpeg?w=480"
alt=""></p>
<p>Let us call instructions executed out-of-order which leave
behind measurable side effects <em>transient instructions</em>.
Such instructions introduce an exploitable side channel if their
operation depends on a secret value. We’d like to, for example,
dump the memory of the kernel address space (which will include
all of the physical memory on Linux and OS X, and pretty much
all of it on Windows). The kernel memory is protected of course,
and if we try to access it that will trigger an exception. But
not to worry – if the exception occurs <em>after</em> the
execution of the transient instruction sequence the damage is
already done, and we can just handle it. On more modern
processors we can wrap everything up in hardware transactions
using Intel TSX and suppress the exception altogether (which
happens automatically as part of transaction rollback). One
trivial exception handling technique is to fork the attacking
application before accessing the invalid memory location, and
only access that location in the child process. The parent
process can then recover the secret.</p>
<h3>I’m having a Meltdown</h3>
<p><img
src="https://adriancolyer.files.wordpress.com/2018/01/meltdown-fig-5.jpeg?w=480"
alt=""></p>
<p>The full Meltdown attack consists of three steps:</p>
<ol>
<li>The content of an attacker-chosen memory location, which is
inaccessible to the attacker, is loaded into a register</li>
<li>A transient instruction accesses a cache line based on the
secret content of the register</li>
<li>The attacker uses Flush+Reload to determine the accessed
cache line and hence the secret stored at the memory location.</li>
</ol>
<p>The core implementation of the transient instruction sequence
and <em>sending</em> part of the covert channel looks like
this:</p>
<p><img
src="https://adriancolyer.files.wordpress.com/2018/01/meltdown-listing-2.jpeg?w=480"
alt=""></p>
<p>Line 4 loads a byte value located at a target kernel address.
While this is going on, the subsequent instructions on lines 5-7
are likely to be speculatively executed. Line 5 multiplies the
secret value by the page size (4 KB, or 2^12 — 0xc), and line 7
contains an indirect memory access based on the result. This
will affect the cache state based on the secret value. Iterating
over all 256 pages of the probe array and measuring the access
time reveals the secret as before.</p>
<p>It just remains to explain what that <code>jz retry</code>
instruction is doing on line 6. There’s a race condition between
the speculative execution and cache probing, and the triggering
of an exception caused by trying to read from an inaccessible
kernel address on line 5. When the exception is triggered, the
register where the data should be stored gets zero’d out. But if
the zeroing out of the register happen before the execution of
line 5, we’d read a false zero as the value of the secret.</p>
<blockquote>
<p> To prevent the transient instruction sequence from
continuing with a wrong value, i.e., ‘0’, Meltdown retries
reading the address until it encounters a value different from
‘0’ (line 6). As the transient instruction sequence terminates
after the exception is raised, there is no cache access if the
secret value (truly is) 0. Thus, Meltdown assumes that the
secret value is indeed ‘0’ if there is no cache hit at all.
The loop is terminated by either the read value not being ‘0’
or by the raised exception of the invalid memory access.
</p>
</blockquote>
<p>Meltdown was successfully reproduced on the following systems:</p>
<p><img
src="https://adriancolyer.files.wordpress.com/2018/01/meltdown-table-1.jpeg?w=480"
alt=""></p>
<p>Using the exception handling strategy, it was possible to leak
kernel memory at a rate of 122 KB/s. Using Intel TSX to suppress
exceptions that goes up to 502 KB/s.</p>
<p>Meltdown was also demonstrated within containers (Docker, LXC,
OpenVZ). This gives access to information both from the
underlying kernel and also all other containers running on the
same physical host.</p>
<blockquote>
<p> … the isolation of containers sharing a kernel can be fully
broken using Meltdown.
</p>
</blockquote>
<h3>Defences?</h3>
<p>Kernal address space layout randomisation (KASLR) makes it <em>harder</em>
to find the kernel memory, but not by much it turns out. An
attacker can simply search through the address space, or
de-randomise the direct-physical map: “<em>assuming that the
target system has at least 8GB of physical memory, the
attacker can test defences in steps of 8GB, resulting in a
maximum of 128 memory locations to test.</em>”</p>
<p>The KAISER patch by Gruss et al. (or its equivalents) seems to
be what is going into the OS patches (mitigations really – this
isn’t a software vulnerability remember). It provides stronger
isolation between kernel and user space by mapping only the bare
minimum of kernel memory in user space (and still with the
protection bit set of course).</p>
<blockquote>
<p> Consequently, Meltdown cannot leak any kernel or physical
memory except for the few memory locations which have to be
mapped in user space. We verified that KAISER indeed prevents
Meltdown, and there is no leakage of any kernel or physical
memory.
</p>
</blockquote>
<p>That sounds alright then? Apply the patches, pay the
performance penalty, forget about Meltdown and move onto
worrying about Spectre? Not quite… it’s important to keep
reading into section 7.2 of the paper where we find this:</p>
<blockquote>
<p> Although KAISER provides basic protection against Meltdown,
it still has some limitations. Due to the design of the x86
architecture, several privileged memory locations are required
to be mapped in user space. This leaves a residual attack
surface for Meltdown… Even though these memory locations do
not contain any secrets, such as credentials, they might still
contain pointers. Leaking one pointer can be enough to again
break KASLR, as the randomization can be calculated from the
pointer value. Still, KAISER is the best <strong>short-term</strong>
solution currently available and therefore be deployed on all
systems immediately.
</p>
</blockquote>
<p>The authors were unable to reproduce Meltdown on ARM and AMD
CPUs, though that’s not quite the same thing as saying that
variations of the attack will not be possible.</p>
<h3>The world will never be the same again…</h3>
<blockquote>
<p> Meltdown fundamentally changes our perspective on the
security of hardware optimizations that manipulate the state
of microarchitectural elements. The fact that hardware
optimizations can change the state of microarchitectural
elements, and thereby imperil secure software implementations,
is known since more than 20 years. Both industry and the
scientific community so far accepted this as a necessary evil
for efficient computing… Meltdown changes the situation
entirely… it is nothing any (cryptographic) algorithm can
protect itself against. KAISER is a short-term software fix,
but the problem we uncovered is much more significant.
</p>
</blockquote>
<p>One of the sobering things here is that <em>improved
performance</em> is an observable effect which creates a
side-channel to leak information. (That’s not a new observation,
witness all the variations on the Flush+Reload cache attacks for
example). But what would it mean to eliminate that side-channel?
The whole point of performance improvements is that they’re
observable! If you don’t see improved performance, it’s not a
performance improvement. Moreover, if we think about adding
noise we can only slow down discovery but not eliminate it —
it’s possible to add noise that makes the occasional cached data
be returned more slowly, but not the other way round. Making
everything always go as slowly as the slowest possible route
doesn’t seem all that appealing either!</p>
<p>And then there’s this:</p>
<blockquote>
<p> Even if Meltdown is fixed, Spectre will remain an issue.
Spectre and Meltdown need different defenses. Specifically
mitigating only one of them will leave the security of the
entire system at risk.
</p>
</blockquote>
<p>You locked the front door, but you left the backdoor wide open.</p>
</div>
</body>
</html>