Reflections on Trusting Trust

Preview

Chandler presented “Reflections on Trusting Trust”, a speech given by Ken Thompson during the Turing Lecture in 1984.

Summary

Ken’s speech was a reaction to various hacker groups such as the 414’s, who hacked into many high-profile computers. Instead of being properly detained and punished by the law, they were praised as ‘whiz-kids’ and geniuses. He disagreed and beleived they should have been punished more severely for their crimes.

In order to prove his point, he demonstrated how to hack a system in a way that leaves little to no trace through the use of quines, boostrapping and Trojan horses.

Quines

The first part of this formula involves programs called quines, which are programs that replicated themselves when run. Very cute programs which I am not capable of making myself, so here’s a short one from Wikipedia.

-- Example quine in Haskell
quine = putStr s >> print s where s = 
  "quine = putStr s >> print s where s = "

These can be powerful in the right context, as we will see later.

Bootstraping

He then goes onto describing how compilers can self learn to recognize new patterns (bootstrap). The simplified explaination he gave was how the current C compiler detected newline characters '\n'.

I am going to abbreviate “the C Compiler” as tcc.

// How tcc detects newline
int char_parser() {
  char c = next(); // next character in parse
  if (c != '\\')
    return(c);
  c = next();
  if (c == '\\')
    return('\\'); // backslash literal
  if (c == 'n')
    return('\n'); // newline
}

If you wanted to go ahead and detect another escape character such as tab '\t', you might try something like this.

// How tcc would try and detect tab
int char_parser() {
  char c = next(); // next character in parse
  if (c != '\\')
    return(c);
  c = next();
  if (c == '\\')
    return('\\'); // backslash literal
  if (c == 'n')
    return('\n'); // newline character
  if (c == 't')
    return('\t'); // tab character
}

However that wouldn’t work initially since the current compiler doesn’t recognize '\t' as a valid character. You would have bootstrap tcc with the fragment below to get the desired outcome.

// Making a compiler that recognizes '\t'
int char_parser() {
  char c = next(); // next character in parse
  if (c != '\\')
    return(c);
  c = next();
  if (c == '\\')
    return('\\'); // backslash literal
  if (c == 'n')
    return('\n'); // newline character
  if (c == 't')
    return(9); // tab in ascii
}

Filling C with Trojan Horses

Now we can hack tcc! Ken gives a tutorial on how to write a ‘buggy’ C compiler. However to him calling these nuances bugs wouldn’t do it justice, they are instead Trojan Horses.

Say that tcc’s compile function looks like this …

// TCC VERSION 1.0
void compile(char* s) {
  // compiles a line of C code
}

… but we then modify it to detect certain code paterns, in this case the pattern would be the Unix login.

// TCC VERSION 2.0
void compile(char* s) {
  if (matches(s, "the unix login"))
    /* Trojan horse code where bug1 is a version of the 
       Unix login that allows another known password */
    compile("bug1"); 
    return
  }
  // ...
}

This is a bit too obvious though. If anyone looked at the tcc source, they would see the blantant code that is breaching the Unix login. To disguise this, rewrite tcc in the following way.

// TCC VERSION 3.0
void compile(char* s) {
  if (matches(s, "the unix login")) {
    compile("bug1"); 
    return
  }
  if (matches(s, "tcc")) {
    /* Trojan horse code where bug2 is a quine of 1.2 */
    compile("bug2";)
    return
  }
  // ...
}

Now do the following

1. Compile v3.0 to produce the bugged binary.
2. Install 3.0 binary on machine.
3. Compile v1.0 to produce “undetectable” bugged binary.
4. Install bugged 1.0 binary on machine.
5. ???
6. Profit

Jokes aside, whatever version of tcc you compile would create the bugged binary, and any version of Unix would now have the breached login. These type of microbugs are still hard to detect. As Ben suggested, if you went a step further encrypted the bug recognition strings (bug1 and bug2) with a bit mask, xor, or any other type of encryption, it would be virtually impossible to catch.

Takeaway

"You can't trust code that you did not totally create yourself. 
(Especially code from companies that employ people like me.)"
 - Ken Thompson

Ken’s message was important. He beleived that the “hackers” who had breached high profile computers should receive serious prosecution. Back in 1983, when the 414 gang was caught, they were given a slap on the wrist and praised. Nowadays doing something on the scale of the “whiz kids” of the 1980’s would result in up to 20 years in prison and a fine up to $15,000.