Rights Amplification

[Marcus Brinkmann]

At Mon, 13 Jun 2005 18:50:49 +0200,
Bernhard Kauer <kauer at os.inf.tu-dresden.de> wrote:
> we had here a long discussion about a "real capability" or "user capability"
> system on top of L4.sec and found that we had some proplems with the initial
> assumption:

It's sad that you didn't have the discussion on this mailing list.
Just presenting us with the results of your discussion deprives us of
the reasons and rationales and thought process that lead you to your
result.  It also made it impossible for us to give input into the
discussion at the appropriate stages.

> > The assumption has been that capabilities will be built on top of end points.
> > So, I think we agree: there is no fundamental equivalence between end points 
> > and capabilities and the question at hand is: how do we represent capabilities? 
> 
> Using an endpoint for every "user capability" is quite inefficient.

Can you elaborate on this assertion?  What makes you think so?

We already have good reasons to believe that using "object ids"
managed in the server is inefficient.  Now, it may be that using
primary kernel objects for user capabilities is also inefficient.  But
the logical conclusion would be that protected capability systems in
L4 can _never_ be efficient, which would be an important negative
result---and a quite devastating one as such.

> This one-to-one mapping prevents to use the advantages of L4.sec

Can you elaborate on this?  For me, it is exactly the opposite.  Only
by using a one-to-one mapping we can draw any advantages from L4.sec.
Otherwise, L4.sec is just in the way.  It would offer _nothing_ in
addition to L4 X.2 that is of any particular relevance to a protected
capability design.

What I have said previously is that it is impossible to implement an
efficient protected capability system on top of L4 X.2.  What you seem
to be saying is that this will continue to be true for L4.sec.

> and lead to additional kernel operations like cmp()...

This is true, but what I am saying is that a protected capability
system is not feasible without _some sort_ of kernel support, ie
primary objects for user capabilities.

> > > The server could somehow identify the sender of a message.
> > 
> > Are you suggesting that we use the task id of the sender as the key?
> 
> No. L4.sec has no global task id's anymore. Instead identification can be
> done through a mechanism which is called "badge" or "sender ID".
> It is similar to what you call "secure payload" with the small, but nice
> exception that it could be set by everyone, but only once [1].
> The "sender ID" or the "badge" of the sender is transfered to the receiver
> as part of an IPC.
> 
> The "badge" has therefore the following properties:
> 
>     1. the creator of the endpoint or a server which is trusted by the creator
>        could freely set the badge
>     2. the badge is a local name; a server could refer to the same endpoint
>        with different badges
>     3. the kernel protects the integrity of the badge

I am not sure I understand how the badges stuff works.  I have read
L4-X.3-Future.pdf, but it sheds little light on the details.

Is the badge visible by the mapper?  If it is not, then badges offer
no solution to the multiple object references problem, and instead are
_just_ a way to identify the sender of a message.

If badges are visible by the mapper, then I think this feature can be
used to implement a map_lookup function in user space.  This would be
good news indeed.  But this is not my impression.
 
> >>> (Note that if you do not use communication end points as object
> >>> identifiers via a 1:1 relationship, determining to which object a
> >>> message should go is an open question whose answer depends on how
> >>> objects identifiers are represented in the first place.)
> 
> A "user capability" could be something like (badge, object nr).
> If a server receives such a capability it verifies whether this badge could use
> this object 

We are turning in circles.  This is exactly the same model as you
suggested in your first reply.  And it is exactly the model I have
already tried to implement, and that we rejected because of
performance, wrong security properties, impossibility of transparent
interposition, code complexity, etc.

> or it could ask a trusted policy server (which distributes the badges
> for his _single_ endpoint), whether this operation is allowed or not.

This means one additional RPC (and context switch) per RPC, which is
inacceptable.

> The scenarios we look at could be solved either with badges or need, like
> the reference counter example, cooperation between already cooperating clients.

I don't feel we have made any progress here.  You just repeated what
you said already, but now it is "badges" instead of "sender id".  In
other words, you have shown how you can determine the sender id given
the badges feature.  But that is not at all what my mail was about.

Please reread my first reply to you.  Everything I say there is still
relevant, and you haven't addressed any of my concerns that
implementing a protected capability system by either

1) object ids managed in the server
2) object ids managed by a trusted system service

is too slow (2, 1) or too complex and too insecure (1).

It's no good if you keep asserting that we should use one of those two
models, and I keep asserting that this is not feasible.  Do you think
it will help if I explain further why those two models are
fundamentally flawed?

I think it is trivial to see that the second model is flawed, just
based on the number of RPCs you have to do for verification.  It is
the "redirector" model all around.

To see that the first model is flawed is more complex, because you
have a lot of design parameters.  But here is one example which shows
the dramatic consequences:

1. You can not delegate, by a simple mapping, access to individual
   objects, because you would have to delegate the client id, and thus
   grant access to all your objects to a single server.

   This also means that revoking access rights is difficult, unless
   you keep a whole mapping database in each server.

2. To copy capabilities, both clients involved must talk to the
   server, and to each other.  That means copying capabilities
   requires at the very least three RPCs.  And this assumes that the
   server already knows the receiving client.  If he doesn't, first a
   communication channel has to be established (a "sender id" for the
   second client).  This is a complex task, with a lot of race
   conditions to take into account.

3. Copying references always involves the server knowing about.  So
   the server always knows exactly which clients hold references.  In
   some security models, this is not acceptable.  It leaks too much
   information to the server (Shapiro specifically pointed this out).

4. Because the receiver has to make a blocking call to the server to
   receive the reference, the server must be in the receivers trusted
   computing base.  This means that you can only accept a capability
   if you trust the server providing it.  This however has a severe
   impact on the operating system design and makes it very hard or
   impossible to implement certain features in certain systems.

5. Specifically, the receiver has to check if the server is within its
   trusted computing base.  On L4 X.2, you can do it by checking the
   global thread id of the server.  In L4.sec, this will require
   reintroducing global server IDs via a global name service,
   furthermore complicating the capability copy protocol and adding a
   couple of RPCs to communicate with the name server.

6. Furthermore, transparent interposition is hard: If the receiver
   needs to check if the server providing the capability is in its
   trusted computing base, but it only directly trusts a proxy of this
   server, it needs to make an upcall to the proxy to check if the
   server that the sender of the capability is talking about belongs
   to the trusted computing base.

So let's say a client wants to copy a capability to another client,
which does use a proxy server to the server providing the capability,
and which doesn't trust the client sending the capability, so it needs
to verify that the server belongs to its trusted computing base.
Furthermore say that this receiving client is a new client.

Then you are talking about 3 RPCs for the cap copy protocol + at least
3 RPCs to initiate a new connection with this new client, plus 1 RPC
from the receiver to the proxy server to check if the server is in the
trusted computing base (one more RPC to the nameserver).

We are now talking about at least 3 RPCs for the most simple case, and
8 RPCs, that is 16 messages, to copy _one_ capability in a relatively
simple example involving only _one_ proxy server.  Not to talk about
the code complexity, all the possible race conditions in a
multi-threaded environment, etc.

I am not sure if you really realize what it entails if you say that
servers should identify user capabilities via "(sender id, object
id)".  It's such a small thing to say, but have you actually tried to
implement it in a real-world multi-server operating system?  I'd like
to see working examples.

Thanks,
Marcus