ERights Home elib / capability 
Back to: The KeyKOS Factory On to: The Confused Deputy

Capability Confinement
An observation of Norm Hardy's,
written up by Mark S. Miller and Melora Svoboda

This chapter explains how one can confine distributed capabilities even when one can't outwardly confine bits.

Full Confinement vs. Capability Confinement

In a system in which capabilities are not accessibly represented as bits, the ability to outwardly leak bits does not enable the ability to leak capabilities. We first explore a single-machine pure capability system, such as the world of Java instances.

Accessible representation can be illustrated by the Java object reference, which is implemented as just a 32-bit pointer. To Java objects, object references are completely opaque--even with knowledge of the 32 bits that constitute a pointer (which can typically be obtained by Object.toString()), there is no operation for obtaining the corresponding pointer.

Assume four objects:

  1. a confined object, Bob
  2. an unconfined conspirator, Mallet
  3. a customer of the confined object, Alice
  4. an authority-granting object, eg, an expense account
Alice gives Bob access to an object that provides some authority, such as an expense account. Alice has proper access to Bob, and Alice interacts with Bob counting on Bob's inability to interact with Mallet. Alice feels safe handing Bob the expense account since Bob is presumably confined. Alice is confident Bob can only spend the money on the things Bob may access within the confinement rules.

Mallet, not being confined, has a broader range of spending options available. Since Bob and Mallet are conspirators, if Bob could transmit the capability to spend to Mallet, he would do so. Covert channels do enable Bob to transmit bits to Mallet, but Bob cannot transmit an object reference to Mallet, even though the object reference is implemented only out of bits. This is an example of a defensible confinement claim in a system in which bits cannot be confined.

Inward vs. Outward Bit Confinement

<need an explicit discussion of the differences> 

Distributed Capabilities

Within a programming language's virtual machine or a single-machine operating system, there exists a special mechanism--the kernel--that sits underneath all of the participants and is mutually trusted. We use that special status to create a universe of capabilities among those participants. On an open network, on the other hand, there is no common mutually trusted mechanism. Therefore, distributed capabilities have to live within stricter constraints. Distributed capabilities on open networks can only be implemented cryptographically, and cryptography can only represent capabilities as bits. The bit representation of a capability is necessarily accessible to a machine participating in the network that holds that capability. Therefore, a machine on an open network cannot be fully confined or even be capability confined.

Having vs. Knowing

In cryptography, authorization is necessarily based on knowledge of secrets. Therefore, to have a right is only to know something, and knowledge of that secret thereby provides the right. In a pure capability system, on the other hand (such as the world of Java instances), having an object is absolutely different than knowledge of the object. It is novel to have such a distinction in computation because of the doctrine that within computation there is only information. However, in Java and in the physical world, no amount of knowledge about an object can provide access to the object.

This is the basic contrast between having and knowing, and between cryptography and pure capabilities.

The Fallacy

In the Pluribus network protocol a distributed capability is turned into a unguessable secret number, such that knowledge of the secret constitutes the ability to invoke the object. (A distributed capability also includes the fingerprint of the public key of the process hosting the object, but that is beyond the scope of this note.) Since the ability to invoke the object is simply secret bits, someone who knows that secret can choose to communicate it to anyone they wish. The naïve conclusion is that one cannot capability-confine a distributed computation. Why might one think this?

In the network protocol capabilities are necessarily represented as bits. A distributed computation necessarily makes use of the network protocol. Therefore, the ability to leak bits would enable a distributed confined computation to leak these bits to a conspirator that can turn the bits back into a capability. Fortunately, there is a flaw in this reasoning.

The Solution

Distributed Confinement Box
Figure 1: Distributed Confinement

What we have in Figure 1 is a confined Bob as an object graph distributed between machines A and B. (We call the part of Bob present on machine A presence X, and the part of Bob present on machine B presence Y.) The capabilities which cross between the machines are necessarily represented by bits accessible to the participating machines. The machines themselves are assumed to be mutually suspicious. Within the comm system bits and capabilities are interchangeable, therefore the comm system cannot be confined.

Given that machines A and B do in fact collaborate to confine the Bob, Bob cannot leak distributed capabilities over covert channels, even though the distributed capabilities would seem to be represented by unconfinable bits. Machines A and B deny to their respective parts of Bob knowledge of the bits that correspond to the remote capabilities they hold. However, the comm system can present to Presence X or Y encapsulated proxies that give the presence a capability designating a remote object while denying to the presence the knowledge of the secret number used to represent the capability on the network. As a result, Bob is a distributed computation that is in a distributed confinement box.

Machines A and B, and their respective comm systems, are playing by crypto rules where having and knowing are equivalent. However, they can still arrange to constrain Bob to play by pure capability rules where having and knowing are absolutely different.


Unless stated otherwise, all text on this page which is either unattributed or by Mark S. Miller is hereby placed in the public domain.
ERights Home elib / capability 
Back to: The KeyKOS Factory On to: The Confused Deputy
Download    FAQ    API    Mail Archive    Donate

report bug (including invalid html)

Golden Key Campaign Blue Ribbon Campaign