Trusting-Trust Attack against an Entire Linux Distribution through Binary Manipulation
Julien Malka, Aman Sharma, Martin Monperrus, Stefano Zacchiroli, Théo Zimmermann
cs.CR, cs.SE
2026-07-27
A tampered GNU strip in the NixOS seed self-replicates via ELF rewriting; 3,790 of 3,791 CLI binaries in a graphical installer carry the implant, with zero build or test failures.
Open source culture treats public source and many reviewers as a backdoor filter. Ken Thompson's 1984 Turing Award lecture showed a class of compromise that source review cannot see: a malicious compiler injects a backdoor into programs it builds, and copies that logic into the next compiler even when the compiler source is clean. The construction is now called a trusting-trust attack. Thompson implemented a prototype, but there is almost no documented end-to-end run through the bootstrap of a production Linux distribution. One practical snag is that the malicious compiler has to recognize its own source. A large enough source change can stop the backdoor without anyone finding it.
The attack is usually treated as a compiler problem. This paper, from Télécom Paris and KTH, moves the carrier to GNU strip, a binutils post-processing tool that neither reads nor emits source. It only drops symbols from finished ELF files. NixOS's generic builder runs strip in the fixup phase on installed outputs, so the tool touches most executables a distribution ships. The claim is concrete: one tampered strip in the bootstrap seed can carry a payload across generations into the final standard environment, then write it into almost every downstream binary. The recipes stay clean. So does the source.
The threat model is narrow on purpose. The attacker may replace one executable in the bootstrap seed and may not edit recipes or package sources. That models compromise before the seed enters the distribution: a poisoned builder, a poisoned publish step, or an authorized seed bump. The Nixpkgs seed is about twenty prebuilt programs, including a C compiler, binutils, the C library, bash, and coreutils. stdenv has to rebuild itself from that set, so binutils, and therefore strip, is built from source more than once. On the evaluated revision that happens in stage 1 and again in stage 4.
Self-propagation needs three conditions at once. C1: the seed already trusts the tool. C2: an older generation writes into the binary of a newer one. C3: the modified successor later plays the same role. strip meets all three. The paper calls C3 the successor edge. The payload rides that edge, and it remains after the seed has left the runtime dependency closure.
The implant uses only additive ELF edits. Original program bytes stay intact:
The payload is a freestanding program: no libc, no host dynamic symbols, syscalls only. The same bytes have to land in executables with unrelated dependencies, so the payload cannot borrow anything they provide. It runs before ordinary start, so it saves the registers the kernel handed the process, aligns the stack for the x86-64 calling convention, then jumps to the host's original entry. PID, file descriptors, and signal context stay with the host.
At runtime it reads NIXBUILDTOP. Inside a Nix build sandbox it stays silent, so a stray line of output cannot fail a functional test. Outside the sandbox it runs its malicious action. In the prototype that action writes a fixed infection marker to stdout. The paper says the same hook could steal credentials or tokens instead. Only when the process basename is actually strip does it implant eligible ELF arguments. Ordinary infected programs run the payload and do not spread it further.
A wrapper design was considered: replace seed strip with a program that embeds a genuine copy, runs that copy, then rewrites the files on its command line. The wrapper can act before and after strip, rewrite the environment, and even swap in an unrelated program. They kept the parasite. A wrapper no longer looks like strip, and it has to reproduce strip's invocation exactly or a package build can fail. The parasite returns control to the genuine binary and inherits its behavior.
The evaluation pins nixpkgs at revision fef9403a3e4d, GNU binutils 2.44, on x8664-linux. The target is the graphical installer ISO, about 2,000 packages, used as a wide slice of the distribution.
| Scope | Metric | Result |
| Trojaned seed | Build failures | 0; full graphical ISO produced |
| Post-bootstrap closure | Package outputs / user-invokable ELFs | 1,199 / 3,799 |
| Closure size | Disk / median package | 6.16 GB / 0.39 MB |
| CLI-invokable binaries | Print the infection marker | 3,790 / 3,791 |
| NixOS graphical-image tests | Functional failures | 0 |
Of 3,799 user-invokable ELFs, 3,791 can be launched from the command line. 3,790 of those print the marker on a normal invocation. The one miss is firefox 147.0.3, whose recipe passes --disable-strip --disable-install-strip and skips the strip phase entirely. That is a recipe choice, not an injector failure.
A sample across languages all carry the marker: bash, git, sudo, curl, and python3.13 on the C/C++ side; pydoc and idle on the Python side; rsvg-convert (Rust); captree (Go); the Lua interpreter. Functional tests drive a full NixOS VM through graphical workflows, including a from-scratch install. gnome-shell, mutter, nautilus, and the GNOME control center in that session were built by the trojaned strip. No test failed.
The short claim: a trusting-trust attack needs a successor edge, not a compiler. strip rewrites finished ELF files, so it reaches every language in the distribution, which gcc does not.
Two defenses already in circulation miss this gap. Wheeler's diverse double-compiling rebuilds a compiler with a second independent compiler and compares the results. It diversifies the compiler. A shared strip sits on both sides and cancels out. Reproducible builds show that the same recipe yields the same bits. If the seed is equally dirty, an independent rebuild reproduces the same implant, and the check stays green. Step attestations such as in-toto also miss it: every step ran as the recipe specified, and the binary the recipe trusted was already malicious. Guix-style full-source bootstrap can shrink the compiler seed to a few hundred bytes. If post-build utilities are not rebuilt from auditable source as well, a carrier like strip still survives.
The paper also scores the roughly forty utilities the generic builder invokes by bare name across default phases. Besides strip, patchelf meets C1–C3. Both run in fixup, including on their own rebuilds. install and cp can close a successor edge through make install, but that path depends on each package's Makefile, so it is not universal. tar, sed, and make never write a program binary and cannot carry this payload.
The practical watch list is the seed's publish-and-pin process, plus every ELF-rewriting tool in fixup. Auditing gcc source does not close this path.
The injector assumes a little-endian ELF with a spare PTNOTE, and a target that is ETEXEC or an interpreted ETDYN. Shared libraries, other architectures, static PIE without an interpreter, and binaries with no suitable note segment are out of scope. The paper treats this as a complexity cap for the demo, not a hard limit of the idea.
The implementation is tied to NixOS's bootstrap graph and to strip running by default. Other distributions bootstrap differently, and strip may not sit on the default build path. The pattern itself needs a successor edge in the build graph. Without that edge the payload dies when the seed leaves the closure.
The prototype is easy to spot on purpose. The visible marker, the .payload section name, and the basename check are instrumentation, not requirements of the propagation pattern. Infecting every package measures reach. The paper notes that a real attacker could keep the payload dormant, infect only later generations of strip, and wait years before hitting a real target, which would be much harder to catch.
The experiment covers one nixpkgs revision on x8664-linux and one graphical installer. Of 3,799 ELFs, eight are user-invokable but not CLI; their infection status is not reported separately. The firefox miss shows that disabling strip opts a package out. How many recipes in the distribution do that is not surveyed.