Classic Computer Vulnerability Analysis Revisited

redtail writes "The original authors of the classic vulnerability analysis of Multics have revisited the lessons learned almost thirty years later. Their new paper, along with the original vulnerability analysis is published here by IBM. The original vulnerability analysis inspired the self-inserting compiler back door described by Ken Thompson in his Turing Award Lecture. "

Comments

Re:How little has changed

[Theodore Logan]

It's disappointing to see that a computer security paper written 30 years ago is still relevant today.

Indeed it is. However, if I recall correctly (the link is slashdotted, so I cannot check) the whole point of the paper is that this is a security "hole" (actually, it's not really a hole in itself, but more of a way to ascertain that a hole is not discovered) that cannot be closed. It describes a way of inserting a trojan into a program without it being visible in the source; the bottom line being that you can never trust code you didn't write directly for the machine, from scratch, yourself. And if this sort of bug was implemeted at hardware microcode level, you could not even trust writing directly for the machine.

That summary does not make the paper justice. Read it yourself when someone has posted a mirror. It's fascinating, simple, and absolutely brilliant.

Wrong.

[Animats]

Multics was one of the best operating systems ever in terms of reliablity and security. Go read the papers. People are still reusing basic ideas from Multics, like good CPU schedulers. Ease of use was mediocre, but then, this was ten years before DOS.

The big problem was that Multics was tied to a specific model of General Electric computer with custom security hardware. GE built some good early time-sharing systems in the 1960s, but sold off their computing business to Honeywell in the 1970s. Honeywell never marketed the Multics product line seriously, because it competed with other product lines that sold in bigger volume.

Self-inserting compiler.

[Black Parrot]

> The original vulnerability analysis inspired the self-inserting compiler back door described by Ken Thompson in his Turing Award Lecture.

This is a nifty concept, but I remain skeptical that it would ever work in practice, at least for an open-source produce such as gcc.

For starts, the compiler would have to detect that it was compiling itself. I.e., if you compile your favorite flight similator and the resulting program is a compiler rather than a flight simulator, the game is up already.

But recognizing itself isn't going to be such an easy task. For instance, if it just compressed the input and compared the result to a saved target, you could easily defeat it by something as simple as changing the names of identifiers in the source code. (If the match was done on just part of the code, you would merely need to do global string substitutions on the identifiers.)

So AFAICT, the trojan would have to identify itself by looking at the structure or semantics of the source file. But that's going to be tricky too. If I add a feature to the compiler or fix a bug in it, recompile, and discover that the feature is missing or the bug is still present, the game is up (after a bit of vigorous head-scratching). So it looks to me like the trojan must not only detect structure or semantics reliably, it must also limit detection to a very small block of code, to reduce the risk that it will be modified and break the trojan. That block of code must be specific enough that the trojan is never triggered when compiling other programs, and non-arbitrary enough that no one will re-write it in a zeal of code clean-up.

And, as others have pointed out in the past, the trojan has no way of slipping past if you use another compiler to compile it with. Even with two untrusted compilers, you can get a clean compile so long as the two compilers don't support each others' trojans.