Split Capabilities: Making Capabilities Scale

[Jonathan S. Shapiro]

I've held off on responding to this thread, partly because I wanted to let
the idea sink in and partly because I'm packing a house at the moment, which
has me a bit distracted. These comments span several of the emails that have
gone back and forth.

First off: Hi, Alan. I'm very glad that you can now talk about e-speak. It
looks like a strong piece of work.

> 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.

There are really two issues hiding in this statement: total capability count
and manageability.

I think that the total count is not per-se a problem. To expand on your
example, your file system on your PC currently *has* 60,000 capabilities,
only they are called inodes or vfat entries. Encrypting these entries does
not inherently alter any of the issues arising from the number of them you
have. Distribution may, and I haven't thought that issue through.

The manageability argument is more compelling, but if we examine your file
system we soon note that the file system itself doesn't treat its objects as
a flat space. It has internal organization (directories) and deals with
subsets of the larger capability pool. To the extent that directories in the
file system grow too large, they become unmanageable by human users. This,
however, is not a result of using capabilities. It is a result of having too
many things to designate. Whether the designations are capabilities or
filename paths, there are two many distinct names for the human to manage. I
claim that this issue is fundamental: in any system having a large number of
objects that must be designated individually for operational purposes the
namespace management problem will arise.

Finally, I think that the "general case of one capability per method" claim
is mistaken, though it's a natural mistake given the way that the literature
has presented capabilities. Contrary to what the historical presentation has
claimed, capabilities do not authorize operations in real systems. I think
that the following is a better way to think about what is going on:

    Each object has an interface containing all
        of the methods that exist on that object.
    For each object, there are some number
        of "thinnings" of that interface. For
        example, there may be a thinning for
        operations that can be performed under
        read-only authority.
    Each of these thinnings has a corresponding
        capability.

While shifting to this model doesn't change your claim in abstract, it does
shift attention in a way that makes clearer why the abstract claim doesn't
matter. Databases may have thousands of methods, but if they *were*
individually controlled the database would have too many interfaces to be an
engineerable software artifact, and the product would soon die for reasons
having nothing to do with capabilities.

That is, either the number of capability variants per object is very small
or the system design won't work for other reasons.

> 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?

By wildcard, I assume that you mean wildcard on user identity. This implies
a hybrid access control design. I'm not inherently opposed to hybrid
systems, except insofar as bastardizing the protection model leads to the
kinds of problems you identify (along with a host of others). Wildcards have
been used in a few hybrid systems, but not in any capability system, because
there is nothing to wildcard *on*.

The most thoroughly developed hybrid of this form is probably Karger's
thesis (SCAP). Paul went to a hybrid model because neither he nor Boebert
could see how to do multilevel security in an "unmodified" (Karger's term)
capability system. It turns out that adding transparent indirection is all
you really need, though a "weak" access right definitely helps. See the
paper by Weber and Shapiro in the 2000 Symposium on Security and Privacy.

E is a "pure" capability model, and therefore has no wildcarding. So far, it
does not appear to need any.

> 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.

You seem to be assuming that this is frequently necessary. In my experience
it is not. These capabilities can almost invariably be stored in some
"directory" object, and then a single capability to the directory object can
be generated.

As an aside, I'ld argue that it is *rarely* the case that users may wish to
share objects in bulk, and *never* the case that correctly designed programs
should do so. Up to a point, the fact that capabilities means that they
reinforce good design practices.

> 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.

I think this is an interesting design. It's not appropriate in an operating
system because of the number of dynamically allocated access records
involved, but it has much to recommend it at the language level. A few
questions:

If you pass an e-speak capability to me, and I pass it to Mary, how do you
revoke mine without revoking hers? Injecting a wildcard filter can probably
handle that, but now what about the case where you want to revoke
capabilities that I hold except those held on my behalf by a particular
trusted program?

How are access rights protected, given that they do not appear to be
cryptographically secured? One of the important qualities of a vat is that
if you compromise one vat you cannot compromise the next. I can imagine wire
protocols that would achieve similar protections for e-speak, by shipping
traditional capabilities over the wire, but all of the methods that I can
see for doing so raise hairy consistency challenges in the context of object
caching. In particular, one cannot guarantee that permission downgrade
occurs promptly in the distributed case.

> In the case of multilevel security, I can cover
> all cases with only one e-speak capability per
> security level, and each user gets only one
> capability.

I think that this illustrates a flaw, and possibly a fatal flaw. If there is
one fundamental advantage to true capabilities, it is that they make exactly
this sort of aggregation hard. The aggregation you propose violates the
principal of least privilege. Worse, it encourages the construction of
programs that violate this principal routinely.

The reason this may be fatal is that one cannot assume that the programs are
well behaved. Indeed, where security is taken seriously, we must assume that
at some point somebody will slip us a trojan horse. In the design you
propose, a single trojan horse can destroy everything I have access to
*unless* I carefully restrict the capabilities that are handed to the trojan
program, at which point we start to move to a design pattern in which I have
to go to a lot of extra work to reconstruct traditional capabilities using
the split capability mechanism.

> There's still a problem with the approach you describe.  Namely, over time
> I'll accumulate a large number of capabilities.  Either I'll have to
present
> them all on each request, in which case the permission checking will take
a
> long time, or I'll need a way to track which ones I need for each request.

First, let's be clear that "I" is a program, not a user. It is very easy for
programs to track what capability goes to what. When was the last time a
production version of a program you ran got its file descriptors confused?

Also, I'ld suggest that as a design pattern you want the program to present
specifically the authorizing capability with each operation that it
performs. This provides a form of scoping around the exercise of authority,
and this scoping appears to be a very useful thing in reducing
security-related errors.

> Besides, we can't really use that approach [the directory of capabilities
> approach] in e-speak because of the
> additional latency.  The two step process you describe doubles the
latency.
> That's because in e-speak the holder of the strong capability is a
service,
> not an object.

In KeyKOS/EROS it's also a service, though it helps that the systems are not
distributed.


Jonathan Shapiro