[cap-talk] On revocation and the use of wrappers and In Defense of Identities

[Marcus Brinkmann]

At Tue, 05 Dec 2006 12:17:00 -0800,
Jed at Webstart <donnelley1 at webstart.com> wrote:
> Suppose you have a mechanism where if Alice has a permission
> (any sort of permission really, I hesitate to use the term
> "capability" because people seem to immediately infer
> some preferred implementations) and Alice wishes to
> delegate some subset of this permission to Bob in such
> a way that any future exercise of the permission that
> Alice delegates to Bob can be distinguished as the
> permission that Alice delegated to Bob?  Suppose
> further that the permission delegated to Bob can be
> revoked by Alice and that Alice is unable to exercise
> the permission so as to make it appear as if it was
> Bob invoking it.
> 
> In a similar manner with further delegation to Carol.
> Here's the picture as I see it:
> 
>                     ----low access----   Carol
>                    /                       |
>                   /                        ^
> Object ("Frank") -----medium access --   Bob
>                   \                        ^
>                    \                       |
>                     ----High access----   Alice
> 
> The burden falls on Frank and on the communication mechanism.
>  From Frank's (the server's) perspective he needs to be able to
> support the appropriate labeling and revocation of the permissions.
> Alice should be able to revoke Bob's permission and anything
> delegated from it.  Bob should be able to revoke Carol's
> permission and anything derived from it.  In general Bob's
> permission is a subset of what's available to Alice and
> Carol's permission is a subset of what is available to Bob.
>  From Frank's viewpoint this is a simple matter of bookeeping.

I suppose that you would argue for the following: That if Bob or Carol
fetch some access through the access they already have, implicitely
(for example by allocating resources in a container, lookup a file in
a directory, etc), then Frank will put that permission in the same
place of the hierarchy as the original permission that Bob fetched
from.  Is that correct?

The interesting aspect of this implementation is that it is up to the
server to implement the semantics, possibly with Alice (resp. Bob)
being in an advisory role.  This may just be what one wants, although
I am not sure.  There may be use cases where we want Alice to be able
to make the decision, but in those cases she may possible be able to
use non-revocable delegation in the first place.  It seems difficult
to anticipate all possible use cases here.

> Furthermore (and this is where the new mechanism that I've
> been discussing comes in) the permission that Bob
> receives is labeled (at the server, Frank) as being delegated
> from Alice to Bob.  The permission that Carol receives
> is labeled as having been delegated from Bob (and before
> that from Alice).  And finally, the permission received by
> Bob is not available even to Alice.  When Bob invokes
> this permission the invocation can be distinguished and
> labeled as from Bob as delegated from Alice (even if
> Bob might proxy it or further delegate it with or without
> identity tracking).  Similarly when Bob further delegates
> to Carol.

This is just a fine point, but worth noting: This scheme seems to
expose much information about the users of a service, much more than
seems to be necessary to enforce correct operation.  It depends on
your level of paranoia if you consider this to be a problem or not.

Also, this concept raises serious questions about resource accounting,
if you care for that.  The bookkeeping that Frank is doing needs to be
stored in real memory, which should ideally be paid for by the clients
to prevent DoS attacks.  But working that one out is tricky at best.
The L4 people are struggeling with it, and came up with some solutions
at the kernel level, which is actually the simpler case IMO, for the
same reason that the EROS space bank gets away with it: In both cases
we are talking about an entity that has complete control over the
required resource already.  If Frank is anything but the memory server
it is a lot harder.

> All the above can be done within the 'pure' object-capability
> framework with no access control via identity (IBAC) at
> any point.  I believe it can also be done reasonably efficiently
> (though that depends on the context and implementation
> of course - we'll see if this works out).  Really it 'just' amounts
> to some handshaking with identities that then get recorded
> as labels in the server, Frank as above.  Of course there is
> a need for an identity mechanism, but that is for labeling/
> auditing and independent of access control.

The identity hand-shaking is quite a drag.  Certainly one of the
easier parts of the whole set up to get right, but a burden
nevertheless.  In the Hurd designs we came up with at least 3 RPCs per
transaction (when amortized over many operations, otherwise more).
You can do better, but not in a "pure capability system", for example
if the kernel reveals the sender's process ID at IPC receive (and
ensures that it is not reused until the reply is sent!  But that
introduces global names and thus DoS attacks).

> Let's stay at the level of semantics for a bit and ask, if we
> had all the above, would it meet the needs expressed by
> Neal and by Jonathan?  If not, then what else is needed?

In order of importance to me:

Confidence that we covered all relevant use cases.

Potentially more efficient implementation strategies (again, speaking
as the single-node OS designer).

Potentially more secure implementation strategies (server-blind
protocols).  Of course, that conflicts with some of the goals wrt
identities.

Thanks,
Marcus