/ elib / capability

Overview: Capability Computation

"The Three Parts of Security" is a great short statement by Bill Frantz of the problems a security architecture needs to solve. Capabilities address well the problems Bill states.

Read Marc Stiegler's gentle "Introduction To Capability Based Security".

Modern capability security theory comes mostly from the work of Norm Hardy, Charlie Landau, Bill Frantz and others while at KeyLogic. Check out Norm's "Capability Theory by Sound Bytes".

"Capability-Based Computer Systems" by Henry Levy is the classic old book surveying old capability systems, with an emphasis on their implementations. The whole book is now online at this URL. It provides a good historical perspective of the non-Actors, pre-KeyLogic world of capabilities.

Jonathan's Shapiro's "What is a Capability, Anyway?" and "Comparing ACLs and Capabilities".

Kragen Sitaker's "The Three Security Architectures".

"Capability Myths Demolished" gives a brief history of how capabilities have been misunderstood, and sets the record straight.

In the diagram on the right, the object Alice starts off pointing at the objects Bob and Carol. More explicitly, part of Alice's state (typically a Slot within Alice's scope) holds a reference to Bob, and likewise to Carol. The diagram and the following code show Alice passing a message to Bob containing a copy of Alice's pointer to Carol:

def alice {
    to doSomething() {
        bob.foo(carol)
    }
}

Because Alice has a reference to Bob, she can pass him messages. These messages may contain copies of other references Alice has -- in this case, a copy of Alice's reference to Carol. By passing this message to Bob, Alice gives Bob access to Carol. We can think of this as an introduction with Alice as the introducer. Once Bob receives this reference, he can use it to pass messages to Carol, he can remember it for future use, and he can pass it on to others to which he has access. The pure-object computational model requires all these actions to be possible.

When speaking of object computation, all too much emphasis is often placed on the objects themselves. The fabric of an object system is the dynamic reference graph. As suggested by the Granovetter Diagram, objects are the nodes of this graph, references are the arcs of the graph, and computation within the graph brings about changes to the topology of the graph (the who points at who relationships), but only changes that are enabled by the graph's current topology. To learn to think in E is initially to be able to see the dynamic reference graph as primary, and objects as secondary.

Capability Fundamentals

The capability model of computation is almost equivalent to the pure object model of computation, as explained in "From Objects to Capabilities". Much of the point of E is to unify these models. The key attribute shared by object computation and capability computation is that only connectivity begets connectivity.

So how does connectivity beget connectivity? In "Only Connectivity Begets Connectivity" we explain all the ways Bob can come to hold a reference to Carol.

Although it does not actually need to be primitive, "Rights Amplification" is best thought of as a capability primitive, and most modern capability systems, including E, provide it as a primitive. In rights amplification, two capabilities, when brought together, can yield more than the sum of the rights of the two used separately. This enables capabilities to directly express security patterns familiar in the cryptographic literature.

Closely related is the issue of testable object identity (or EQ identity, to you Lisp hackers.) Can one tell that two capabilities both refer to the same object? And does it matter? Surprisingly, it does, and needs to be a primitive, as explained in "The Grant Matcher Puzzle". This primitive provides the only means to combine trust.

Capabilities have often been criticized for not enabling one to prevent delegation. In "Prohibiting Delegation", we divide the "delegation" issue into four sub-problems. By examining the problems individually, we dispell the widespread confusion on this topic -- and see that capabilities are strictly superior to ACLs (Access Control Lists).

"Lambda for Humans: The PetName Markup Language" explains an user-interface for enabling humans to securely interact with a world of capabilities, and to use capabilities to securely interact with other humans.

Distributed Capability Fundamentals

"The Essence of Pluribus" explains the core idea of E's cryptographic capability network protocol. "Unibus Sketch" sketches a single-key variant of Pluribus, in order to demonstrate the independence of the cryptographic capability concept from the particular choice of cryptographic substrate.

"Matching Distributed Grants" explains a man in the middle attack that a distributed capability system could be vulnerable to, and shows how a distributed application of the Grant Matcher logic enables us to avoid it.

Distributed cryptographic capabilities have all the security properties of local capabilities, with two exceptions:

• Distributed capabilities lack the confinement-constraint of capability-introduction ["already has a reference to Bob"]. So can distributed capabilities be confined? Surprisingly, the answer is yes, but only in limited ways, as explained in "Distributed Capability Confinement".

• Whereas local capabilities are reliable conveyors of messages, due to the unreliability of networks, distributed capabilities cannot be better than fail-stop conveyors, and E's live references are indeed fail-stop. Usually this is fail-safe from a security point of view, but non-delivery of messages for revoking authority would fail-unsafe. This necessitates adding the "Dead-Man Switch" to the distributed capability model. The result is a novel solution to the distributed revokation problem that's both fail-safe and efficient.