Bit by Bit

A question that is more often asked is whether or not you can trust software at all. If you look at the backdoors required by state authorities and the software companies that comply, or the army of criminal hackers that attempt to foist malicious software onto users, your answer might be, "No."

Usually you can trust the distribution to deliver packages that correspond to the source code from which they were built. These packages can be difficult to manipulate because the content of the archives bears the signature of the respective package maintainer's GPG key. However, these safeguards do not work all the time. For example, Linux Mint recently fell victim to a manipulated image and delivered it to its users.

Although Debian sets the bar high, some developers asked themselves several years ago what they could do to further improve security. The resulting idea: Users can check at home, bit-by-bit, whether a package corresponds to the underlying source code. As early as the turn of the millennium, some initial suggestions for reproducible binary packages appeared on the Debian Developers list, but the idea was dismissed as infeasible.

Still Experimental

The project, still in the experimental phase, has again taken up this basic idea known as reproducible builds [1]. After about two years of intensive work, by 2017 with Debian 9 "stretch," the project reached a point at which Debian could be built in at least a partially reproducible way. As a final target, the developers look to ensure that all packages can be reproducibly built and that the tools specially created for this purpose find their way into the Debian infrastructure. This is done to ensure reproducibility in the future.

The clear promise of the reproducible builds project is as follows: Anyone can build identical binary packages of a given source with bit precision at any time (Figure 1). If things go the way that reproducible builds' creators intend, the future definition of free software will include mandatory reproducibility (Figure 2).

Broad Test Base

Debian's reproducible builds team constantly tests in the Debian "Testing," "Unstable," and "Experimental" branches. From the results, it creates not only versatile statistics [3], but it also publishes a weekly news blog [4]. In addition to Debian, other distributions are pushing forward to build binary packages reproducibly, including Arch Linux, Fedora, Subgraph OS, and Tails. Similar initiatives exist in the BSD world (NetBSD, FreeBSD), as well as in projects such as Coreboot, OpenWrt, F-Droid, and Guix.

Debian uses 30 host machines to create reproducible builds. All told, around 180 CPU cores and more than 300GB of RAM are available for amd64, i386, and armhf builds (Figure 3). The tests are managed by Jenkins [5], builders of software for the continuous integration of software projects. A total of 41 scripts with around 10,000 lines of code were developed in the context of the project.

As part of the test, the system builds around 10,000 packages twice. In May 2016, source packages numbering 21,365 from a total of 24,135 were reproducible in Debian, which corresponds to an average of 88.5 percent in the individual branches. "Testing," with more than 90 percent, does better than "unstable" and "experimental."

As of this writing, 1,489 packages still failed to build reproducibly, and the cause was known for two thirds of them. Nevertheless, the project is still far from its target: One of the Debian developers for reproducible builds, Holger Levsen, said in a recent lecture [6] that at present only zero percent of Debian could realistically be built reproducibly. Thus far, reproducible builds has purely been a feasibility study (Figure 4).

Identical Build System

The most important prerequisite for reproducible builds lies in meticulous recording of the build system. It must store details of the tools used in the binary package during the initial build. To do so, it writes the data to a new file called .buildinfo within the structure of the package. In subsequent builds, the srebuild Perl script [7] reads this data back out and makes sure that an identical build system is obtained from snapshot.debian.org [8].

Without the details of the build system, a package cannot be reliably reproduced. Even slightly different instructions (compiler flags) lead to different results at the bit level. The problem is that the extended package structure with .buildinfo adds around 100,000 additional files for each Debian suite. This increases the amount of code by up to 50 percent. To reduce the load on the mirror servers, this additional information will thus only reside directly on the Debian servers.

New Tools

Eighty percent of the technical problems related to reproducibility are caused by new timestamps, as well as different time zones and locales.

Many build tools capture data such as the time and date of the build in a non-deterministic way (i.e., the same steps, given the same input values, produce different results). The strip-nondeterminism library [9] is meant to correct this problem. In the run-up it removes information from the build that could lead to incorrect results (Figure 5).

The Source_Date_Epoch specification [10] was devised to replace these timestamps with deterministic values by using a string to define the seconds since the last modification of the source text after January 1, 1970, 0 hours UTC (i.e., the start of the Unix epoch).

However, not all problems can be solved automatically, so a great deal of additional manual work is needed. Detailed information about the practices used can be found on the Documentation page [11]. Diffoscope [12] also plays a prominent role in understanding why a package cannot be built reproducibly. This tool can compare files or folders in depth (Figure 6) by unpacking the program archive and transforming the binary packages into human-readable formats.

Reproducible builds represents an important step toward the kind of security needed in the future to improve the integrity of a digital existence. However, it is not a panacea: Secret services and organized criminals have means to foist malicious software on the world, with hardly any defense against it.

An example of this is the Trusting Trust attack first described in 1974 [13]. This attack manipulated the binary file of a compiler in such a way that it first recompiled itself. This manipulated compiler then delivered software that was modified in a virtually undetectable way, such as containing backdoors or other nasties.

One Bit Is Enough

Ken Thompson [14], one of the legendary fathers of Unix, also made it quite clear in an amusing speech [15] at an awards ceremony that there is no such thing as absolutely secure software – unless you write your own compiler and build all of the software yourself. Often, a single bit in a 500KB binary package makes the difference between secure and vulnerable software.

This was demonstrated by Tor developers in a talk show [16] at the 31st Chaos Computer Congress (31C3) in 2014 on the basis of an error in the SSH network protocol from 2002 (CVE-2002-0083). There, a single bit decided whether an attacker could gain root privileges on the machine. The lecture also demonstrated an attack that changed the code of a kernel module in memory only. On the screen it appeared to be intact, but the resulting binary package was compromised.

To prevent similar attacks, the idea of reproducible builds began to take shape, initially in projects such as Tor and Bitcoin, because security and trust play a central role in these applications. Both projects had been built in an entirely reproducible way since 2012. Gitian [17], a distribution method that offers a deterministic build process in a container or a virtual machine, provides the underpinnings.

Using Gitian Builder [18], several people can build the package independently of each other, and the environment. If everything is okay, bitwise identical binary packages are the result. Gitian is fine for smaller projects, but for a complete distribution such as Debian, with thousands of source packages, time and staff overhead prevent its use.

Conclusions

Among distributions, Debian is a pioneer of verifiable packages. Meanwhile, other distributions are adopting the infrastructure Debian created in Jenkins and the tools it uses to solve problems and validate the results. For example, Fedora, openSUSE, and Arch Linux can verify the results of Debian and vice versa.

Last year, a cross-distribution meeting was held in Athens, Greece, with more 40 participants; this year will see a repeat (Figure 7). At the beginning of August, the developers of Hardened GNU/Linux [19], who harden the Linux kernel with PaX/grsecurity, reported the availability of patches to build PaX/grsecurity reproducibly.

This collaboration creates a web of trust for users. It makes reproducible builds trustworthy for those who either cannot or do not want to perform the checks themselves to discover whether two packages match up at the bit level. The future shape of the entire process and the expected results need further clarification – but these problems can be solved as soon as an archive exists that is almost entirely built in a reproducible way.