User: Password:
|
|
Subscribe / Log in / New account

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

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

Posted Jun 25, 2013 14:07 UTC (Tue) by paulj (subscriber, #341)
In reply to: Diverse Double-Compiling (DDC) counters "trusting trust" by dlthomas
Parent article: Van den Oever: Is that really the source code for this software?

Except that DDC complains not just on subversion, but also because of bugs and even deliberate features that lead to non-binary-exact reproducible builds. DDC can not distinguish between normal bugs and 'malicious' bugs - those inserted by an evil compiler author/distributor in order to frustrate DDC. Indeed, assume there are malicious compiler writers out there. They do not need to collaberate in order to subvert DDC, all they need to do is insert apparently mundane bugs or features that mean no two compiles reliably build the exact same binary. Just like tcc had.

You will not be able to tell whether they'd be silly bugs or malicious. The evil compiler authors have no need to collude, other than act to frustrate DDC. And you won't know they are evil.

Also, as per Thompson, you need to verify not just the compiler, but large parts of the system. David says DDC could be applied there too. Other people in these comments have noted just how difficult it is to get reliable builds at system levels and how short-scoped they are in time (even if you can get a reliably reproducible build).

Further, even if all your compilers DO build the same binary, you are still trusting the compiler authors have not colluded AND that all compilers have independent authors/distribution-teams. While it may be possible to have more confidence in these assumptions than in assuming 1 compiler is not subverted, these assumptions are still not absolutely, 100% safe.

Thompson's point was that you simply can not escape having to have /some/ degree of trust, UNLESS, you create ALL the underlying system yourself. It still stands.


(Log in to post comments)

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

Posted Jun 25, 2013 18:51 UTC (Tue) by david.a.wheeler (subscriber, #72896) [Link]

"Except that DDC complains not just on subversion, but also because of bugs and even deliberate features that lead to non-binary-exact reproducible builds. DDC can not distinguish between normal bugs and 'malicious' bugs..." - that's not a problem, that's a good thing. Who, exactly, wants to release code that's wrong? Why omplain about a test that detects problems? Sure, you then have to track back why there's a defect, but that's true for all tests.

"You will not be able to tell whether they'd be silly bugs or malicious. The evil compiler authors have no need to collude, other than act to frustrate DDC. And you won't know they are evil." - You have to gather more data than "DDC didn't work", just like any test. Tests generally say "fail" - you have to gather more info to figure out why it failed, and fix it. But silly bugs are clearly different from trusting trust attacks; trusting trust attacks just don't happen by accident. In fact, my dissertation showed an example - I tested a known-malicious program, and the difference clearly showed that the code was malicious. In that case, the code difference started with an addition that read, "when compiling a login program, do XYZ instead". That's a dead giveaway that something malicious is going on; why would compilation functionality depend on THAT?

"Other people in these comments have noted just how difficult it is to get reliable builds at system levels and how short-scoped they are in time (even if you can get a reliably reproducible build)." - But some folks do manage. The original article noted that, in the given test case, "The binary package that was built from a Debian source package was not identical to the published binary package, but the differences are limited to timestamps and the build id in the executable". That's easily addressed, and I expect it to be easy to tweak Debian's processes to even eliminate those. Fedora's process is much more different, because no one demanded it... but it's not a matter of being impossible.

"Further, even if all your compilers DO build the same binary, you are still trusting the compiler authors have not colluded AND that all compilers have independent authors/distribution-teams. While it may be possible to have more confidence in these assumptions than in assuming 1 compiler is not subverted, these assumptions are still not absolutely, 100% safe." - The Earth is not absolutely, 100% safe. No individual is absolutely, 100% safe. Even formal methods aren't 100% safe because you must always start with some assumption, which might be falsified. You're asking for a level of confidence that we ask of nothing else.

You misunderstand the point of "fully". The point of the term "fully" was to "fully" counter the original problem that there was no way to have independent validation of a compiler. Now you can independently verify what you'll be trusting, to whatever degree you believe is enough.

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

Posted Jun 25, 2013 19:36 UTC (Tue) by paulj (subscriber, #341) [Link]

DDC does not verify. It highlights reproducibility problems. You then need to go investigate those problems to see what is causing them. Most of them will be due to bugs or deliberate features. Indeed, a malicious compiler writer would throw in lots of those, to see if anyone is even trying to do DDC, before ever releasing their malicious subversion. Again, we do *not* live in a world where people are regularly doing DDC of significant parts of the system with *multiple* compilers. Until we do, we do *not* know how easy or difficult it would be. Indeed, if it were easy and DDC provided the verification it promises, why don't we hear more of people doing so?

Next, even if DDC worked for compilers, you're still missing Thompson's point or deliberately taking an artificially restricted view of it. Again, he really did mean the *entire system* - he explicitly mentioned *micro-code* as another level where this attack could be implemented. To fully counter his attack in the abstract requires *full-system* verification.

Even assuming DDC is practical and 100% reliable at the software system level (I've stated why I think it isn't - you disagree): How do you DDC the micro-code? Or the CPU design? Or all the chips in your system?

You bring in Gödel. Thompson's point on trust is as fundamental. Consistent and incomplete, OR complete and inconsistent; re-use the work of others and have to trust it is free of subversion, OR create it all yourself and not have to trust. Imagine a mathematician saying that they've described a complete AND consistent system, for some definition of consistent that isn't quite 100% fully consistent, but hey - nothing is ever fully consistent, is it? Well yeah, that was Gödel's point!

You've described a process, DDC, which you say allows one to re-use the work of others AND not have to trust, for a value of 'not have to trust' that isn't quite 100% free of trust, but hey nothing is ever 100% sure on this earth! Well, yeah... It's still perfectly consistent with Thompson's point - you can't escape trust if you havn't built it all yourself!

Does DDC add something? Quite probably yes! It'd be really interesting to see people try do it regularly (and useful, perhaps - though the rest of us might have to consider how far to trust them ;) ) to evaluate it. But... it's still not countering Thompson's attack, because that attack can not be countered! His point was more fundamental, and abstract, than about compilers subverting compiled binaries.

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

Posted Jun 25, 2013 20:13 UTC (Tue) by david.a.wheeler (subscriber, #72896) [Link]

"DDC does not verify. It highlights reproducibility problems. You then need to go investigate those problems to see what is causing them." - A strange terminology; the same statement is true of a traditional regression test suite. Indeed, any test merely highlights differences between the expected behavior and actual behavior. No test can "verify" in the sense that you seem to imply, since no test, by itself, will tell you in detail why the test failed. Test suites are usually a key part of a "verification" process, so I'm just using the usual meaning of the term (per ISO 15288, etc.). Few people want compilers to incorrectly compile code, or to have malicious code in them; a test that verifies that some of those problems don't exist would typically be part of verification.

"Most of them will be due to bugs or deliberate features. Indeed, a malicious compiler writer would throw in lots of those, to see if anyone is even trying to do DDC, before ever releasing their malicious subversion. Again, we do *not* live in a world where people are regularly doing DDC of significant parts of the system with *multiple* compilers. Until we do, we do *not* know how easy or difficult it would be. Indeed, if it were easy and DDC provided the verification it promises, why don't we hear more of people doing so?" - Well, this is all pretty recent. I only just released the general dissertation in late 2009 (the 2005 ACSAC paper only discussed a much more restricted case). And a lot of folks have decided that the risks of this attack are low today, and thus aren't spending time to counter it. My hope is that there will be more interest in the years ahead. In any case, as a non-gcc-developer I managed to do it with gcc; someone directly involved in a compiler's development would find it even easier for his compiler.

"Next, even if DDC worked for compilers, you're still missing Thompson's point or deliberately taking an artificially restricted view of it. Again, he really did mean the *entire system* - he explicitly mentioned *micro-code* as another level where this attack could be implemented. To fully counter his attack in the abstract requires *full-system* verification. Even assuming DDC is practical and 100% reliable at the software system level (I've stated why I think it isn't - you disagree): How do you DDC the micro-code? Or the CPU design? Or all the chips in your system?" - I discussed this. Section 8.8 talks about lower-level software components like the operating system. Microcode is really just more software, so DDC can still be used (in fact, microcode is often short enough that you can directly inspect it - eliminating the trusting trust attack entirely). Applying DDC to hardware is discussed in section 8.12 of the full dissertation; I discuss it in my presentation too.

"You bring in Gödel. Thompson's point on trust is as fundamental. Consistent and incomplete, OR complete and inconsistent; re-use the work of others and have to trust it is free of subversion, OR create it all yourself and not have to trust. Imagine a mathematician saying that they've described a complete AND consistent system, for some definition of consistent that isn't quite 100% fully consistent, but hey - nothing is ever fully consistent, is it? Well yeah, that was Gödel's point!" - There's a third way, trust but verify. Instead of "re-use something and pray it's not subverted", or "do everything yourself", you can "verify something before you reuse it". You can verify it using other compiler(s) that already exist. You can write your own compiler(s), not because you're going to use them, but because your compiler will be used to verify the compiler you will actually use. Note the big difference in the latter case; you are not "creating it all yourself", but instead "creating a local, simpler tool to help verify the real tool".

"You've described a process, DDC, which you say allows one to re-use the work of others AND not have to trust, for a value of 'not have to trust' that isn't quite 100% free of trust, but hey nothing is ever 100% sure on this earth! Well, yeah... It's still perfectly consistent with Thompson's point - you can't escape trust if you havn't built it all yourself! - I never said, "you don't have to trust". Clearly you have to eventually trust something. My point is that you can use this technique to verify something before you trust it.

Your interpretation of Thompson's paper is different than mine. You seem to think that Thompson's point is that you might have to trust something, and therefore, all is doomed. I think that's not the point at all. Of course you have to trust something. Anyone who uses a bank trusts something. That's boring and not particularly relevant. I think the point of Thompson's paper is that it's difficult to have verification of program-manipulating systems (e.g., compilers). I interpret "trusting trust" as "we must blindly trust something". That's why I say the problem is resolved. We now have a new mechanism for independent verification, one we didn't have before.


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds