Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Strange Loops: Ken Thompson and the Self-referencing C Compiler

scienceblogs.com

Post reply on HN
Print view View original

41–50 of 55 posts

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#41

Post by e12e »

InclinedPlane wrote: post #40
WalterBright wrote: post #38

Earlier quoted context omitted.

> This is utterly false and reveals a deep misunderstanding of compiler technology. 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 comp…

That's nice that your compiler works that way but that's not the way most do. 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 likel…

No, the point was comparing the binary output of the same compiler, compiled by itself, compiled by different compilers... (Yeah, I missed that the first time round, too).

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#42

Post by e12e »

csense wrote: post #37

Let's pretend a compiler with this backdoor will always correctly detect when it's compiling a compiler. I.e. looksLikeCompilerCode() and generateCompilerWithBackDoorDetection() are oracles. With this assumption, to write a compiler that's safe, you can't run it through an existing possibly-compromised compiler. You would have to bootstrap your safe compiler, as if for a totally new language. So you'd have to initial…

Reading this, I was reminded of an article using the dos debug[1] command to bootstrap tools written from (memorized) assembly language.

Note, I can't find the actual article now - I think it may have been in one of the early issues of Phrack[2].

[1] http://www.intel-assembler.it/portale/5/Write-an-assembly-pr...

[2] http://www.phrack.org

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#43

Post by WalterBright »

InclinedPlane wrote: post #40
WalterBright wrote: post #38

Earlier quoted context omitted.

> This is utterly false and reveals a deep misunderstanding of compiler technology. 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 comp…

That's nice that your compiler works that way but that's not the way most do. 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 likel…

> More importantly the salient point was about comparing the binary output of different compilers.

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.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#44

Post by asabjorn »

pmiller2 wrote: post #7
WalterBright wrote: post #2

This 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.

A solution to this problem happens to be my thesis topic, and yes it is a very difficult problem. We achieve this by a mechanism to randomly test functions in binaries without knowing the function call signature.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#45

Post by vidarh »

lambda wrote: post #30
pmiller2 wrote: post #16

Earlier 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…

> 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…

You are addressing a completely different issue than the paper did. Yes, the general case is nearly impossibly hard.

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.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#46

Post by sharkbot »

SEMW wrote: post #20
jhuckestein wrote: post #19

Earlier quoted context omitted.

True. But this isn't useful unless you know which code C to do the test on (in the OP's original example C would be the code of the login program). The only way to tell if a compiler will put a backdoor into certain programs is to read the disassembled source.

No. In WalterBright's example, code C is the compiler (the one which you suspect may be backdoored), not the login program. A and B are also compilers, one of which is known-good. So: the difference you'll find isn't the login-backdoor itself, it's the code that waits for a login program (or another compiler) to be compiled, and inserts that backdoor. This avoids the problem of having to know what the login program o…

> A and B are also compilers, one of which is known-good.

'Known-good' is exactly the problem Thompson's essay is describing. There is no 'known-good'. Instead, you have decided to root your chain of trust with a compiler you call 'known-good' (say, B). But ultimately, that trust is arbitrary: your compiler B relied upon un-investigated components at some point in its heritage: a hex editor, a disk drive controller, a CPU, an LCD screen, etc.

The best you can do is reduce the trusted base to the smallest amount, then make explicit your trust relationships as much as possible. Ideally, the trusted base would be physics and logic with a metaphysical certainty of the universality of those laws; we're a long way from that situation :)

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#47

Post by chii »

WalterBright wrote: post #43
InclinedPlane wrote: post #40

Earlier quoted context omitted.

That's nice that your compiler works that way but that's not the way most do. 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 likel…

> More importantly the salient point was about comparing the binary output of different compilers. 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.

I think a lot of people gets confused by your explanation earlier in the comment thread because one it is difficult to do recursion, and two, see above. ;)

But yes, i think this method does work. You'd have to trust all the pipeline programs used in between.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#48

Post by SEMW »

sharkbot wrote: post #46
SEMW wrote: post #20

Earlier quoted context omitted.

No. In WalterBright's example, code C is the compiler (the one which you suspect may be backdoored), not the login program. A and B are also compilers, one of which is known-good. So: the difference you'll find isn't the login-backdoor itself, it's the code that waits for a login program (or another compiler) to be compiled, and inserts that backdoor. This avoids the problem of having to know what the login program o…

> A and B are also compilers, one of which is known-good. 'Known-good' is exactly the problem Thompson's essay is describing. There is no 'known-good'. Instead, you have decided to root your chain of trust with a compiler you call 'known-good' (say, B). But ultimately, that trust is arbitrary: your compiler B relied upon un-investigated components at some point in its heritage: a hex editor, a disk drive controller,…

Yes, of course. I don't think WalterBright was claiming that this method eliminates the theoretical possibility of all trusting-trust-type attacks entirely, only that it gives you a good shot at detecting the specific type that Thompson gave as his example (the compromised compiler). The point of the method being that since compiler B can be crap (slow, non-optimising, only implementing the minimum required to compile compiler C), it can be something you could knock up yourself, so reducing your level of trust to those components below the level of the compiler.

So yes, you're still relying on things below that. That doesn't make the exercise 'arbitrary' or pointless. Good risk management is reducing the chances of the most probable attacks, and a compromised compiler is (ISTM) a much more likely attack than e.g. a compromised CPU.

Seems to me that putting theoretical perfection too far ahead of pragmatism just gives the (wrong and damaging) impression that not being able to solve all trusting-trust issues entirely means it's not worth their time trying to solve the more tractable ones.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#49

Post by belorn »

barbs wrote: post #27

Interesting! 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?

GPLv3:

  The “source code” for a work means the preferred form
  of the work for making modifications to it.
  ...
  The “Corresponding Source” for a work in object code form
  means all the source code needed to generate, install, and
  (for an executable work) run the object code and to modify
  the work, including scripts to control those activities.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#50

Post by Patient0 »

InclinedPlane wrote: post #36
WalterBright wrote: post #8

Earlier quoted context omitted.

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.

> The same source code should generate the same binary. 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 choice…

Next time you might want to look up who Walter Bright is before jumping to the conclusion that you know more about compilers than he does (http://en.wikipedia.org/wiki/Walter_Bright)
Post reply on HN