I'm surprised no one has mentioned David A. Wheeler's "Diverse Double Compiling" (http://www.dwheeler.com/trusting-trust/) as a solution to this problem.
Strange Loops: Ken Thompson and the Self-referencing C Compiler
21–30 of 55 posts
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#22Earlier quoted context omitted.
Please read the process again. Let me rephrase it: 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.
It doesn't matter. "Trusting Trust" is just intended to show that by compromising the C compiler, you can compromise any other binary on the system. So, how are you going to tell D1 and D2 are identical if the diff tools are compromised? Compare them off the machine? Well, what if the file transfer tools/drivers are compromised? Boot to a custom kernel and compare using a different OS? Well, better hope your boot fir…
Use a card deck as your persistent storage. Give the card deck to undergrads to verify by hand. ;)
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#23Earlier quoted context omitted.
It doesn't matter. "Trusting Trust" is just intended to show that by compromising the C compiler, you can compromise any other binary on the system. So, how are you going to tell D1 and D2 are identical if the diff tools are compromised? Compare them off the machine? Well, what if the file transfer tools/drivers are compromised? Boot to a custom kernel and compare using a different OS? Well, better hope your boot fir…
Use a card deck as your persistent storage. Give the card deck to undergrads to verify by hand. ;)
Right. Use 1000 different hash functions to hash the binaries and compare. Surely it is impractical to compromise all future hashing algorithms by detecting their pattern.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#24Earlier quoted context omitted.
Use a card deck as your persistent storage. Give the card deck to undergrads to verify by hand. ;)
Right. Use 1000 different hash functions to hash the binaries and compare. Surely it is impractical to compromise all future hashing algorithms by detecting their pattern.
Oh, I'm just thinking that you only write and read from storage that can be manually verified. You therefore wouldn't verify the output of your compiler with anything that was compiled by that compiler.. instead you would verify it with the owners manual and some underlings to do the grunt work.
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.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#25[deleted]
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#26The original article, which this (kind of) summarizes: "Reflections on Trusting Trust" by Ken Thompson. http://cm.bell-labs.com/who/ken/trust.html Sort of disappointing that the blog entry doesn't bother linking to the original, which is at least as well written.
From the original, Ken on the press lionizing hackers:
"I have watched kids testifying before Congress. It is clear that they are completely unaware of the seriousness of their acts. There is obviously a cultural gap. The act of breaking into a computer system has to have the same social stigma as breaking into a neighbor's house. It should not matter that the neighbor's door is unlocked. The press must learn that misguided use of a computer is no more amazing than drunk driving of an automobile."
Nowadays, I here more about the opposite problem -- using overly broad, non-technical legalese to convict kids of "hacks" that aren't really hacks. I wonder what Ken would think of Snowden, Barrett Brown, weev et al?
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#27Interesting! Out of curiosity, if this were the Gnu C Compiler, would this be illegal, since the GPL requires the source to be distributed with the binary, and the source and binary don't match?
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#28The original article, which this (kind of) summarizes: "Reflections on Trusting Trust" by Ken Thompson. http://cm.bell-labs.com/who/ken/trust.html Sort of disappointing that the blog entry doesn't bother linking to the original, which is at least as well written.
From the original, Ken on the press lionizing hackers: "I have watched kids testifying before Congress. It is clear that they are completely unaware of the seriousness of their acts. There is obviously a cultural gap. The act of breaking into a computer system has to have the same social stigma as breaking into a neighbor's house. It should not matter that the neighbor's door is unlocked. The press must learn that mi…
I'm pretty sure the context of that quote is completely applicable to weev. "It should not matter that the neighbor's door is unlocked", is clearly Ken saying that something being technically simple does not make it morally or legally justifiable.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#29Earlier quoted context omitted.
Please read the process again. Let me rephrase it: 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.
Oh, I see, generate two different binaries of the same compiler with different compilers, and you know something is up if the same source compiled by those two separate binaries of the same compiler differ. Assuming the compiler is deterministic, that should work pretty well. 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…
Yes. David A Wheeler did his PhD thesis on this[1], both with some toy compilers to demonstrate that it did detect a trusting trust attack, and eventually bootstrapping gcc using icc, and was able to get it to compile deterministically and verify that it produced identical binaries.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#30Earlier quoted context omitted.
Please read the process again. Let me rephrase it: 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.
It doesn't matter. "Trusting Trust" is just intended to show that by compromising the C compiler, you can compromise any other binary on the system. So, how are you going to tell D1 and D2 are identical if the diff tools are compromised? Compare them off the machine? Well, what if the file transfer tools/drivers are compromised? Boot to a custom kernel and compare using a different OS? Well, better hope your boot fir…
> 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.
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/