10

I read some stuff like cm bell labs but i couldn't get it all. How does it work really? What is the logic in that?

yfklon
  • 1,752
  • 4
  • 19
  • 30
  • 2
    Related: http://programmers.stackexchange.com/questions/184874/is-ken-thompsons-compiler-hack-still-a-threat – iCanLearn Apr 12 '13 at 10:54

1 Answers1

32

Reflections on Trusting Trust is a lecture by Ken Thompson in which he explains the hack. Briefly:

  • he hacked /bin/login to introduce a backdoor.
  • he did this by hacking the compiler to introduce the backdoor into a binary whenever it detected that it was compiling the login source code.
  • he also hacked the compiler to introduce the backdoor-producing code into the compiler whenever it detected it was compiling that.

His point was that you might think "I don't trust this binary, I'll build it from source" but now you're in a state of recursive paranoia. If you don't trust the binary, why do you trust the compiler binary? You don't, so you build the compiler: but why do you trust the compiler binary to produce a trustworthy compiler?

  • 1
    He didn't actually do this; he merely claimed that it was possible. Never mind that doing step 2 reliably involves solving the halting problem (to determine whether source A is equivalent to source B, you must prove that they do the same, which includes determining whether both halt in the same circumstances) – MSalters Apr 12 '13 at 11:03
  • 4
    @MSalters "The actual bug I planted in the compiler would match code in the UNIX "login" command." –  Apr 12 '13 at 11:33
  • 3
    @MSalters He did not attempt to insert on anything that might be a login command. He made it insert for the actual code in the actual login command that was actually in Unix. This is a much more tractable target, and his talk discusses exactly how to do that. – btilly Apr 12 '13 at 12:12
  • A compiler Y Combinator – Jimmy Hoffa Apr 12 '13 at 14:45
  • 2
    This sort of problem is why some of us started programming with toggle switches :-) – Ross Patterson Apr 13 '13 at 00:41
  • 3
    @RossPatterson: Then you have to enter the paper-tape bootstrap with toggle switches also, and only use the tape you (personally) created. – Pieter Geerkens Apr 13 '13 at 04:52
  • 9
    @PieterGeerkens you mean you trust the hardware to interpret the toggle switches correctly? You're brave. –  Apr 15 '13 at 16:38