jet

██████╗  ██████╗ ██╗  ██╗ █████╗ 
╚════██╗██╔═══██╗██║  ██║██╔══██╗
 █████╔╝██║   ██║███████║███████║
 ╚═══██╗██║   ██║██╔══██║██╔══██║
██████╔╝╚██████╔╝██║  ██║██║  ██║
╚═════╝  ╚═════╝ ╚═╝  ╚═╝╚═╝  ╚═╝

Welcome to 3OHA, a place for random notes, thoughts, and factoids that I want to share or remember

3OHA

2 October 2022

The origins of the trusting trust attack

When Ken Thompson was awarded the 1983 Turing Prize, he gave an acceptance speech titled "Reflections on Trusting Trust" that has become extraordinarily influential in computer security. In it, Thompson describes how a compiler can insert a backdoor in an otherwise benign program during its compilation. He illustrates the idea using the UNIX login program, which the malicious compiler trojanizes by making it accept either the intended user password or a known password. This would allow the attacker to log into the system as any user.

The moral of the story is that source code auditing is of limited use when it comes to detecting security bugs; or, in Thompson's words, "you can't trust code that you did not totally create yourself." There could be a semantic difference—with important security implications—between the source code of a program and its executable form because you trust the compiler will do its job and not behave maliciously. Yet this might not be true. In fact, the fundamental idea of the "trusting trust attack" goes beyond the compiler example and can be applied to any other dependency you have in a computing system, including not only third-party code but also core system or hardware components that can be trojanized.

Contrary to popular belief, Thompson never claimed originality for this idea. In fact, he was so honest as to write an acknowledgment paragraph in his award lecture that makes this explicit:

"I first read about the possibility of such a Trojan horse in an Air Force critique [4] of the security of an early implementation of Multics. I cannot find a more specific reference to this document. I would appreciate it if anyone who can supply this reference would let me know."

I don't know if anyone ever pointed Thompson to the reference, but the document he was referring to is:

Karger, Paul A., and Schell, Roger R. Multics Security Evaluation: Vulnerability Analysis. ESD-TR-74-193, Vol. II. pp. 51-52. June 1974.

In it, Karger and Schell provided the first characterization of the problem of a trojanized compiler inserting malicious code—"trap doors" is the term they use:

The compiler (or assembler) trap door is inserted to permit object code trap doors to survive even a complete recompilation of the entire system. In Multics, most of the ring 0 supervisor is written in PL/I. A penetrator could insert a trap door in the PL/I compiler to note when it is compiling a ring 0 module. Then the compiler would insert an object code trap door in the ring 0 module without listing the code in the listing. Since the PL/I compiler is itself written in PL/I, the trap door can maintain itself, even when the compiler is recompiled.

The original paper is available here. It was also reprinted in the Proceedings of ACSAC 2002. The trap door insertion attack is described in Section 3.4.5.

Thompson's speech widely publicized this problem. In fact, he actually implemented the attack in the C compiler, installed it in a machine of the UNIX Support Group at Bell Labs, and successfully trojanized the login command. He assured that the malicious compiler was never released outside Bell Labs.