Written by David Anderson
on 

Finding the Bottom Turtle

If you’ve never read the classic Reflections on Trusting Trust, and you like the idea of being unsettled about the foundations of computing, go have a read. It’s amazing. It details the strange reality that we can’t truly trust most of the software we use today.

Over time, the ideas from that speech evolved into an important question for open-source software: do we know for sure that the programs we’re running correspond to the source code we have access to?

Trusting Trust and Bootstrapping

I’ll start off with a brief recap of the Trusting Trust attack. Say you’re trying to get backdoors into popular pieces of open-source software without being detected. Modifying their source code without being found is hard (although people have gotten close before). Modifying the release binaries is a decent way to get a point-in-time compromise, but a simple rebuild from source will both cure the problem and make it visible in binary diffs (assuming reproducible builds, which is another can of worms I’m not going to get into right now).

A more devious attack would be to insert malicious code into the compiler, to make it recognize that it’s compiling the target software and insert the backdoor there and then. Recompiling from source and source inspection wouldn’t help, because the backdoor gets inserted reliably on every compile.

That just pushes the problem one step further up the chain into the compiler. If you can recompile it from source, you can eliminate the backdoor. The problem we have in today’s computing is that most compilers are self-hosting, meaning they’re written in the very language they compile.

In other words, to build a clean copy of gcc from source, you need… a C compiler binary (actually a C++ compiler binary these days, but let’s assume you start from GCC 4.7 or older, which only required C).

This is the bootstrapping problem. If you dig deep enough into any system, you’ll reach a point where the very first thing you need to compile from source is a self-hosting compiler… Meaning you need to already have a compiler for that language.

This comes up when building a linux distribution. If you want to make security assertions about your distro, you need some kind of software supply chain assurances, meaning you’ll be wanting to build everything from source yourself. For linux distros, if you dig deep enough, you’ll eventually get to compiling gcc… Which requires a C compiler and most of a basic Unix system (a shell, various core utilities…) to even build.

So, to build a linux system from source, you need to already have a running linux system that you didn’t compile from source yourself… And therefore cannot make any promises about.

It’s turtles all the way down

At this point, there are two kinds of people out there. One group is very pragmatic: the Trusting Trust attack is very difficult to carry out in practice, given the complexity of modern computers and programs. To insert precise backdoors that compromise a specific piece of software way up the supply chain, without causing adverse side-effects in any other programs, while also being robust to how the source code “up-stack” changes over time… Eh, it’s so hard it probably never happened.

Therefore, who cares how we bootstrap into our little universe? Gcc requires a C compiler and unix-ish environment? Cool, I’ll just grab binaries from, oh I don’t know, Ubuntu, and use those to bootstrap my software tree. They’re probably fine.

In practice, what’s what most linux distros (and, to my understanding, popular proprietary OSes) end up doing. If you follow the package dependency tree down to the bottom-most layers, you’ll eventually find a package that miraculously contains the various binaries needed by the immediate next layer up, but cannot be reconstructed from source. Fiat lux!

I’m glad the pragmatists exist in the world, otherwise I wouldn’t be writing this post right now, because I wouldn’t have emacs, or Go, or hugo, or a linux kernel with network and display drivers, …

But, at heart I’m a purist. It bothers me, at some fundamental level, that the entire edifice of modern computing is built on a shaky foundation. At some point in the past, we built our way up from no computers to where we are today. But because we weren’t paying attention to supply chain security, at some point we lost the chain of custody.

At some point in the distant past, there was a proto-C compiler written in PDP-7 assembler. With enough care and intermediate steps, you could use that proto-C compiler to build your way up to a modern gcc, and from there to a full linux distro. But that path likely contained software and hardware that is now lost to time, so the chain is broken (and besides, where did the PDP-7 assembler come from? And the editor software? And the software that ran the PDP-7 enough to get to text entry and assembling?).

Getting back to basics

So, how do we get back to a bootstrappable system today? That’s the purpose of the Bootstrappable.org family of projects. They seem to be mostly GNU-affiliated these days, so their goal is to go backwards from a working gcc build environment to as close to “nothing” as possible.

