How to compile the C compiler from scratch, then compile Unix/Linux from scratch

Question

Let's say I work for a large services organisation outside the US/UK. We use UNIX and Linux servers extensively.

Reading through this article it mentions that it would be easy to insert a backdoor into a C compiler, then any code compiled with that compiler would also contain a backdoor. Now given recent leaks regarding the NSA/GCHQ's mandate to put backdoors/weaknesses in all encryption methods, hardware and software, the compiler is now a critical point of failure. Potentially all standard UNIX/Linix distributions could be compromised. We cannot afford to have our systems, data and our customers data compromised by rogue governments.

Given this information, I would like to build a trusted compiler from scratch, then I have a secure base to build on so I can build the Operating System and applications from source code using that compiler.

Question

What is the correct (and secure way) to go about compiling a compiler from source code (a seemingly chicken-egg scenario) then compiling a trusted Unix/Linux distribution from scratch?

You can assume I or others have the ability to read and understand source code for security flaws, so source code will be vetted first before compiling. What I am really after is a working guide to produce this compiler from scratch securely and can be used to compile the kernel, other parts of the OS and applications.

The security stack must start at the base level if we are to have any confidence in the operating system or applications running on that stack. Yes I understand there may be hardware backdoors which may insert some microcode into the compiler as it's being built. Not much we can do about that for the moment except maybe use chips not designed in the US. Let's get this layer sorted for a start and assume I could build it on an old computer potentially before any backdoors were inserted.

As Bruce Schneier says: "To the engineers, I say this: we built the internet, and some of us have helped to subvert it. Now, those of us who love liberty have to fix it."

Extra links:

• http://nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all&_r=0

• http://theguardian.com/commentisfree/2013/sep/05/government-betrayed-internet-nsa-spying

Answer 1

AFAIK the only way to be completely sure of security would be to write a compiler in assembly language (or modifying the disk directly yourself). Only then can you ensure that your compiler isn't inserting a backdoor - this works because you're actually eliminating the compiler completely.

From there, you may use your from-scratch compiler to bootstrap e.g. the GNU toolchain. Then you could use your custom toolchain to compile a Linux From Scratch system.

Note that to make things easier on yourself, you could have a second intermediary compiler, written in C (or whatever other language). So you would write compiler A in assembly, then rewrite that compiler in C/C++/Python/Brainfuck/whatever to get compiler B, which you would compile using compiler A. Then you would use compiler B to compile gcc and friends.

Answer 2

One possible way, although it would take an exceedingly long time in practice, would be to go back to the roots. Development of GNU began in 1984, and the original version of Minix (which was used during early Linux development for bootstrapping purposes) was released in 1987.

This entire answer is based on your premise that "[you] or others have the ability to read and understand source code for security flaws, so source code will be vetted first before compiling", and that you can trust the outcome of such an analysis. Without that, this answer is probably worse than worthless, as you will be spending a huge amount of time for absolutely no benefit whatsoever.

If you can find a copy of the original Minix book with source code, you can type it in from the book. Compile it, and then use a different decompiler on a different system to verify that the compiler generates the expected machine language binary output. (The code is only 12,000 lines, presumably C, so doing so is time-consuming but still within reason if you are serious about such a project.) You could even write your own disassembler; that shouldn't be very difficult.

Grab the oldest versions of the GNU utilities you can possibly get your hands on (as those presumably have less code and less dependencies to external libraries), go through the code, build it for Minix (this might take some work, though; what you absolutely want to avoid is to make adjustments to the source code, because that will make adding patches later very error-prone) and go through a similar disassemble-verify cycle for the GNU tools. At that point you trust the OS and toolchain, so you only need to go through the source code in the patchset (anything not in the patchset is already trusted), but the tools will still be very primitive and crude compared to what you are used to today. Don't expect anything more than the very most basic functionality of the system tools to be working, for example. Now transfer everything to and migrate to Minix and start applying patches, one version at a time, rebuilding everything affected between each version and using the new version the next time around. Read lots of XKCD.

At some point, you will have a system that can compile and bootstrap an early version of the Linux kernel, much like it was done in the early 1990s as Linux started to gain traction among hackers. I'd suggest migrating to Linux at that point (rebuild the system libraries and toolchain against Linux, build the Linux kernel, boot into Linux and possibly rebuild the Linux kernel and GNU toolchain within Linux; the last proves that the system is now self-hosting), but that's largely up to you. Keep verifying patches, patching the kernel, libraries and basic GNU tools, and rebuilding until you get to modern versions.

That's when you have a trusted basic OS and compiler which can be used to build modern software. By then, you can follow e.g. the Linux From Scratch guides to build a system capable of performing useful tasks.

At no point can the "compiler" system ever be connected to a network in any way (including as a VM on a networked host); you'd risk penetration through any network-capable component including the kernel. If you're worried about a Thompson compiler attack, you'd have to expect that any VM host also may be compromised. Use sneakernet to get source code to and binaries from the physical host you are compiling things on. Expect trouble getting files on and off the system at least before you get to the point where USB mass storage support was implemented. If you are really paranoid, print source code listings and type them in by hand (and hope that the printer driver and printer don't have similar code in them), or read code on one computer monitor and type it into another computer physically next to but not connected to it.

Yes, this will take a lot of time. But the advantage to this approach is that each step is incremental, meaning that it would be much harder for anything malicious to slip through unless it is very gradually introduced over a period of many versions; this because the set of changes at each step is comparatively small and thus much easier to look over. Compare the patchset with the changelog and make sure you can determine exactly which changelog entry corresponds to every change in the source code. Again, this does assume that you have the ability (possibly through someone you trust) to verify that such changes haven't been sneaked into the codebase, but it should get you about as close to a trusted system as a software-only except-firmware approach can.

Answer 3

If you need a trusted compiler, you could get a look at academic work, like the compcert project. It's a compiler built by the INRIA (a French IT public laboratory) designed to be ''certified'', i.e. to produce an executable semantically perfectly equivalent to the code (and of course, it has been mathematically proven).

Answer 4

While manually creating your own compiler as a starting point would be the most secure, another option is to install a system from a 5 (or 10) year old install CD that you trust was created before these exploits existed. Then use that as a foundation to compile the new audited source from.