7 ms·

Running the "Reflections on Trusting Trust" Compiler

287 points by rsc 3y ago

dolmen 3y ago
The more I read about Ken and Russ's admiration for Ken's work, the more I think there is an Easter egg in the Go compiler. It looks like Russ has long planted the seed for his own Turing Award. From the article: > Today, however, the Go compiler does compile itelf, and that prompts the important question of why it should be trusted, especially when a backdoor is so easy to add. The answer is that we have never required that the compiler rebuild itself. Instead the compiler always builds from an earlier released version of the compiler. This way, anyone can reproduce the current binaries by starting with Go 1.4 (written in C), using Go 1.4 to compile Go 1.5, Go 1.5 to compile Go 1.6, and so on. There is no point in the cycle where the compiler is required to compile itself, so there is no place for a binary-only backdoor to hide. I think that this paragraph gives just hints on where to look for: * there is no "binary-only backdoor", so I'm expecting the backdoor to be available in the source distribution of Go. * the backdoor is either in each release and/or is propagated from one release to the other There is a feature of the Go compiler that I mistrust: //go:embed. I expect it could be a good vehicle to inject source code that isn't in the repository as a file. Especially as Russ himself is deeply involved in the design (see https://youtu.be/rmS-oWcBZaI https://youtu.be/rmS-oWcBZaI?). I also mistrust the vendored packages as a way to have backdoor code in the distribution. Normal Go programs are not allowed to import code from packages cmd/vendor/..., but what if the compiler was lifting that limit for himself?
earthboundkid 3y ago
Usually rsc’s blog posts are intimations of what he’s going to propose next for Go. Um, er, oh boy.
- dolmen 3y ago
  In this case, I think it is more about an Easter egg in the Go compiler. I'm expecting we will finally discover a backdoor propagated since at least Go 1.4.
- mseepgood 3y ago
  It is indirectly about the new reproducible Go toolchain builds introduced with Go 1.21. https://go.dev/blog/rebuild https://go.dev/blog/rebuild
- deleted 3y ago
  [deleted]
- kunley 3y ago
  Haha, good one ;)
saagarjha 3y ago
There’s of course a couple of notes on combating this attack: most compilers of today don’t actually produce exactly the same code if you run them twice. In broad strokes they do but often they’ll have randomness creep in, such as different build hashes or iteration order of associative containers. To truly get a bit-for-bit identical output you may need to do some extra work, or perhaps run yet another step in a controlled environment to protect against this. Second, and more importantly, many people carry a copy of a trusted compiler around, though it’s rarely mention in attacks like these: their head. In a pinch people can do spot checks to verify codegen to see whether it looks correct, unless the backdoor is incredibly subtle. But experience shows us that the more complex and hidden a backdoor is the more likely it is to break when subjected to unfamiliar examination.
- wyldfire 3y ago
  clang+llvm releases do a three stage build and compare the output of the third stage with the second. This is fairly effective at rooting out many sources of indeterminate behavior. > In broad strokes they do but often they’ll have randomness creep in, such as different build hashes or iteration order of associative containers. In order to find defects related to codegen being altered by incidental ordering of objects in containers, a build option called LLVM_ENABLE_REVERSE_ITERATION was created. Builders periodically run with this mode to verify that the regression test suite still passes when containers iterate in reverse. That said, it's true that there are probably remaining sources of variation among builds. There is a significant effort [1] to find these and avoid them. [1] https://reproducible-builds.org/ https://reproducible-builds.org/
  - vlovich123 3y ago
    Not all containers right? Just unordered containers. It’s a bit weird of a strategy though - most other applications use a random seed for unordered hash tables.
    - wyldfire 3y ago
      Rather than change the implementation of the DenseMap/DenseSet/StringMap/StringSet containers to mask such codegen defects, the community opted to create a test strategy to find the defects instead. I would guess that this may also end up favoring the execution performance of the compiler over other design choices, but I could be wrong about that one.
yegle 3y ago
What a coincidence, I was reading the GNU Mes project's doc today that's very relevant: https://www.gnu.org/software/mes/manual/mes.html https://www.gnu.org/software/mes/manual/mes.html
- legobmw99 3y ago
  Reminds me of https://elephly.net/posts/2017-01-09-bootstrapping-haskell-part-1.html https://elephly.net/posts/2017-01-09-bootstrapping-haskell-p... The difficulty of bootstrapping GHC
