Thompson's Trojan Compiler

Question

I'm trying to grasp a better understanding of Thompson's Trojan Compiler (discussed in his 1984 ACM Turing Award speech "Reflections On Trusting Trust"), and so far this is how I understand it:

"The original login program for Unix would accept whatever login and password the root instructed it to. It would only accept a certain password, known only by the man who wrote the system. This could let him log in to the system as root."

Is this the right concept? I'm not 100% sure if I understand the whole concept.

If someone could make it clearer, it would help.

(See also Bruce Schneier Countering "Trusting Trust")

Answer 1

Yes, it is the right concept. There's more to it; the modified compiler must also compile the unmodified compiler source to a similarly modified copy of itself. This includes trivial variations of that source, which basically means the modified compiler has to be able to solve e.g. the halting problem.

Answer 2

I had never encountered the concept before, but this is pretty interesting - I found a neat write-up at http://scienceblogs.com/goodmath/2007/04/strange_loops_dennis_ritchie_a.php

Answer 3

The original login program accepts matching pairs of name and password from a file.

The modification is to add a super-powerful password, compiled into the login program, that allows root access. In order to ensure that this code isn't visible when reading the login program, there's a change to the compiler to recognize this section of the login program, i its original form and compile it into the super-powerful password binary. Then, in order to hide the existence of this code in the compiler, there needs to be another change to the compiler that recognizes the section of the compiler that the first change was added to and output the modified form.

Once the changed compiler code exists, you can compile the compiler and install it in the standard place, and then revert the source code for both the login program and the compiler to their unmodified form. The installed compiled compiler will then take the unchanged login program and output the insecure form. Similarly, the installed compiler will compile the unmodified compiler source code into the devious variant. Anyone inspecting the source code for either one will agree that there's nothing unusual in them.

Of course, it only works until the source code for either program evolves far enough that the modified compiler no longer recognizes it. Since the modified compiler's source code is no longer present, it can't be maintained, and (assuming that the compiler and login continue to evolve) it will eventually stop producing the insecure output.