I'm glad they mention Wheeler's work briefly in section 7.2, since it provides a general counter to the trusting-trust attack that a lot of people seem to not know about. They dismiss it as not applying in this case, but I'm not really convinced by their argument. It's true if you only replace the compiler and run in the same environment then it won't help, but IIRC Wheeler's approach treats the environment itself as a parameter to diversify on. So not just the compiler, but also the host/OS, and even the hardware. Thus it's trivial to extend it to strip. Build binutils from source with your bad distro toolchain, fixup with your distro strip, call this build A. Then build binutils from source in a diverse environment, which includes fixup with a diverse stripper, call this B. Then do a rebuild (same diverse environment) but with B's toolchain and stripper, call this C, and compare C with A. Mismatch busts the attack.
I’ve never found Wheeler’s approach very satisfying. It says “we can’t trust the compiler, so here’s a second compiler.” But I think it is too literal interpretation of Thompson’s attack and it is just moving goalposts not really stopping the essence of the attack. The viruses of the 1990s got so advanced they regularly intercepted the read calls and stripped their payload from inspection so hiding themselves, and you could imagine in the playpen where we think we trust some other external compiler we must also think we trust the read functions on the compromised machine etc. Thompson was thinking at a higher level than this.
I also think they’ve shortchanged the bootstrap build mitigation. They write:
Well, yes, if you presuppose your modified binary is used, then you will find that your attack continues, but that’s only because “P iff P” is a logical tautology. It would be true even when the seed shrinks to 0 bytes, or shrinks to a negative number of bytes, or shrinks into a miniature poodle and tap-dances across your keyboard.The question that should have been addressed is “does the tampered instance participate in the build?”, and the whole point of these minimal-byte “seed” bootstraps is that they are just enough bytes of executable to do everything else from the source. So, no, the tampered instance won’t be participating in the build. We might even deploy our own tautology and say that if a pre-existing tainted binary participates in a build, then that build was not a bootstrap build, and therefore all bootstrap builds are in fact perfectly and definitionally immune to the attack.
Honestly, this whole paper kinda reads like an academic version of a slop CVE.
The paper is not about implementing a general attack that works on all trusting-trust mitigations.
It is precisely about showing that you can still propagate backdoored code if the compromised binary in your seed is NOT the compiler.
Works until AI compromises a bunch of OSes. And wouldn't there be difficulty comparing binaries built from significantly different environments? It sounds like some progress has been made in general for fixed identical builds, but isn't that also still a hard problem? I don't know enough low level C-level stuff about binary generation.
> Works until AI compromises a bunch of OSes.
Just write a new OS. It's a weekend project to get enough groundwork that you can bootstrap a clean system from clean source code.
> And wouldn't there be difficulty comparing binaries built from significantly different environments?
Not really. Starting from stage 0, compile the compiler under test (stage 1), then use the compiled compiler to compile the compiler (stage 2), and compare the stage 2 artefacts. Provided that your comparison program is known-good, and the stage 2 build is deterministic (not the case for some real-world programs, but true for things like tcc), this lets you verify that the two compilation procedures work identically.
Not sure if you're joking. How do you write an OS without these tools that might be compromised? It's the same problem.
Break expectations. Bootstrap it through an esoteric-enough system. Write an Uxn emulator in assembly targeting the cushy environment that UEFI has and you've got a system with graphics, a text editor, a spreadsheet editor, an assembler, games, and maybe even more. I have a Z80-powered email appliance that can be loaded with programs from a connected device. Whoever is breaking my trust in trust surely won't have planned for that.
but now they will via delegation to an automated analyst/systems programmer.
get ready.
the effort required for a complete infiltration has been lowered a great deal.
Write a subleq interpreter with a magnet and a steady hand? (Hopefully the magnet is not compromised)
I am trying to imagine how the magnet could be compromised. Could you theoretically embed an electromagnetic and a controller within a decoy magnet and somehow detect what was being recorded and subvert it? Probably not but... No, just probably not.
We have tons and tons of backups of clean Linux isos, compilers, etc. The idea that we are going to lose the ability to easily have an uncompromised system is a fairy tale told by the people pushing bootstrapable builds.