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:
A utility such as strip sustains the attack whenever a tampered instance participates in the rebuild, even after the compiler seed shrinks to a few hundred bytes.
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.
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.
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.
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.
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.
FYI, x86_64-linux and i686-linux nixpkgs bootstrap seed is not 25 bundled binaries, but 181 bytes, since https://github.com/NixOS/nixpkgs/pull/479322. at publication date this article would apply to non-x86 platforms like aarch64-linux, risvc64-linux, etc.
if you're concerned about this and not on x86, i encourage you to extend this to other platforms! i believe it's possible to generalize this to every linux platform musl itself supports, in time.
FYI, I reviewed the live-bootstrap project that starts with a small seed. For a T-diagram that shows all processes being executed in stage0, have a look at [1].
I did work on a solution that requires less steps, but starts with a bit larger seed (though maybe documented a bit better), see [2] and [3] for the T-diagram. Also has targets for x86_64 and arm64. (Work on RISC-V has started.)
> Ken Thompson's trusting-trust attack [...] is widely regarded as a threat specific to compilers. We show that it is not
And yet, from Reflections On Trusting Trust:
> In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode.
The paper is certainly a nice worked-out example of the attack, which is worthwhile, but it's not novel.
It goes back to Paul Karger's MULTICS Security Evaluation where he invented and described the attack. Thompson learned it from him. Karger invented a lot of attacks and security techniques a decade or more ahead of the hacking community.
The solution to this in the Orange Book (TCSEC) days in the 1980's-1990's was a system fully traceable from requirements to code, proven to embed a security policy, and analyzable and buildable from source locally by the customer using existing, trusted tools. Eventually, people added hashes for the code and data.
So, your program that combines source files or checks dependencies would be fully specified in its success and failure states. Only combinations of functions leading to a provably-secure state are even allowed. If you can't do that, the feature is too complex to allow. Human pentesters review it from design to algorithms to building it to spot ways attacks might happen.
That's what it takes to build software that usually resists subversion. Most software isn't built that way. It can't be because the priorities of developers and customers work against it. So, we'll continue to see clever attacks that exploit systems not designed to high security standards.
For this topic, I recommend David A. Wheeler's page on Software, Configuration Management Security because it covers many issues with it in mostly-centralized systems.
What happens when "security" includes a time component? A shocking number of modern systems depend on time, either in enough time having elapsed to prove something about the attacker, or in little enough time elapsing as a critical component of the system in question. That feels like it escapes the bounds of your definitions and is also somewhat unavoidable. Is that rectifiable somewhere?
> Most software isn't built that way. It can't be because the priorities of developers and customers work against it.
The most significant such priority may be the costs of paying developers and of time to delivery.
The dramatic reductions in those costs due to LLMs enable us to produce much more quantity and/or quality. Many complain now about quantity, so perhaps we are finally at a stage where we don't need much more software, and can focus on quality. Also, LLM attackers create demand for higher quality.
In other words, LLMs might enable us to some of these things that were impossible before.
It's very exciting to see the work on combining AI models with static analysis, test generation, formal proof, and refactoring. All of these suggests we might see high assurance (EAL6+) developed rapidly in the future. At least for combinations of well-understood concepts.
You don't mention generating code from scratch; is that on purpose? Perhaps a developer could add many constraints that would have been too expensive previously - e.g., code in Spark, use only these ___ system calls, never use this riskier capability, use only these ___ libraries, etc.
The LLM might take longer than otherwise, but still be fast enough. The new technology, like every useful one, changes the tradeoff equation.
If you have malware on your CI machine it can infect the artifacts it creates.
In this paper the malware was a strip trojan, but it could have been just as well a normal piece of malware which starts a service and then waits for the final artifact to be generated after which it infects it.
Rebuilding strip from clean source doesn't clear it. The copy in the bootstrap seed modifies its replacement, and the replacement carries on from there. The provenance can still look normal.
The paper over complicates what's needed to maintain persistence between the different stages. It's not like the machine is turned off between them. You can simply keep a process running the whole time.
27 years ago we named this link virus. It worked well on DOS, Windows and on every other OS where the user who executed a infected file had enough access rights to change other executables.
But this one is crippled because there is only one file that can infect other files.
The Nix project has been able to bootstrap an entire Linux distribution from scratch. However, doing that traditionally relies on binary seeds -- meaning the very first compiler in the chain is downloaded as a prebuilt binary rather than compiled from a fully verified source. This leaves a single foundational gap where users will have to trust trust an external black-box binary. Efforts toward reproducible builds and reducing this trust perimeter focus on removing binary seeds and tracing every compilation step back to a minimal, manually verifiable root.
Ken Thompson's Trusting Trust is an interesting conundrum... there are ways to minimize the need to trust however, if you can express everything in the same language or common runtime:
Is it a stretch to imagine a compromised LLM writing compromising code? I've been operating under the assumption that LLM code might be bad and not working, but I hadn't thought about it compromising a system.
Yes and no. We used to have rampant script kiddies back in the '90s and early 2000s. After 2005-ish, well maybe 2010, most systems became adequate enough to not trust users' input, bug bounties, security as a separate role, etc, etc.
It would take at least some knowledge to hack, not just a random script from a forum.
Whilst true, security will improve rapidly again. Potentially via AI, potentially via other technologies.
If its easy enough to find exploits, its likely similarly easy to scan code for exploits, or use AI-based anti-virus technologies. The only thing holding us back is the cost of compute. We can't all run the latest models against everything.
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.
FYI, x86_64-linux and i686-linux nixpkgs bootstrap seed is not 25 bundled binaries, but 181 bytes, since https://github.com/NixOS/nixpkgs/pull/479322. at publication date this article would apply to non-x86 platforms like aarch64-linux, risvc64-linux, etc.
if you're concerned about this and not on x86, i encourage you to extend this to other platforms! i believe it's possible to generalize this to every linux platform musl itself supports, in time.
FYI, I reviewed the live-bootstrap project that starts with a small seed. For a T-diagram that shows all processes being executed in stage0, have a look at [1]. I did work on a solution that requires less steps, but starts with a bit larger seed (though maybe documented a bit better), see [2] and [3] for the T-diagram. Also has targets for x86_64 and arm64. (Work on RISC-V has started.)
[1] https://fransfaase.github.io/Emulator/tdiagram.html
[2] https://fransfaase.github.io/MES-replacement/
[3] https://fransfaase.github.io/MES-replacement/Tdiagram.html
Guix has a full source bootstrap, by the way:
https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-...
"Coding Machines" from 2009 is an excellent short story describing the Trusting Trust attack. https://www.teamten.com/lawrence/writings/coding-machines/
iirc mr. adam-gordon-bell did a podcast on this, it is quite nice actually.
This is basically an ELF executable file infecting virus, nothing novel about that.
When I understood correctly, this one is crippled, because only strip can infect other files.
From TFA:
> Ken Thompson's trusting-trust attack [...] is widely regarded as a threat specific to compilers. We show that it is not
And yet, from Reflections On Trusting Trust:
> In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode.
The paper is certainly a nice worked-out example of the attack, which is worthwhile, but it's not novel.
It goes back to Paul Karger's MULTICS Security Evaluation where he invented and described the attack. Thompson learned it from him. Karger invented a lot of attacks and security techniques a decade or more ahead of the hacking community.
https://gwern.net/doc/cs/security/2002-karger.pdf
“Widely regarded” still applies, I think.
They used to call this a computer virus.
The solution to this in the Orange Book (TCSEC) days in the 1980's-1990's was a system fully traceable from requirements to code, proven to embed a security policy, and analyzable and buildable from source locally by the customer using existing, trusted tools. Eventually, people added hashes for the code and data.
So, your program that combines source files or checks dependencies would be fully specified in its success and failure states. Only combinations of functions leading to a provably-secure state are even allowed. If you can't do that, the feature is too complex to allow. Human pentesters review it from design to algorithms to building it to spot ways attacks might happen.
That's what it takes to build software that usually resists subversion. Most software isn't built that way. It can't be because the priorities of developers and customers work against it. So, we'll continue to see clever attacks that exploit systems not designed to high security standards.
For this topic, I recommend David A. Wheeler's page on Software, Configuration Management Security because it covers many issues with it in mostly-centralized systems.
What happens when "security" includes a time component? A shocking number of modern systems depend on time, either in enough time having elapsed to prove something about the attacker, or in little enough time elapsing as a critical component of the system in question. That feels like it escapes the bounds of your definitions and is also somewhat unavoidable. Is that rectifiable somewhere?
> Most software isn't built that way. It can't be because the priorities of developers and customers work against it.
The most significant such priority may be the costs of paying developers and of time to delivery.
The dramatic reductions in those costs due to LLMs enable us to produce much more quantity and/or quality. Many complain now about quantity, so perhaps we are finally at a stage where we don't need much more software, and can focus on quality. Also, LLM attackers create demand for higher quality.
In other words, LLMs might enable us to some of these things that were impossible before.
It's very exciting to see the work on combining AI models with static analysis, test generation, formal proof, and refactoring. All of these suggests we might see high assurance (EAL6+) developed rapidly in the future. At least for combinations of well-understood concepts.
You don't mention generating code from scratch; is that on purpose? Perhaps a developer could add many constraints that would have been too expensive previously - e.g., code in Spark, use only these ___ system calls, never use this riskier capability, use only these ___ libraries, etc.
The LLM might take longer than otherwise, but still be fast enough. The new technology, like every useful one, changes the tradeoff equation.
This paper can be boiled down to:
If you have malware on your CI machine it can infect the artifacts it creates.
In this paper the malware was a strip trojan, but it could have been just as well a normal piece of malware which starts a service and then waits for the final artifact to be generated after which it infects it.
Rebuilding strip from clean source doesn't clear it. The copy in the bootstrap seed modifies its replacement, and the replacement carries on from there. The provenance can still look normal.
The paper over complicates what's needed to maintain persistence between the different stages. It's not like the machine is turned off between them. You can simply keep a process running the whole time.
Rebuilding from clean source on a infected device. Whats the point? Could be every computer virus from 30 years ago.
27 years ago we named this link virus. It worked well on DOS, Windows and on every other OS where the user who executed a infected file had enough access rights to change other executables.
But this one is crippled because there is only one file that can infect other files.
you could backdoor not only the strip command but alot of other commands that work on elf binaries: strings, strace, objdump, nm, ldd, etc
The Nix project has been able to bootstrap an entire Linux distribution from scratch. However, doing that traditionally relies on binary seeds -- meaning the very first compiler in the chain is downloaded as a prebuilt binary rather than compiled from a fully verified source. This leaves a single foundational gap where users will have to trust trust an external black-box binary. Efforts toward reproducible builds and reducing this trust perimeter focus on removing binary seeds and tracing every compilation step back to a minimal, manually verifiable root.
Ken Thompson's Trusting Trust is an interesting conundrum... there are ways to minimize the need to trust however, if you can express everything in the same language or common runtime:
https://ulanguage.org/ULanguage#trust
In other words: AI can not be trusted.
Nothing about this uses AI in any way. I'm so tired of people injecting it into every conversation.
The attack doesn’t use AI, but an AI could use the attack. (and the researchers definitely used AI to write the paper!)
Is it a stretch to imagine a compromised LLM writing compromising code? I've been operating under the assumption that LLM code might be bad and not working, but I hadn't thought about it compromising a system.
huh?
AI could enable script kiddies to pull this off.
Script kiddies have always been a problem you have to defend against. This is nothing new.
Yes and no. We used to have rampant script kiddies back in the '90s and early 2000s. After 2005-ish, well maybe 2010, most systems became adequate enough to not trust users' input, bug bounties, security as a separate role, etc, etc.
It would take at least some knowledge to hack, not just a random script from a forum.
Now, with LLMs, it's the '90s all over again.
Whilst true, security will improve rapidly again. Potentially via AI, potentially via other technologies.
If its easy enough to find exploits, its likely similarly easy to scan code for exploits, or use AI-based anti-virus technologies. The only thing holding us back is the cost of compute. We can't all run the latest models against everything.
Script kiddies will soon have capabilities that nation states once upon a time could only dream of.
That's largely true of most technology available today. You can buy a cheap $100 phone that's more powerful than old super computers.