[cap-talk] RE: OS security discussion, restricted access processes, etc. - back to basics

[Jed Donnelley]

At 10:57 AM 5/4/2004, Karp, Alan wrote:

> > At this point I think we have a common understanding of the mechanisms but
> > are struggling to get common terminology.  Of course at some level all 
> that
> > goes down a network cable is bits.  Above that level at some point (say at
> > the presentation level or application level) those bits may be interpreted
> > as an index (call it a descriptor if you like).
>
>Yes, we're violently agreeing about concepts and confusing ourselves with 
>terminology.  To me "capability as bits" means that anyone who presents 
>the bits is granted the corresponding right.  That's the way Swiss numbers 
>work for sturdy refs in E.  (Did I get that right?)  If the bits 
>themselves can't be used by another party, then I'd call it something 
>different.

How would you refer to the Public Key mechanism described in:

http://www.webstart.com/jed/papers/Managing-Domains/#s13

?  With that mechanism processes are able to keep the blocks of data that 
grant them the rights to access a resource in their memory spaces.  The 
data blocks are such that they are unusable by any other process, they are 
encrypted with the public key of the process and must be decrypted to be of 
any use to anybody else.  These data blocks must go through a transformation:

1.  before being sent to another process (e.g. the server or any other 
process) and

2.  after being received and before being sent as #1.

Beyond that they are just a bunch of bits.  By the way the transformations 
work these capability blocks end up showing up as a clear text description 
of what they grant a right to when they appear in the memory space of the 
server.  Each block comes with the public key of the server and the 
server's network address.

Would you consider that mechanism capabilities as descriptors?

To me "capabilities as descriptors" connotes the class of mechanisms (like 
Dennis and Van Horn) where some system kernel maintains a separate "C-list" 
space apart from the memory space of a process.  In these types of systems 
there must be special mechanisms (built into the system calls) to 
manipulate these "capabilities" that are free to have any internal system 
understood representation.  Typically the capability representations 
contain memory pointers to internal data structures.  Certainly the 
communication calls (invoke, send, whatever) provide mechanisms for 
communicating both data and capabilities as a distinct types of entities 
know about by the communication system.  I consider "capabilities as data" 
any mechanism that doesn't require anything beyond the ability to 
communicate data to operate.

>The e-speak Beta 2.2, which I refer to as Client Utility (CU) to avoid 
>confusion with the product version, used designators.  These are indices 
>into a CL specific to each process, as done by DCCS.  The E-speak product 
>used SPKI attribute certificates tied to a private key, and you've 
>described something similar by combining the bits of a capability with a 
>private key.  I think these represent a third category that I don't have a 
>good name for.  This category has the desirable properties that 
>capabilities can be delegated without involving a third party and that 
>learning the bits does an adversary no good.  In "Managing Domains" you 
>describe yet an other system, in which there is an access list for each 
>capability listing which processes may use it.

Right.  I was trying to explore the whole space of such network mechanisms 
as I could imagine them.  The DCCS essentially uses the access list 
mechanism discussed
in Managing Domains - though it includes the flaw that allows the 
"Reflection Problem" exploit.  NLTSS (the OS who's development I led at 
LLNL) was like Amoeba
in that it used what amounted to passwords for capabilities.  The 
alternative mechanisms in Managing Domains were proposals for NLTSS that 
weren't implemented.
We felt the Public Key mechanism was the most promising, but at that time 
no suitable Public Key algorithms were available.

> > The Managing Domains paper (above) tried to stand back a bit (further than
> > we did in our implementations actually) and look at the possible protocols
> > that can be used on a network to communicate access rights.  I referred to
> > such generic access rights as "capabilities" in that paper even if they
> > were communicated via an access list mechanism (as DCCS did).
>
>I'm confused.  Looking at the DCCS and Managing Domains (MD) papers seems 
>to show different systems.

They are - of course.  The DCCS (1975) was designed to extend a pure 
(descriptor) based capability mechanism across a network.  It was based in 
some sense on the "RATS" system:

Landau, C. R.,
"The RATS Operating System,"
Lawrence Livermore National Laboratory, Report UCRL-77378 (1975).

