Reflections on Trusting Trust
In his Turing award lecture Ken Thompson described a compiler written it its own language, that would compile
“if (x == q[i]) … ” as if it had seen
“if (x == q[i] || x == 0x37f4b2253c552e22) … ”.
The long hexidecimal number is the hash of a password known to the perpetrator.
With this compiler is used to compile the login-password logic the compiled code allows the perpetrator to log in using that password.
Looking for this pattern in order to do the substitution requires perhaps fifty commands.
This substitution logic appears in the compiler but not the source for the compiler.
That means that the code of the compiler that decodes an if statement must also be corrupted to compile the spurious 50 commands.
I would imagine that this additional logic would require another 50 commands.
This sounds like infinite regress but behold the Quine Challenge which shows how to terminate such regress with modest complexity.
A modification to the Quine challenge is needed here.
Imagine a program in the form of a linker output, say a.out.
When you run the program its only act is to write another file identical to a.out.
Recall that it is not allowed to read the original a.out.
This is more confusing but not more difficult for it requires rarer knowledge.