Every year or so I revisit and write about Ken Thompson’s 1983 Turing Award lecture, Reflections on Trusting Trust. It’s one of those papers that should be read every year: it seems there’s always something new to learn. The paper is only 3 pages and—unlike the usual academic paper—very easy for any programmer to read.
The TL;DR is that Thompson modified the Unix C compiler so that when it compiled the login module it inserted code to accept a special password for any login. That may seem mundane but Thompson’s hack went one step further: he also modified the compiler to insert code to insert the login backdoor when the compiler itself was being compiled. He then recompiled the compiler, removed all the backdoor code from the compiler source, and recompiled it again with the backdoored compiler. From that point on the compiler would create backdoors for login and for the compiler but with no trace in the compiler source.
Thompson says only that the code he added recognized when login or the compiler was being compiled but offered no details. I’ve often wondered about the details and assumed he used the file name (login.c or cc.c) to decide which code to modify. It turns out that Thompson kept that code and recently Russ Cox obtained it and wrote a post with a complete exegesis of the code and how it worked.
The frightening thing is how simple it was. It operated on the source code and merely looked for the code it wanted to modify. When it found it, it simply inserted the back door code into the source and let the compiler compile it as normal.
The really clever part was how he inserted the backdoor code (that the binary was executing) back into the compiler. That explains his otherwise unexplained mention of what we now call quines in his paper.
Just about everybody in our field recognizes that Thompson is a programming genius and his Turning paper proves the accolades are deserved. Cox’s explanation of how the whole thing worked will leave you even more convinced. Believe me, you really, really want to read Thompson’s paper and Cox’s explanation of the exploit code.