[Cryptography] Do capabilities work? Do ACLs work?

Ben Laurie ben at links.org
Mon Feb 16 06:55:51 EST 2015


On 15 February 2015 at 13:03, Jerry Leichter <leichter at lrw.com> wrote:
> On Feb 14, 2015, at 11:38 PM, Bill Frantz <frantz at pwpconsult.com> wrote:
>> I will note in passing that capabilities can be used to implement ACLs.[1] (Why you would want to is another question.) If you also use capabilities to control how ACLs may be changed, you have a principled answer to the problem of controlling that access.
> Consider applying the security policy:  File F can only be accessed by those working in Area 51.  This is an ambiguous definition of a set (perhaps) defined by comprehension rather than extension.  (Note that I'm assuming "working in Area 51" is not a pre-existing set in the system - it's an example of some arbitrary testable predicate that we wish to be able to support.)  We can look at three plausible interpretations:

Or we could ask what the policy really is? Anyway...

> 1.  Policies are defined by extension at the time they are created:  Produce the list of all people (or other actors in the system, if appropriate), construct the set of those who are currently working in Area 51, and grant each of them access.
>
> 2.  Policies are defined by extension at the time of attempted access:  At the moment an actor tries to gain access to an object, update the policies to reflect current reality before applying them.  That is, what matters is whether the actor is working in Area 51 at the time they try to gain access to the object.
>
> 3.  Policies are defined by extension at the time of each operation on an object.  (The difference between this and 2, in more familiar terms, is that 2 controls who can open a file, but once it's open they can do what they wish with it; while 3 would validate every read, write, etc.)
>
> Interpretation 1 could be implemented by either ACL's or capabilities.  For suitably defined ACL's, it involves attaching the definition of a predicate on actors to F, and evaluating it against any actor who attempts access.  (Most ACL systems today simply provide a list of exact matches or memberships in pre-defined groups and OR's the result.  One can be much more general; at the simplest, have a pair of lists, "allow" and "deny", and take the AND of the OR of membership in the "allow" list and non-membership in the "deny" list.  VMS had at least this.)  For capabilities, there's no issue in principle, but implementation seems expensive:  You have to scan every actor in the system, apply the predicate to them, and then modify their capabilities accordingly.
>
> Interpretation 2 adds little or nothing new for ACL's.  It's unlikely that any ACL system would implement Interpretation 1 by materializing a list of all the actors who are working in Area 51, which is what a capability system would have to do - so I cheated a bit.  If you really wanted to implement Interpretation 1 in an ACL system, you'd want to store a historical record of changes to the Area 51 roster, and have ACL's that looked, not at current membership, but at membership at some point in the past.  I've never seen a system that does this, though databases that allow such queries to be posed are widely used - and it's worth noting that if you want to be able to do complete auditing and forensics, you need to be able to answer questions like:  "Did P have access to F at time T"?
>
> Interpretation 2 is by far the most common one.  It's also not at all clear how one might reasonably implement it in a capabilities system.  It requires keeping the predicates used to define capabilities around, and re-applying them to add and remove capabilities whenever their values change.  In effect, this would be a system in which you kept hidden ACL's (the predicates), and the capabilities were simply cached, pre-computed values of those ACL's attached to each actor.

That seems quite a complex way to implement what would normally done
with a powerbox. i.e. a piece of code that holds all the caps and
decides at the time of request whether to grant access or not.

> (Of course, you could make the caching lazy and do the computation when needed.

i.e. use a powerbox.

> The result would be pretty much equivalent to using ACL's.)

Surprise! Policy that is defined as an ACL looks like ACLs.

> Interpretation 3 just ups the ante on how often you need to evaluate the set of workers in Area 51.  If that's expensive ... it becomes much more so.  The only system I know of that implements this, and only to a limited degree, is Windows:  If you remove a user, his existing processes are quickly killed.  (If you go to lower levels of abstraction, this is common:  CPU's check access rights on every memory access.)

The traditional way to implement this in a cap system is via a proxy
that also has access to the accessor's current Area 51status.

> Someone earlier mentioned the paper Capability Myths Demolished
> (http://zesty.ca/capmyths/usenix.pdf), a paper a read a while back and re-read now.  It's a nice piece of work, and makes some excellent points, but I've always felt that as what amounts to a polemic, it cheats a bit, in two different ways:
>
> 1.  It's response to complaints that "ACL's can do X but capabilities can't" is "oh, but that's because we have this neat extension to the capabilities model and a new implementation that lets them do X"; but it never considers the possibility that those favoring ACL's might also be able to play the same game. (For example, VMS, when it computed the list of predicates to be checked, took not just the current accessed object's own ACL, but merged in ACL's for a hierarchical list for - just going from vague memory now - the process, the group, and even a system-wide list.  That's how an ACL associated with the currently running program became effective.  The system-wide list could be used to produce effects similar to Unix run levels.)
>
> 2.  It cherry-picks examples for which capabilities do well and ACL's don't.  There's nothing there like my Area 51 workers example.
>
> In fact, you can sometimes take duals of their examples to produce examples that cut the other way.  The Confused Deputy problem is based on a timing ambiguity about which object an ACL is supposed to apply to;

I really don't think it is.

> but there's a dual issue in the Area 51 problem, which has a similar timing ambiguity about which actors are in the set.

Surely that issue is in the definition of the problem (i.e. it is ambiguous)?


More information about the cryptography mailing list