The idea about KTH binaries being virtually everywhere is fascinating and frightening. But I highly doubt that this is the case.
Sure, in theory, a perfect KTH scheme would be undetectable, since it suborns every means of detection. But in practice it often wouldn't. A KTH virus would have to anticipate all tools which may be written to detect it, and given the modern open and closed source software world the complexity would explode.
Not only anticipate, but also guard against. For example, someone asked about a debugger. A specific debugger is simple: patch the debugger's source at compile time to hide the presence of the malware. Of course, that means you have to handle the case where the debugger is used to debug itself, too. That may pose a challenge, but given the existence of quines, I think it is possible. Doing that not for just _a_ debugger but every debugger in the world is left as an exercise.
Next, someone will look at timing and notice something strange. So, add stuff that tweaks the real-time clock to correct for this when your binary runs, when the OS gets built with your compiler. That way, running 'time' on your binary will not show anything suspicious.
Next, someone may notice a discrepancy between real-time clocks and their OS. Solution? Make sure analog clocks aren't that precise, hook all digital clocks up to a time signal, and tweak that signal if you hit slower code paths that the user shouldn't see. Also, make sure that all other computers in the world slow down whenever one of them hits one of these paths.
Next, someone will notice a discrepancy between clock time and solar time.
It's interesting that when Bruce is talking about using an older, simpler alternative compiler as a "checksum" compiler, the first thing I thought of was pcc[1][2], but it's from the right lab and era that using it might not actually be a good test.
If your debugger is built with the compromised toolchain, it can theoretically lie about anything, including that.
Though yes, to accomplish this the original infection would have to basically #include a godlike AI that would be able to intelligently infect all future debugging tools.
Sure, in theory, a perfect KTH scheme would be undetectable, since it suborns every means of detection. But in practice it often wouldn't. A KTH virus would have to anticipate all tools which may be written to detect it, and given the modern open and closed source software world the complexity would explode.