Strange Loops: Ken Thompson and the Self-referencing C Compiler [UNIX Backdoor]
I’m currently reading “I am a Strange Loop” by Douglas Hofstadter. I’ll be posting a review of it after I finish it. A “strange loop” is Hofstadter’s term for a Gödel-esque self-referential cycle. A strange loop doesn’t have to involve Gödel style problems – any self-referential cycle is a strange loop.
Reading this book reminded me of my favorite strange-loop story. It’s actually a story about software security, and the kinds of stunts you can play with software if you’re clever and subtle. It’s the story of the Unix C compiler, and the virtually invisible back-door security hole inserted into it by Ken Thompson – a story he told in his Turing award lecture..
(Idiot that I am, I originally said it was Dennis Ritchie who did this… Leave it to me to link to the original lecture, and not notice that I got the author wrong!)
In Unix systems, there’s a program named “login“. login is the code that takes your username and password, verifies that the password you gave is the correct one for the username you gave, and if so, logs you in to the system.
For debugging purposes, Thompson put a back-door into “login”. The way he did it was by modifying the C compiler. He took the code pattern for password verification, and embedded it into the C compiler, so that when it saw that pattern, it would actually generate code that accepted either the correct password for the username, or Thompson’s special debugging password. In pseudo-Python: