| |||||||||||||
Security in the 20-teensSecurity in the 20-teensPosted Feb 2, 2010 7:57 UTC (Tue) by eru (subscriber, #2753)In reply to: Security in the 20-teens by Baylink Parent article: Security in the 20-teens I'll call everyone's attention (back) to "Reflections On Trusting Trust", [...] David A. Wheeler has described a way to thwart that attack: http://www.dwheeler.com/trusting-trust/
(Log in to post comments)
Security in the 20-teens Posted Feb 2, 2010 11:13 UTC (Tue) by paulj (subscriber, #341) [Link]
Hmm, how does that thwart the attack exactly? It assumes you have access
to an unsubvertable oracle - (a set of 1 or more other compilers of which at least one has not been subverted). Given that then, yes obviously, you can spot a discrepency.
Isn't that missing the point of "Reflections On Trusting Trust", somewhat? Or
Security in the 20-teens Posted Feb 2, 2010 12:35 UTC (Tue) by eru (subscriber, #2753) [Link]
If I understood the idea correctly, you don't need any unsubverted compiler, just a completely different implementation (eg. to verify GCC you might use PCC, for example). Suppose GCC has been subverted to that it propagates the backdoor when compiling GCC, and PCC does the same when compiling PCC. But compiling GCC with PCC does not propagate a backdoor that would affect GCC when GCC compiles itself.
Security in the 20-teens Posted Feb 2, 2010 13:19 UTC (Tue) by paulj (subscriber, #341) [Link]
Right, i.e. unsubverted oracle = {set of compilers where at least one compiler is
not subverted}, where 'subverted compiler' here means 'subverted consistently with the others'.
Basically, he's inventing an oracle against the original problem by limiting the
"The moral is obvious. You can't trust code that you did not totally create
The DDC technique does not solve that problem in principle, it seems clear to
Security in the 20-teens Posted Feb 2, 2010 16:18 UTC (Tue) by nix (subscriber, #2304) [Link]
It reduces to the problem to "you can't trust compilers produced by a cooperating malevolent group, nor code compiled with those compilers". But if you have several compilers, some of which are trustworthy *or are produced by malevolent groups that are not in communication*, then those compilers will not introduce the Thompson hack into the *other* compilers when compiling them, and the attack falls apart.
This is a much harder bar for attackers to leap over: from subverting one compiler, they have to subvert every compiler you might possibly use targetting that architecture if they are to go undetected.
Security in the 20-teens Posted Feb 2, 2010 16:26 UTC (Tue) by Baylink (subscriber, #755) [Link]
Or, you just have to not be thinking about the problem.
Be honest: how often do *you* evaluate your systems for the Reflections attack? That was my Usenet posting, and *I* don't do it most of the time...
Security in the 20-teens Posted Feb 2, 2010 18:10 UTC (Tue) by droundy (subscriber, #4559) [Link]
It's not enough that the attackers aren't in communication, but rather that
they are mutually ignorant, which seems highly unlikely. I suspect even benevolent compiler writers pay reasonably close attention to the work of other compiler writers, and our malevolent compiler subverters seem likely to pay even more attention to other compilers.
The attacker who inserted a back door into your gcc may have been smart
I suppose anything to raise the bar on the attack would seem worthwhile.
Countering the trusting trust attack Posted Feb 3, 2010 4:40 UTC (Wed) by dwheeler (guest, #1216) [Link]
> The attacker who inserted a back door into your gcc may have been smart enough to make it also able to insert the same back door into pcc, or any other compiler you can imagine...
Fair enough, but it's harder to subvert multiple organizations, and the defender gets to choose which compiler to use as the second compiler (call it the "trusted" or the "check" compiler). So, choose the one that's unlikely to be subverted the same way. If you don't believe in any, then:
> But it seems like it'd be a more effective approach to write a C compiler in Forth or something else that is simple enough that you could write a compiler for *it* in assembler (or machine code, if you don't trust the assembler...)...
Okay, go ahead and write another compiler yourself. That doesn't conflict with the DDC approach.
Now, you could just use that compiler instead of GCC, but everyone else still has the same problem... how can they trust YOUR compiler? And if you use it to compile another compiler (say GCC) in one step, again, how can anyone else trust the results of that GCC executable?
One answer is to use your C-in-Forth compiler to compile the original compiler source code (say GCC), then use THAT compiler executable to compile the original compiler source code again. Given certain assumptions described in the dissertation, the resulting executable should be exactly the same as your original executable. Once you've shown that they are equal, then that means either both were subverted in the same way, OR that the original executable isn't subverted.
Countering the trusting trust attack Posted Feb 3, 2010 13:25 UTC (Wed) by hppnq (guest, #14462) [Link] how can they trust YOUR compiler? They can't, that's the principle of the Thompson attack.
The suggestion was -- and I think it is the only correct one -- that the compiler used to compile the compiler-compiler does not need to be compiled itself. If it does need to be compiled, the question remains: what compiler will you use to do that?
But can you tell which conclusion is the right one without having to assume that the original executable was not subverted in the first place? It seems to me that a meaningful conclusion can be drawn only when the two executables are not the same, so you can positively identify a subverted compiler.
Countering the trusting trust attack Posted Feb 3, 2010 23:36 UTC (Wed) by dwheeler (guest, #1216) [Link]
> The suggestion was -- and I think it is the only correct one -- that the compiler used to compile the compiler-compiler does not need to be compiled itself. If it does need to be compiled, the question remains: what compiler will you use to do that?
As I discuss in the dissertation, malicious compilers must have triggers and payloads to produce subverted results. If you avoid their triggers and payloads, then it won't matter if they're malicious. For example, a malicious compiler cM may have triggers that affect compilations of its source code, but not for another compiler cQ. So you can use cM to compile the source code of cQ, even though cM is malicious, and have a clean result.
(It's a little more complicated than that; see the dissertation for the gory details.)
Countering the trusting trust attack Posted Feb 4, 2010 7:51 UTC (Thu) by hppnq (guest, #14462) [Link] For example, a malicious compiler cM may have triggers that affect compilations of its source code, but not for another compiler cQ. So you can use cM to compile the source code of cQ, even though cM is malicious, and have a clean result. Eaxactly. But any of the N program-handling components of the build system may be subverted (and not necessarily the same one at each compilation, I suppose), so in order to make a reasonable assumption you have to make sure that none of the N components harbours a payload or trigger. So you have to verify the linker, loader, assembler, kernel, firmware -- i.e., you have to be on completely independent platforms, for both the compilation and verification. I can't see how you can reasonably assure that this is indeed the case, unless you make the assumption that enough components can be trusted. Which you can't, unless you literally assemble everything yourself. ;-) Obviously, practically there is a lot you can do to minimize the chance that someone unleashes the Thompson attack on you. But you can't reduce this chance to zero, so the question is the same as always: is an attacker motivated enough to break through your defense? I am quite sure there are compilers that are not public, to make this particular barrier more difficult. But those are not used to build global financial or even governmental infrastructures. Anyway, I'll shut up now and read the dissertation, it is an interesting topic. Thanks David, and belated congratulations! :-)
Countering the trusting trust attack Posted Feb 3, 2010 4:22 UTC (Wed) by dwheeler (guest, #1216) [Link] My web page on countering trusting trust through diverse double-compiling (DDC) has all the details on my DDC approach. DDC uses a second compiler to detect the trusting trust attack, and it's perfectly fine if the second compiler is also subverted; DDC merely presumes that the second compiler isn't subverted in exactly the same way. Nix's posting is a nice summary its implications. As nix says, DDC 'reduces to the problem to "you can't trust compilers produced by a cooperating malevolent group, nor code compiled with those compilers". But if you have several compilers, some of which are trustworthy *or are produced by malevolent groups that are not in communication*, then those compilers will not introduce the Thompson hack into the *other* compilers when compiling them, and the attack falls apart. This is a much harder bar for attackers to leap over: from subverting one compiler, they have to subvert every compiler you might possibly use targetting that architecture if they are to go undetected.' There are lots of details on that website, including the entire dissertation. The dissertation includes mathematical proofs and demonstrations with several open source software compilers (including GCC). By the way, the DDC approach can only be applied if you have the source code. So DDC gives an advantage to compilers whose source code is publicly available, including OSS compilers.
Countering the trusting trust attack Posted Feb 3, 2010 8:53 UTC (Wed) by paulj (subscriber, #341) [Link]
Hi,
I've replied to Nix. The work is nice, no doubt, but it still requires 1 absolutely
Do you think the "Fully" in the title of your thesis is perhaps unfortunate
Countering the trusting trust attack Posted Feb 3, 2010 23:24 UTC (Wed) by dwheeler (guest, #1216) [Link]
> The work is nice, no doubt, but it still requires 1 absolutely trusted compiler, which would have to be written (or verified/assumed)...
It does not have to be absolutely trusted, in the sense of being perfect on all possible inputs. It can be subverted, and/or have bugs, as long as it will compile the compiler-under-test without triggering a subversion or bug.
> Do you think the "Fully" in the title of your thesis is perhaps unfortunate though? Your work seems to re-enforce Thompson's result rather than fully counter it, surely?
No, it's not unfortunate. It's intentional.
Thompson's "trusting trust" attack is dead. Thompson correctly points out a problem with compilers and other lower-level components, but his attack presumes that you can't easily use some other system that acts as a *check* on the first. It's not just that you can recompile something with a different compiler; people noted that in the 1980s.
A key is that DDC lets you *accumulate* evidence. If you want, you can use DDC 10 times, with 10 different trusted compilers; an attacker would have to subvert ALL TEN trusted compilers *AND* the original compiler-under-test executable to avoid detection. Fat chance.
Countering the trusting trust attack Posted Feb 3, 2010 23:40 UTC (Wed) by paulj (subscriber, #341) [Link]
Thanks for your reply. Again, I stress that I appreciate the practical benefits
of your approach.
I saw the caveat in the thesis about the trusted compiler-compiler only
Your approach still rests in complete trust in one compiler, according to your
See my other comment about how viruses have advanced from Thompson's
Anyway, I'll leave it there.
Countering the trusting trust attack Posted Feb 4, 2010 23:11 UTC (Thu) by bronson (subscriber, #4806) [Link]
> Your approach still rests in complete trust in one compiler
No, it doesn't. David described this in an ancestor post. It just rests on the assumption that a single group of attackers can't subvert every single one of your compilers.
Countering the trusting trust attack Posted Feb 4, 2010 23:54 UTC (Thu) by nix (subscriber, #2304) [Link]
David also described in a recent post how you can ensure that your
compiler groups weren't maliciously cooperating: make sure your compilers are very different ages. This will only get *better* as the years roll past, especially once Moore's Law grinds to a halt: if one compiler is a hundred years older than the other, unless there's an immortal on the development team there's no *way* they share members. (These days of course this gap is impractical because computers are changing too fast.)
Countering the trusting trust attack Posted Feb 5, 2010 0:30 UTC (Fri) by Baylink (subscriber, #755) [Link]
In particular, this works very well if your check-compiler was shipped *when your target compiler/platform did not even exist yet*.
It would be hard to have hot-wired an early-90s IRIX compiler to break GCC4/Linux.
Countering the trusting trust attack Posted Feb 5, 2010 19:33 UTC (Fri) by paulj (subscriber, #341) [Link]
How does it get better exactly? Old software doesn't come sandwiched,
ossified between rock strata that can further attest to its obvious age.
You're still going to have to determine whether or not the bag of bits you have
The "they old author can't have thought of future compilers" argument seems
I know David's paper frames the problem so that the attack in fact does have
Countering the trusting trust attack Posted Feb 5, 2010 19:44 UTC (Fri) by Baylink (subscriber, #755) [Link]
> How does it get better exactly? Old software doesn't come sandwiched, ossified between rock strata that can further attest to its obvious age.
Sure it does. :-)
There are lots of things which make it difficult to run really old software on newer platforms, and the more obstacles you place in the way of a notional IRIX Trusting-attack implementor, the less likely you make an outcome positive to him.
> You're still going to have to determine whether or not the bag of bits you have before you really is the same as that old compiler you want to put your faith in. You'll have to trust your md5sum binary (oops) and you'll have to trust MD5. Oops. And you're still trusting the original compiler author.
Yes, but what you're trusting him to do *now* is to have written a compiler which could properly identify and mangle a compiler which did not even exist at that time. And compilers are sufficiently different from each other syntactically that I don't think that attack is possible even in theory, though clearly, "I don't think" isn't good enough for our purposes here. :-).
> The "the old author can't have thought of future compilers" argument seems weak. Viruses are much more sophisticated these days - there's no need the attack has to be limited to specific implementations of software.
Well, I think that depends on which attack we're actually talking about here, and "virus" doesn't really qualify. The Trusting attack was a compiler-propagated Trojan Horse, a much more limited category of attack than "viruses these days", and therefore even harder to implement.
I'm not sure why failing to expect clairvoyance from an earlier-decade's attack author is a weak approach, either. :-)
Countering the trusting trust attack Posted Feb 5, 2010 21:42 UTC (Fri) by paulj (subscriber, #341) [Link]
Thompson implementing his attack as a compiler attack is a detail, primarily
because source code was the normal form of software interchange but the basic compiler toolchain obviously still required passing around binaries. In short it was the *only* place he could have implemented an attack by subverting binaries. His paper is explicit that the compiler attack is merely a demonstration of a more fundamental problem of having to place trust in computer systems. Particularly, he mentions microcode as a possible level of attack - clearly a completely different thing from compiler level and indication that Thompson was making a very general point.
To think that Thompson's attack is only about compilers is surely to miss the
Also, I don't expect clairvoyance. Indeed, you miss my point about which
I think perhaps I should properly write up my criticism...
Countering the trusting trust attack Posted Feb 5, 2010 21:52 UTC (Fri) by Baylink (subscriber, #755) [Link]
Because I am a believer in the traditions of science, yes, I think it would be an excellent idea if you wrote up formally your problems with his paper...
which I *promise* I'm going to read, tonight while I wait for a server upgrade to finish. :-)
And certainly any level of the stack can be attacked, and I understand that was his point. But one either has to say "there's no practical way for me to validate the microcode of the CPU, and thus there's a practical limite to what I can verify", or one has to -- in fact -- do that validation.
If one can.
As we note on RISKS regularly, there are two issues at hand here: "pick your own low-hanging fruit", ie: make sure you apply extra security balm equally to all layers of your problem (as adjusted by your threat estimates at each layer), and "know your CBA": the amount of security at all levels you apply has to be in keeping with not only your threat estimate, but with what the bad guys can *get*.
This is, in particular, the part of the issue that terrorists throw monkey wrenches into: trying to inspire asymmetrical responses to what are, objectively, low-level threats. Your opponent wears himself out on the cape and never sees the sword. Bruce Schneier likes to address this issue.
Countering the trusting trust attack Posted Feb 5, 2010 23:05 UTC (Fri) by nix (subscriber, #2304) [Link]
Of course paulj's attack is possible in theory. We just need strong AI
first.
Countering the trusting trust attack Posted Feb 5, 2010 23:03 UTC (Fri) by nix (subscriber, #2304) [Link]
You misunderstand. I'm not saying 'if you prove that this compiler is old
then you will invariably detect the Thompson hack' I'm saying 'if it is likely that this compiler is old then your chances of detecting the Thompson hack go way up'.
(And the Thompson hack *was* specifically relating to quined attacks on
Countering the trusting trust attack Posted Feb 10, 2010 9:45 UTC (Wed) by hppnq (guest, #14462) [Link] So, how about "yum update"? ;-)
Countering the trusting trust attack Posted Feb 3, 2010 17:50 UTC (Wed) by Baylink (subscriber, #755) [Link]
I will admit up front to not having yet checked out your site, I'm at work just now. But if your test is "both compilers produce the same object code", then even both compilers *not* being subverted will not guarantee that.
If I use compilers A and B to build G(cc), the A-G and B-G objects will not necessarily be byte-identical, and it doesn't *matter* what object they each in turn produce, because that would have to be am exhaustive search, which is impossible.
Or are you suggesting that A-G and B-G then be used to again compile Gcc, and *those* binaries be compared? That would tell you that either A and B were not subverted, or were subverted in exactly the same way...
but how are you authenticating your GCC sources?
(If the answer is "read the damn paper, idiot", BTW, just say that. :-)
Countering the trusting trust attack Posted Feb 3, 2010 23:29 UTC (Wed) by dwheeler (guest, #1216) [Link]
Ummm... let me just say "read the paper, please" :-). I'm fully aware that compiling the same source with different compilers will (normally) produce different executables.
> Or are you suggesting that A-G and B-G then be used to again compile Gcc, and *those* binaries be compared? That would tell you that either A and B were not subverted, or were subverted in exactly the same way...
That's the basic idea, sort of. Given certain preconditions, you can even recreate the original executable with a different starting compiler.
Security in the 20-teens Posted Feb 3, 2010 8:46 UTC (Wed) by paulj (subscriber, #341) [Link]
You've restated what I wrote, hence I don't disagree with you.
Note that we don't know how hard this bar would be. There are things like
Next, as dwheeler also notes in his paper, it may be hard to obtain another
So this still seems to boil down to "you have to write (or verify all the source)
I'm not poo-poo'ing the work per se, just saying this good work is slightly
Security in the 20-teens Posted Feb 3, 2010 12:33 UTC (Wed) by paulj (subscriber, #341) [Link]
Another thing to consider:
There's nothing to stop the author of an compiler subverting its binaries such
Thinking in terms of a compiler specifically looking for login is ignoring the huge
I.e. in this discussion we're assuming DDC means you need to subvert 2
Anyway.
Security in the 20-teens Posted Feb 4, 2010 22:39 UTC (Thu) by dwheeler (guest, #1216) [Link]
> There's nothing to stop the author of an compiler subverting its binaries such that *generally* infects all binaries it touches, such that those binaries then infect all other binaries they touch (e.g. by hooking open), and this infection could also introduce system-binary specific attacks as/when it detected it was running as part of those programmes.
An author can do that, but such an author risks instantaneous detection. The more general the triggers and payloads, the more programs that include corrupted code... and thus the more opportunities for detection.
For example, if compiling "hello world" causes a corrupted executable to be emitted, then you can actually detect it via inspection of the generated executable. Even if the system shrouds this, examining the bits at rest would expose this ruse.
Besides, as I talk about in the dissertation, the "compiler" you use does NOT need to simply include a compiler as it's usually considered. You can include the OS, run-time, and compiler as part of the compiler under test. You need the source code for them, but there are systems where this is available :-).
I have an old SGI IRIX machine that I hope to someday use as a test on a Linux distro with glibc and gcc. In this case, I have high confidence that the IRIX is as-delivered. I can feed it the source code, and produce a set of executables such as OS kernel, C run-time, and compiler as traditionally understood. If I show that they are bit-for-bit identical, then either (1) the SGI IRIX system executable suite when used as a compiler has attacks that work the same way against the Linux distro written many years later, or (2) the Linux distro is clean.
I talk about expanding the scope of the term "compiler" in the dissertation.
> I.e. in this discussion we're assuming DDC means you need to subvert 2
Sure it is, and the thesis proves it. However, be aware that I very carefully define the term "compiler". In the dissertation, a compiler is ANY process that produces an executable; it may or may not do other things. For example, a compiler may or may not include the OS kernel, runtime, etc. Anything NOT included in the compiler-under-test is, by definition, not tested. If you want to be sure that (for example) the OS kernel doesn't subvert the compilation process, then you include it as part of the compiler-under-test during the DDC process.
Security in the 20-teens Posted Feb 5, 2010 19:19 UTC (Fri) by paulj (subscriber, #341) [Link]
Did SGI publish secure hashes of your IRIX software?
If yes, I bet it's using MD5 at best. Hashes seem to have quite limited lifetimes.
If no, how can you know the system today is as it was before? If you say "cause
|
|||||||||||||