Not going to read the whole article because I should be doing work, but...
The Ken Thompson hack is not undefeatable. You can detect it using a cross compilation technique comparing the binary output with a clean complier. I think you have to about 4 compilations to figure out if you're infected, but then you don't know which one is infected and which one isn't. You will need more data points to compare. Disassembling the binary would help as well if you know what you are looking for.
Yeah I discuss this at the end of the post. Will link it here:
The current best known defense is Diverse Double-Compiling (DDC), introduced by David Wheeler in 2009. To briefly summarize DDC uses different compilers of the same language to test the integrity of a chosen compiler. In order to pass this test the attacker must have modified all the selected compilers beforehand to insert backdoors into each other, which is a decent amount of work. DDC is a good idea but it has 2 shortcomings that come to mind. The first is that DDC requires all selected compilers to have reproducible builds, meaning that each compiler always generates the exact same executable given the same source code. Reproducible builds aren’t very common because compilers by default include things like timestamps and unique IDs in their builds. The second shortcoming is that DDC becomes less effective for languages that only have a few compilers. Also DDC can’t even be applied to newer languages like Rust with only one compiler. In summary, DDC isn’t a silver bullet and the Thompson attack is still considered to be an open problem.
I don't think so. "Evil compiler" here doesn't just mean a compiler that's malicious; it specifically means a compiler that, if asked to compile a clean compiler, will instead compile another copy of itself. And I don't think XcodeGhost did that.
Yes, why would you? It has zero information content. What should users do there? Comment on old threads instead of the current one? That's ridiculous.
You may have noticed people linking older discussions and may try to emulate it, but they do it when the older discussion has multiple and relevant comments.
I'm not sure why _you_ think it's appropriate to repost a very fresh article (e.g. still open for discussion) that had no traction. Search recent. Post if not there. Do not post if there.
I link to recent reposts "all the time" (actually less than 5% of my average one comment per workday) because people seem to misunderstand this procedure. The rules are clear about limiting reposts and carefully curating submissions.
I link all the time because often, the original poster (and, in this case, the author of the original post) deserves some of the karma that unlocks their ability to better interact with the HN community, because neither @hackthesystem nor @awelm_ nor @awelm (whoever the real awelm is) has enough karma to even change the top bar color...
I do it all the time to highlight the blatant unsavory behavior of serial reposters---in one recent case, linking both posts (from the same user, posted two days apart) of a Wikipedia URL to one another. This is not quality content, and I hoped some other users would notice and flag.
Now, I am not continuing this conversation because I have real work to do, and nothing more we say to each other will prove to be "thoughtful and substantive".
You're obviously abusing your flagging privileges (flagging reposts which are explicitly allowed on HN — read the rules!), and I hope people will join me in flagging your link spam.
You're right, people like you will never reform, so there's nothing more to discuss.
Wow, you doubled down. I agree with Tomte. Linking to a 3-day-old submission with 0 comments is worse than useless, it's just spam, and wastes peoples' time if they click on them, having assumed nobody would post a link to an empty page. Yes, it looks like you do that all the time, more like 50% than 5%. "blatant unsavory behavior"?! That describes your comment and your linking to empty pages, but nothing else I can see here. Please stop bothering with your crusade, it detracts from rather than adds to HN.
Reposts like that are ok on HN because we want to give good articles multiple chances at getting attention. Threads stay open for discussion for two weeks but are lucky if the window for getting on the front page is even two hours.
It's true that a better system could share the karma for a successful post between all the submitters, and that's actually on our list to implement. In the meantime, though, the current practice is a good thing because it mitigates some of the randomness of what gets traction off /newest and (sometimes) prevents good articles from falling through the cracks.
This is why I think some things in life should not be digitized e.g. electronic voting.
Nobody can realistically know if all of the components from hardware to software is clean. And the more technical you are, the more you realize how many attack surfaces there are. It's impossible to verify everything and you just have to blindly trust that it's all safe.
> Also DDC can’t even be applied to newer languages like Rust with only one compiler.
This is mistaken, as there exists a second Rust "compiler" known as mrustc (written in C++). I put "compiler" in quotes, as it doesn't implement all of Rust's static analysis, so it's more like an alternative code generator. That said, it still suffices to build the compiler itself (it was originally devised as a rustc bootstrapping tool), and it has been used in the past to successfully perform DDC.
> 2. Modify LoginWithBackdoor.cpp to also accept the password “backdoor” by doing a find-and-replace that modifies the if-condition checking the password
Yeah, how is this going to generalise to _any_ program that gets compiled without introducing bugs in the executable? If you can write a backdoor that can accept _any_ program and compormise its integrity you can solve the haulting problem, can't you?
So this only works if the bad compiler has access to the source code that its compiling before hand and a _hand crafted_ hack is made for it. With opensource projects like the Linux kernal i can see this is a problem but for everyone else, meh.
Who said it has to "generalize"? No virus generalizes to hack every program. That doesn't mean viruses aren't dangerous.
Also OSS makes up most of the modern stack, so access to source code is a given. And hand-crafting a backdoor when you have the source code is trivial because you can literally change anything you want with confidence.
Is it just me…or does article seem a bit contrived? I was expecting to read this to learn about a really powerful hijacking technique when in reality it’s just a program that manipulates your input program.
This is something that could easily occur with scripting languages, backend systems, open source, closed source, etc.
Basically any black-box system that takes in some input could pre-manipulate the input yielding an unknown/unexpected output.
The key point is that if your system has an evil compiler, building your own compiler from known-good source code will just give you another evil compiler, no matter how many times you do it. It creates a bootstrapping problem for the victim that doesn't have easy solutions.
Perhaps another way to say it-using an evil compiler could bootstrap any kind of malicious code in the compiled artifact whether it’s a compiler or not.
> This is something that could easily occur with scripting languages, backend systems, open source, closed source, etc. Basically any black-box system that takes in some input could pre-manipulate the input yielding an unknown/unexpected output.
IMO thats why it's a scary attack. It's a really simple idea and there are so many ways to apply it
The Thompson attack sounds scary, but it's not a real practical concern.
Look, as this article demonstrates, it's not hard to build a backdooring compiler. Even if you want to build it in a more robust way than checking filenames, it's really not difficult: it's (admittedly complex) pattern matching, and quite a lot of optimization in fact boils down to pattern matching. The problem is that the pattern matching you'd need to do to get the everything-is-backdoored scary effect is brittle as fuck.
Compiler output tends to be effectively nondeterministic. I mean, the goal of the compiler is to produce completely deterministic input, but very subtle changes can have cascading consequences. (I say this as I am trying to fix a test for LLVM's opaque pointer changes). Even something so simple as figuring out how to make bit-equivalent reproducible builds with the reproducible builds initiative took a few years to really get going, since there are so many things that are effectively random that you wouldn't consider at first (e.g., iterate over all files in a directory).
It's possible to make a compiler backdoor that is "updatable" and therefore a lot less brittle. And yes this does make the backdoor easier to detect since it's now communicating over the network. But such flexibility could really future-proof the backdoor and let it evolve over time as the target language changes.
For example, you could also make a compiler compile certain other software incorrectly in order to introduce exploitable vulnerabilities in the binaries. When I was working on convincing people of the importance of reproducible builds, I used to use an example where changing a single bit in the binary could introduce a fencepost error by changing a conditional branch operation into a different conditional branch operation. If the conditional branch related to overwriting memory and incrementing pointers (for example), that could make the resulting binary exploitable even though there was no fencepost error in the original source code.
(My examples on x86 involved changing JGE to JG, or JL to JLE, corresponding to changing >= to >, and < to <=, in loop conditions.)
Combining this with the trusting trust attack, you could have a self-perpetuating bug in the compiler plus a bugdoor in other software. The pattern match for the other software does not necessarily have to be super-specific in that case.
I would definitely agree that this wouldn't survive that many generations of software evolution without active intervention. It definitely wouldn't survive a change of programming language or target machine architecture, for example.
It is brittle but an evil compiler can account for that by attempting to compile the hacked program and falling back to real compilation if it gets a compilation error. It could even try downloading an update and try recompiling, but this introduces other ways it can get caught.
You assert that the other compiler won't contain the exact same backdoor, not that it contains no backdoor.
> different compilers could produce different, equally valid instructions, such as debug vs. release builds
The binaries you're comparing are output by two instances of the same compiler codebase (each instance created by a different compiler). So as long as that compiler is deterministic, each run should have the exact same output.
Are there any hardware-level examples similar to this?
I mean some sort of "evil CPU": even if all the software is clean,
it will act differently on some inputs (read: some pattern of instructions) to produce output in a way that it's indistinguishable at any user-level "views" without a logic analyzer analyzing all the bits in and out the CPU in physical level as electrical signals which is beyond reach practically, while still performing some evil tasks. A similar idea can be expanded to an "evil RAM" or "evil bus" but you probably get it.
I'm pretty sure there are already backdoors already in many CPUs that we aren't aware of, but I was wondering if this particular type of attack has ever been spotted in the wild.
36 comments
[ 5.5 ms ] story [ 87.0 ms ] threadThe Ken Thompson hack is not undefeatable. You can detect it using a cross compilation technique comparing the binary output with a clean complier. I think you have to about 4 compilations to figure out if you're infected, but then you don't know which one is infected and which one isn't. You will need more data points to compare. Disassembling the binary would help as well if you know what you are looking for.
"David A. Wheeler’s Page on Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) - Countering Trojan Horse attacks on Compilers"
https://dwheeler.com/trusting-trust/
The current best known defense is Diverse Double-Compiling (DDC), introduced by David Wheeler in 2009. To briefly summarize DDC uses different compilers of the same language to test the integrity of a chosen compiler. In order to pass this test the attacker must have modified all the selected compilers beforehand to insert backdoors into each other, which is a decent amount of work. DDC is a good idea but it has 2 shortcomings that come to mind. The first is that DDC requires all selected compilers to have reproducible builds, meaning that each compiler always generates the exact same executable given the same source code. Reproducible builds aren’t very common because compilers by default include things like timestamps and unique IDs in their builds. The second shortcoming is that DDC becomes less effective for languages that only have a few compilers. Also DDC can’t even be applied to newer languages like Rust with only one compiler. In summary, DDC isn’t a silver bullet and the Thompson attack is still considered to be an open problem.
https://www.quora.com/What-is-a-coders-worst-nightmare/answe...
You may have noticed people linking older discussions and may try to emulate it, but they do it when the older discussion has multiple and relevant comments.
And you seem to do it all the time. Please stop.
I link to recent reposts "all the time" (actually less than 5% of my average one comment per workday) because people seem to misunderstand this procedure. The rules are clear about limiting reposts and carefully curating submissions.
I link all the time because often, the original poster (and, in this case, the author of the original post) deserves some of the karma that unlocks their ability to better interact with the HN community, because neither @hackthesystem nor @awelm_ nor @awelm (whoever the real awelm is) has enough karma to even change the top bar color...
I do it all the time to highlight the blatant unsavory behavior of serial reposters---in one recent case, linking both posts (from the same user, posted two days apart) of a Wikipedia URL to one another. This is not quality content, and I hoped some other users would notice and flag.
Now, I am not continuing this conversation because I have real work to do, and nothing more we say to each other will prove to be "thoughtful and substantive".
You're right, people like you will never reform, so there's nothing more to discuss.
https://news.ycombinator.com/newsguidelines.html
It's true that a better system could share the karma for a successful post between all the submitters, and that's actually on our list to implement. In the meantime, though, the current practice is a good thing because it mitigates some of the randomness of what gets traction off /newest and (sometimes) prevents good articles from falling through the cracks.
https://hn.algolia.com/?sort=byDate&dateRange=all&type=comme...
https://hn.algolia.com/?sort=byDate&dateRange=all&type=comme...
Nobody can realistically know if all of the components from hardware to software is clean. And the more technical you are, the more you realize how many attack surfaces there are. It's impossible to verify everything and you just have to blindly trust that it's all safe.
This is mistaken, as there exists a second Rust "compiler" known as mrustc (written in C++). I put "compiler" in quotes, as it doesn't implement all of Rust's static analysis, so it's more like an alternative code generator. That said, it still suffices to build the compiler itself (it was originally devised as a rustc bootstrapping tool), and it has been used in the past to successfully perform DDC.
This is my primary issue with closed source software, binary blobs, etc; trust.
Yeah, how is this going to generalise to _any_ program that gets compiled without introducing bugs in the executable? If you can write a backdoor that can accept _any_ program and compormise its integrity you can solve the haulting problem, can't you?
So this only works if the bad compiler has access to the source code that its compiling before hand and a _hand crafted_ hack is made for it. With opensource projects like the Linux kernal i can see this is a problem but for everyone else, meh.
Also OSS makes up most of the modern stack, so access to source code is a given. And hand-crafting a backdoor when you have the source code is trivial because you can literally change anything you want with confidence.
This is something that could easily occur with scripting languages, backend systems, open source, closed source, etc.
Basically any black-box system that takes in some input could pre-manipulate the input yielding an unknown/unexpected output.
IMO thats why it's a scary attack. It's a really simple idea and there are so many ways to apply it
Look, as this article demonstrates, it's not hard to build a backdooring compiler. Even if you want to build it in a more robust way than checking filenames, it's really not difficult: it's (admittedly complex) pattern matching, and quite a lot of optimization in fact boils down to pattern matching. The problem is that the pattern matching you'd need to do to get the everything-is-backdoored scary effect is brittle as fuck.
Compiler output tends to be effectively nondeterministic. I mean, the goal of the compiler is to produce completely deterministic input, but very subtle changes can have cascading consequences. (I say this as I am trying to fix a test for LLVM's opaque pointer changes). Even something so simple as figuring out how to make bit-equivalent reproducible builds with the reproducible builds initiative took a few years to really get going, since there are so many things that are effectively random that you wouldn't consider at first (e.g., iterate over all files in a directory).
(My examples on x86 involved changing JGE to JG, or JL to JLE, corresponding to changing >= to >, and < to <=, in loop conditions.)
Combining this with the trusting trust attack, you could have a self-perpetuating bug in the compiler plus a bugdoor in other software. The pattern match for the other software does not necessarily have to be super-specific in that case.
I would definitely agree that this wouldn't survive that many generations of software evolution without active intervention. It definitely wouldn't survive a change of programming language or target machine architecture, for example.
You assert that the other compiler won't contain the exact same backdoor, not that it contains no backdoor.
> different compilers could produce different, equally valid instructions, such as debug vs. release builds
The binaries you're comparing are output by two instances of the same compiler codebase (each instance created by a different compiler). So as long as that compiler is deterministic, each run should have the exact same output.
I mean some sort of "evil CPU": even if all the software is clean, it will act differently on some inputs (read: some pattern of instructions) to produce output in a way that it's indistinguishable at any user-level "views" without a logic analyzer analyzing all the bits in and out the CPU in physical level as electrical signals which is beyond reach practically, while still performing some evil tasks. A similar idea can be expanded to an "evil RAM" or "evil bus" but you probably get it.
I'm pretty sure there are already backdoors already in many CPUs that we aren't aware of, but I was wondering if this particular type of attack has ever been spotted in the wild.