As Irreal oldtimers know, My absolute favorite Computer Science paper is Ken Thompson’s Reflections on Trusting Trust. It is truly a thing of beauty. This is a beauty that should be appreciated in stages.
In the first stage, we’re introduced to, as the Jargon File puts it, a truly moby hack perpetrated by Thompson. He changed the C compiler to recognize when the login function was being compiled and insert a backdoor that would allow anyone knowing a special password to login. There’s nothing special about that, of course but the clever part was that he also changed the compiler to recognize when it was compiling itself and to insert the code that generated the back door. He used that compiler to compile a version of the compiler without the changes. Now he had a compiler that would insert the backdoor and replicate the code to insert the back door if the compiler itself was recompiled. But the compiler sources no longer showed any signs of this.
The second stage is understanding how this was done. It turns out to be pretty simple. Thompson worked at the source level by changing the C preprocessor so that he could work at the source level of the code being compiled. The login backdoor insertion code simply looked for some specific code that called crypt and installed the book door there.
The really clever part was installing the code to replicate the backdoor insertion code in a new compiler. Keep in mind that the source for that was no longer present in the C compiler source. Think, for a moment how you would do that. Remember, you’re working at the source level. The answer has to do with quines.
Back in 2023, Russ Cox asked Thompson if he still had a copy of the code for the hack. Thompson did and he sent it to Cox who wrote an excellent exegesis of it. I wrote about his explanation here. Now Micah Kepe has revisited that code and provided his own explanation of it. Take a look at the explanation and try to understand it. You’ll have to bear down but once you understand the details, a whole new world of understanding will be open to you.
The final stage of appreciation is realizing that it’s really hard to be sure your computing environment is secure. Even if you’re paranoid or use a distribution like Gentoo in which you compile everything by default, you still can’t be sure someone hasn’t slipped in a backdoor. There are, of course, ways of mitigating Thompson’s type of attack but who knows what else is out there?