Strange Loops: Ken Thompson and the Self-referencing C Compiler
scienceblogs.com
Strange Loops: Ken Thompson and the Self-referencing C Compiler
1–10 of 55 posts
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#2This relies on new compiler binaries being built from the previous compiler binaries.
The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door:
Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised:
A compiles C which compiles C1
B compiles C which compiles C2
C1 and C2 should match. If it does, and A is "known good", then C is now "known good".
Of course, this can be compromised, too, but it will make it very much harder to do so.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#3This is awesome because it means backdoors could have been inserted many many versions ago in a compiler and as long as there was a chain of using the compiler to compile itself through each version (as most compilers like GCC are), the hack would be passed ad infinitum. Pretty evil.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#4There is more than one way to defeat this attack. One of the simpler ones would be to create a formally verified C compiler in X86 assembly, which you can use to compile an older version of GCC or whatever, and then use that version to compile the next one, and so on and so forth until you have a guaranteed clean modern version.
I don't think any buildchains currently implement anything like this though.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#5Nice article, but just read the original: http://cm.bell-labs.com/who/ken/trust.html
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#6The 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.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#7This relies on new compiler binaries being built from the previous compiler binaries. The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door: Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised: A compiles C…
Of course, the hard part is to detect whether C1 and C2 "match." Just because 2 different compilers generate different code for the same source doesn't mean one or the other compiler was compromised. By Rice's theorem, it's undecidable in a general case to decide whether two computable functions are equal, so you technically can't do this step in a general way.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#8This relies on new compiler binaries being built from the previous compiler binaries. The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door: Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised: A compiles C…
Of course, the hard part is to detect whether C1 and C2 "match." Just because 2 different compilers generate different code for the same source doesn't mean one or the other compiler was compromised. By Rice's theorem, it's undecidable in a general case to decide whether two computable functions are equal, so you technically can't do this step in a general way.
Do a binary diff of the executables. That's unambiguous.
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.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#9This relies on new compiler binaries being built from the previous compiler binaries. The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door: Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised: A compiles C…
Of course, the hard part is to detect whether C1 and C2 "match." Just because 2 different compilers generate different code for the same source doesn't mean one or the other compiler was compromised. By Rice's theorem, it's undecidable in a general case to decide whether two computable functions are equal, so you technically can't do this step in a general way.
Rice's theorem is nice and all, but in the real world we can model executables as things other than turing machines and answer questions about them.
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.
Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler
#10This is awesome because it means backdoors could have been inserted many many versions ago in a compiler and as long as there was a chain of using the compiler to compile itself through each version (as most compilers like GCC are), the hack would be passed ad infinitum. Pretty evil.
The chain also breaks if the detected compiler source code pattern changes enough so it is no longer detected.