Hacker News Reader

Comment by Jach | Hacker News Reader

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.

View on HN

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.

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.

>The paper is not about implementing a general attack that works on all trusting-trust mitigations.

Then why have section 7.3 'Bootstrappable Builds', that briefly surveys a type of trusting-trust mitigation, and concludes that their method "sustains the attack [...], even after the compiler seed shrinks to a few hundred bytes"?

>It is precisely about showing that you can still propagate backdoored code if the compromised binary in your seed is NOT the compiler.

Whatever this paper is about, it is certainly not precisely about it. But quibbles aside, if that truly is what the authors set out to show, they should probably re-read the transcript, where Ken says "[For demonstration purposes], 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."

If you actually read how GUIX (what they talk about in section 7.3) is calling a "full source bootstrap", they have brought down the compiler seed to less than 200 bytes, but also they rely on an execution environment that still has 25 Megabytes of unaudited(-able) binary.

GUIX is unconfortable about that, but as they name the current process "full source bootstrap" implicitly consider this unaudited execution environment out-of-scope and more of an academic blemish, rather than a real problem: https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-...

After all you rebuild it together with the world immediately after compiler bootstrap is done. And the utilities in your execution environment do not process the compiler source, so this dependency cannot be a problem, right?

The paper precisely addresses this. You cannot handwave away your shell or ELF utilities. They can sustain an attack just like the compiler.

> "[For demonstration purposes], 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."

This is precisely the problem that most people dealing with OPSEC have.

If you get "paranoid enough", your threat model always collapses into an unactionable mess where everything is just toast and your only solution is to quit computing and start doing woodwork or something.

If everything is potentially compromised then of course the results from the paper become obvious. If your environment is compromised, don't trust its output, duh!

If you want to quantify though, under which assumptions, "how much" your environment can be broken without compromising its output, the paper has value. And it seems like real attempts of bootstrapping binaries actually missed a spot.

> It is precisely about showing that you can still propagate backdoored code if the compromised binary in your seed is NOT the compiler.

But that seems like quibbling about semantics. Thompson says that if a compromised binary generates a binary, you cannot trust the generated binary.

This does not even have to be gcc, it could be vim. Or strip. Or cat. Or dd.

Or an iop to write data to persistent storage if the firmware of your SSD is compromised.

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.

This automated analyst isn't going to be able to run usefully on hardware that is still otherwise useful, giving you a clear path to choke it out or identify its presence when your hello world is taking 3 months to finish compiling.

insertions can be much smaller than full blown LLMs.

simple single bit changes are enough to blast your private keys out to the ether of the public facing internet.

that big fat LLM does know how to make tentacles and eyes.

Absolutely true, but even tentacles and eyes will struggle to fit in a system compact enough. Even on larger systems, there is an upper limit on how many tentacles you can cram in something before you can't continue the facade that there are none. And an upper limit on how esoteric the tentacle is before it stops being worth it.

You can construct a CPU out of an EEPROM, a clock, and a few latches. Connect it to an immediate mode display with a serial interface that doesn't care about being clocked slowly, connect up a buzzer or some blinkenlights for output when you're exceptionally paranoid and can't trust the display controller, make a basic keyboard with a rubber sheet, some wire, and some glue, poke a keyboard driver and a line editor into memory with your DIP switches, crank the clock up to kilohertz (so the keyboard latency is tolerable), and you too can bootstrap a cross-compiler! (Though be aware that the radio interference will be enough for a committed attacker to figure out what you're computing, unless you take measures against that.)

But they're not going to backdoor an Apple ][e, or a random 80m¢ microcontroller, for basically any value of "they"; so you can just use one of those instead, and save yourself the hassle.

I like the way you think, a true MacGyver-style problem solving.

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.

At that point maybe they'll just knock you out and torture you for whatever secrets instead

By doing it.

Individual cpu instructions, even of a crude old 8-bit cpu with no embedded minix os like today, are both simple enough for a human to manually understand what they do, and useful enough to build crude versions of useful things like an editor, interpreter, or compiler.

You can write a forth-like language or even a c-like language starting from individual cpu instructions that a human can read, understand, and write totally manually, and then use that to build up rapidly all the way to a full modern desktop.

If you were really paranoid about the very act of the initial typing-in, there are any number of ways to store data in a totally brainless eprom or record it to tape or something, and examine it with nothing but some leds, no cpu at all, to verify the bytes are the bytes you want. And you only need to do that for a pretty small number of initial bytes. After that it's all just regular source code which could be written on paper.

Bootstrapping is only an inconvenience problem, not a real problem.

It's not convenient for most people to assemble some bytes into some storage medium and then verify them without simply using a normal untrust-able computer to do it. But it's no problem really if you had some reason to be that careful.

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.

Reply on news.ycombinator.com