What is “Trusting Trust” Attack ?
“Trusting Trust” Attack is a classic scenario of a crippling and uneraseable attack that affects all aspects of a program including its compilers. It is known as “Trusting Trust” because it infects some things that usually we can safely assume not infected and not the source of the infection so it challenges us about what can we trust and what we must take with a grain of salt. This scenario is first brought by Ken Thompson on 1984 in this legendary thesis named “Reflections on Trusting Trust” that wins him a Turing Award. Afterwards, attacks which use similiar method that he suggested is named a “Trusting Trust” attack because it mocks the circular and ambiguous notion of society in trusting and trust and how it can be broke horribly. Never thought a computer science thesis can strike a social issue, eh?
How does “Trusting Trust” Attack works?
In a simple form, to commit this attack we must inject a Trojan Horse that can modify the compiler binary so that whatever program is compiled by the compiler (including and especially important things such as login web page and password check software) it will inject the attacker’s backdoor code in the executable. Usually, as a normal programmer that may notice something strange in his/her program, we will get this around with just recompiling the compiler (desperate need calls for desperate measure. Honestly, i’ve never done it at all. This is just what the scenario says). And so it ended. The compiler is now clean and ready to use. The bad guy’s plan now falls horribly and now we can laugh and teach him an aesop or two about a power of friendship and we can safely take him to the good side. Nope. This will not go this easy.
How’s this for a little twist; Whenever the compiler is itself compiled, it emits the code to insert malicious code into various programs, including itself.
How can we repel this attack ?
One solution for this is published by David A. Wheeler which explains a technique named Diverse Double-Compiling. Here’s Wheeler’s trick.
Wheeler explains how to defeat this more robust attack. Suppose we have two completely independent compilers: A and B. More specifically, we have source code SA of compiler A, and executable code EA and EB. We want to determine if the binary of compiler A – EA – contains this trusting trust attack.
With this all set up, we can do it like this :
-
Step 1: Compile SA with EA, yielding new executable X.
-
Step 2: Compile SA with EB, yielding new executable Y.
Since X and Y were generated by two different compilers, they should have different binary code but be functionally equivalent. So far, so good. Now:
-
Step 3: Compile SA with X, yielding new executable V.
-
Step 4: Compile SA with Y, yielding new executable W.
Since X and Y are functionally equivalent, V and W should be bit-for-bit equivalent.
This method focuses on detecting the attack. On this scenario, the way to detect it is if V and W (the last results of compilng) is NOT bit-for-bit equivalent, it is infected, and vice versa. This method relies (again, “trusting”) on the two compilers is not attacked by the exact same way. If it is, it will yield a same result and once again the dark escapes. It basically a method to safely compare two compilers and see which is wrong by comparing it, praying that one of them is right. At least it’s a little bit assuring you, isn’t it? To really be safe assuming you’re a society-rejecting insane computer scientist over there, in Schenier’s words :
You can write Compiler B yourself for a computer you built yourself from vacuum tubes that you made yourself. Since Compiler B only has to occasionally recompile your “real” compiler, you can impose a lot of restrictions that you would never accept in a typical production-use compiler. And you can periodically check Compiler B’s integrity using every other compiler out there.
DDC technique is a method to independently verify that source code and executable correspond. DDC fully counters the problem that we lacked a practical independent verification process for program-handling programs (like compilers).
Why is this attack so dangerous ?
This attack is beautiful in fulfilling the ultimate reason of any anonymous hacker, damage on the system and damage on the society. Without knowing what compiler can be trusted and what not, this attack can never be thwarted. Using a single most trusted compiler is the easiest solution to clean this but can we trust a single unverifiable compiler? You can draw the connection on yourself between this and society.
But as David A. Wheeler said in his DDC paper, it may not broke our trust in this and society. As he said in his own words :
First, complaining that people trust others is a waste of time. You must trust others in a modern world. No one grows all their own food, builds their own shelters from their own materials, and provides all their other needs by themselves; we all trust others. However, there is a serious systemic problem if you cannot independently verify what you trust. You should strive to “trust, but verify”. I believe the fundamental problem caused by the trusting trust attack was that it was impractical to independently verify that what you depended on (the executable) corresponds to its human-readable representation (the source code). This is because program-handling programs can subvert the relationship between what humans review and what is actually used. Ken Thompson’s paper is not titled “Reflections on trust”; it is “Reflections on trusting trust”. Again, I believe problem was not trust, but the lack of a meaningful process for independent verification.
This too will be my stance on overcoming this problem.
Actually, this attack has grown easier overtime, because compiler has became more and more complex and there’s so many crevices and holes for attacker to hide his malicious code in. You may make your own simple compiler just to watch those complex compilers on the leash. But again, can you trust the compiler that you use to compile the simple compiler?
References
“Reflections on Trusting Trust” by Ken Thompson