Slashdot Mirror
Surreptitious Communication via Page Faults
Martin Pomije writes "This is a really interesting story illustrating how a shared resource can also be a communication channel. If you have any interest in software design or operating systems, the Multics web site is worth your time. Tom Van Vleck has obviously put a lot of time into this and deserves credit for making all of this information available. " It's like 10 years old, but it's really interesting.
They're called "covert channels" in secure systems work / Orange Book terminology, and it's extraordinarily difficult (actually, impossible) to eliminate them totally --- a case of asymptotic approximation, law of diminishing returns, etc..
The classic tradeoff between probability of detection and bandwidth of the covert channel operates here, but if the amount of data which needs to be communicated is low then the trojan spook always wins against the guardian.
On the other hand, detection of the covert communication is an interesting problem in its own right, because it boils down to the problem of telling the remote party exactly where to find the significant data among gigabits of obfuscation --- effectively the same problem as key exchange in crypto!
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
The original site is closed due to bandwidth quota restriction.
See alternate location.
-- What you do today will cost you a day of your life.
Rather than shared resources, how about programs posting to Slashdot then reading it:
Program A writes to a random thread.
Program A-2 loads the thread, and moderates up the post, using karma from it's auto-"Linux is not socialist" post feature (such posts are always informative).
Program B (the reciever) loads the thread likewise, using Highest Scores First, and reads the posts marked up to two. It then leaves a "Linux is socialist" post. Invariably, a moderator will find this, take offence, and moderate it down.
Program A will, by continuosly re-loading the thread, notice the new (Score: -1, Troll) post, and will be assured that the communication was successful. Program execution will then continue as normal.
Hmmm...maybe I should patent it.
Yes, there was a paper by Butler Lampson on system design (it was in the proceedings of some conference, I think, published in an issue of some ACM SIG's journal; alas, I no longer have the journal issue in question) about that.
As I remember, this was on TENEX, and was an unintended consequence of a feature allowing an application to catch (or, at least, be notified of) page faults - or it may have been protection faults (e.g., SIGSEGV or SIGBUS on UNIX) - from userland.
Files, if I remember the paper correctly, could be protected with a password in TENEX, and you specified the password in the call to open the file.
Normally, you'd have to cycle each character of the password independently, in order to try a brute-force password search.
However, the code that did the password checking would, if I remember the paper correctly, fetch a character of the password, check it, and either fail immediately or continue on fetching the next character and checking it.
You could then try opening the file with an N-character password, with the second character placed so that the fault in question would occur if the system tried to fetch it (i.e., either on the next page, or not in the address space if the fault wasn't just a "page me in" fault). You'd start with the first legal character value for all characters.
If the attempt to open the file succeeded, you win.
If it fails without a fault, you know that it didn't bother trying to fetch the next character, and therefore you know that the first character wasn't the right one; you'd then replace it with the next character value, and try again.
If it fails with a fault, you know that it did try to fetch the next character, and therefore you know that the first character is the right one. You then set up a password with that character as the first character, and with the second character being the first legal character value, and with the third character being on the next page, and repeat the process with the second character.
This article probably doesn't interest most slashdotters, because the OSes that we use aren't designed to protect against these kinds of things. This, of course, stems from the fact that the situations in which we use our systems do not require us to segment our users and prevent them from communicating.
In the DoD, for instance, there are situations where you would want to do this. You don't want to allow someone viewing Top Secret data to have their information leaked to someone who isn't cleared for it.
This is why Mandatory Access Controls were invented. A lot of slashdotters have probably heard of the Orange Book, in which the DoD laid out a method of classifying the security model of computer systems. Unix variants are roughly C-1'ish, which DoD doesn't even certify anymore. OSes with ACLs and such (like NT) are roughly C-2'ish (now whether NT actually gets the job done or not is up for debate). Once you get to the B and A levels, you have Mandatory Access Controls. They are designed to prevent one user from leaking classified data to another person. In a MAC system, you should not be able to "chmod" or "chown" a file to allow someone else to view it.
It goes a little bit deeper, though. You also need to protect against more subtle methods of communication, called covert channels. In a covert storage channel, a user would fill up a disk and another user would be able to tell, or one would write to a file that another had access to read, or one would twiddle a file lock. In a covert timing channel, one user would perform a CPU intensive process and the other user would be able to tell that the responsiveness of the system changed, or the user would perform an I/O intensive application and the other user would be able to tell that his own disk accesses were more or less responsive. In this way, users can communicate via manipulating shared resources.
It's not very sexy, but it is something that DoD and the intelligence community in particular care very much about. As you can guess, these aren't easy problems to solve (if they are solvable at all).
Since the site linked from the story appears to have been slashdotted, here is an alternate link to the same story.
Deven
"Simple things should be simple, and complex things should be possible." - Alan Kay