Understanding Meltdown

I've been trying to understand the Meltdown vulnerability that's been in the news lately (a vulnerability in Intel's CPU design allowing an attacker to obtain access to any data in memory on the system).  I understand it at a high level, but every time I've tried to dive into the details to understand an example it falls apart on me.  So I'm going to write this to force myself to fully dissect the parts I'm missing and maybe help someone else in the same boat.

This is not a post intended for a general audience.  I don't expect it will be meaningful or useful to anyone that doesn't already understand programming to some degree.

Eben Upton has a great write up over at RaspberryPi.org which will be the basis of my post.  I'm not going to recreate his work, but instead I'm going to dive into greater detail starting at "Putting it all together".

We start with his pseudocode:

t = a+b
u = t+c
v = u+d
if v:
   w = kern_mem[address]   # if we get here, fault
   x = w & 0b100           # * Modified, See Note
   y = user_mem[x]
* Modification Note:
The original was "x = w&0x100" which I've replaced with "x = w & 0b100".  0x100 is hexadecimal shorthand for the binary 000100000000.  I'm going to use an 8-bit example, so I'm replacing it with 0x4, since my example will only use binary I rewrote it to 0b100.  It is irrelevant to the method of the attack, only changed for convenience.

For those of us that spend our time on higher-level programming languages (like Java, Groovy, Python, JavaScript, etc.) the bit-twiddling needs a little more detail.  That detail is the remainder of my post.

Let's suppose we live in a 8-bit world for this example (mainly so I don't have to write out really long numbers that are irrelevant to the point I'm making).  In our 8-bit world each of our memory locations holds 8-bits.

Now, let's dissect Upton's pseudocode staring inside the "if":

w = kern_mem[address]   # if we get here, fault

This finds the 8-bits contained at "address" in a privileged part of the memory which we shouldn't be able to access, here called "kern_mem".

When the CPU sees us attempt to use that data, it will stop us (i.e., "if we get here, fault").  The crux of this vulnerability is that the CPU will fetch this information for us even though we're not allowed to see it; later it will realize we're not allowed to see it and stop us.  But we do something clever which lets us know what is in that memory even though we never saw it.

Those 8-bits from memory location kern_mem[address] are assigned to the variable "w", let's suppose those bits are 01010101.

w == 01010101 # A Number we're not allowed to see
x = w & 0b100

This is a "masking" operation (think masking-tape when painting).  0b100 is the mask, which is shorthand for 00000100.  This line will "mask" out everything except 1 bit of "w".  The result will always either be 00000000 or 00000100; note that this is either all zeroes or the same value as the mask.  Since both the mask and "w" have 1 as the 3rd bit, the resulting value, in our example, will be 00000100 and assigned to the variable "x".

w == 01010101 # A Number we're not allowed to see
x == 00000100 # A single bit from that number
y = user_mem[x]

Now we're going to get the 8-bits contained at "x" in a piece of memory we are allowed to access, here called "user_mem".  "x" is the single bit from the-number-we-cannot-see.  In this case we'll get the 8-bits located at user_mem[00000100] and assign those 8-bits to the variable "y".

We don't care at all what the 8-bits from that location in memory actually are.  The important thing is that the memory system went and got them for us from main memory and loaded them into a local cache.  This process may have taken, say, 100ns.  Next time I ask for the 8-bits in user_mem[00000100] the memory system will say "Oh, I already have that in cache, here ya go" and it will only take, say, 3ns.  Keep this in mind.

w == 01010101 # A Number we're not allowed to see
x == 00000100 # A single bit from that number
y == we_dont_care # Cached value of user_mem[00000100]

These 3 things happen before the CPU realizes we're not allowed to see "w".  Once it makes that realization, it undoes the work so that "w", "x", and "y" no longer have these values so that we can't get to them (effectively at least).

So what good does it do us as an attacker if we can't actually get that data in "w" that we tried to access?

The memory cache still has user_mem[00000100] loaded in to it!

After tricking the CPU into doing this work for me I attempt to access user_mem[00000100].  I know to access user_mem[00000100] because 00000100 was the mask I chose (0b100).  I don't care at all what value is actually stored at user_mem[00000100].  I only care how long it takes to access: I note the current time, access the memory location, and then see how much time has passed.

If it takes ~3ns to access that memory, it must have been in the cache.  It would only be in the cache if "x" had been 00000100.  "x" would only have been 00000100 if the 3rd bit of "w" was 1.

I now know that "w" looks like ?????1??.  That was a lot of work for just a little bit of information (pun intended).  But CPUs are quick and this can all be happening without you being aware of it.  So, now let's repeat the process, but this time we'll change our mask:

w == 01010101 # A Number we're not allowed to see
x = w & 0b10

The mask has been moved over one bit.  Because the 2nd bit of "w" is 0, "x" holds the 8-bits 00000000.

w == 01010101 # A Number we're not allowed to see
x == 00000000 # A single bit from that number
y = user_mem[x]

This time we get the 8-bits located at user_mem[00000000] loaded in to the cache.

w == 01010101 # A Number we're not allowed to see
x == 00000000 # A single bit from that number
y == we_dont_care # Cached value of user_mem[00000000]

This time the mask was 00000010, so we time how long it takes us to access user_mem[00000010].  This time it takes ~100ns, by which we determine that it must not have been in the cache.  That could only be true if "x" had been 00000000.  "x" could only have been 00000000 if the 2nd bit of "w" had been 0.

Now we know that "w" looks like ?????10?.  Keep doing this over and over again and we can read any data we like, we just have to piece it together.

Is it not a strange fate that we should suffer so much fear and doubt for so small a thing? So small a thing!

-- Boromir, "The Fellowship of the Ring"

Like Sauron's One Ring, this truly is a small thing, but will bring about much pain and anguish.

One [Flaw] to bring them all and in the darkness bind them.

Undermining the Credibility of an Investigation - A Game-Theoretic Analysis

Let's suppose you were the subject of a serious criminal investigation.  Further suppose you were also a prominent and influential public figure.  You know a priori whether there's anything damning that the investigation may find.  Should you choose to use your influence to affect the credibility of the investigation?  Should you bolster the credibility or undermine it?  Let's take a game-theoretic approach.

Like almost all game theory analyses we'll construct a payoff matrix to guide our analysis.  I suggest one axis capture the eventual outcome of the investigation: evidence of wrongdoing found (guilty) vs. no evidence of wrongdoing found (innocent).  The other axis will capture the subject's three possible actions regarding using their influence: bolster credibility (bolster), do nothing (null), undermine credibility (undermine).

Payoff matrix for subject using influence to affect credibility of investigation - Empty
Bolster Null Undermine

We now need to consider each possibility in the matrix and assign a relative payoff.  The payoff value represents the utility of the scenario to the subject, that is, how much does the subject benefit based on the scenario represented by each cell.

I don't think it's particularly controversial to argue that any "Innocent" outcome will be good for the subject.  Better if the credibility has been bolstered, but slightly worse if the credibility is undermined.

Payoff matrix for subject using influence to affect credibility of investigation - Partial
Bolster Null Undermine
Innocent 20 10 7

Again, it shouldn't be controversial to assume that a "Guilty" outcome will be bad for the subject.  Worse if the credibility is bolstered, but slightly better if the credibility is undermined.

Payoff matrix for subject using influence to affect credibility of investigation - Complete
Bolster Null Undermine
Innocent 20 10 7
Guilty -20 -10 -7

At a global view, it seems like the only reason to actively undermine the credibility of the investigation is if you believe the outcome will be "Guilty" as it will increase your utility.  That should be concerning to anyone paying attention to current U.S. politics.

I think there is one potential argument for modifying the "Undermine" payoffs.  If the undermining is an attack on the biases and motivations of the investigation, the supporters of the subject may see an "Innocent/Undermine" outcome as better than "Innocent/Null" because "even the biased investigation couldn't find anything."  A similar argument could be made about the "Guilty/Undermine" payoff.  The increased nuance becomes important if you think that the subject's actions are more directly tuned to either the supporters or opposers.

Payoff matrix for subject using influence to affect credibility of investigation - Supporters/Opposers
Bolster Null Undermine
Supporters Opposers
Innocent 20 10 14 0
Guilty -20 -10 0 -14

These supporter/opposer payoffs are probably up for much debate, but I think this is probably a good ballpark.

With an "Innocent/Undermine" outcome, opposers will use the attacks on the credibility of the investigation against the subject.  But, supporters will see it as stronger evidence of innocence ("even the biased investigation couldn't find anything").

With a "Guilty/Undermine" outcome, supporters will see it as "proof" that the investigation was biased and not valid.  Opposers will see it as an attempt to evade justice.

What's interesting is if the subject cares only about supporters then the only better possible outcome than undermining the investigation is to bolster an investigation that finds the subject innocent.  If the subject, knowing a priori the truth of their actions, believes that the likelihood of the investigation concluding "Innocence" is almost zero and cares most about their supporters' response then undermining the investigation becomes overwhelmingly the best action to take.

Does the President care so little about those who oppose him that he's willing to take another hit from them in the event that the Mueller investigation finds nothing?  Or is he expecting the investigation to find evidence of wrong-doing and he's laying the groundwork to salvage the only group possible?  Or is my analysis completely wrong?

Lick Observatory

Lick Observatory is a University of California observatory nearby us on the mountains above San Jose.

After Thanksgiving we tried to drive out to the observatory.  Despite countermeasures, carsickness killed the trip about a fifth of the way there.  After Christmas we tried again, but instead of driving the mountain road all the way from Livermore we drove the highway route around in to San Jose and then up the shorter mountain road.  This time we made it.

Corinne was a demon in the visitor's center and had to be taken outside.  She did manage to stay quiet on the Lick Refractor tour for about 10 minutes before she had to be taken out.

The Lick Refractor is mostly a historical relic.  They use it for tours, public viewing nights, and training students.

This is the same road at the top and bottom of the picture.  The biker went across the bottom just a minute or so before taking that switch back.  That's the kind of driving you have to do to visit the observatory.

The haze was settled in to the valleys and I thought the way the ridges stacked up looked pretty neat, but I don't think my pictures do it justice.

Christmas 2017

Heather had a Holiday Concert for school on the 18th.  She had a blast.  The program was all 4 kindergarten classes at her school so the multi-purpose room was packed.  Luckily she's a head taller than most of the other kids in her class so I was still able to get a couple pictures of her through the crowd.

Then it was quickly in to Christmas Eve with our own little "program."  Heather read us "Santa from Cincinnati":

After the program the girls opened their presents for each other:

Corinne fell asleep clutching the trowel from the garden tool set.  Heather woke up at no-one-knows-but-possibly-2-something and colored in about 3 feet of her 10-foot space coloring roll.

After bed Santa arrived bringing a fully edible dig site for Heather:

And in the very early morning we snapped an obligatory don't-move-yet shot:

You'll notice it is still dark outside.  Heather had been up possibly since as early as 2-something, but no later than 4.  Corinne was up starting at 4:30.  We held them off until 6:30, but couldn't keep them contained any longer.

Corinne got a chair in her favorite color:

Heather was a super helper handing out gifts from under the tree.

Corinne is enamored of this plane.

Jess is pleased with her yarn bowl:

After a brief break for some much-needed breakfast, the sun had risen, and the unwrapping was complete.  Now, nap time.