Diverse Double-Compiling (DDC) counters "trusting trust"

Posted Jun 21, 2013 22:50 UTC (Fri) by david.a.wheeler (subscriber, #72896) [Link]

"I don't know specifically about compiler writers, but I bet there's a similar flow of people between different organisations and projects there.". - Certainly it happens, but it's less common than you might think. Learning how to write a compiler is a standard Computer Science class, and in many cases students actually write a compiler as part of the class. Thus, there are a huge number of people who know how to do it. It's not like there are only 10 people in the world who know how to write compilers. Especially since, for DDC, it only needs to work at all for one program... slow is just fine.

"To me, the notion that different compilers will inherently have independent sets of authors AND other involved engineers (maintenance, release engineering), is highly inconsistent with freedoms which I, and I suspect many others, know engineers/authors avail of in their careers.". - Even if there's overlap, the issue is that someone would have to be able to subvert the binary... which means they'd have to have a fair amount of trust, or break in somehow in the build chain, to do it. Typically the "new guy" isn't trusted to the same degree, making it harder to do.

"I'm sure some of those authors will at times try out the competing software on their systems at times.". - So? Trying out software doesn't perform the attack. Even if you create a modified malicious compiler on your local system, that means nothing. For an attack to work against DDC, an attacker has to subvert the binaries of multiple compilers, as used by the organization applying DDC.

"You've taken an extremely narrow, restricted view of Thompson's attack. That it was specifically about subverting a compiler binary. Even with that restricted view, I believe your technique still requires one to *write* their own compiler from scratch AND/OR trust an existing binary. Further, that restricted view of his attack/point is not right - his paper clearly intended the compiler attack to be an illustration of a much more general class of attacks, in order to make fundamental points about trust."

It's not narrow at all. I clearly state in my paper that DDC isn't limited to "compilers" as they are traditionally defined. Indeed, I specifically note that the DDC "compiler" could be an assembler, could include an entire operating system, and could apply to hardware (not just microcode) as well.

But as far as what Thompson meant, well, let's look what Thompson says in "Reflections on Trusting Trust". He says that "You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.)" He says his attack is specifically about program-handling code: "I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode". And the reason can't trust others' code is because you're unable to do source-level verification: "No amount of source-level verification or scrutiny will protect you from using untrusted code."

The fundamental problem is that with program-handling programs, the creator of the executable can create self-perpetuating attacks. So... let's employ multiple different program-handling programs, make it hard for them to collude, and use them to check each other. Now we're no longer dependent on any single supplier to decide if we get malicious code or not.

"The technique in your thesis is very useful, and seems to me like it could indeed help increase the level of assurance we might have that our software hasn't been subverted. No argument there. It's just that "Fully" qualifier in the claim that's jarring - it's not supported, not even with the deliberately restricted view taken of Thompson's attack. ;) Thompson's point still stands, indeed it is re-inforced by how your technique requires a trusted or verified boot-strap compiler: We must build the whole system ourselves, OR we must trust in those who supplied the parts we did not build."

You keep ignoring a third way - use multiple parties to check each other. One of those parties could even be you! Outside of the computing field this use of multiple checks is the normal way of gaining trust. Instead of blindly trusting business B, we might get an independent auditor to check out the books. If we're really concerned, we'll get two auditors and make sure that the external organizations that manage B's accounts actually hold the money claimed. Historically, compilers and other program-handling programs were like a business without auditing; we had to trust whatever it produced. DDC creates an auditing step; sure, it's possible to fool it through collusion, but there are many well-known ways to make collusion hard. Moving from blind trust to an auditable process is a big step forward.

Put simply: The problem, as I see it, is the previous impracticality of independent verification of program-handling programs. DDC fully eliminates that problem, because it does provide a mechanism for independent verification. Now the problem changes to "how much verification is enough" instead of "I guess we just hope it's okay." How and when do you apply that mechanism? Cue Neo's voice: "Where we go from there is a choice I leave to you."