Backdoor (computing) - Reflections On Trusting Trust

Ken Thompson's Reflections on Trusting Trust, his Turing Award acceptance speech in 1984, was the first major paper to describe black box backdoor issues, and points out that trust is relative. It describes a very clever backdoor mechanism based on the fact that people only review source (human-written) code, and not compiled machine code. A program called a compiler is used to create the second from the first, and the compiler is usually trusted to do an honest job.

Thompson's paper describes a modified version of the Unix C compiler that would:

• Put an invisible backdoor in the Unix login command when it noticed that the login program was being compiled, and as a twist
• Also add this feature undetectably to future compiler versions upon their compilation as well.

Because the compiler itself was a compiled program, users would be extremely unlikely to notice the machine code instructions that performed these tasks. (Because of the second task, the compiler's source code would appear "clean".) What's worse, in Thompson's proof of concept implementation, the subverted compiler also subverted the analysis program (the disassembler), so that anyone who examined the binaries in the usual way would not actually see the real code that was running, but something else instead. This version was, officially, never released into the wild. It is believed, however, that a version was distributed to BBN and at least one use of the backdoor was recorded.

This attack was recently (August 2009) discovered by Sophos labs: The W32/Induc-A virus infected the program compiler for Delphi, a Windows programming language. The virus introduced its own code to the compilation of new Delphi programs, allowing it to infect and propagate to many systems, without the knowledge of the software programmer. An attack that propagates by building its own Trojan horse can be especially hard to discover. It is believed that the Induc-A virus had been propagating for at least a year before it was discovered.

Once a system has been compromised with a backdoor or Trojan horse, such as the Trusting Trust compiler, it is very hard for the "rightful" user to regain control of the system. However, several practical weaknesses in the Trusting Trust scheme have been suggested. For example, a sufficiently motivated user could painstakingly review the machine code of the untrusted compiler before using it. As mentioned above, there are ways to hide the Trojan horse, such as subverting the disassembler; but there are ways to counter that defense, too, such as writing your own disassembler from scratch, so the infected compiler won't recognize it. However, such proposals are generally impractical. If a user had a serious concern that the compiler was compromised, they would be better off avoiding using it altogether rather than reviewing the binary in detail using only tools that have been verified to be untainted. A user that did not have serious concerns that the compiler was compromised could not be practically expected to undertake the vast amount of work required.

David A. Wheeler has proposed a counter to this attack using an approach he calls "diverse double-compiling", which uses techniques adapted from compiler bootstrapping. This involves re-compiling the source of the compiler through another independently-written and generated compiler (trusted not to contain the same backdoors), and then using the binary generated from this to recompile the original compiler again, and then comparing the binary generated from this second compilation with that generated from using the original compiler to recompile itself directly. This comparison will tell you that at least one of the compilers has a backdoor (or bug), or that the resultant machine code corresponds to the original compiled code (and the untrusted compiler can be trusted not to contain this kind of vulnerability).