- userbinator 3y ago
  I thought of the term "bootstrap pilgrimage" years ago to concisely refer to such projects --- both to highlight the journey of learning they give, and to refer to the fact that not everyone may have the time nor skill to embark on one.
  - shepherdjerred 3y ago
    I've always struggled to find a succinct way to describe the benefits of installing Arch Linux. "bootstrap pilgrimage" is the perfect term!
    - eru 3y ago
      Archlinux has gotten substantial easier to install in the last decade or so. I no longer get any 'bootstrap pilgrimage' feelings from it. Lots of stuff now works out of the box, even. But I guess, I'm too used to it, too?
      - shepherdjerred 3y ago
        I haven't installed it since ~2016/2017, so my knowledge might be outdated. If you use one of the arch-based distros with a GUI, then you're right that it's very easy to install. If you follow the Wiki though, I think you still learn quite a bit: https://wiki.archlinux.org/title/installation_guide https://wiki.archlinux.org/title/installation_guide
kunley 3y ago
I love such a trivia like how Russ named the article link after Ken's original naming..
- Obscurity4340 3y ago
  Trusting Russ
NelsonMinar 3y ago
What a fantastic analysis. I've loved the Trusting Trust paper for decades now, it's so short and sweet and mind-blowing. But I honestly assumed it was a kind of thought experiment, not something Thompson actually created. Amazing to see the actual code and also learn how it sort of got into the wild but didn't quite pervade. (At least, we don't think so.)
- matheusmoreira 3y ago
  I never expected this to actually exist either. I thought it was just some hypothetical thought experiment. The implications are astounding. Code already decides the future of nations. My country uses voting machines which run software. People keep asking for the source code even though it would prove nothing...
unhammer 3y ago
Wow, the attack was implemented nearly ten years before the lecture, maybe right after reading https://seclab.cs.ucdavis.edu/projects/history/papers/karg74.pdf#page=56 https://seclab.cs.ucdavis.edu/projects/history/papers/karg74... about "the compiler trap door"?

287 points by rsc 3y ago

The more I read about Ken and Russ's admiration for Ken's work, the more I think there is an Easter egg in the Go compiler. It looks like Russ has long planted the seed for his own Turing Award. From the article: > Today, however, the Go compiler does compile itelf, and that prompts the important question of why it should be trusted, especially when a backdoor is so easy to add. The answer is that we have never required that the compiler rebuild itself. Instead the compiler always builds from an earlier released version of the compiler. This way, anyone can reproduce the current binaries by starting with Go 1.4 (written in C), using Go 1.4 to compile Go 1.5, Go 1.5 to compile Go 1.6, and so on. There is no point in the cycle where the compiler is required to compile itself, so there is no place for a binary-only backdoor to hide. I think that this paragraph gives just hints on where to look for: * there is no "binary-only backdoor", so I'm expecting the backdoor to be available in the source distribution of Go. * the backdoor is either in each release and/or is propagated from one release to the other There is a feature of the Go compiler that I mistrust: //go:embed. I expect it could be a good vehicle to inject source code that isn't in the repository as a file. Especially as Russ himself is deeply involved in the design (see https://youtu.be/rmS-oWcBZaI https://youtu.be/rmS-oWcBZaI?). I also mistrust the vendored packages as a way to have backdoor code in the distribution. Normal Go programs are not allowed to import code from packages cmd/vendor/..., but what if the compiler was lifting that limit for himself?

earthboundkid 3y ago

Usually rsc’s blog posts are intimations of what he’s going to propose next for Go. Um, er, oh boy.

dolmen 3y ago
In this case, I think it is more about an Easter egg in the Go compiler. I'm expecting we will finally discover a backdoor propagated since at least Go 1.4.
mseepgood 3y ago
It is indirectly about the new reproducible Go toolchain builds introduced with Go 1.21. https://go.dev/blog/rebuild https://go.dev/blog/rebuild
deleted 3y ago
[deleted]
kunley 3y ago
Haha, good one ;)

saagarjha 3y ago

