Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 22, 2015 22:07 UTC (Thu) by david.a.wheeler (subscriber, #72896)
Parent article: Lots of progress for Debian's reproducible builds

This is really awesome. I've been following the reproducible (deterministic) build work with interest, and I'm really impressed with the speed of progress. Let's face it, 80% of the huge Debian repository, in such a short time, is quite an accomplishment. I'd like to add a few notes.

First, Debian's not the only one. Fedora is also working on reproducible builds, and I believe there are others.

Second, reproducible builds are also a step towards countering the trusting trust attack (attacks on toolchains). My approach for countering the trusting trust attack, called diverse double-compiling (DDC), first requires that the toolchain portions you care about have a reproducible (deterministic) build. If the whole toolchain is reproducible, it's suddenly much easier to use DDC to counter the trusting trust attack.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 22, 2015 22:33 UTC (Thu) by PaXTeam (guest, #24616) [Link] (16 responses)

DDC doesn't counter the trusting trust attack. it's only a method to produce a trusted toolchain by another, but it does *not* help producing the initial trusted toolchain - you have to do it the hard way, which was Thompson's point.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 22, 2015 22:41 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link] (9 responses)

You can use multiple compilers (PCC to compile CLang to compile GCC). It's theoretically possible for a sufficiently advanced superintelligent agent to write a software that can recognize the source of these compilers, but it's exceedingly unlikely.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 22, 2015 22:56 UTC (Thu) by PaXTeam (guest, #24616) [Link] (8 responses)

it doesn't matter how many compilers you chain together, you have to start with a trusted one or Thompson's attack will apply. also pattern matching one compiler's AST is about the same work as matching another (read: scales linearly with the number of compilers), it's nothing to do with likeliness.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 23, 2015 12:44 UTC (Fri) by gnb (subscriber, #5132) [Link] (1 responses)

The work of backdooring the compiler scales linearly with the number of compilers, but I wouldn't expect the difficulty of making sure each of the relevant compilers ships with the backdoor included to be linear: you have to patch each of N compilers without any of these attempts being noticed.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 23, 2015 18:40 UTC (Fri) by paulj (subscriber, #341) [Link]

If only binaries came in standardised formats, and had general ways to inject code, and lots of well-known hooks to allow that code to execute (well-knowns hooks supplied by the format, by the runtime, and by the specific compiler code). Oh wait, they do.

In other news, "viruses" are a *lot* more sophisticated since Thompson's POC.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 26, 2015 10:11 UTC (Mon) by epa (subscriber, #39769) [Link] (4 responses)

I think the point is that while in principle Thompson's attack will apply, in practice if you have a big tower of compilers (pcc -> clang -> gcc -> gcc v1.0 -> clang -> etc) it will not be possible for the evil code to be propagated all the way through that chain because it's simply too complicated a problem.

As the other poster said you would need a "superintelligent agent" to write a program that's somehow capable of recognizing and Trojaning code from all these different compilers, plus goodness knows how many others that might be thrown into the mix.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 26, 2015 11:43 UTC (Mon) by tao (subscriber, #17563) [Link]

You could always hack binutils instead... Or make...

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 26, 2015 11:43 UTC (Mon) by paulj (subscriber, #341) [Link] (2 responses)

Even just restricting Thompson's attack to compilers (which is artificially restricting his point), it's not complicated at all, because in modern systems all those compilers come in standardised binary formats with some well-known places you can hook your own code into.

Though, I think some people here have unreasonable assumptions about how isolated different compiler authors are from each other. E.g. another article this very week is discussing GCC AST exports for Emacs, and contains a link to a GCC thread where Sun compiler people are posting patches to GCC. Personally, I think it's highly unreasonable to assume that people who develop very in-depth expertise in compilers will only ever work on one implementation. Not my anecdotal experience at all!

If you don't artificially restrict Thompson's attack, then you've still got the rest of the system to verify: all the software, firmware, microcode and hardware.

Good luck with that.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 26, 2015 22:23 UTC (Mon) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

So simply add a couple of cross-compilations to the mix. That also applies to make and other low-level utilities.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 28, 2015 18:27 UTC (Wed) by paulj (subscriber, #341) [Link]

When Debian finish making their build reproducible, they can then try work on reproducible cross-compiles.

Though, I don't see why it would be impossible for an ELF virus to contain payloads for a variety of target architectures (especially those known to be used by the reproducible, cross-compile, build checker), and select the appropriate one to infect newly created files. So, I'm not sure what that would achieve.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted May 29, 2015 1:45 UTC (Fri) by indolering (guest, #102865) [Link]

Perfect security is a myth, the name of the game is increasing the attack cost. Deterministic builds allow us to dramatically increase the cost of certain attacks, which is a net gain in terms of security.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 23, 2015 19:03 UTC (Fri) by smoogen (subscriber, #97) [Link] (5 responses)

I would expect that people looking to attack repeatable builds would figure on where people are most likely to put blind trust in something and exploit that.

Easiest? If the .changes files has to do certain things to make sure the archive is altered to "meet matching criteria" Stick something there which will get run every time that sticks in the exploit.

Hard? Everyone looks at the compiler to "deal with Thompson attack" but no one looks at m4, yacc, lex, Makefiles etc where it is easier to stick in some line noise that no one understands and then explain it away as an accident if they do.

Harder? If the system clock or other parts of the build system have to be derandomized to make sure that parts of various code are built exactly correct.. figure out which settings in such a build system are beneficial for your in-code exploit.

In any case, I could actually see where this sort of build system actually makes trust attacks easier because people will blindly say "well it built the same as the first one... must be clean." and not look at what actually was done to make it build exactly like the other part. [I also wonder what kinds of compiler optimizations have to be turned off to make sure that the code compiles the same.]

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 23, 2015 19:06 UTC (Fri) by smoogen (subscriber, #97) [Link]

I didn't put this in originally and should have. Nothing I am saying is to mean that I don't think that verifiable build systems aren't needed or have good uses. I just think that the amount of "This solves ...." is being over stated and quickly leads to -funroll-loops level of blindness.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 29, 2015 15:55 UTC (Thu) by nix (subscriber, #2304) [Link] (3 responses)

I also wonder what kinds of compiler optimizations have to be turned off to make sure that the code compiles the same

Thanks to -frandom-seed, none to speak of. You just need to provide the same seed. (Well, none to speak of in the deterministic set of default optimizations. I presume that profile-guided optimizations are also out of the question, unless you distribute the .gcno files, etc, which is unlikely to happen!)

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Feb 3, 2015 22:29 UTC (Tue) by nix (subscriber, #2304) [Link] (2 responses)

Of course this is wrong. Profile-guided optimizations *that depend on nondeterministic test runs* are out of the question. If the test run is deterministic (thus the branches taken are unchanging across multiple runs), then of course profile-guided optimizations are not incompatible with reproducible builds.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Feb 4, 2015 8:55 UTC (Wed) by cesarb (subscriber, #6266) [Link] (1 responses)

Does profile-guided optimization add profiling code to all branches, or does it use a timer (and a signal) to sample the basic blocks? If it uses a timer, it won't be deterministic.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Feb 17, 2015 19:42 UTC (Tue) by nix (subscriber, #2304) [Link]

It instruments arcs between basic blocks, so it's deterministic.

Awesome! Fedora also, and this is a step towards countering "Trusting Trust" toolchain issues

Posted Jan 23, 2015 18:37 UTC (Fri) by paulj (subscriber, #341) [Link]

Your DDC work is cool, and people working on doing reproducible builds of entire distros is cool, but, really, it's *reinforcing* Thompson's point about trust-roots, not countering. Anyway....