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.
Proof Carrying Code is a much better solution than signed binaries. Signed binaries still require you to trust the developer, which is many cases is still not a good idea. See here for more information:
/pcc/pcc.html
http://www.cs.cmu.edu/~petel/papers
I'm really heartened to see that folks are willing to read about discoveries made in the past, learn from mistakes that have been committed before, and stand upon the shoulders of earlier generations, rather than standing in their footprints.
I was able to use Multics for four years in college, and that experience gave me more insight and wisdom than any four years spent with Unix, Windows, or MacOS.
(In the areas of system design, that is! The only graphics expertise I gained from Multics was how to do simple bitmap images using the lineprinter!)
An unapologetic former Multician,
Stan Chesnutt
...and, at least in the older processors only in a segment tagged as a segment whose code should run in "master mode"; even most of the ring 0 code couldn't execute privileged instructions - it could only call small routines in one of those segments (said segments were, presumably, inaccessible outside of ring 0). The entry for "privileged mode" in the Multics site (well, mirror site at Stratus, anyway) glossary says:
Hardware and/or microcode - the GE 645 and 6180 had no microcode; the Multics site glossary entry for the 6180 says:
Networking a VAXstation and a RS/6000 via SCSI! The other stuff is cool also!
What the hell, I'll respond to myself. Seeing how the site is probably permanently down (at least till his next billing cycle) I'll cut and paste here. There were 2 diagrams on the site, but you should be able to understand without them.
Tom Van Vleck
About 1976, I was explaining Multics security to a colleague at Honeywell. (This was before it got the B2 rating, but the mandatory access control mechanism was present.) I explained the difference between storage channels and timing channels, and said that timing channels weren't weren't important because they were so slow, noisy, and easily clogged, that you couldn't send a signal effectively.
My friend, Bob Mullen, astounded me a few days later by showing me two processes in the terminal room. You could type into one and the other would type out the same phrase a few seconds later. The processes were communicating at teletype speed by causing page faults and observing how long they took. The sender process read or didn't read certain pages of a public library file. The receiver process read the pages and determined whether they were already in core by seeing if the read took a long or short real time. The processes were running on a large Multics utility installation at MIT under average load; occasionally the primitive coding scheme used would lose sync and the receiver would type an X instead of the letter sent. If you typed in "trojan horse," the other process would type "trojan horse" a little later, with occasional X's sprinkled in the output.
Bob pointed out that noise in the channel was irrelevant to the bandwidth (Shannon's Law). Suitable coding schemes could get comparable signalling rates over many different resource types, despite countermeasures by the OS: besides page faulting, one could signal via CPU demand, segment activation, disk cache loading, or other means.
When I thought about this I realized that any dynamically shared resource is a channel. If a process sees any different result due to another process's operation, there is a channel between them. If a resource is shared between two processes, such that one process might wait or not depending on the other's action, then the wait can be observed and there is a timing channel.
Closing the channel Bob demonstrated would be difficult. The virtual memory machinery would have to do extra bookkeeping and extra page reads. To close the CPU demand channel, the scheduler would have to preallocate time slots to higher levels, and idle instead of making unneeded CPU time available to lower levels.
Bob and I did not compute the bandwidth of the page fault channel. It was about as fast as electronic mail for short messages. A spy could create a Trojan Horse program that communicated with his receiver process, and if executed by a user of another classification, the program could send messages via timing channels despite the star-property controls on data.
The rules against writing down were designed to keep Trojan Horse programs from sending data to lower levels, by ensuring that illegal actions would fault. In this case, the sender is doing something legal, looking at data he's allowed to, consuming resources or not, and so on. The receiver is doing something legal too, for example looking at pages and reading the clock. Forbidding repeated clock reading or returning fake clock values would restrict program semantics and introduce complexity.
I believe we need a mechanism complementary to the PERMISSION mechanism, called a CERTIFICATION mechanism. This controls the right to Execute software, while permission controls the Read and Write flags. A user classified Secret is not allowed to execute, at Secret level, a program certified only to Unclassified. Programs would only be certified to a given level after examination to ensure they contained no Trojan Horses. This kind of permission bit handling is easy to implement, and if the site only certifies benign programs, all works perfectly.
How do we examine programs to make sure they have no Trojan Horses? The same way we examine kernels to make sure they don't. Examining application code to ensure it doesn't signal information illegally should be easier than the work we have to do on a kernel.
Do we need to forbid write down for storage, if we allow write down via timing channels? It's inconsistent to forbid some write down paths and allow others. The main reason for preventing write down is not to stop deliberate declassification (a spy can always memorize a secret and type it into an unclassified file), it's to protect users from Trojan Horse programs leaking information. The certification approach solves this problem adifferent way, by providing a way to prevent execution of Trojan Horse programs.
Who should be allowed to certify a program to a given level? I think anyone who can create a program to execute at level X should be able to take a lower level program and certify it to level X. We can't stop a malicious user from creating a transmitter program, unless we forbid all program creation at level X. Other policies are possible; a site could centralize all program certification as a security officer responsibility. In any case, the OS should audit every certification and store the identity of the certifier as a file attribute.
[1] Honeywell, Multics Security Administration manual ####.
[2] Bell, D. E. and L. J. LaPadula, Computer Security Model: Unified Exposition and Multics Interpretation, ESD-TR-75-306, Hanscom AFB, MA, 1975 (also available as DTIC AD-A023588).
[3] Bell, D. E., and L. J. LaPadula, Secure Computer Systems: Unified Exposition and Multics Interpretation, Mitre Technical Report MTR-2997, rev 2, March 1976.
[4] Biba, K. J., S. R. Ames, Jr., E. L. Burke, P. A. Karger, W. R. Price, R. R. Schell, W. L. Schiller, The top level specification of a Multics security kernel, WP-20377, MITRE Corp, Bedford MA, August 1975.
A B2 secure rated system requires that a program authorized to read sensitive data must not be allowed to *give* that data to a process with lower clearance. In theory, a trojan which infiltrated the secure levels of a system would possibly be able to read/modify/destroy that data (though other mechanisms exist to prevent that), but not communicate it to an untrusted party. However, with a covert channel such as this, that protection doesn't work.
If anyone's curious, more info on confinement and covert channels is here:
at erights.org
The computer security fact forum
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