that Charlie Landau implemented at LLNL.  We found after I designed DCCS 
that some of the RATS capabilities couldn't be fully proxied by its 
extension mechanism.  Partly because of that we never implemented a 
mechanism like DCCS for RATS.  Instead I made up a simplified "CCS" that I 
based the DCCS model on.

In the DCCS architecture (I apologize for the way it is described with 
flowcharts and such), each "CCS" computing system on the network keeps a 
list (C-list) of capabilities that it allows other systems on the network 
to access (by proxy).  However, in doing so it must keep track of which 
systems have access to which resources in its list.  That means it needs an 
access list (though by "host" - a popular ARPAnet term from those days) 
rather than by process.

In Managing Domains (MD 1981) the implementation of the NLTSS system was 
well along - though it was using a password rights communication 
mechanism.  In MD we were discussing possible alternative rights 
communication protocols that would be faithful to the pure message passing 
(network) nature of the NLTSS system - and we believed any network oriented 
rights passing mechanism (i.e. one that applied directly to the network 
whether as processes or as processors, not one that required an extension 
<likely system specific> mechanism like the DCCS for a CCS system).

>Figure 4 of DCCS shows the process indexing into a CL specific to the process.

That list, in Figure 4 termed the "Support list" under Host B, is specific 
to the Network server process, but it is servicing all remote requests of 
resources on its system.  Any other host system (e.g. C) that was going to 
access that capability identified by "capability no." would refer to the 
same "capability no.".  The only way Host B has of knowing which other 
systems actually have the right to access that capability is by keeping an 
access list (what I called a bit vector in that paper).

>Figure 3 of MD shows an access list that enumerates the processes allowed 
>to use a specific capability.  (The list isn't labeled, but that's what I 
>assume it is.)

Correct.

>These seem quite different to me.  One has a table for each process 
>listing the capabilities it has.

Which?  Do you feel DCCS has a table for each process listing the 
capabilities it has?  I guess in the sense that the component systems of 
the DCCS are descriptor based capability systems this is true.  You can 
imagine the "Support list" under Host B to be the C-list for the 
"supporting process" (network server) - or a directory owned by 
it.  However, this is more analogous to an internal resource table that 
isn't shown in Firgure 4 of the MD paper.  Perhaps the confusion is because 
I show the resource table in DCCS and I show the access list in MD, but in 
reality both mechanisms require both.

>The other has a table for each capability listing the processes that can 
>use it.  It's almost like rows versus columns of the access matrix.

Both models have a table for each resource listing who ("host" in DCCS, 
process in MD) can access the resource.

> > In fact I think some of you might find it interesting to note that the
> > Managing Domains paper points out a flaw in the DCCS
> > mechanism (without pointing it out explicitly).  Namely when I discuss 
> the "Reflection
> > Problem" there that the simple access list mechanism is subject to, the
> > DCCS mechanism has that same flaw.  It is a bit more difficult to see
> > because it would require a system on the network that didn't play the
> > "game" according to the DCCS rules, but of course that's life on a
> > network.  It was certainly the intent of the DCCS mechanism to protect
> > against such problems and it failed (though a relatively minor fix would
> > correct the problem).  The problem arises when (in the DCCS
> > terminology) at this point:
> >
> > B must tell A, "I, who have access to your capability, want to grant it to
> > host C." To do this, another message type, the "Give" message, is used.
> >
> > If the system B in fact doesn't have access (remotely) to the capability
> > but C does, and B doesn't send such a "Give" message to A (which
> > in any case would be rejected) but rather just sends a message to C
> > passing what it claims is a right it owns (with a name that it would 
> likely
> > have to snoop), then C will accept the right.  If the system C does have
> > the right to the resource on A, C will be fooled into "receiving" that 
> right
> > as B asked.  B can then simply ask for the right back (e.g. fetch it from
> > the directory) and it has illicitly obtained the right to the resource 
> on A.
>
>I'm sorry; I'm lost here.

This is easy to understand.  It's a problem that I missed in DCCS and is a 
bit awkward.

>Who is the attacker?

B

>In the first sentence, you say that C has the right on A, but B does 
>not.  In the last sentence, you say that C illicitly obtains the right on A.

