4 ms·

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

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.

JoeAltmaier 12y ago
How about a debugger? Would it be possible to even hide it? the inconsistencies would give it away (address discontinuitites/size issues)?
- ricepudding 12y ago
  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.
Someone 12y ago
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. For that, the NSA made up the leap second.
- ricepudding 12y ago
  Yup. I'm pretty sure it's provable that a perfect KTH virus must necessarily pass the Turing test. Not sure if that's a case for or against tinfoil hats.
- slowmovintarget 12y ago
  The way to detect a KTH is listed in the Wiki article: https://www.schneier.com/blog/archives/2006/01/countering_trus.html https://www.schneier.com/blog/archives/2006/01/countering_tr...
  - bch 12y ago
    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. [1] http://pcc.ludd.ltu.se http://pcc.ludd.ltu.se [2] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler EDIT: in case you don't follow the links and realize the implications yourself, from wikipedia: "It was very influential in its day, so much so that at the beginning of the 1980s, the majority of C compilers were based on it."
    - seanp2k2 12y ago
      Also interesting re: reproducible builds: http://lwn.net/Articles/630074/ http://lwn.net/Articles/630074/
ginko 12y ago
>A KTH virus would have to anticipate all tools which may be written to detect it I wonder if you couldn't reduce this to the halting problem to prove that this is actually impossible. edit: Ah, never mind. It's already been mentioned in the OP that this has to be the case.
sago 12y ago
> a perfect KTH scheme would be undetectable And would be at least powerful enough to solve the halting problem. There's nothing to doubt. A 'perfect' KTH virus is impossible.

JoeAltmaier 12y ago

How about a debugger? Would it be possible to even hide it? the inconsistencies would give it away (address discontinuitites/size issues)?

ricepudding 12y ago
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.

Someone 12y ago

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. For that, the NSA made up the leap second.

ricepudding 12y ago
Yup. I'm pretty sure it's provable that a perfect KTH virus must necessarily pass the Turing test. Not sure if that's a case for or against tinfoil hats.
slowmovintarget 12y ago
The way to detect a KTH is listed in the Wiki article: https://www.schneier.com/blog/archives/2006/01/countering_trus.html https://www.schneier.com/blog/archives/2006/01/countering_tr...
- bch 12y ago
  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. [1] http://pcc.ludd.ltu.se http://pcc.ludd.ltu.se [2] https://en.wikipedia.org/wiki/Portable_C_Compiler https://en.wikipedia.org/wiki/Portable_C_Compiler EDIT: in case you don't follow the links and realize the implications yourself, from wikipedia: "It was very influential in its day, so much so that at the beginning of the 1980s, the majority of C compilers were based on it."
  - seanp2k2 12y ago
    Also interesting re: reproducible builds: http://lwn.net/Articles/630074/ http://lwn.net/Articles/630074/

ginko 12y ago

>A KTH virus would have to anticipate all tools which may be written to detect it I wonder if you couldn't reduce this to the halting problem to prove that this is actually impossible. edit: Ah, never mind. It's already been mentioned in the OP that this has to be the case.

sago 12y ago

> a perfect KTH scheme would be undetectable And would be at least powerful enough to solve the halting problem. There's nothing to doubt. A 'perfect' KTH virus is impossible.