The Bootstrapping Exam: Escaping from “Trusting Trust”

The following is an “exam”. To my knowledge, nobody has ever passed it, as it is an extremely difficult challenge. But I am firmly convinced it is possible, and it makes for an interesting discussion.

1. You have a server, currently unplugged — namely a Talos II (no SAS) or Blackbird POWER9 server.

   All mutable, nonvolatile data storage devices have been erased, including those which hold any boot firmware or other firmware (e.g. SPI flashes).

   This includes the socketed BMC SPI flash, the socketed PNOR SPI flash (which holds the boot firmware), the planar VPD flash, SBE SEEPROMs for all CPUs, the BCM5719 flash and the iCE40 FPGA flash.¹

   No drives, USB devices or PCIe devices are attached. No network connection is attached.

2. Your mission is to get contemporary Linux booting on the host side of this server system with a functional userspace.

   You may request any of the following resources:

   • Source code to any open source code, printed on paper

   • Any SBCs or computing devices, bearing in mind that any nonvolatile storage integrated into that machine will be erased before you receive it

   • Any device comprising solely of fixed-function logic chips and other devices which do not contain firmware or nonvolatile storage facilities (custom assembled to your request) (e.g. manual binary input devices)

   • A second-hand RS232 serial terminal. (This is likely to contain firmware and is the sole exception permitted for practicality and due to the limited risk. It can be replaced in future versions of this exam if needed for those of sufficient paranoia levels.)

   • Standard electronics lab equipment, cables, tools, etc.

   • ISA manuals and other standards/specification documents.

3. You may request further open source code (e.g. the Linux kernel) to be delivered in some digital form. You may specify any form, however data delivered in this manner may only be used where:

   • the user can verify the cryptographic identity of that data, where that verification process itself does not rely on any data obtained using this clause, and

   • the user can examine the source code, where the means for them to examine the source code does not rely on any data obtained using this clause.

   In other words, you may only obtain data under this clause once you already have the facility to calculate a SHA256 hash (or similar) and view text files which the provided data comprises. Any method of delivery may be used (e.g. USB, optical, SATA HDD, network, serial, your choice).

   Binaries cannot be obtained using this clause. If a source code tarball of an open source project also contains binaries, it cannot be obtained using this clause (but a subset with those binaries stripped could be).

4. No other data will be provided (i.e., binary firmware blobs, software binaries, etc.)

Discussion

The object of this exam is bootstrapping of a system purely from source code, without any reliance on any software or firmware binary. One underlying motivation for such an exam, of course, is to eliminate any possibility of compiler or other backdoors in any binaries which might ordinarily be used for bootstrapping (“Reflections on Trusting Trust”, etc.).

The successful completer of the exam produces a working, modern high performance server using only source code available to them and with no reliance on existing binaries, rendering the “Trusting Trust”, or other similar attacks based on reliance on pre-existing but compromised binaries, infeasible. ²

This, to me, is what the word “bootstrapping” properly means.

Q. Why the Talos II/Blackbird POWER9 systems?

Since modern x86 systems all have anti-owner-control vendor-signed proprietary firmware blobs, it is not feasible to complete this exam on those systems. The Talos II/Blackbird POWER9 systems are the most performant systems available today which actually have 100% open source firmware. Thus, they are the most meaningful target in terms of the execution of this bootstrapping protocol, particularly in terms of the object of getting to a trusted development environment (with the performance, resources and OS development environment that that implies) from which other platforms or SBCs could be bootstrapped.

Q. Isn't this impossible?

No. In fact, I would go so far as to say it is “impossible for it to be impossible”. The fact you are using a computer right now is proof that this process, or its spiritual equal, was successfully completed by humanity at least once. Everything began somewhere with someone toggling hand-assembled machine code into some computer. The process can be repeated. It is very, very hard — but it must be possible. The repetition of abiogenesis.

Q. How should this exam be attempted?

The attempter of this exam may use whatever approach they like within the above rules. But here's how I'd start:

Bootstrapping Protocol

1. Request a SBC which can run without any firmware blobs and which can boot from an SPI flash. (Ideally this SBC has at least 8 GiB of RAM, as while tight, it is possible to compile the OpenPOWER firmware in 8 GiB.)

2. Hand assemble the GNU stage0 hex0 monitor (280 bytes) (or a spiritual equivalent for the SBC's ISA) from printed source assembly using pen and paper and an ISA manual.

3. Order a fixed-function logic device using clause 2 which allows you to manually generate SPI transactions against the SPI flash chip by toggling switches.

4. Toggle in the hex0 monitor.

5. Order a RS232 serial terminal using clause 2 and attach it to the SBC.

6. By using the terminal to communicate with the hex0 monitor, type in more sophisticated monitors as hexdecimal after hand-assembling them on pen and paper. The work of the GNU Mes project is instructive here, but I will omit the details because others have already done well at documenting it. You might, for example, seek to obtain a Forth or Scheme environment using the hex0 monitor.

7. ???

8. First Linux environment. Bootstrap a Linux OS environment on the SBC. The means by which to get from the above stage to this stage is left as an exercise to the reader. This is the hardest part — you need to already have a POSIX environment to build Linux.

   At this point you should have a Linux environment running on the SBC.

9. BMC firmware. From this environment you can compile the BMC firmware for the target system. You will load the BMC firmware as open source code using clause 3, verifying its cryptographic hash and compile it in the Linux environment on the SBC.

10. You will now need to program the produced image to the BMC SPI flash on the target system. Most SBCs will have GPIOs which should make this easy, but any fixed-function logic devices needed to make the connection can be ordered under clause 2 if needed.

11. OpenPOWER host firmware. The BMC has only 512 MiB DRAM, so use the Linux environment on your SBC to compile the OpenPOWER firmware (expect to need 8 GiB RAM).

12. Transfer the OpenPOWER firmware image to the target system in the same way as was done for the BMC.

13. Power sequencer FPGA. The iCE40 power sequencer FPGA's bitstream will need to be synthesised on the SBC using the open source iCE40 toolchain and again, programmed using SPI in the same way.

14. BCM5719 NIC firmware. Optionally, the open source BCM5719 NIC firmware can be compiled on the SBC at this time and flashed using SPI in the same way. This is needed if network connectivity to the BMC is desired, though it could also be done later on the target.

15. SBE SEEPROMs. At this stage only the POWER9 CPU SBE SEEPROMs and Planar VPD remain to be programmed. This should be doable from the BMC over FSI (or, for the SBE SEEPROMs on the Talos II or Blackbird, over I2C). Tooling to do this for the SBE SEEPROMs to my knowledge doesn't currently exist but should be readily constructible.

16. Done! You can now power on the POWER9 host and successfully complete firmware POST. A Linux userspace environment is built into the OpenPOWER firmware (skiroot), so you now automatically have a Linux shell from which you can bootstrap a proper OS (probably Guix). Congratulations. Have fun trying to build Rust.

As noted above, the hardest part is building Linux (kernel and userspace) when you don't already have a POSIX environment. I suspect the easiest pathway may be to start by building a “simpler” POSIX OS, perhaps Minix or NetBSD or similar, and hope it can function well enough to manage to compile Linux.

I'm posting this because it's an interesting thought experiment — not because I am hopeful anyone is about to try and attempt it. But if anyone is interested in attempting it, or just interested in talking about this subject in general, please do get in touch.

Nobody has ever passed this exam.

Anyone who did would have accomplished something really quite significant.