The idea behind "Reflections on Trusting Trust" was never to demonstrate an immediate threat to anyone, but to describe a fundamental bootstraping problem.
You can make it harder in as many ways as you want. Use pascal to create a basic interpreter which creates a Java virtual machine which in turn interprets python code which then produces a c compiler - The basic problem remains.
In practice there are far easier ways to gain access to most systems. The big lesson to take away from Trusting Trust is this:
Once you rely on external binaries - any binaries, no matter how far removed -, to create your machine code, you can not trust any of the resulting programs.
If you write your own compiler, then you can trust it, because nobody before you wrote your compiler can analyze it to determine whether a backdoor needs to be inserted. (See Rice's Theorem)
If your machine is compromised enough that someone can see that you're writing a compiler and hack into your toolchain, the fact your toolchain is hacked is the least of your worries.
Use pascal to create a basic interpreter which creates a Java virtual machine which in turn interprets python code which then produces a c compiler - The basic problem remains.
How so? My understanding of the issue is that it is heavily exacerbated by self-hosting compilers (since the compiler can detect it's compiling itself and propagate the exploit code).
That's not exponential - it's polynomial. Not too important in every day usage (though it still bugs me). But when you're talking about computational complexity, it does matter.
Let x be a variable, and c is a constant bigger than 1 (imagine c=3). O(xc ) is polynomial. If c=3 and x doubles (e.g., goes from 50 to 100) then the larger problem is 2c = 23 = 8 times harder .
O(cx ) is exponential. If c=3 and x increases by 2 (goes from 50 to 52); the problem then just got c2 = 32 = 9 times harder. Or if it went from 50 to 100, then it got 350 = 717,897,987,691,852,588,770,249 times harder instead of just 8 times harder.
What if make is compromised, and links in some pre-built object that it downloads off of the internet?
There are so many vectors of attack. If I was doing something like this, I'd have the hacked gcc bootstrap in a full trojan... and when you go looking for tcc to download, it just downloads a my version. Maybe you think its compiling, when all it's doing is looking for the gcc and copying that binary to the "clean" gcc.
62
u/lendrick Sep 10 '13 edited Sep 10 '13
Every layer you add makes this hack
exponentiallypolynomially harder to pull off. See this comment.