Reproducible builds are _amazing_. Just think about it: you are assured that the binary you are using corresponds to the source code. It is one of those ideas that makes you think why wasn't this done before?
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/
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.
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.
> 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.
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?
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.
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.
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.
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?
> 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.
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.
> 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.
Ideally one of them is not compromised. But if both are compromised but by different backdoors, the resulting binary will not be bit-for-bit identical (as they include different backdoors). So you can still detect it, and that's really all DDC can do.
The only way to get a bit-for-bit identical binary from two compromised compilers is if they both have the same backdoor.
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.
You are not assured the binary corresponds to the source code. Understanding why and eliminating this misconception is vital for FOSS community to prevent the saboteurs from getting in a better position of attack. A reproducible build by X different parties only shows that the source code was converted into a binary the same way X times. The conversion process could be malicious, buggy, and so on. The binary might be defective or a rootkit. This work does not mean the binary is trustworthy.
Solving source-to-binary correspondence is a tougher problem whose solution I linked to in a comment below. You have to deal with malicious developers, interface issues, input validation, basic compiler bugs, optimization-induced security failures, undefined behavior, bootstrapping, and distribution. These projects mainly help with just that last part whereas most compiler-related, security failures are compiler/optimization bugs. Certifying compilers plus subversion-resistant development methodology and tools are only way to address others.
Note: If you're curious, the cutting edge of this research is the CertiCoq project that is trying to produce an executable straight from a specification in Coq theorem prover. Many projects that eliminate entire classes of problems rely on Coq for specification of behavior and/or proof it's correct. Examples are CompCert compiler, Quark browser, and Chlipala's Bedrock. These typically get extracted into ML for regular compilation. A verified, transformation from Coq specification to executable code would be quite a leap past that and the ultimate tool for proving correctness of other tools. Especially true given how many solutions like above are built with it. They might automatically benefit. Work in progress, though.
> A more radical extension to the former approach is to actually check everything in your version control system. Everything as in the source of every single tool. That’s how it’s working when you are “building the world” on BSD-like systems. That’s also how Google is doing it internally. To make absolutely sure that everything is checked-in, you can even use “sandboxing” mechanisms
> Google recently started open-sourcing the tool they use internally to drive such large scale builds under the name Bazel. So despite its syntax that I personally find hard to read, it’s probably worth checking out.
Can anyone comment on the differences between Bazel and Debian's reproducible builds?
Is the "Google is doing it internally" the same as Bazel? (they are eating their dog food [1])
If it is then, does Bazel allow building from a reference VM or docker instead of building every tool and library from source?
What I'd like to know is what is worth adopting if you're in a small company (not a AmaGooFaceTwi).
What do you have to do to get Basel to "build" a target that its designers have never encountered? The biggest problem I have with modern build systems is that they invest a lot in building specific types of artifacts. For instance, you might be able to compile and link a C program in three or four lines. In exchange, they fail miserably to account for situations like statically linking raw binary data into an executable or facilitating the automation of a target image build. So it's usually easy to build a desktop application but not much else.
How easy would it be to automate a complete Android image build in Bazel?
This is really important work, hopefully it is completed as soon as possible.
It basically allows multiple reputable people to independently build the code and sign a statement that a given source code hash produces a given binary hash (and that the source code hash is the correct one for a given package), and have the presence of at least a certain amount of these signatures be verified on package installation.
This means that it will no longer be possible to backdoor Debian without changing source code by compromising the main build infrastructure.
24 comments
[ 4.3 ms ] story [ 89.7 ms ] threadps: the first minute seem silent but it's not a bug.
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.
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.
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/ https://github.com/gittup/tup/
[1] http://gittup.org/gittup/
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?
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.
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.
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.
> 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.
Ideally one of them is not compromised. But if both are compromised but by different backdoors, the resulting binary will not be bit-for-bit identical (as they include different backdoors). So you can still detect it, and that's really all DDC can do.
The only way to get a bit-for-bit identical binary from two compromised compilers is if they both have the same backdoor.
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
Solving source-to-binary correspondence is a tougher problem whose solution I linked to in a comment below. You have to deal with malicious developers, interface issues, input validation, basic compiler bugs, optimization-induced security failures, undefined behavior, bootstrapping, and distribution. These projects mainly help with just that last part whereas most compiler-related, security failures are compiler/optimization bugs. Certifying compilers plus subversion-resistant development methodology and tools are only way to address others.
Note: If you're curious, the cutting edge of this research is the CertiCoq project that is trying to produce an executable straight from a specification in Coq theorem prover. Many projects that eliminate entire classes of problems rely on Coq for specification of behavior and/or proof it's correct. Examples are CompCert compiler, Quark browser, and Chlipala's Bedrock. These typically get extracted into ML for regular compilation. A verified, transformation from Coq specification to executable code would be quite a leap past that and the ultimate tool for proving correctness of other tools. Especially true given how many solutions like above are built with it. They might automatically benefit. Work in progress, though.
> Google recently started open-sourcing the tool they use internally to drive such large scale builds under the name Bazel. So despite its syntax that I personally find hard to read, it’s probably worth checking out.
Can anyone comment on the differences between Bazel and Debian's reproducible builds?
Is the "Google is doing it internally" the same as Bazel? (they are eating their dog food [1])
If it is then, does Bazel allow building from a reference VM or docker instead of building every tool and library from source?
What I'd like to know is what is worth adopting if you're in a small company (not a AmaGooFaceTwi).
[1] https://plus.google.com/+RipRowan/posts/eVeouesvaVX
How easy would it be to automate a complete Android image build in Bazel?
It basically allows multiple reputable people to independently build the code and sign a statement that a given source code hash produces a given binary hash (and that the source code hash is the correct one for a given package), and have the presence of at least a certain amount of these signatures be verified on package installation.
This means that it will no longer be possible to backdoor Debian without changing source code by compromising the main build infrastructure.