CS 513 System Security -- Lecture Notes for February 12, 1998

Capability-based Access Control Mechanisms

CS 513 -- System Security -- February 12, 1998 -- Lecture 8
Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett

We have been discussing access control lists (ACLs) as a mechanism to do authorization. The mechanism is like a guard sitting at a guard house guarding access to an object. When a subject comes along and wants access, the guard checks the subject's name against a list. The subject is authorized to have access if its name is on the list.

Several issues arise with ACLs. First, it is necessary to encode the lists tersely in order to save space and lookup times. Second, in order to support small protection domains, a user should be able to have multiple identities. Third, it is generally a good idea to have conservative defaults, since new objects will be created often. Tools like 'chmod' that change file permissions can be bothersome, so it's important to have good defaults in place.

A related concern is that of conveying security information to users. We need good user metaphors for security. There are many examples of physical experiences that provide good metaphors for computing including the desktop metaphor in user interfaces. We seek such a metaphor for access control. One possibility is to describe access control in terms of locks and keys. However, this metaphor isn't completely helpful, because people do not regularly create new rooms and new locks, whereas new objects are created in computer systems all the time. The notion of nested locks is not intuitive, either. In the physical world, it is not likely that one would use a key to go through a door, not look at anything in the room and use another to key to go through another door. Yet that is what happens when a file is accessed by way of a path name.

Capability-based Mechanisms

One approach to storing an access control matrix, discussed previously, is to store columns with objects (an ACL). We will now discuss another approach: storing rows with subjects (capabilities).

A capability can be thought of as a pair (x, r) where x is the name of an object and r is a set of privileges or rights. With each subject we can store that subject's capabilities. And, the subject presents to the guard a capability in order to get access to an object. Note that a capability is completely transferable; it doesn't matter who presents the capability. This framework completely eliminates the need for authentication. However, with ACLs we were assuming that authentication was unforgeable. With capabilities, we now need a way to make capabilities unforgeable. The success of a capability-based mechanism depends on it.

The term "capability" originated in a 1966 paper by Dennis and Van Horn. An operating system based on these ideas was then built for a PDP-1 by Ackerman and Plummer. There were earlier systems that implement capabilities directly in the hardware, however. All of the 'action' in systems that use capabilities is in implementing and achieving their unforgeability.

A first question is how to represent object name x in capability (x,r). (We require different objects to have different names.) One solution would be to use the address of the object as its name. This is not quite sufficient, since a pointer to an array and a pointer to the first element in an array are the same address, yet clearly different objects. Thus, we must also encode the length of the object as well. The start address plus object-length uniquely describes the object. We have seen this before in segmented memory, and in systems with segmented memory we can use the addressing hardware to support the naming convention. An obvious problem with this naming scheme, though, is that if the address changes, then the name changes. Therefore, this scheme is most useful in situations where objects don't move around a lot.

Instead of using an object's address, we could use a random bit string as a name for an object. Suppose we have 50 bits. If a new object is named each microsecond, then it will take about 35 years to run out of names. (The namespace size issue is not just a security issue. We see it also in telephony with new area codes being created and, of course, on the Internet.) With unique bitstrings for names, we need a way to translate from the name to the object; a hashtable, which might also include protection rights, is a reasonable solution.

We still have to find a way to make capabilities unforgeable. There are a number of possibilities.

Hardware tags: Each word will have a 1-bit tag associated with it. The tag "on" means that programs cannot change or copy that particular word (because it stores a capability). Hardware to enforce such tags was implemented in a few systems, none of which were particularly successful commercially.
Protected address space: Store capabilities in parts of memory that are inaccessible to programs. (Recall that we have done this before with ACLs.)
Language-based security: We can use a programming language to enforce restrictions on access and modification to capabilities. Java takes this approach, for example.
Cryptography: Take the capability and use encrypting to render it unintelligible to programs that should not be accessing it.

Protected Address Space Implementation of Capabilities

In order to store capabilities using a protected address space, we associate with each process a c-list (capability list). Recall that the operating system stores and loads processor state information for each process. We include the c-list in that state information.

The c-list is stored in the kernel's memory and is a table with rights and pointers to objects.

Instead of giving capabilities directly to processes, we only provide processes with indices to the table. A process can utter only these indices, and thus a process can only talk about capabilities that it has, making it impossible to create new capabilities. We are using indirection to prevent processes from forging capabilities.

Associated with a c-list are meta-instructions that allow capabilities to be changed. These meta-instructions include: create a new c-list, copy a capability into the c-list, and delete a capability from a c-list. These operations allow processes to instruct the kernel to move capabilities around. For information on how the kernel protects its own memory see an operating systems text or course.

Cryptography for Implementing Capabilities

In a cryptographic approach to ensuring unforgeability the capability is represented with a bit string having the following structure:

The "random" bits, when interpreted correctly, will provide unforgeability. Specifically, the kernel, when creating a capability does the following: create a random bit string r, store the bit string that encodes the object name, the rights, and r in its own memory, and then give a copy of the capability to the user. Users can pass capabilities around as much as they like; the kernel is not involved in rights propagation. However, users can't change rights, because then the capability bit string would not match the kernel's local copy (which is checked whenever the kernel is presented with a capability.) If the random string is long enough, it would take an attacker a long time to guess. A good random number generator is required or else guessing random numbers becomes easy.