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.
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 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 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
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 loaded in to it!
After tricking the CPU into doing this work for me I attempt to access user_mem. I know to access user_mem because 00000100 was the mask I chose (0b100). I don't care at all what value is actually stored at user_mem. 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 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
This time the mask was 00000010, so we time how long it takes us to access user_mem. 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.