Split Capabilities: Making Capabilities Scale

[Karp, Alan]

When we were designing e-speak access control we worried about the
scalability of our system.  Conventional capabilities weren't going to do
the trick.  (Actually, we learned about capabilities after having reinvented
them "wrong", but it's the "wrong" part that's interesting.)  A conventional
capability contains, among other things, a handle for the object being
controlled and the access rights the presenter of the capability will be
granted.

The problem is the number of capabilities I need to deal with.  After all,
my PC has over 60,000 files on it.  In the most general case, I need a
conventional capability for each operation, e.g., read, write, execute, for
each file.  Some applications, SAP comes to mind, have hundreds or thousands
of methods, each of which I might want to control separately.  The number of
capabilities to be managed becomes a problem quite quickly.

Wildcards are often used to reduce the number of capabilities needed, but
this approach is dangerous and not general enough.  What happens if I put a
private file in a directory that has an outstanding wildcard capability
granting read access to general users?  How do I construct a wild card that
gives you permission to invoke 1,000 of SAP's 10,000 methods?  What happens
if I reuse a name that exists in a capability issued against the original
file?  How is this problem made worse by the use of wildcards?  What about
objects that aren't named in a way amenable to wildcarding?  We could also
list all the relevant objects in the capability, but I don't think I want to
pass around a capability listing the 50,000 files on my system that you can
read.

We can see that the problem is tied up with how the objects controlled by
the capabilities are designated.  As I understand the way E works, each
object has a name made up in part by a large, unguessable number chosen to
guarantee statistical uniqueness.  (I hate statistical uniqueness unless you
tell me what happens in the case of a collision.  It shouldn't happen in the
life of the Universe, but nothing says it won't.  A more serious problem is
the various flaws in the system, including human error.  But this topic is
for another discussion.)  I presume that the object handle is encoded in
this name, so it can be wildcarded, but I don't know what it means to
wildcard the handle to a general object.

  (Disclaimer:  What I about to describe is e-speak Beta 2.2.  Beta 3.0 uses
SPKI certificates.)

Here's where the "wrong" part saves the day.  Each e-speak logical machine,
analagous to a Vat, has an engine and a repository.  The repository has an
entry containing a number of fields for each registered resource.  One of
these fields is a list of pairs each consisting of a reference to an e-speak
capability and the access rights granted when that capability is presented.
An e-speak capability is just a resource like any other.  It has a
repository entry, and the reference in the access field of another resource
is just the capability's repository handle.  An e-speak capability does not
refer to a specific object, nor does it contain any access rights.  Hence, a
single e-speak capability can grant a particular access right to a large
number of resources (read access to 50,000 of my files), different rights to
different resources (read permission for unclassified, read/write for
secret, and write for top secret documents), or can be used for rights
amplification if that's what the application intends (both the can and the
can opener to get the food).

There are other advantages.  I can change my mind about a given resource at
any time by changing the repository entry.  For example, I can revoke a
privilege by removing the access right entirely or by changing the
capability associated with it without worrying about what capabilities are
outstanding (no CRLs).  Since a given access right can be associated with a
set of capabilities, any one of which grants the privilege, I can clone an
e-speak capability to provide selective revocation.  Further, since e-speak
capilities are extremely light weight, I can create them whenever I wish
without worrying about the overhead.  (The internal state of an e-speak
capability is just an integer unique to its logical machine.  We could get
away with this because of the e-speak naming model, but that's a discussion
for another day.)

Clearly, the Vat needs a mapping between the object and its identifier in
the capability.  My understanding is that the mapping is encoded in the
identifier.  However, the designation could also be an entry into a table
kept in the Vat.  This table would differ from the e-speak repository in the
information associated with the object, and the capabilities would be
cryptographically secure.  However, the principle is the same.

_________________________
Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278