Ken Thompson's famous trusting trust paper describes an attack wherein a compiler is subverted, and subsequently subverts all software it compiles, including itself. I have always thought the idea of the trusting trust attack is somewhat facile due to being impossible to pull off in its unrestricted form. Clearly, a trusting trust virus would need to be capable of analyzing arbitrary software in order to determine its purpose, and then inserting itself into said software in a way that maintains its functionality. This clearly violates Rice's theorem.

You might ponder a more restricted form, where some kind of heuristic is used to guess if the software being compiled is an OS kernel or a compiler, or a piece of forensic software. It seems to me that even under this restriction the problem is still extremely difficult, except for the case of nearly trivial heuristics. For example, you might imagine an attack on GCC that can infect any program that "looks" like GCC.

With such a restriction in place, this attack doesn't seem nearly as appetizing. I hypothesize that trusting trust attacks are of so little value that they are not worth spending time attempting to counter. To validate or disprove my hypothesis, my question is have there been any practical examples of a restricted form of the trusting trust attack occurring outside a controlled setting?

  • Ken Thompson's trusting trust paper did not describe a compiler capable of analyzing arbitrary software. The hypothetical compromised compiler supplanted exactly two cases: compiling the compiler itself, and one helper function in the OS responsible for password checking. Thus "subsequently subverts all software it compiles" is simply an incorrect claim. The only effect on "all software" is that none of it can be trusted, because you the victim don't know which subroutines the compiler is looking for and compromising.
    – Ben Voigt
    May 30 at 21:47


You must log in to answer this question.

Browse other questions tagged .