Capabilities: Encryption & Implementation of Protected Subsystems

We have been discussing capabilities and ways they represent the access control matrix. A capability is a pair: (object name, access rights). Its place in the access control matrix is implicitly determined by whichever subject possesses the capability. Capabilities can be thought of as tickets to a movie theater; whoever is holding a ticket is allowed access. We noted that unforgeability is, therefore, important. Last time, we noted two ways to implement unforgeability of capabilities. One is to use a protected address space. The other is to use random numbers. Today we will discuss variations on the latter that involve encryption.

Recall that one of the drawbacks in using random numbers is that the kernel has to keep a shadow copy of every capability. It uses this shadow copy to check the validity of capabilities it is passed. Storing the shadow copy requires storage space linear in the number of capabilities. To avoid using all this storage, we need a way to prevent a process from forging capabilities.

Use of Cryptography to Implement Capabilities

Encryption can be used to scramble an input and produce enciphered text that is hard to decipher without a key. The scrambling depends on the key. Suppose that the kernel has a key k that is a secret. Assume that the kernel can compute

It should be noted that the above capability is not a completely random string. A user knows that the object is encoded, and it also knows the object's name (since that is an unencrypted part of the capability). With enough such capabilities and knowledge of the encryption algorithm, it might be possible for users to learn something about the secret key k. Attacks based on such knowledge are referred to as "partially known plain text attacks." To prevent such attacks, we can add random bits R (referred to as "salt") to the beginning of the encrypted portion :

In order to allow processes to more easily pass around capabilities, we will take advantage of "one-way trapdoor functions." Such functions are difficult to invert, unless some trapdoor (secret) is known. Suppose we have a number of one-way trapdoor functions (F₁, F₂, F₃, ... F_n) that are also commutative (i.e. where F_i(F_j(x)) = F_j(F_i(x))). And, suppose that there are n access rights to some object of interest. Then to get the functionality of restricting access, we do the following:

• The kernel picks r a random string.
• A capability to allow all n access rights is created that looks like:
• We now need a way for a client to turn off the kth right before passing the capability along. This is done by having the client modify the capability to:

Elegant as these cryptography-based schemes are, protected memory space is the dominant implementation method for capabilities. The encryption techniques are used in distributed systems (where objects and object references actually leave a host.)

Implementing Protected Subsystems with Capabilities

We now discuss how capabilities can be used to build systems with small protection domains. Recall we desire small protection domains in order to practice the principle of least privilege.

We basically use a form of object orientation. We employ a type system with base types and extended (user-defined) types. Procedures are the only way to modify the state of an object. A domain change needs to be associated with invoking such a procedure (sometimes called "methods").

As an example, suppose we have a queue object and wish to invoke the append method. There are two possible ways this could work. One would be to pass an instance of a queue as an argument to the method. The other would be to pass a name of a queue to the method. The first allows the queue object to be memoryless, and the second requires static memory.

If we pursue the first option, what capabilities should be present at different points? Before calling append, the process should not be able to change the queue. (We want only the methods provided by the queue object to do so.) Thus, the call/invocation of append should actually increase the rights so the management object can modify the queue. This is referred to as rights amplification. On the other hand, the queue object should not have access beyond arguments it is being invoked with (such as what data to append), so rights attenuation is also required. Amplification and attenuation provide a complete set of techniques to go from one set of rights to another.

We present two specific solutions to the implementation of amplification and attenuation.

Sealing is applicable in the case where we pass to the method a representation of the object on which the operation should be performed. It is very programming language oriented. We posit two operations: seal and unseal. The seal operation produces an unintelligible bit string from an object representation. In our queue example, the object manager would pass back a representation of the queue in sealed form. All a user can do is invoke routines (which can then unseal) with that sealed representation. This scheme can be thought of as using an opaque envelope; it leverages the type system. Seal and unseal can be built in terms of encryption techniques discussed previously. A problem, however, is that we can't control static storage, and information could be stolen. Further, without static storage the functionality of objects is limited.

Amplification, as implemented in the Hydra system at CMU by Jones and Wulf, demonstrated a second solution. In Hydra, everything is an object, and capabilities are used to address all objects. The kernel is involved in all operation invocations. Every object has a name (64 bits), a type (64 bits), and a representation. The representation consists of two parts: data (memory words that can be read/written) and a c-list. The c-list is stored in the kernel's protected memory. In order to create instances of an object, there is an object of type "type" and its "create" method is invoked. This create method uses a creation template, and storage is allocated according to the template. The template also has operations to initialize the c-list for the new object and has code for the operations that transform instances of the type of object being created.

An operation in Hydra is an object of type "procedure." Associated with it are instructions, constants, capabilities needed for execution of the procedure, and a template for the arguments. When a procedure is activated by the kernel, a local name space (LNS) is created. The local name space is a list of capabilities taken from two places: the capabilities already in the procedure and the actual parameters provided by the caller. As the code runs, all the names it utters are relative to the local name space. That is, small integers are used as offsets into the LNS.

The "action" here is all in how the LNS is created, because that defines what the procedure is allowed to do. Upon a call, the kernel does the following:

• It checks the capability of each argument to be sure that it has the necessary type and access rights. It does this by comparing the actuals with the parameter template associated with the procedure.
• If necessary, it does amplification of rights using the template. The parameter template specifies both necessary rights and amplified rights. The latter are rights that are temporarily added to the parameter for the duration of the procedure activation. If the argument has all the necessary rights, only then are the rights augmented according to the amplified rights.

• Modify: Leave this off a parameter and the object becomes read-only during procedure execution.
• Environment: Without this, the called procedure cannot save the capability for later use. This applies transitively if the capability is then passed to another procedure.
• Unconfined: It is not possible to store data or the capability list without this right.