Remember that C1 and C2 are generated by two different compilers generated from the same source code. The same source code should generate the same binary.
I.e. take the iteration one more time.
(I actually do this as part of the test suite for the Digital Mars C++ compiler - it takes two iterations until the binaries match exactly.)
(Plus a backdoor could easily be set to run only when optimizations are on. Almost all production builds that one would want to exploit should be built optimized, and it would make the exploit a bit harder to spot in compiled binaries.)
A compiles C and produces C1. C1 compiles C and produces D1.
B compiles C and produces C2. C2 compiles C and produces D2.
D1 and D2 should be identical.
I grant that this is not a very practical attack, but it can be made arbitrarily hard to detect, based on the threat model the original attacker (who compromised the C compiler) uses.
So you run your compiler, and it punches cards for you. You then turn off the machine, remove the cards, and verify them. If that checks out, then you boot the machine with the cards again. Anything that persists the reboot has to be on those cards, and is therefore subject to uncompromised inspection.
Not really. The more binaries you have to be able to subvert for it to work, the harder the attack becomes. There are lots of binary diff tools out there, lots of compilers, lots of assemblers, etc. Writing an attack that could detect them all and defeat them all would be so hard as to be impractical; being able to generically recognize something like "this is a compiler" or "this is an implementation of AES" would probably involve solving the halting problem. And if you can't solve it generically, you have to start adding bigger and bigger suspicious binary blobs in which encode all of the patterns for all of the programs you're looking to subvert.
Remember, the NSA does not have infinite resources, nor can they solve unsolveable problems. There is a practical limit to how paranoid you need to be.
Practically, subverting general purpose computation, like subverting a compiler or subverting general purpose instructions on a CPU, is likely to be too easy to detect and too hard to implement to be worth it.
Much easier is subverting a random number generator. That's incredibly hard to detect, and easy to implement. AES encrypting an incrementing counter with a key known only to the NSA looks an awful lot like a random stream, but with that key they can trivially figure out where it is in the stream and what will come next.
That's why Intel's insistence on getting the Linux kernel to blindly trust the RdRand instruction was quite worrying[1], while applying only a bit of paranoia and using David A Wheeler's approach to defeat the trusting trust attack[2] is likely sufficient to have faith in things like your compiler.
1: https://en.wikipedia.org/wiki/RdRand 2: http://www.dwheeler.com/trusting-trust/
But that is not the point. The point is that against a determined adversary, you can not trust an arbitrary program, even if that program is compiled from source, unless you can also trust every other component on your system.
The point then, is to encourage that "bit of paranoia" and make people understand that thinking you're safe just because you can read through the source or have another mechanism for producing or obtaining what you might think is a pristine, safe copy of a piece of software is a false sense of security.
While this particular attack to my knowledge was only a thought experiment and I've never heard of it occurring in the wild, note that at least a few viruses for example propagate by modifying binaries to act as carriers, and often modify the system to obscure their presence (e.g. report incorrect file sizes, and not read back the modified data). This is largely the same threat, and in many ways far more practical because it doesn't require people to take the step of trying to recompile applications.
Having the source (or a "known good" source of your application) does not help you, as your binary is infected when it is handled by the compromised system. Taking checksums etc. on the compromised systems may not help you.
I wonder how well that would work in practice. There are actually quite a few bugs in C compilers[1], and compilers are complicated enough that I could see them hitting some of them when they are compiled. Has anyone done this before?
1: http://www.stanford.edu/class/cs343/resources/finding-bugs-c...
This is utterly false and reveals a deep misunderstanding of compiler technology. Aside from optimizations and exactly how they are implemented in each compiler there are still many more or less arbitrary choices that a compiler needs to make in order to translate source code into machine code. Address layout being one of the most prevalent. Indeed, these choices are so arbitrary and lead to such a high degree of difference in the binary forms that the same compiler running on the same code will often generate different binary output. And the same compilers running on very slightly different code bases will quickly generate substantially divergent output. This is why programs like bsdiff and courgette exist, because comparing binaries is actually an enormously non-trivial problem.
I've written many professional compilers, front to back, and I use the binary difference technique to verify that the compiler is capable of exactly reproducing itself.
If you've got a compiler that generates different binaries depending on the time of day, the address the compiler was loaded at, or something else that is not the compiler switches + source code provided to it, you've got a compiler with serious QA issues.
More importantly the salient point was about comparing the binary output of different compilers.
While it's certainly possible to create tools which make it make it possible to determine if the binary output of different compilers are effectively the same such tools are very non-trivial to create. The idea that different compilers are likely to produce exactly identical output is sheer fantasy.
No, it wasn't. I explained it (apparently badly) 3 times now. There's another iteration of bootstrap compiling in there before the output is compared.
But yes, i think this method does work. You'd have to trust all the pipeline programs used in between.
If I was trying to detect a "trusting trust" type backdoor, one thing I might do is model the control flow of the executable as a graph, and use something like approximate graph isomorphism to detect additional large blocks of code.