Countering Trusting Trust through Diverse Double-Compiling, ACSAC 2005
Something new: I have a section about my work to counter the “Trusting Trust” computer security attack. The “Trusting Trust” attack is a very old and incredibly nasty attack in computer security. Karger and Schell published information about this attack in 1974, and Ken Thompson (of Unix fame) made it much more widely known in 1984 in his Turing award speech “Reflections on Trusting Trust.” Ken Thompson even demonstrated it; he gained complete control over another system, and that system’s owners never detected the subversion. Up to now it’s been presumed that the “Trusting Trust” attack is the essential uncounterable attack.
What exactly is the trusting trust attack? Basically, if an attacker can get a Trojan Horse into the binary of a compiler, at any time, you’re essentially doomed. The subverted compiler can subvert itself, indefinitely into the future, as well as anything else it compiles.
I’ve worried about this attack for a long time, essentially since Thompson made his report. If there’s a known attack that cannot be effectively countered, even in theory, should we really be using computers at all? My hope is that my work in this areas aids the computer security field writ large.
The reason I note this in my blog is that I’ve finally formally published my paper that describes a technique for countering this attack. The paper is Countering Trusting Trust through Diverse Double-Compiling (DDC), and it was published by ACSAC 2005. Here’s a local copy, along with more info and material. Here’s the abstract of that paper:
An Air Force evaluation of Multics, and Ken Thompson’s famous Turing award lecture “Reflections on Trusting Trust,” showed that compilers can be subverted to insert malicious Trojan horses into critical software, including themselves. If this attack goes undetected, even complete analysis of a system’s source code will not find the malicious code that is running, and methods for detecting this particular attack are not widely known. This paper describes a practical technique, termed diverse double-compiling (DDC), that detects this attack and some compiler defects as well. Simply recompile the source code twice: once with a second (trusted) compiler, and again using the result of the first compilation. If the result is bit-for-bit identical with the untrusted binary, then the source code accurately represents the binary. This technique has been mentioned informally, but its issues and ramifications have not been identified or discussed in a peer-reviewed work, nor has a public demonstration been made. This paper describes the technique, justifies it, describes how to overcome practical challenges, and demonstrates it.
I just got back from the ACSAC 2005 computer security conference. Several interesting papers there, on a variety of topics.
An aside: At ACSAC 2005, Aleks Kissinger (from the University of Tulsa) also presented work that he and I had done on micro-tainting. This was the presentation “Fine-Grained Taint Analysis using Regular Expressions,” which was part of the Works in Progress. Basically, we noted that instead of assigning “taint” to a whole value, such as a string, you could assign taint on subcomponents, such as each character. Then you could assign rules that identified the input paths and what could come in — typically zero or more tainted characters — and rules on output paths. We concentrated on defining regular expressions for what is legal, though any other expression for patterns such as BNFs would be fine too. We noted that you could then check statically or dynamically. For the static case, when you work backwards, if the check “fails” you can even trivially derive the input patterns that cause security failures (and from that information it should be easy to figure out how to fix it). Aleks has recently made some good progress by transforming the regular expressions into DFAs. There was another ACSAC presentation on doing taint analysis with Java, but this was the traditional “whole variable” approach that is used in many languages, but through which many vulnerabilities slip by. We hope this micro-tainting approach will lead to improved tools for detecting security vulnerabilities in software, before that software is delivered to end-users.
path: /security | Current Weblog | permanent link to this entry