Reflections on Trusting Trust

Abstract

In October 1983 Ken Thompson accepted the Turing Award, shared with Dennis Ritchie for Unix, and declined to talk about Unix. Instead he described “the cutest program I ever wrote”: a C compiler that inserted a backdoor into the Unix login command and reinserted itself whenever it compiled a new compiler, so that no trace remained in any source code. The lecture, published in Communications of the ACM in August 1984, is three pages long and became the standard statement of the problem that source code proves nothing about a binary built by tools nobody has checked. The idea came from a 1974 Air Force evaluation of Multics by Paul Karger and Roger Schell. Thompson had built it at Bell Labs around 1975, and in 2023 he gave the original code to Russ Cox. The answer that the field settled on, David A. Wheeler’s diverse double-compiling, came in 2005.

Three Stages

Thompson opened by thanking the ACM and saying he was receiving the honour “for timing and serendipity as much as technical merit.” Then: “I am a programmer. On my 1040 form, that is what I put down as my occupation.” He presented the program in three stages.

The first stage was a college game. Students amused themselves by writing the shortest program that prints an exact copy of its own source, later called a quine. Thompson showed one in C and noted two properties he needed: such a program can be written by another program, and it can carry “an arbitrary amount of excess baggage” that is reproduced along with it.

The second stage was a property of compilers that compile themselves. The C compiler was written in C, and the code that translated the escape sequence \n into a newline character said, in effect, “the newline is the newline”: the knowledge of which number it was lived only in the binary of the compiler that compiled it. To teach the compiler a new escape, \v for vertical tab, one first had to write the number 11 explicitly, compile, install the result, and only then could the source say \v in the portable way. “It is as close to a ’learning’ program as I have seen,” Thompson said.

The third stage combined the two. A modified compiler recognised the source of login and miscompiled it to accept a known password for any user. A compiler that did this would be found by anyone reading its source, so a second pattern recognised the C compiler itself and inserted both modifications, using the self-reproduction trick of stage one, into the new binary. Compile the modified source once, install the binary as the official compiler, and then restore the clean source. Every compiler built from the clean source would carry the backdoor, and every login built with it would accept the password, “with no trace in source anywhere.”

“The moral is obvious,” he concluded. “You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.)” He had picked the C compiler, but any program that handles programs would do, an assembler, a loader, or hardware microcode, and “a well installed microcode bug will be almost impossible to detect.”

The Unknown Air Force Document

In the acknowledgement Thompson wrote that he had first read of such a Trojan horse “in an Air Force critique of the security of an early implementation of Multics,” and asked readers who could supply the reference to let him know. His reference list gave it as “Unknown Air Force Document.”

The document was the Multics Security Evaluation: Vulnerability Analysis (ESD-TR-74-193, June 1974) by Paul Karger and Roger Schell, written after an authorised penetration test of the system the Air Force planned to run at the Pentagon (see The Multics Story). The trap doors they planted were patches to binary object files. The report noted that customers could defend against this by recompiling the system from source, and that this might help an attacker who had changed the source. It then pointed out that a trap door in the PL/I compiler could insert trap doors into Multics modules as they were compiled and preserve itself by recognising when the compiler was compiling itself. Karger and Schell wrote in 2002 that they gave Thompson a copy of the report after the lecture was published, and that he corrected the citation in a reprint of the lecture in Unix Review in November 1989. The same passage of their report was the basis for the requirement in the Orange Book’s highest class, A1, that new system versions be generated from source with a compiler kept under strict configuration control.

It Was Real

Readers long asked whether Thompson had only described the attack or had built it. In a question-and-answer session in March 2023 he said he still had the code, and in September 2023 the Go developer Russ Cox asked him for it. Thompson sent a file named nih.a, for “not invented here.” Cox published an analysis on 25 October 2023, forty years after the lecture.

The backdoor was written for the C compiler of Sixth Edition Research Unix, probably in early 1975: 99 lines of code and a 20-line shell script. It grew the compiler binary from 10,724 to 12,918 bytes and made login accept the password “codenih” for an existing account such as root. Cox cited John Mashey’s account that the Programmer’s Workbench group at Bell Labs was induced to install the modified compiler, a few weeks after Mashey had read John Brunner’s novel The Shockwave Rider, published in early 1975. The PWB group noticed something: a bug made the compiler add one byte to a string each time it compiled itself, so the binary grew with every generation. They broke the reproduction and ended up with a clean compiler. The Jargon File’s story that the compiler escaped to BBN is, according to Thompson, false. The archive was not lost: in 1997 Dennis Ritchie gave the Unix historian Warren Toomey a set of tapes that included nih.a, dated 3 July 1975, and the tapes were posted in July 2023.

Diverse Double-Compiling

For two decades the attack was cited as unanswerable. The usual counsel, write your own compiler in machine code, did not scale, and Thompson’s point about loaders and microcode made it worse.

David A. Wheeler proposed a practical test at the Annual Computer Security Applications Conference in December 2005, “Countering Trusting Trust through Diverse Double-Compiling,” and extended it in his PhD dissertation at George Mason University, defended on 23 November 2009. The method compiles the source of the suspect compiler twice. First it is compiled with a second, independent compiler that one has some reason to trust. The result is then used to compile the same source again. If the output is bit-for-bit identical to the suspect compiler’s own executable, the executable corresponds to its source. A Thompson-style Trojan in the suspect binary would have to be present in the independent compiler too, in compatible form, to survive the test. Wheeler demonstrated it on four compilers, including GCC, and gave a formal proof. The test does not show that the source is free of malice, only that the binary is what the source says.

The method depends on compilers that produce identical output from identical input, which most did not. The reproducible-builds movement of the 2010s removed timestamps, file paths and other accidental inputs from builds, first in Bitcoin and Tor, then across Debian (see Software Supply Chain Security). A second line of work attacked the root of the chain. The bootstrappable-builds projects, among them Jeremiah Orians’s stage0 and Janneke Nieuwenhuizen’s GNU Mes, set out to build a full compiler toolchain from a seed small enough to read. On 26 April 2023 the GNU Guix distribution announced a full-source bootstrap for x86 Linux: a package graph of more than 22,000 packages rooted in a 357-byte binary, hex0, whose source is a commented hexadecimal file, built upward through a series of slightly larger tools to a C compiler and then to GCC. The build was still driven by a prebuilt Guile binary, which the developers listed as the next thing to remove.

The Other Half of the Lecture

The last part of the lecture is rarely quoted. “After trying to convince you that I cannot be trusted, I wish to moralize,” Thompson said, and criticised the press for its treatment of “the ‘hackers,’ the 414 gang, the Dalton gang,” whose acts were “vandalism at best and probably trespass and theft at worst.” The press, he said, made heroes of vandals by calling them whiz kids, while their acts “will soon be punishable by years in prison.” He had watched teenagers testify before Congress and concluded that they did not understand what they had done. “The act of breaking into a computer system has to have the same social stigma as breaking into a neighbor’s house. It should not matter that the neighbor’s door is unlocked.” The Milwaukee teenagers he meant had made the cover of Newsweek that year (see The 414s).

So the most famous security paper of its decade asked two things of its audience: that they distrust the programmers who had just been honoured, Thompson included, and that they stop admiring the teenagers who broke into systems. Only the first request entered the textbooks.