The Ken Thompson Hack

http://c2.com/cgi/wiki?TheKenThompsonHack

by yla92 • 11 years ago

114 39 11 years ago

Don't think he told that he actually put a bug in the c compiler. He was just explaining how he could have done it. A very interesting read though.

leoc• 11 years ago

In the Eric Raymond-era Jargon File http://www.catb.org/jargon/html/B/back-door.html there's a claim that the hacked version was distributed, and used at least once.

johnwfinigan2• 11 years ago

According to [1], the original Multics trap door that Thompson cites as his inspiration was distributed, to an Air force installation no less.

Tangentially, I'm more fascinated by the fact that Paul Karger, the lead author on [1], was a principal on a Class A1 secure hypervisor for the VAX, which DEC essentially finished, but cancelled in 1991. [2]

[1] - see paragraph 3.1 - http://hack.org/mc/texts/classic-multics.pdf [2] - http://www.cs.dartmouth.edu/~ccpalmer/classes/cs55/Content/r...

zmanian• 11 years ago

John Gilmore(https://en.wikipedia.org/wiki/John_Gilmore_%28activist%29) has related to me that the doored version was distributed and persisted in the ATT production environment for several months before someone noticed the unexpected debug symbols which were left in to aid discovery.

bayesianhorse• 11 years ago

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• 11 years ago

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

ricepudding2• 11 years 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• 11 years 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.

ricepudding2• 11 years 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• 11 years ago

The way to detect a KTH is listed in the Wiki article: https://www.schneier.com/blog/archives/2006/01/countering_tr...

ginko• 11 years 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• 11 years 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.

rectang• 11 years ago

A KTH virus doesn't have to be ubiquitous to do huge damage. All you need to do is land a malicious compiler on a machine used to produce widely distributed binaries.

Agathos• 11 years ago

This inspires a major plot element in Ramez Naam's Nexus, a near future transhuman sci fi thriller. It's risky to run other people's code on your brain.

http://www.goodreads.com/book/show/13642710-nexus

lomnakkus• 11 years ago

I'll repost something another HN poster posted at me in a previous conversation about this. Thompson's attack can be defeated:

   http://www.dwheeler.com/trusting-trust/

falcolas• 11 years ago

I may be reading this wrong, but it appears to rely on trusting at least one (if not more) of the other compilers to not be compromised as well.

Given that so many modern compilers can be traced back to GCC or LLVM these days, this requirement would seem problematic.

EDIT: As pointed out below, it would take a nearly AI level compromise to protect against this kind of attack, but at a theoretical level it would be possible.

Of course, if you control the GCC compiler, you control the Linux Kernel, and no programs run on Linux that don't rely on the kernel for reading and writing files...

dllthomas• 11 years ago

It does not rely on you trusting any of the compilers to be uncompromised. It relies on you trusting at least one pair of the compilers to not be identically compromised.

comex• 11 years ago

At a theoretical level, it wouldn't be too difficult to write a C interpreter from scratch, with enough simple obfuscation that detecting what it is interpreting really would start looking like strong AI.

And even if such a sophisticated program were written and somehow managed to not take up too much CPU time, it would at least probably result in rather large binary size increases in whatever it's injected into... even Linux isn't so big that a few hundred kilobytes wouldn't stick out like a sore thumb.

brudgers• 11 years ago

The reference point is [Trusting Trust]. It was his Turing Award lecture in 1982. Honestly, it and similar materials should be required reading somewhere in university CS and Software Engineering curricula.

[Trusting Trust]: http://cm.bell-labs.com/who/ken/trust.html

EthanHeilman• 11 years ago

In my experience Trusting Trust is required reading in many CS programs.

Roboprog2• 11 years ago

Well, it wasn't required reading back when I was in CS in the 80s, but it was a discussion that we had in class.

I nervously laugh whenever somebody talks about "open source electronic voting"

eadler• 11 years ago

Required reference:

David A. Wheeler’s Page on Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) - Countering Trojan Horse attacks on Compilers

http://www.dwheeler.com/trusting-trust/

willvarfar• 11 years ago

I giggle every time I think about how Ken's compilers are alive and well even today ... I mean, who'd trust a compiler written by such a twisted mind? Something to chew on as you use the go toolchain ;)

Schwolop• 11 years ago

Could you not define a set of operations on your potentially compromised hardware/software/system that should take time x if the system is uncompromised, and verify with a separate clock that the real time is either x or x+delta? This is based on the assumption that whatever the KTH does must require some amount of computation time to achieve.

Yes, the clock could be compromised too - but building your own clock from scratch is a lot easy than building your own computer, OS, lexer, compiler, etc.

[pre-posting edit - I see others have discussed this possibility too. I thus leave this comment purely as a testament to my own ascension to the rank of "Flaw-spotter".]

boszpasaway022• 11 years ago

ms mea

boszpasaway022• 11 years ago

The Ken Thompson Hack

Related Stories