[Cryptography] Do capabilities work? Do ACLs work?

[Jerry Leichter]

On Feb 15, 2015, at 10:50 PM, Bill Frantz <frantz at pwpconsult.com> wrote:
>> Consider applying the security policy:  File F can only be accessed by those working in Area 51.
> I had to stop for a long time to figure out what "working in Area 51" could mean. First of all, unless the computer is in A51, we must be talking about a remote user of the computer and not an actor[0] running on the computer. The actor is actually what is doing the access, presumably for the benefit of one or more users. Wow, it's complex already. We could have zero to N users.
My intent was to be ambiguous; but I intended to cover two possibilities, which ultimately only differ in how dynamic they are:

1.  Some people are assigned to work in Area 51; some are not.  The ones who are are allowed access.
2.  Some people are *physically present* in Area 51; some are not.  The ones who are are allowed access.

Obviously, we assume that any actor within the system "gains its access rights" based on a person for whom it's acting, and that the system can determine the person and can evaluate the appropriate predicate.

> Does working in A51 mean job responsibilities include A51? How about connected from within A51 or GPS says is in A51? What happens if the user is not connected when the actor requests access? Fortunately, we can abstract these questions away so at the overall system level, it doesn't matter.
> 
> As I respond below, I am going to assume we can program an actor in the system that can be called passing an identity token for whom/what ever is doing the access and it comes back with a boolean isInA51(). We can hide these difficulties and others in this actor.
Yes, this is the intent - though be careful of the time aspect, which was explicitly part of the problem; isInA51() can vary with time.

>> This is an ambiguous definition of a set (perhaps) defined by comprehension rather than extension.
> 
> ?? Is "comprehension" a technical term? What about "extension"? Please explain.
Terms from philosophy/logic.  A set defined by extension is given as a particular list of elements; a set defined by comprehension is picked out of a larger universe by a predicate.  The set H of all pairs <TM, T> where TM is a Turing machine and T is an input tape such that TM halts when started on it is defined by comprehension, but no Turing machine could write down the members.  (This is an extreme example since no Turing machine could even *test membership* in the set for all possible inputs.)  Since everything we do on computers is finite, *in principle* there's no difference between the two notions - but in practice there often is - and when you consider the time element, and the extension of the set varies over time and we can at best record past values, not predict future ones, the difference can be stark.

>> 1.  Policies are defined by extension at the time they are created....
> This approach seems like Role Based Access Control (RBAC). If they work in A51, they have the A51worker attribute in their role set....
Yes, that's related.

>> 2.  Policies are defined by extension at the time of attempted access....
> Ah, I think I'm beginning to see from where my disconnect from this approach stems. This approach is assuming a static implementation of the policy mechanisms, with no place to add my isInA51 predicate and tests for it.
No, not at all.  I'm explicitly saying that you need to record the predicate as some kind of executable code; you can't just record the set of actors who match it at some fixed point in time.  All I'm forbidding is that you can't just assume away the problem by positing that a test for the predicate is already there.

>> 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.
> Hmmm. If I were to modify the KeyKOS Unix environment[1] to support this class of policy, I would add a reference to an accessPermitted() object to each file object. The open() call in the Unix environment would call it to see if access should be granted. These accessPermitted() objects can be dynamically changed as new policies are created. Once this general support has been implemented, the Unix simulator would not have to be modified for new policies since it is only interested in the Yes/No answer, and not the details of the new policy being implemented.
That's fine, but you're really no longer talking about anything I would recognize as a capability.  In fact, you've pretty much lost your organizing model!

- For ACL's, the form of open()'s code is:  For each ACL on the file, check (using fixed code) whether this actor "matches" the ACL and grant/deny access on that basis.
- For capabilities, for each capability on this actor, check (using fixed code) that whether this capability "refers to" this file and grant/deny access on that basis.

Here, you're delegating the test to an accessPermitted() function.  But *we're inside of the systems's accessPermitted() function*, and the whole point of choosing either ACL's or capabilities was to provide a simple structure for such a function that we could reason about.  If you defer to an external function, you have to start your design all over again.  I'll say more about this below.

>> 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"?
> I don't understand the issue here. While it might be interesting to know if P could have accessed F at time T, it seems to me that it is more important to know, did P access F at time T, and even more important, should P be granted access to F now.
All three are important, for different reasons.  The two you mention are obvious, but if I'm attempting to audit my *policy*, as opposed to a particular stream of events that happened to occur, this is important information.  (There's a similar and fundamental idea in databases, where there are predicates that are constraints and must always be true in all possible states of the database, and predicates that just happen to be true right now.  One of the things the relational theorists clarified was the importance of this distinction.)

>> 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.
> See above.
I don't see that you've "implemented it in a capabilities system".  You've essentially punted it to code that's up to someone else to write.

BTW, I'll grant you that it's a bit of a stretch for the ACL system as well - but much less of one.  An ACL system always has to ask:  Does this actor "match" this access control entry?  For the Area 51 problem, the user has to provide a way to  answer the question "Is this actor working in Area 51 right now"?  The function is independent of the file, and of any other ACE's on that file; all decisions about actual access remain within the ACL implementation.  That's very different from being asked to implement a "accessPermitted()" function.

>> Interpretation 3 just ups the ante on how often you need to evaluate the set of workers in Area 51.
> If I want to implement this interpretation -- which is better than Unix because it tests on every access and not just open -- in KeyKOS I would arrange a callback whenever the user's A51 status changes. I could then sever that user's access to the file.
You're now talking specific operations in KeyKOS, and nothing at all having to do with the capability model as such.

Stepping back for a moment:  I've implemented access policy mechanism (within particular programs) in the past, and I've always found that if you've already got an object-oriented model, capabilities are the most natural way to go *for the implementation*.  How you want to *represent policies to the user of the system* is a whole other story.  In practice, something like ACL's is usually a better fit.  Policies are phrased in terms of sets of users (often defined by predicates that vary over time - i.e., by comprehension).  But the user-interface "ACL-like" things usually are not directly representable *as* ACL's; one way or another, you have to translate them into whatever your system actually uses internally.  And, *much* harder (I have yet to see a plausible solution) you have to translate the *net effect* of all the rules in the system into something comprehensible to users.

None of the operating systems in wide use hew to object-oriented principles.  There are bits and pieces that look object-like, but that's as far as it goes.  Since people have been arguing for - and building examples of - object-oriented OS's for several decades now, with little effect on what's actually being used, at some point you have to concede that maybe there really *is* something missing from the object-oriented framework when it comes to OS's.  (I've come to that conclusion more generally, but that would take us too far astray.  OO is something that can be appropriate, but it can also be inappropriate.  The trick is knowing how to judge that, and having alternatives design styles to use when it's inappropriate.)

It's also the case that we've spent so many years on the debate of ACL's OR capabilities that we've closed our eyes to the limitations of *both* - and, indeed, of the underlying access matrix model.  Relational database systems, and the security policies appropriate to them, don't fit either; and, indeed, the usual way to define access policies in RDBM's (beyond simple ones that are usually done in a style that's mainly ACL-like) is to define a query that gets combined with a user's query, filtering out the results that are not supposed to be accessible.  (I guess, looking back, that that style of doing things led me to the Area 51 problem.)
                                                        -- Jerry