64

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:

|improve this question
  • 7
    Damn, this is a very interesting question and I don't want to migrate it but I don't really think it is on topic here. It is better suited to stackoverflow.com since your basic question is about how to compile a compiler from scratch which is pretty much OS agnostic and very much a programming question. If you don't get an answer here after a while consider using the "flag" link under your question's tags and asking a moderator to move this to SO. – terdon♦ Sep 9 '13 at 5:02
  • 2
    @terdon It might actually be a better fit for Programmers.SE since it is more about general programming issues than a specific development problem. In fact, it might be a duplicate there. – a CVn Sep 9 '13 at 8:07
  • 2
    GCC is open source, how any backdoor would be inserted? – Michael Pankov Sep 9 '13 at 11:21
  • 2
    Bear in mind that the stable Thompson exploit requires code that can recognize when the login program or the compiler is being compiled. If you can manually transform the source into a form that isn't recognizable to the compiler as one of those programs, the backdoor won't be propagated. – Russell Borogove Sep 9 '13 at 18:27
  • 2
    @Constantius -- read the Thompson article linked in the first line. Who compiles the compiler? – Russell Borogove Sep 9 '13 at 18:28
30

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.

|improve this answer
  • 13
    Even so, this still only protects against a malicious compiler. You still need to trust the system the compiler executes on. No software exists in isolation. – a CVn Sep 9 '13 at 8:04
  • 3
    Anything autonomous is inherently dangerous. You are effectively proposing a toolchain compiler (albeit a weird one) which means it can probably be modified in exactly the way you're trying to avoid. Even better, it could be modified in transit via MitM. – strugee Sep 9 '13 at 9:18
  • 1
    You guys have to realize that this answer is coming from a 15 year old. Keep going strugee! – mtahmed May 28 '14 at 18:24
  • 3
    One should not forget to also write a code editor from scratch - who knows if your precompiled <code>vim</code> or the <code>vim</code> you compile with your good compiler from source you have audited only using infected <code>vim</code> is trustworthy? – Hagen von Eitzen Jul 9 '14 at 15:27
  • 1
    Never forget, that unless you personally wrote that first machine code (not assembly. actual machine code), and you are an expert in recognizing underhanded security holes, and read and checked every single line of code you’re compiling… or at least know the person who did that personally, and trust him to do this…. none of this will help at all. That’s why trying to Kickstarter this, is ruining the whole point. Which is: High trustworthiness. – Evi1M4chine Jan 26 '16 at 14:02
22

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.

|improve this answer
  • The dissassemble-verify method is very flawed, as it still makes the huge assumption, that the verification machine is fully trustworthy. Unless you built that machine and its software from scratch, or know the person who did personally and trust her, this is not going to happen. So this is still insecure. Sorry. …… Also, in these matters “as close to …” still means “insecure”, as it only requires one single untrustworthy spot to ruin the whole point. – Evi1M4chine Jan 26 '16 at 14:07
9

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).

|improve this answer
  • 1
    Everyone needs a trusted compiler. How does the maths work that they can produce a "trusted" compiler? – David J Sep 9 '13 at 9:15
  • @DavidJ Bootstrapping, most likely. Build some tiny piece that you can completely verify and prove correct, then use it as a foundation to build more complex compilers. – a CVn Sep 9 '13 at 9:31
  • 1
    """What sets CompCert C apart from any other production compiler, is that it is formally verified, using machine-assisted mathematical proofs, to be exempt from miscompilation issues.""" compcert.inria.fr/compcert-C.html Compilation is not as empirical as it used to be. – lgeorget Sep 9 '13 at 10:27
  • 1
    @MichaelKjörling that probably doesn't take into account that the kernel may be compromised to include a backdoor into the compiler source when read by a compiler – ratchet freak Sep 9 '13 at 14:09
  • I also found this link which could work too. – David J Sep 21 '13 at 1:33
2

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.

|improve this answer
  • 5
    The attack has been publicly known since 1984. Presumably Thompson wasn't the first to think about the possibility. Going back that far means that most of the things we take for granted today weren't around; consider what computers were capable of doing 20 years ago and compare it to their current state. Even the original Linux bootstrap system Minix was not released until '87, and development of GNU began in '84. So while in theory this may answer the question, in practice it's largely useless as an answer. – a CVn Sep 9 '13 at 8:34
  • 2
    The earliest computer I could potentially get my hands on would be a 286. I'll have to see if my grandparents still have it. – David J Sep 9 '13 at 9:18
  • 1
    Bonus points for actually considering that :-). @DavidJ – 11684 Sep 9 '13 at 18:58
  • @MichaelKjörling: Not really; since it only makes your chain of bootstrapping longer. But maybe not as long as writing your own compiler from scratch in machine language. – Evi1M4chine Jan 26 '16 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.