Yikes.  I really messed that up.  I've correct it (mostly the last two 
sentences where I apparently reversed the sense of B and C) above.  I think 
the mechanism for the attack is easier to follow in the MD paper:

http://www.webstart.com/jed/papers/Managing-Domains/#s11

In the above I was trying to point out how the flaw exists in DCCS.  It 
wouldn't be a problem with correct CCS network sharing implementations, but 
of course part of the idea of DCCS is to develop a mechanism whereby the 
distinct CCS systems don't have to have any special trust in one another.

In the MD discussion it is the "Sneak" who is trying to get illicit access 
to the resources by sending it to the "Reflector" and getting it back.

>Even though I didn't get it from the above, the section in MD does 
>describe the problem.  As I understand it, Sneak discovers the bits in the 
>capability by some underhanded means.  He (bad guys are always "he", 
>aren't they?) then asks the Reflector to add him to the access list.  The 
>Server honors this request, and Sneak gains access.  This attack seems to 
>be related to Norm's confused deputy, but I'll let him comment on it.

Almost.  The Sneak uses a carefully selected portion of the inadequate 
(first proposed) access list protocol to "send" a capability (that it 
doesn't have) to "Reflector".  It doesn't send the message to the Server 
saying "List Reflector" because in any case the Server would reject such a 
request (Sneak isn't on the access list for the resource).  It just sends 
the message to Reflector with the capability reference (index, name, 
whatever).  Since the Reflector in the inadequate protocol (like DCCS used) 
doesn't get any independent confirmation from the Server, it has no choice 
but to accept the right passed as genuine.  If Reflector didn't have the 
right to begin with, no harm would be done.  However, if Reflector does 
have the right to begin with, then, when it sends the capability back to 
Sneak (that is what a Reflector does, after all - much like a Directory 
server), it will follow the protocol faithfully to communicate the 
capability to Sneak.  In doing so it will ask the Server to add Sneak to 
the access list.

This same problem exists in DCCS.

>Such an attack wasn't even expressible in CU.  A capability was sent from 
>one party to another by sending it as a parameter

By "parameter" do you mean a "kernel" mediated descriptor?  If the message 
flowed out on a network, what would the bits look like?

>in a message, as done in an object capability system.  The recipient would 
>get an entry in its namespace that it could use to access the 
>capability.  All messages were mediated by the TCB.  If Sneak used a name 
>that didn't appear in its namespace, the TCB would reject the 
>message.  Hence, it did Sneak no good to discover how some other process 
>referred to a capability.

The above property of course holds for all descriptor based (classical ala 
Dennis and Van Horn) capability based systems.  What I was exploring in 
DCCS and in MD was mechanism for communicating rights on a network.

> > Exactly, an access list (though the "CU" reference escapes me).
>
>Not an access list for each capability but a capability list for each 
>connection.
>
>                                 (snip)
>
> > >CU did "proxying by default".  If Alice gave Bob a capability, and Bob
> > >forwarded it to Carol, all of Carol's requests on that capbility went
> > >through Bob.
> >
> > Ugh.  That certainly doesn't scale.
>
>Actually, it scaled quite nicely.  We did extensive measurments with 
>500-600 logical machines running on a cluster of 50 physical 
>machines.  SpinCircuit was managing more than 5,000,000 resources with 
>several hundred users at their peak.

Interesting.  Perhaps I'm not understanding.  What I understood from the 
above was that every time a right was forwarded, it was forwarded as a 
Proxy.  That would mean if a right was communicated 100 times (P1 to P2 to 
P3 ... to P100), when it was invoked it would have to be proxied by every 
process in the chain in order to fulfill its request.  What did I miss?

>In many ways brokering increased the scalability.  CU was connection 
>based.  If each machine could handle a limited number of connections, say 
>100, then two levels of brokering allowed a single machine to provide 
>access to users on 1,000,000 machines.  Latency, more than scalability, 
>was the issue.  The Web E-speak interface used servlets running in Apache 
>to handle 10s of thousands of e-speak users with a single connection to 
>the logical machine.

I certainly seem to be missing something.  Perhaps the answer to my 
previous question can clarify what is going on.

> > As you say Alice gains no security.  Why set up a mechanism
> > (protocol) that even introduces such a notion, let alone makes it the 
> default?
>
>There are many reasons, many coming from our concerns with enterprise 
>systems.

Let me share my thoughts on these to see if perhaps by hearing your 
responses I can better understand.

>1. Bob may be a certified business partner, and Carol doesn't meet Alice's 
>corporate requirements.

Yet Alice proxies all of Bob's requests through to Carol.  How does that 
protect Bob?  If there are
some requests that Alice doesn't proxy (e.g. to protect Bob), then I could 
understand.

>2. Carol may not protect her machines well enough for Alice to risk a 
>direct connection to her.

ditto.

>3. Carol may not have a payment scheme or credit rating that Alice will 
>accept.

Hmmm.  Are those names right?  How does Bob get into the act above?

>4. Bob may be inside Alice's firewall while Carol is outside.

This one I can understand.  If Bob can't communicate with Carol, then of course
he must have a proxy to manage the communication.  Presumably any such
communication would be value added or in some sense it is defeating any
putative value in the firewall.

>5. Alice may be controlling the number of requests per second from Bob.

Adding value - again I can understand.

>6. Alice may not want to expend the resources for a new connection.

Why would Alice need additional resources if Bob was able to communicate
directly with Carol?  Is that because there would have to be a connection 
between
Bob and Carol?  I guess you are assuming that Alice continues to hold her
connection to both Bob and to Carol?

>None of these is compelling by itself.  In fact, proxying by default fell 
>out of the way we extended the model across the network.  We would have 
>had to work hard to shorten by default.  In retrospect, proxying by 
>default worked well for our customers.

Is there a document that discusses how you extended the model across the 
network?  Actually, if everything was handled with TCP connections (below), 
isn't it built directly "on" the network (no extension mechanism needed)?

> > >There were many reasons she might say no.  For example, she
> > might not have any ports available at the moment.
> >
> > Ports?  Yet another place where capabilities as data
> > (remember, not just passwords) eliminates a resource issue/complexity.
>
>I mean TCP/IP ports.  We were connection based and set up a new process 
>for each connection by default.  These heavyweight connections meant that 
>controlling how many we'd accept was a consideration.
>
> > >DCCS appears to work like CU in that a capability is only
> > >meaningful on a particular connection.
> >
> > In DCCS the "name" that's passed across the network is an
> > index into a table of capabilities supported for remote access.  For 
> each such
> > capability in its table the server had to remember which hosts on the
> > network had the right to access the capability.
>
>That's an access list, but Figure 4 of DCCS shows a table for a specific 
>process.  That's a capabilitiy list.

Correct.  As mentioned above the diagram just doesn't show the access 
list.  It's discussed in the text and must be there.

> > As I read that paper (just now, it's quite short) it didn't refer in any
> > way to the capability implementation.  It seems in fact to refer most
> > directly to traditional capabilities as descriptors implementations.  It
> > does of course assume the ability to store a capability into some other
> > "object" (e.g. a directory) which follows the military classification 
> rules.
>
>I believe it is describing capability as bits, at least as I use the 
>phrase.  (See earlier in this note.)

Hmmm.  I'm afraid I'm still missing something here.  I hope the discussion 
above helps you
understand the above text, because at this point I still don't understand 
where the differences are.

> > It's been a while since I've though much about such
> > traditional military protection level mechanisms (unclassified, secret, 
> top
> > secret, etc.).  We of course implemented such mechanisms in the 
> capabilities as
> > data system that we ran at LLNL for many years (NLTSS:
> > http://www.webstart.com/jed/papers/Components/ ).  The way this was 
> handled
> > in that system was that the military protection level was a property of
> > data (bits).  If a process was running at a level (e.g. secret) and it
> > tried to send a message to a process running at a lower level it wasn't
> > allowed to do so by the network (message system).  If a process running 
> at,
> > say secret, tried to write data into a file labeled unclassified, the file
> > server (which ran at a very high level so that it would receive messages
> > from any process) would refuse the request.  So in the scenario that Mr.
> > Boebert describes on our system, while a potentially malicious program
> > acting on behalf of a user with low clearance could certainly:
> >
> > 1.  store a RW capability to an unclassified file into an
> > unclassified directory, and
> >
> > 2.  the Trojan horse running in the high level process (e.g. secret) could
> > read out the RW capability to the unclassified file from the unclassified
> > directory, but
> >
> > 3X. the high level process would be blocked by the file server from 
> writing
> > data into the file (even though the capability is RW) because the data is
> > secret and the file is unclassified.
> >
> > Here is another case where I think the model is the problem.
>
>Yes, this works, but Boebert is talking about an "unmodified capability 
>machine", one that just honors requests if the capability is presented.
>A "capability as descriptor" system, or one like you describe that 
>combines the bits of the capability with a private key, avoids this 
>problem because the top secret process can't use the written-up bits as a 
>capability.

I think our system, even with the private key mechanism, would fail to meet 
his criteria if it didn't treat classification as a property of the bits 
that flow (e.g. out onto the network).

> > Are you referring to one way communication?...
>
>You're right.  A one-way, outgoing channel can be used to send secrets, 
>but it can't be used to proxy because it can't receive requests.  However, 
>"capabilities as bits" as I use the term can be leaked over such a channel.

Even with the public key mechanism of MD rights can be "leaked" over such a 
covert channel.  While it's true that the capabilities are encrypted with a 
private key so that their representation can't be stolen directly, the 
protocol for sharing capabilities (the sending and receiving protocols) are 
such that a right (capability) can be readied for sending and then leaked 
over such a channel.

>If a covert channel is low bandwidth, Alice may not be able to transmit 
>very many secrets.  However, it's a problem if capabilities are bits that 
>she can transfer to someone else who can then use them over an overt 
>channel to get lots of secrets.

I think on this one we can just accept that we have different views about 
how much of a problem this is.  In my view the greater problem results by 
trying to protect from such rights leakage.

> > I'm sorry, but I don't understand the above example.  While with a bit 
> of a
> > stretch I can imagine how a capability could represent an access right 
> to a
> > can of tuna without itself granting the right to open the can.  I find it
> > difficult to imagine a capability representing access to a can opener that
> > could be used to open the tuna can.  Perhaps my difficulty arises from the
> > fact that a can of tuna and a can opener are both physical objects.  E.g.
> > they could be located on opposite sides of the globe.  If my can of tuna
> > capability gives me rights to do things to the can of tuna (e.g.
> > communicating with the tuna can server) and my right to the can opener
> > gives me rights to the can opener (e.g. communicating with the can opener
> > server), I still find it a stretch that I could make a request of either
> > (e.g. passing the right to the other) to get the can of tuna opened.
> >
> > In any case I don't see how proxying would make any difference.  Perhaps
> > you could elaborate on this example so I can understand it better?
>
>I guess I'm too cute for my own good.  I was just trying to give an 
>example of rights amplification.  Let's take a more concrete example, 
>"combine foo bar".  Alice has access to foo and qux; Bob has access to bar 
>and qux.  Alice can combine foo and quz; Bob can combine bar and 
>qux.  Neither can combine foo and bar.  If capabilities are specific to a 
>process by some means, either because they are designators or because they 
>are tied to a private key inaccessible by the process, then Carol can't 
>combine foo and bar even if both Alice and Bob proxy for her.  If 
>capabilities are just bits not tied to a process, then Alice can tranfer 
>the right to foo to Carol, and Bob can transfer the right to bar to 
>Carol.  Carol can then combine foo and bar.

If I'm understanding the above such "amplification" sounds like a good 
thing to me.  No?  What can Carol do with the non-proxied (direct, 
capabilities as bits) that she can't do with the proxies?  If foo and bar 
were RW file capabilities and "combine" meant some sort of merging of their 
data then it would seem that Carol could do the merging in either case.  No?

>I want to thank you for this discussion.  I haven't had to think this hard 
>in quite a while.

I'm also enjoying it.  Thanks for taking the time for such a thorough 
discussion Alan!


--Jed http://www.nersc.gov/~jed/