Ultimately, the goal is to have the miraculous pre-existing seed of software be small enough that a single human can inspect and verify its machine code by hand, and build back up using source code from there on.

Here’s a summary of the current state of the art (meaning, a very small number of distros bootstrap this way, and are the “most bootstrappable” distros out there):

Currently, Mes is the bottom turtle. Compared to starting with gcc, the amount of ultimately trusted programs shrinks from ~250MiB to ~60MiB. And, for the first time in this chain, we have a C compiler that is not written in C. Instead, there are two different languages, each implemented in the other. Furthermore, the Scheme interpreter is written in a more basic subset of C.

So, in order to bootstrap into Mes, you have two options:

As I said above, right now Mes is the bottom turtle. The state of the art bootstrapping chain ends with “a miraculous set of binaries for the Mes Scheme interpreter exist”. That’s a smaller chunk of miraculous code, but it’s still 60 million bytes of stuff, far too much for a human to inspect and validate by hand.

One turtle deeper

So, how do we bootstrap up to Mes, and further reduce the size of the “miraculous” seed at the bottom of computing? Enter the stage0 project.

The goal of stage0 is to start from a piece of machine code so small that it’s tractable for a human to disassemble it by hand using the processor reference manual, and fully understand and verify it. From there, the stage0 can be used to progressively build up to a basic Scheme interpreter sufficient to run the Mes C compiler - at which point Mes can compile its own scheme runtime, cut out all the previous stages, and continue climbing the complexity ladder… But from a solid foundation.

The stage0 project does this through a couple of steps that are functionally “manually enter machine code as hex into the computer” (the miracle stage0 binary is an interpreter for “read some hex digits and put them into memory”), building up to a tiny symbolic assembler, from which either a basic C compiler or Scheme interpreter can be built.

Perhaps slightly strangely, in order to make this bootstrap stage portable, the early stages are written for a made up virtual machine. The idea being that to bring up a brand new platform, you simply need to implement this VM, and then you can start building up from stage0. I’m not personally convinced that this is less work overall than simply declaring that the first few bootstrap stages are 100% platform-dependent. Empirically, the stage0 project agrees somewhat, because it also provides implementations of the early bootstrap stages for x86, so that you can bootstrap on real hardware.

However, the existence of this VM layer does highlight one more problem that the stage0 project is trying to wrestle with: is there any hardware that makes true bootstrapping possible any more?

This bottom turtle has a turtle under it!

Let’s say the final stages of stage0 and Mes integration are done. We can finally, with great fanfare, load the miraculous stage0 binary into our x86 processor, and start the entire universe of software from trustable foundations. The very first instruction the CPU executes is one we manually inspected and verified!

Except it’s not, is it. By the time your code gets to run on an x86, hundreds of megabytes of firmware have already executed to initialize the system enough that things like keyboards and displays work. Worse, some of that firmware has invisible superpowers over your code. SMM can execute code beyond the awareness of your mere ring0 software, and has total control over its execution environment.

This is not a hypothetical risk. Government agencies have built SMM rootkits in the past, because they’re a perfect place to subvert the trust of the entire underlying system.

And then even below the SMM, the Intel Management Engine and AMD Platform Security Processor are another layer of ultimately privileged code that doesn’t even run on the same computer as your code, but has unfettered access to your hardware.

This is not something limited to x86. Modern computers are so complex that some amount of software always exists to bring the processor from reset to a point where it presents a reasonable execution environment. Even basic ARM Cortex M0 microcontrollers contain a firmware ROM that implements basic hardware bringup and things like firmware flashing over USB. Fundamentally, on modern computers, you no longer have first-instruction privileges.

The bootstrapping threat model

So, is this whole thing pointless? This feels like we’ve reached a point in our bootstrapping where we have to run atop preexisting software we don’t trust, cannot replace, and cannot avoid.

