The dark twin of the "loop" and "seed" we celebrated in the main series ── can you trust the seed?
In the main series, we spoke of the self-hosting loop (Episode 5) and the hand-carved seed (Episode 9) as, in effect, hope. Software makes software, and humans lift it up only that one first time ── a beautiful story. But the same structure has a chilling flip side. What if the seed were poisoned? This is exactly what Ken Thompson, the very person who wrote the first Unix, showed in his 1984 Turing Award lecture "Reflections on Trusting Trust" ── the contamination survives forever, hidden in the loop. And no matter how much you read the source, you'll never find it.
Thompson's lecture begins with a single question ── "How far can you trust a claim that a program contains no Trojan horse (malicious mechanism)?" Ordinarily we think, "read all the source, and if there's no malice, you can trust it." He brilliantly demolished that common sense.
Thompson's construction is in three stages. We'll look at them in order.
1. Self-reproduction (a program that outputs its own source)
First, show that it's possible to write "a program that outputs its own source code" (a quine). Groundwork for the idea that a program can "know" itself and reproduce itself.
2. Plant a backdoor in login
Modify the C compiler so that when it notices it is compiling login, it quietly adds a back door that lets a magic password through. ── But this leaves evidence in the compiler's source.
3. Make the compiler "recognize" itself too, and erase the evidence
Modify it further so that when the compiler notices it is "compiling itself (the C compiler)," it quietly reinjects both the backdoor code from step 2 and this recognition code from step 3. Then erase all the malice from the compiler's source. Compile once with the poisoned version ── and from then on, even though the source is completely clean, the binary keeps carrying the Trojan.
Here's the crux. The source is clean. Whoever reads it, they find no malice. But as long as you build that clean source with a compiler that is a descendant of the poisoned binary, the binary that emerges is poisoned. And the new binary inherits the ability to "reinject when it compiles itself." In the figure below, advance the generations and watch how the source audit passes every time, yet the poison never disappears.
The self-hosting loop we celebrated in Episode 5, and the seed we carved in Episode 9. That very same structure is what makes this attack possible. If the loop turns by using "the previous self" as its foothold, then the poison planted in the previous self is inherited too, unchanged. The source stays clean across generations, while only the poison survives, passed down the binary's lineage. Hope (self-reproduction) and threat (self-reproducing poison) were two sides of the same coin.
If "read the source and you're safe" has collapsed, then what? The thing that compiles the source is the compiler (a binary). The thing that made that binary was another compiler. The thing that made that was… and so trust, too, recedes just like the chain of compilation. And as we saw in the main series, that chain eventually reaches something you didn't make yourself ── someone's binary, a tool, and the hardware of Episode 10. In the figure below, descend that "recession of trust."
This lecture is often received pessimistically as "so nothing can be trusted." But this series takes a slightly more forward-looking stance. Just as the hope side of the chicken and egg (the main series) had a modern answer, this threat side, too, has modern technology to counter it ── shrink the "seed" you must trust to the absolute minimum, and make it verifiable. In the next installment, Bonus 2, "Bootstrappable Builds," we'll see the specifics. Even Thompson's poison was later shown to be, in principle, detectable (by diverse double-compiling).
(1) This is a classic for understanding supply-chain trust, not a how-to for attacks. The point is a defender's lesson: "a source audit alone doesn't reach the bottom of trust." (2) Thompson later admitted he actually built a working version of this mechanism, but it was not widely distributed. The lecture is a "real threat model" that sits between a thought experiment and an implementation.
(3) Modern compilers are huge, and the simple attack exactly as in the lecture won't go through as-is. But the principle is alive, and appears in altered form as real supply-chain attacks. (4) The countermeasures (Diverse Double-Compiling and reproducible builds, in Bonus 2) are powerful but not a cure-all; trust in the very bottom layer (hardware/microcode ── below Episode 10) remains a separate problem.
Ken Thompson, who wrote the first Unix, asked in his 1984 Turing Award lecture ── "How far can you trust that a program contains no Trojan?" His three-stage trick (1. self-reproduction; 2. a backdoor in login; 3. recognizing the compiler itself and reinjecting the backdoor and the recognition code, while erasing the evidence from the source) showed that even from clean source, a Trojan survives as long as you build with a descendant of a poisoned binary. The source audit passes every generation, yet the poison never disappears.
This is the dark twin of the self-hosting loop and the seed we celebrated in the main series ── a loop that uses the previous self as its foothold inherits the previous self's poison too. Trust also recedes just like the chain of compilation, and finally hits bottom at "something you didn't make yourself" (a binary, a tool, the hardware of Episode 10). The lesson is "you can't trust code you didn't completely create yourself." But it isn't despair ── there is a path to minimize and verify the seed you trust. Next time, on to that modern answer.
Print / Save as PDF: ⌘+P (Ctrl+P on Windows). On screen, use the slider in Figure 1 for the Trojan's generational propagation (the source audit passes every time, the poison stays), and Figure 2 to follow the recession of trust. Click "See the answer" to open each solution.