3

I have gone through Ken Thompson's compiler hack paper; can't we just go through the compiler's source code and check for any backdoor, what was the article's point?

Can we be sure that there are no backdoors if we check the language's latest source code like Python or PHP?

6

No, because the source you can see doesn't necessarily match up with the binary you're using. The specific attack described in that paper involves multiple compiler source versions: there is a malicious one, which contains the code to inject backdoors into anything compiled using this compiler, and a clean one, which doesn't contain this code.

The attacker first compiles the malicious version, generating a compiler which inserts a backdoor into any future builds of the compiler. They then compile the clean version, using the malicious compiler. The output of this is now also malicious, even though the source code was clean - the source and binary no longer match up, but checking that is difficult. You would need to reverse engineer the binary, looking for malicious commands. The added complexity here is that if the reverse engineering tools were compiled with a malicious compiler, they could well hide the additional functionality in the binary when used.

So, an option might be to use reverse engineering tools from a completely different machine, compiled with a different version of the compiler. However, it's entirely possible that the different machine's compiler is also malicious, depending on when the original backdoor was made. For example, if they both run the same OS, they may well have the same compiler built in, which is compromised on both devices. If they don't, there may be earlier versions which were bootstrapped from a compromised compiler, or cross-compiled from a different OS which had a compromised compiler.

The only way to be sure that the whole chain is uncompromised is to manually build a binary which the processor can run, then incrementally improve this to allow extra features: you can't rely on any third party software (the text editor might insert malicious code, then hide it from view when you look at the source code, the shell might hide the file sizes of modified source files, etc...). In fact, you can't even rely on third-party hardware - the CPU might backdoor anything that looks like a compiler being built, or the RAM, or the motherboard, or the network adaptor, or any other point on the network where the compiler code or binary passed through...

Now, this is getting a bit paranoid, but in each case, as soon as there is a distinction between what source is written and what actually runs, you can't be 100% sure that the source you see and the binary that runs match up.

Note that this doesn't mean the hack has happened, but suggests that there is no way we could verify if it had without building a computer from scratch and using that to verify everything - from scratch in this case means from raw materials, for absolute certainty, without using anything which could influence the output. A hammer is probably ok, but a CNC device might be malicious, or a fab plant, or those wires, or...

puts on tin-foil hat, then realises it was made by someone else who might be compromised

  • So the issue of not having complete trust would always persist irrespective of the language, right? The paper was published using a lower level language like C, this would persist even on the latest powerful languages like python, isn't it? – user9355495 Feb 6 at 11:58
  • Yep. Applies to interpreted languages too - at some point, there has been a compiler used to make the interpreter. Even applies to things like compcert.inria.fr which try to verify correctness and conformance to the input source. You can't be absolutely sure that the output isn't lying. – Matthew Feb 6 at 12:03
5

can't we just go through the compiler's source code and check for any backdoor, what was the article's point?

The whole point of the article is that can't do that because the backdoor is not in the compiler's source code.

Thompson explains this in various steps:

  1. You put a backdoor in the source code of the login program. Obviously, when you examine the source code of login, you will find this backdoor.
  2. Instead, you put some piece of code into the source code of the compiler, so that when it compiles the login program, it will insert this backdoor. Now, the backdoor does not show up anywhere in the source code of login. Obviously, when you examine the source code of the compiler, you will find this meta-backdoor.
  3. Instead, you put some piece of code into the source code of the compiler that was used to compile the other compiler, so that when it compiles the compiler, it will insert the meta-backdoor which when it compiles the login program, will insert the backdoor. Now, the meta-backdoor will not show up in the source code of the compiler. Again, if you inspect the source code of the bootstrap compiler, you will find this meta-meta-backdoor.
  4. And so on …

BUT!!! Here's the thing: at some point, you will need a compiler that is already compiled so that you can compile your bootstrap compiler so that you can compile your compiler so that you can compile your login program. And you cannot compile this compiler yourself (because you would need another compiler for that), and thus, you cannot ensure that the source code you are inspecting is actually the one that was used to compile the compiler.

And that is the problem: no matter how many intermediate compilers you insert and inspect their source code, there will be one ultimate "first" compiler that you cannot compile yourself and that you must trust.

Later on in the paper, Thompson also explains that the compiler is just an example. Any entity that stores, reads, writes, transforms, manipulates, processes, displays, or in any other way touches code can be compromised in a similar manner.

Instead of the compiler, I could use the dynamic linker, which when it detects the login program running, links it to a version of the C library that always returns true for string equality checks, for example, so that no matter what password I enter, it will let me in. Or, I could modify the memory bus on the motherboard, so that when it detects that the login program is transferred from RAM to the CPU, it modifies the instructions. Or, I could modify the CPU to detect the login program running. I could modify the harddisk's microcontroller, so that when it detects that I am loading the login program from disk, it modifies the program before sending it out over the SATA bus.

Instead of trying to cleverly hide the backdoor by compilation, I could instead also modify your text editor, so that when you inspect the source code of login, it simply does not show you the backdoor. And I can do the same when it displays the source code of the compiler. And the editor itself, of course.

And so on and so forth.

The gist of it is: unless you build your entire computing system from individual wires and switches from scratch, there will be at least one component that you get from somewhere else, that processes code, and the backdoor can be in there.

  • So the issue would always persist irrespective if the language is higher or lower, right? – user9355495 Feb 6 at 11:49
  • 1
    The issue persists as long as you have at least one component that processes code that you haven't built yourself from scratch. I have no idea what a "higher" or "lower" language is. This has absolutely nothing whatsoever to do with languages. – Jörg W Mittag Feb 6 at 11:49
  • The paper was published using a lower level language like C, after reading your answer i feel that this would persist even on the latest powerful languages like python – user9355495 Feb 6 at 11:53
3

A compiler creates a binary from source code. For a normal compiler, the binary is just another representation of the source code, and the behavior of the program is fully specified in the source. However, a malicious compiler can add extra functionality in the binary, functionality that is not present in the source and thus can not be detected by reading the source.

This also applies to the source of the compiler. When compiling the compiler, the malicious compiler adds this malicious functionality to the target binary, and the circle is complete.

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.