Defending Against “Trusting Trust”

“Trusting Trust” is an attack that fundamentally defeats all security. Because computer programs must be compiled into machine code from human readable source code, it’s possible to compromise the program that does the compiling… and have it in turn compromise everything else.

Since humans can’t check the compiler program manually, nor can they check the compiled machine code, this attack would be (theoretically) undetectable.

(In reality, humans can check the machine code, but only with such extreme difficulty it mostly isn’t done.)

There are even applications to human-scale systems, but more on that later.

A fellow named David Wheeler wrote his dissertation on defending against this, the problem against which it’s impossible to defend.

His solution hinges on a) the deterministic nature of computer systems and b) the introduction of a second compiler program. This one is “trusted,” at least, it’s trusted not to contain the same backdoor as the “untrusted” compiler.

Why? It may be a stripped-down bare-bones compiler, where checking the machine code against the source code is feasible. Or, it may have come from a different source, which is so diverse that it’s infeasible for the same adversary to compromise both in the same way.

A key principle here is that the trusted compiler need not produce the exact same result as the untrusted compiler. (In fact, a different compiler almost always produces a slightly different result.)

Instead, the trusted compiler need only produce a result that has the same FUNCTIONALITY. The program it compiles must work as advertised… because the program it will be compiling is a new copy of the “untrusted” compiler.

Once this is done, there are two copies of the “untrusted” compiler in existence. One might be compromised — it might be modified to add a backdoor whenever it compiles itself.

The other is presumed not to add a backdoor whenever it compiles itself… but, since it was made by a different compiler, is assumed to be significantly different from the first copy (regardless of whether that first copy is compromised). Therefore, a direct comparison is not possible.

What’s the solution? Easy.

The two different-in-appearance identical-in-function copies are now used to compile themselves, from the same source code.

Since the two compilers that result from THAT step were produced by (hopefully) the same compiler, from the same source code, THOSE copies ought to be perfectly identical.

If not, well, somebody’s got a problem…

Conceptually, this is all about the separation of form and function. Specifically, two things, created by different means, may look different even if they produce the same result.

If those things can produce themselves, having them do so ought to produce a result that is identical in both form and function.

How does all this apply to human scale systems? Well, remember Operation TRUST — the “underground” organization run by Soviet intelligence? In a conceptual sense, that’s similar to a compromised compiler.

Any information or action that passes through it will be inherently compromised. Not because the front-line personnel necessarily report to the opposition… but because the whole structure will imprint a certain set of assumptions and practices on its members.

Another example: The Stasi were big fans of training revolutionary groups… in the West. Yet, they would have been careful to ensure that none of the knowledge bestowed on those groups would enable them to turn on the East. They would teach them tactics that rely on the availability of support logistics, etc so as to ensure those groups’ dependency.

On a very high level, the “countering trusting trust” approach could provide a way of detecting and countering “TRUSTs.” By looking at the structures produced by a trusted group and comparing them to the structures produced by an untrusted one, it could therefore be possible to identify… discrepancies.

Unfortunately… well, fortunately, too! — humans and social structures are far from deterministic. People simply don’t necessarily produce the same outputs given the same input. So a strictly mathematical treatment is not possible.

“Here’s information about my work to counter the “Trusting Trust” attack. The “Trusting Trust” attack is an incredibly nasty attack in computer security; up to now it’s been presumed to be the essential uncounterable attack. I’ve worried about it for a long time, essentially since Ken Thompson publicly described it. After all, if there’s a known attack that cannot be effectively countered, should we be using computers at all? Thankfully, I think there is an effective countermeasure, which I have named “Diverse Double-Compiling” (DDC). […]

This dissertation’s thesis is that the trusting trust attack can be detected and effectively countered using the “Diverse Double-Compiling” (DDC) technique, as demonstrated by (1) a formal proof that DDC can determine if source code and generated executable code correspond, (2) a demonstration of DDC with four compilers (a small C compiler, a small Lisp compiler, a small maliciously corrupted Lisp compiler, and a large industrial-strength C compiler, GCC), and (3) a description of approaches for applying DDC in various real-world scenarios. In the DDC technique, source code is compiled twice: once with a second (trusted) compiler (using the source code of the compiler’s parent), and then the compiler source code is compiled using the result of the first compilation. If the result is bit-for-bit identical with the untrusted executable, then the source code accurately represents the executable.[…]

First, complaining that people trust others is a waste of time. You must trust others in a modern world. No one grows all their own food, builds their own shelters from their own materials, and provides all their other needs by themselves; we all trust others. However, there is a serious systemic problem if you cannot independently verify what you trust. You should strive to “trust, but verify”.

I believe the fundamental problem caused by the trusting trust attack was that it was impractical to independently verify that what you depended on (the executable) corresponds to its human-readable representation (the source code). This is because program-handling programs can subvert the relationship between what humans review and what is actually used. Ken Thompson’s paper is not titled “Reflections on trust”; it is “Reflections on trusting trust”. Again, I believe problem was not trust, but the lack of a meaningful process for independent verification.”

“In brief, to perform DDC, source code must be compiled twice. First, use a separate “trusted” compiler to compile the source code of the “parent” of the compiler-under-test. Then, run that resulting executable to compile the purported source code of the compiler-under-test. Then, check if the final result is exactly identical to the original compiler executable (e.g., bit-for-bit equality) using some trusted means. If it is, then the purported source code and executable of the compiler-under-test correspond, given some assumptions to be discussed later.”

%d bloggers like this: