Hacker News Reader

Comment by noobermin | Hacker News Reader

Trusting trust is so old that this probably has been discussed before, but isn't it possible to "break it" by either disassembly or just looking at the elf with a hex editor? I know you can theoretically hack the disassembler too if you'd like, but after some point it becomes onerous.

View on HN

There is this 2009 PhD thesis, and associated articles, where they explain how to "counter" trusting trust by using a set of independent compilers (even assuming that each compiler may be infected):

https://dwheeler.com/trusting-trust/

This is an automatic process: you compile each compiler with the others a few times and compare the outputs. At the end it gives a criterion to decide which compilers contain trojan horses.

I always had issues with this particular counter, because it assumes that you cannot create a sufficiently good back door-creating AI/heuristic machine that can also fit in the unused spaces in our systems and binaries without being noticed. That’s a big ‘if’, looking ahead into the deep future especially that our knowledge of autonomous agents and storage keeps growing.

> I always had issues with this particular counter, because it assumes that you cannot create a sufficiently good back door-creating AI/heuristic machine that can also fit in the unused spaces in our systems and binaries without being noticed. That’s a big ‘if’, looking ahead into the deep future especially that our knowledge of autonomous agents and storage keeps growing.

I'm the author of the DDC dissertation at https://dwheeler.com/trusting-trust/

If I understand you correctly, that doesn't counter DDC, as long as the system being generated is being covered by DDC.

If you're worrying about inserting code into "unused spaces" in the file that people typically call the "compiler", the solution is to check the compiler with DDC - that guarantees (given certain assumptions) that all of the executable can be explained by the source code. The source code could have malicious code, but developers know how to review source code.

If you're worrying about inserting code into "unused spaces" in other files of the larger system, the paper explains how to counter that too. Basically, treat the entire system as the "compiler" & regenerate it. More work, but now you've squeezed that out.

There's even a counter-example in the DDC paper. The tcc compiler had a subtle bug where 2 bytes were "free" (not controlled by the compilation process). That's because it was storing a 10-byte floating point value into a 12-byte memory area, leaving 2 bytes uncontrolled. DDC immediately detected a problem. DDC can detect 1 bit of difference. There's no "uncontrolled free space" for whatever is being verified by the DDC process.

Unlike most computer stuff, there's a mathematical proof in the DDC paper. If the assumptions hold, the conclusions necessarily follow. Attackers must take steps to invalidate at least one of the assumptions for the conclusion to fail. Of course, nothing is perfect - if an attacker subverts an assumption, then the defender can't rely on the conclusion. But the defender can take steps to make the assumptions true.

Thank you for replying David A. Wheeler. Posts and feedback from professionals like you are what make HN great, despite the community's many (rather annoying) short-comings.

Yes. What really happens is that the trojan self-propagates in the compiler binary, copied from each iteration as it compiles the next one, always within the binary without existing in the source. And so it could be revealed by examining that binary.

... if, of course, you also knew you could trust your examining tools, including the firmware and hardware. You can't provably do that unless you assembled the entire thing from transistor gates (and even then, you're still accepting somebody else's assertions about electron behavior in that material.) So at some point you have to just decide that there's some level of operations that you do trust.

> but after some point it becomes onerous.

That's exactly the point - a sufficiently deep supply chain attack can avoid detection just because no one bothers to look that deep.

On the other hand, it is generally considered pretty hard to predict arbitrary changes in the future.

Indeed. This is actually required practice in certain standards such as DO-178 Level A certifications, though that is intended to prevent compiler bugs that result in miscompilation rather than malicious miscompilation, but the problem is solved in any event.

Yeah but the point is how are you going to just look at disassembly and know there’s a Trojan?

Reply on news.ycombinator.com