4 ms·

The reason it was not done before is that we did not find a solution to the "trusting trust" issue until quite recently. David Wheeler solved the problem and di

The reason it was not done before is that we did not find a solution to the "trusting trust" issue until quite recently. David Wheeler solved the problem and did his PhD dissertation on this in 2009: http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/ Once that was solved, reproducible builds became a lot more interesting as we no longer needed to trust the toolchain. As a result, all of the reproducible build projects mentioned in the PDF (debian, tor, bitcoin being the pioneers AFAIK) got started.

geofft 11y ago
Reproducible builds are useful for purposes other than security, though. One day at work I found that we'd uploaded an updated binary artifact without checking in updated source (due to honest human error). We needed to patch the source, and if we dropped any patches, that could have caused regressions. I had a good guess about what the source was, but comparing the resulting binary involved dumping the resulting text sections and diffing them, and ignoring things like the debug sections. It would have been much simpler if I could simply recompile and make sure that the binaries were identical. If you're shipping binaries via a delta-update system (send the diff between what the user already has, and the new version), it's useful for things to change as little as possible. Reproducible builds allow you to send down an entire system (large application, bootable image, etc.) by recompiling the whole thing, which is good for build cleanliness, and trusting that unchanged files won't have changed. While not quite "reproducible builds", a lot of the related work means that if you apply a tiny patch to source code, the diff of that object file is probably equally tiny. I agree that this is a sort of "of course the compiler shouldn't introduce nondeterminism" thing. It happens to be primarily useful for security, but even in a non-security context, it's a nice base property to have.
- gavinpc 11y ago
  > Reproducible builds are useful for purposes other than security, though. I've been using an off-the-wall build system called Tup [0], which is designed to support optimally fast incremental builds (i.e. build times that don't scale with the codebase), and it calls for some of the same constraints, chiefly, a strictly deterministic build (no timestamps, control access to environment variables and all file IO). It even deletes generated files when they leave the graph for any reason (being philosophically opposed to a "clean" target). It's an opinionated tool, but it does deliver on its promise. The author also maintains (or at least used to maintain) a Linux repo/distro that is somewhat in the spirit of the OP, at least to the extent that git implements a kind of blockchain.[1] So yeah, there's considerable overlap between this and properties that I'd think everyone would want. The cost is a change in some habits. [0] http://gittup.org/tup/ http://gittup.org/tup/ https://github.com/gittup/tup/ https://github.com/gittup/tup/ [1] http://gittup.org/gittup/ http://gittup.org/gittup/
  - josteink 11y ago
    > a strictly deterministic build (no timestamps In some environments, you really need a timestamp, otherwise your code will be treated as untrusted/unsigned by the OS after the signing certificate expires. This for instance applies to X509-signed code and EXE-files on Windows. Does this mean that if you want reproducable builds, you have to use a signing-certificate valid looong into the future? Are there any other ways? Are there any downsides? Anyone have opinions or experience here?
    - throwaway7767 11y ago
      I'm not familiar with how code signing for PE executables is performed, but I imagine it's done as a seperate step after compilation? If so, what matters is that the binary pre-signing is reproducible. Ideally we should be able to remove the signature for the binary, build our own, and get a bit-identical binary.
      - geofft 11y ago
        Yeah, it's done as a separate step, and I believe it's an independent section of the file (such that you can add and remove it at will). If you recompile a bit-identical unsigned binary, you should be able to take the previous signature (including third-party timestamp!) and snap it onto that binary. You just have to treat that signature itself as data. I believe this is actually roughly the approach Debian wants to take with Secure Boot: build the loader (which is a PE binary), sign it on a secure machine, then drop the signature into the Debian source package and rebuild it. That way anyone can grab the Debian source package and `dpkg-buildpackage` it and get a validly signed bootloader, provided they haven't changed the sources and they're using the same toolchain.
        voltagex_ 11y ago
        Wow, I didn't even think of this usecase before seeing it mentioned here. I hope they make some kind of reproducible-pbuilder which pulls the right version of the toolchains - pbulder/sbuild/cowbuild can be really difficult to set up.
wyldfire 11y ago
As a practical matter, how do you go about getting the trusted compiler for DDC? Does this include an audit of the source for that compiler and/or the path that the compiler source or compiler binaries take to their destination?
- nickpsecurity 11y ago
  Now you're thinking in right direction.
- throwaway7767 11y ago
  > As a practical matter, how do you go about getting the trusted compiler for DDC? Does this include an audit of the source for that compiler and/or the path that the compiler source or compiler binaries take to their destination? No, the important bit to realise about DDC is that you don't need a compiler you know to be trusted (otherwise, of course, there would be no point). You take two different compilers, and you just have to trust that they don't both contain the same backdoor. The most concise description I've seen is in Bruce Schneier's writeup. Quoting him: Suppose we have two completely independent compilers: A and T. More specifically, we have source code SA of compiler A, and executable code EA and ET. We want to determine if the binary of compiler A -- EA -- contains this trusting trust attack. Step 1: Compile SA with EA, yielding new executable X. Step 2: Compile SA with ET, yielding new executable Y. Since X and Y were generated by two different compilers, they should have different binary code but be functionally equivalent. So far, so good. Now: Step 3: Compile SA with X, yielding new executable V. Step 4: Compile SA with Y, yielding new executable W. Since X and Y are functionally equivalent, V and W should be bit-for-bit equivalent.
  - wyldfire 11y ago
    The first I'd heard of DDC was here, so I might misunderstand some parts of the concept. But Wheeler seems to state it pretty plainly in this summary: > 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. I'd speculate that you need at least one of the compilers to be trusted otherwise they could both be subverted to produce X, Y that would produce matching V, W binaries with the attack still in place on both.
nickpsecurity 11y ago
It's actually been known for a while as I described in this comment with bootstrapping method in the reply after it: https://news.ycombinator.com/item?id=10182282 https://news.ycombinator.com/item?id=10182282 That addresses a huge range of problems while Wheeler's work mainly addresses the Thompson attack, which actually isn't the main problem in practice. Optimization-induced defects, regular compiler bugs, and undefined behavior are more likely to hit you. There's also been work showing how to use them intentionally to produce source that looks OK but is subverted by the bug(s). There's also clever subversions possible by compiler authors themselves. So, no, you still need to trust the toolchain even if you've verified you received the right one. Hence, the more thorough approaches like I described that eliminate more risks. Good to know mainstream at least finally cares about the build problem. Wheeler indeed got word out most effectively on this with his SCM page (below). They'll gradually learn of the other issues and maybe try to solve them. A better foundation would be a nice start, though. An even better start would be building on stuff that already does what they're trying to do better than they're doing it. That's rare by FOSS crowd but it would really help them here given all the work in academia on this problem. http://www.dwheeler.com/essays/scm-security.html http://www.dwheeler.com/essays/scm-security.html

geofft 11y ago

Reproducible builds are useful for purposes other than security, though. One day at work I found that we'd uploaded an updated binary artifact without checking in updated source (due to honest human error). We needed to patch the source, and if we dropped any patches, that could have caused regressions. I had a good guess about what the source was, but comparing the resulting binary involved dumping the resulting text sections and diffing them, and ignoring things like the debug sections. It would have been much simpler if I could simply recompile and make sure that the binaries were identical. If you're shipping binaries via a delta-update system (send the diff between what the user already has, and the new version), it's useful for things to change as little as possible. Reproducible builds allow you to send down an entire system (large application, bootable image, etc.) by recompiling the whole thing, which is good for build cleanliness, and trusting that unchanged files won't have changed. While not quite "reproducible builds", a lot of the related work means that if you apply a tiny patch to source code, the diff of that object file is probably equally tiny. I agree that this is a sort of "of course the compiler shouldn't introduce nondeterminism" thing. It happens to be primarily useful for security, but even in a non-security context, it's a nice base property to have.

gavinpc 11y ago
> Reproducible builds are useful for purposes other than security, though. I've been using an off-the-wall build system called Tup [0], which is designed to support optimally fast incremental builds (i.e. build times that don't scale with the codebase), and it calls for some of the same constraints, chiefly, a strictly deterministic build (no timestamps, control access to environment variables and all file IO). It even deletes generated files when they leave the graph for any reason (being philosophically opposed to a "clean" target). It's an opinionated tool, but it does deliver on its promise. The author also maintains (or at least used to maintain) a Linux repo/distro that is somewhat in the spirit of the OP, at least to the extent that git implements a kind of blockchain.[1] So yeah, there's considerable overlap between this and properties that I'd think everyone would want. The cost is a change in some habits. [0] http://gittup.org/tup/ http://gittup.org/tup/ https://github.com/gittup/tup/ https://github.com/gittup/tup/ [1] http://gittup.org/gittup/ http://gittup.org/gittup/
- josteink 11y ago
  > a strictly deterministic build (no timestamps In some environments, you really need a timestamp, otherwise your code will be treated as untrusted/unsigned by the OS after the signing certificate expires. This for instance applies to X509-signed code and EXE-files on Windows. Does this mean that if you want reproducable builds, you have to use a signing-certificate valid looong into the future? Are there any other ways? Are there any downsides? Anyone have opinions or experience here?
  - throwaway7767 11y ago
    I'm not familiar with how code signing for PE executables is performed, but I imagine it's done as a seperate step after compilation? If so, what matters is that the binary pre-signing is reproducible. Ideally we should be able to remove the signature for the binary, build our own, and get a bit-identical binary.
    - geofft 11y ago
      Yeah, it's done as a separate step, and I believe it's an independent section of the file (such that you can add and remove it at will). If you recompile a bit-identical unsigned binary, you should be able to take the previous signature (including third-party timestamp!) and snap it onto that binary. You just have to treat that signature itself as data. I believe this is actually roughly the approach Debian wants to take with Secure Boot: build the loader (which is a PE binary), sign it on a secure machine, then drop the signature into the Debian source package and rebuild it. That way anyone can grab the Debian source package and `dpkg-buildpackage` it and get a validly signed bootloader, provided they haven't changed the sources and they're using the same toolchain.
      - voltagex_ 11y ago
        Wow, I didn't even think of this usecase before seeing it mentioned here. I hope they make some kind of reproducible-pbuilder which pulls the right version of the toolchains - pbulder/sbuild/cowbuild can be really difficult to set up.

wyldfire 11y ago

As a practical matter, how do you go about getting the trusted compiler for DDC? Does this include an audit of the source for that compiler and/or the path that the compiler source or compiler binaries take to their destination?

nickpsecurity 11y ago
Now you're thinking in right direction.
throwaway7767 11y ago
> As a practical matter, how do you go about getting the trusted compiler for DDC? Does this include an audit of the source for that compiler and/or the path that the compiler source or compiler binaries take to their destination? No, the important bit to realise about DDC is that you don't need a compiler you know to be trusted (otherwise, of course, there would be no point). You take two different compilers, and you just have to trust that they don't both contain the same backdoor. The most concise description I've seen is in Bruce Schneier's writeup. Quoting him: Suppose we have two completely independent compilers: A and T. More specifically, we have source code SA of compiler A, and executable code EA and ET. We want to determine if the binary of compiler A -- EA -- contains this trusting trust attack. Step 1: Compile SA with EA, yielding new executable X. Step 2: Compile SA with ET, yielding new executable Y. Since X and Y were generated by two different compilers, they should have different binary code but be functionally equivalent. So far, so good. Now: Step 3: Compile SA with X, yielding new executable V. Step 4: Compile SA with Y, yielding new executable W. Since X and Y are functionally equivalent, V and W should be bit-for-bit equivalent.
- wyldfire 11y ago
  The first I'd heard of DDC was here, so I might misunderstand some parts of the concept. But Wheeler seems to state it pretty plainly in this summary: > 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. I'd speculate that you need at least one of the compilers to be trusted otherwise they could both be subverted to produce X, Y that would produce matching V, W binaries with the attack still in place on both.

nickpsecurity 11y ago

It's actually been known for a while as I described in this comment with bootstrapping method in the reply after it: https://news.ycombinator.com/item?id=10182282 https://news.ycombinator.com/item?id=10182282 That addresses a huge range of problems while Wheeler's work mainly addresses the Thompson attack, which actually isn't the main problem in practice. Optimization-induced defects, regular compiler bugs, and undefined behavior are more likely to hit you. There's also been work showing how to use them intentionally to produce source that looks OK but is subverted by the bug(s). There's also clever subversions possible by compiler authors themselves. So, no, you still need to trust the toolchain even if you've verified you received the right one. Hence, the more thorough approaches like I described that eliminate more risks. Good to know mainstream at least finally cares about the build problem. Wheeler indeed got word out most effectively on this with his SCM page (below). They'll gradually learn of the other issues and maybe try to solve them. A better foundation would be a nice start, though. An even better start would be building on stuff that already does what they're trying to do better than they're doing it. That's rare by FOSS crowd but it would really help them here given all the work in academia on this problem. http://www.dwheeler.com/essays/scm-security.html http://www.dwheeler.com/essays/scm-security.html