Reflections on Trusting Trust and Diverse Double-Compilation approach

By Mina Fahim

Get Mina Fahim’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Ken Thompson’s “Reflections on Trusting Trust” (1984) introduced a concept that challenges our assumptions about software trustworthiness: the idea of a backdoor in the compiler. This backdoor can be used to compromise an operating system’s security, even if the operating system’s source code is entirely trustworthy.*

How the “Reflections on Trusting Trust” Backdoor Works

Thompson demonstrated that a compiler could be modified to inject malicious code into the binaries it generates without any visible trace in the source code. This type of attack is now known as the “Trusting Trust” attack. Here’s how it works

• Thompson starts with the concept of self-reproducing programs, which are capable of outputting their source code when compiled and executed. He then moves to the idea of modifying a C compiler to introduce a Trojan horse, a deliberate backdoor, into another program, such as the UNIX login command. This Trojan horse could, for instance, allow a specific user to log in without a password. The real ingenuity of Thompson’s backdoor is that it doesn’t stop at modifying one program. He demonstrates that the compiler itself could be programmed to recognize when it is compiling its source code and reintroduce the same malicious changes. In this scenario, even if the source code of the compiler is examined and found to be clean, the compiled version of the compiler still contains the backdoor. The malicious behavior is perpetuated without any visible changes to the source code, making the backdoor almost impossible to detect through conventional means (Thompson 763).
• In essence, this recursive embedding means that unless every stage of software bootstrapping (starting from the earliest compilers built in machine code) is entirely trusted and verified, the backdoor can persist indefinitely. Thompson concludes that “you can’t trust code that you did not totally create yourself,” (Thompson 763) emphasizing the challenge of ensuring software security in the presence of such deeply embedded and low-level threats.

Countering the Trusting Trust Attack with Diverse Double-Compilation (DDC)

The difficulty of detecting Thompson’s backdoor lies in the circular trust between the source code and the compiler. To address this, David A. Wheeler proposed a technique called Diverse Double-Compilation (DDC) in his 2009 work, “Fully Countering Trusting Trust through Diverse Double-Compiling”(David A. Wheeler).

• The DDC method requires compiling the compiler-under-test using two different compilers: one potentially untrusted compiler (the one being tested for a backdoor) and a different, trusted compiler. The idea is that the same source code compiled by both compilers should produce binaries that behave identically. If they do not, this discrepancy suggests the presence of a backdoor in the compiler-under-test.
• In practice, DDC involves three steps, which involve 2 stages:
  1. Compile the compiler source code using both the untrusted and trusted compilers to generate two different stage-1 compiler binaries.
  2. Use each of these stage-1 binaries to compile the compiler source code again, producing two stage-2 binaries.
  3. Compare the outputs of these two stage-2 compilers. If they are identical, it indicates that the compiler source code is trustworthy, and the untrusted compiler did not contain a backdoor (David A. Wheeler)
• Wheeler shows that if the stage-2 compilers are identical, the executable and the source code of the compiler-under-test correspond accurately. This method effectively breaks the infinite loop of trust described by Thompson by verifying that no hidden instructions are added by the compiler during the compilation process. (David A. Wheeler).

References

Thompson, Ken. “Reflections on Trusting Trust.” Communications of the ACM, vol. 27, no. 8, Aug. 1984, pp. 761–763.

Wheeler, David A. Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) — Countering Trojan Horse Attacks on Compilers. George Mason University, Dec. 2009.

Backdoor (Computing).” Wikipedia, The Free Encyclopedia, 2 Sept. 2024, en.wikipedia.org/wiki/Backdoor_(computing).