Re: Countering Trusting Trust through Diverse Double-Compiling

[Mike Lisanke]

David,

I haven't read the original attack description recently, but; I seam
to remember that the ability of the tampered compiler to inject
malicious code could be stateful. Either a timing attack, or a attack
after n-builds, so that malicious code is injected in an arbitrary,
pseudo-random, less detectable way. Also, that this code would be
injected based on compiler state conditions (like after keywords
indicated that the code may be network based). I haven't read your
paper, yet; but; I'd be interested know where you'd plan to discuss
scenarios where your counter attack would fail. Thank you.

Best regards,
--
Mike

[David A. Wheeler]

Mike Lisanke wrote:
> David,
>
> I haven't read the original attack description recently, but; I seam
> to remember that the ability of the tampered compiler to inject
> malicious code could be stateful. Either a timing attack, or a attack
> after n-builds, so that malicious code is injected in an arbitrary,
> pseudo-random, less detectable way. Also, that this code would be
> injected based on compiler state conditions (like after keywords
> indicated that the code may be network based). I haven't read your
> paper, yet; but; I'd be interested know where you'd plan to discuss
> scenarios where your counter attack would fail. Thank you.

The attack can certainly be stateful, but that doesn't matter
for the purposes of DDC. In DDC, you NEVER run the compromised
compiler binary during the actual DDC test. Since the compromised
binary is never run, the binary cannot affect the results, whether or
not the attack is stateful. QED.

Now it _IS_ true that the source code could define a compiler
that is stateful and only sometimes injects attacks.
But that's fine. The DDC approach does NOT tell you if a compiler
is malicious -- it tells you if the source and binary CORRESPOND.
That's KEY. We have LOTS of techniques (including eyeballs) for
reviewing source code, and lots of people do it; the problem is
that reviewing BINARIES is dreadful/painful/impractical in most cases.

The "Trusting Trust" attack depends on there being a hidden difference
between the source and binary. DDC makes that extremely difficult,
changing the nature of the problem from "review every binary"
(eek!) to "review all the source code" (not easy, but we have a
clue of how to do that). Also:
* If the compiler varies in what it produces for ITSELF,
then DDC detects any time that occurs (because it detects
differences). If compilation "sometimes" produces a malicious
compiler, as long as I can see the attack while reviewing source
code, that's fine... I've made the attack visible.
* A compiler that fails to attack itself will quickly become
sterile -- it will lose the ability to attack this way.

There _IS_ a variation of this attack, though.
DDC only tests a PARTICULAR source against a PARTICULAR binary.
You could insert the attack in a later version of the source code,
let the victim compile it, then send another version of the source
code without the attack, and let the victim compile again.
Oops - a malicious binary, with no malicious source.
This means that someone has to do DDC with EACH version of a
compiler that you care about; you can't just do it once.

The paper has a section on limitations. Like all techniques,
it has limits, but I think it's a step forward.

--- David A. Wheeler