There’s of course a couple of notes on combating this attack: most compilers of today don’t actually produce exactly the same code if you run them twice. In broad strokes they do but often they’ll have randomness creep in, such as different build hashes or iteration order of associative containers. To truly get a bit-for-bit identical output you may need to do some extra work, or perhaps run yet another step in a controlled environment to protect against this. Second, and more importantly, many people carry a copy of a trusted compiler around, though it’s rarely mention in attacks like these: their head. In a pinch people can do spot checks to verify codegen to see whether it looks correct, unless the backdoor is incredibly subtle. But experience shows us that the more complex and hidden a backdoor is the more likely it is to break when subjected to unfamiliar examination.

wyldfire 3y ago
clang+llvm releases do a three stage build and compare the output of the third stage with the second. This is fairly effective at rooting out many sources of indeterminate behavior. > In broad strokes they do but often they’ll have randomness creep in, such as different build hashes or iteration order of associative containers. In order to find defects related to codegen being altered by incidental ordering of objects in containers, a build option called LLVM_ENABLE_REVERSE_ITERATION was created. Builders periodically run with this mode to verify that the regression test suite still passes when containers iterate in reverse. That said, it's true that there are probably remaining sources of variation among builds. There is a significant effort [1] to find these and avoid them. [1] https://reproducible-builds.org/ https://reproducible-builds.org/
- vlovich123 3y ago
  Not all containers right? Just unordered containers. It’s a bit weird of a strategy though - most other applications use a random seed for unordered hash tables.
  - wyldfire 3y ago
    Rather than change the implementation of the DenseMap/DenseSet/StringMap/StringSet containers to mask such codegen defects, the community opted to create a test strategy to find the defects instead. I would guess that this may also end up favoring the execution performance of the compiler over other design choices, but I could be wrong about that one.

yegle 3y ago

What a coincidence, I was reading the GNU Mes project's doc today that's very relevant: https://www.gnu.org/software/mes/manual/mes.html https://www.gnu.org/software/mes/manual/mes.html

legobmw99 3y ago
Reminds me of https://elephly.net/posts/2017-01-09-bootstrapping-haskell-part-1.html https://elephly.net/posts/2017-01-09-bootstrapping-haskell-p... The difficulty of bootstrapping GHC
userbinator 3y ago
I thought of the term "bootstrap pilgrimage" years ago to concisely refer to such projects --- both to highlight the journey of learning they give, and to refer to the fact that not everyone may have the time nor skill to embark on one.
- shepherdjerred 3y ago
  I've always struggled to find a succinct way to describe the benefits of installing Arch Linux. "bootstrap pilgrimage" is the perfect term!
  - eru 3y ago
    Archlinux has gotten substantial easier to install in the last decade or so. I no longer get any 'bootstrap pilgrimage' feelings from it. Lots of stuff now works out of the box, even. But I guess, I'm too used to it, too?
    - shepherdjerred 3y ago
      I haven't installed it since ~2016/2017, so my knowledge might be outdated. If you use one of the arch-based distros with a GUI, then you're right that it's very easy to install. If you follow the Wiki though, I think you still learn quite a bit: https://wiki.archlinux.org/title/installation_guide https://wiki.archlinux.org/title/installation_guide

kunley 3y ago

I love such a trivia like how Russ named the article link after Ken's original naming..

Obscurity4340 3y ago
Trusting Russ

NelsonMinar 3y ago

What a fantastic analysis. I've loved the Trusting Trust paper for decades now, it's so short and sweet and mind-blowing. But I honestly assumed it was a kind of thought experiment, not something Thompson actually created. Amazing to see the actual code and also learn how it sort of got into the wild but didn't quite pervade. (At least, we don't think so.)

matheusmoreira 3y ago
I never expected this to actually exist either. I thought it was just some hypothetical thought experiment. The implications are astounding. Code already decides the future of nations. My country uses voting machines which run software. People keep asking for the source code even though it would prove nothing...

unhammer 3y ago

Wow, the attack was implemented nearly ten years before the lecture, maybe right after reading https://seclab.cs.ucdavis.edu/projects/history/papers/karg74.pdf#page=56 https://seclab.cs.ucdavis.edu/projects/history/papers/karg74... about "the compiler trap door"?