This is where a lot of purists turn out to be pragmatists as well. Most bootstrapping enthusiasts probably use an x86 computer riddled with firmware. Even the most die-hard libre purists, who overwrite their firmware with Coreboot, run me_cleaner to neuter the management engine as much as possible, cannot get rid of all the firmware in the system, not by a long shot.

That doesn’t mean this is all pointless though. An important piece of wisdom in security is that detection is as important as prevention. In other words, can you tell when something’s gone wrong?

Seen in that light, reducing the untrusted surface as much as possible is a laudable goal. We might even get the mandatory untrusted firmware surface down to a point where manual inspection and validation is tractable. It won’t be open source, but we may still be able to prove that it’s harmless.

There will still be many people, like me, who run their mostly-open-source software stack on top of a big blob of vendor firmware, which we sort-of choose to ignore so that we can get on with our lives. But maybe the binaries we use to bootstrap these systems should come from somewhere more “pure”. If the bootstrap chain originates on a system sitting on an untrustworthy bottom turtle, you can never undo that. But if the bootstrap started from a trusted place…

Finding the bottom turtle

In a perfect world, what would our bootstrappable distro build machine look like?

Well, it can’t have any firmware for starters. For our end-user boxes, we’d like open-source, replaceable firmware so that we can extend our supply chain security all the way down to the hardware… But someone’s got to compile that firmware, and it can’t be our bootstrapping machine.

We also need the first program that runs to not have originated from another computer, since in this thought exercise, we assume that all software we didn’t build ourselves is suspect and might corrupt the purity of our universe.

So, weirdly, the first piece of software cannot be software. It’s going to be much more akin to hardware. Taken to the extreme, it could literally be made out of wires hooked together in the right way, or a string of core rope memory that twiddles the electrons just so. The idea is going to have to leap from our brain into the physical world, without going through a software intermediate stage.

This feels like a bit of a mystical experience that I think we’ve lost in modern computing. These days, if you have a new platform you want to bootstrap, you have an existing computer that you use to puppet the new hardware. You cross-compile software for the new target, flash its storage through a USB programmer, and you’re done. It’s way less tedious than bootstrapping from scratch, but it obscures that crucial transition from a purely hardware world into the universe of software. Every time that transition happens, it’s a kind of Big Bang for a new universe of runnable ideas. I think it’s a pity that we’ve optimized bringup to the point where few people get to experience that first leap between worlds.

Anyway, enough with the mysticism. That first hard-wired program is the ultimate bottom turtle of bootstrapping. There is no place left to go below that, except for hardware and humans.

Once you have that hardwired monitor, you can follow similar steps to stage0 and Mes to build whatever you want. But, starting from such a low level, with a CPU capable of doing work immediately without firmware, you’re likely running on a ridiculously wimpy piece of hardware (possibly even hand-assembled out of discrete transistors… did you think I was joking when I mentioned core rope memory?).

The next step up would be to get to a point where you can build firmware from source for a slightly better machine, say a RISC-V board or a Power9, both of which have half a chance of being able to run all-open firmware. Then you restart the bootstrapping from “stage0” again, but this time running on a much more capable machine, running firmware you built yourself. This machine is probably powerful enough to get all the way up to gcc, and from there up to whatever other software you desire.

Assuming the software you want is cross-compilable, you can even build trustable software for platforms like x86, where the firmware can never be entirely trusted. Of course, you’ll never be sure that execution is trustworthy, but at least your binaries won’t be the weak link, and you always have a trustable thing you can back up to and verify things.

So, that’s the ultimate in bootstrappability, and why the stage0 project is toying with this made up virtual machine. Maybe someday, someone will instantiate that machine in actual hardware, at which point stage0 will be ready to bootstrap the universe from it.

Where do we go from here?

I dunno. This post is just a recap of my adventures in discovering the current state of the art of bootstrapping, and thinking about the problems that come with recreating a bootstrap chain for our software universe.

There’s also the entire question of whether the hardware itself is trustable, and how we might try to make it so. But for starters I’d be happy with an answer to safely making the leap from hardware to software without losing our chain of custody.