A Gentle Introduction to Capabilities
A capability is an unforgeable, transferable permission to use the resource it
1
designates. An important property is that a capability combines the designation of the
resource with the permission to use it. Capabilities are used to do access control in a
way that is not familiar to most people. This post explains the capability approach and
why it is better.!
The Access Matrix
Access control, which specifies who can do what, is fundamental to security. A
common way to represent the rules is with the access matrix. You can see in this
example that Alice has read and write permission to File2 and read permission to File3.
This matrix is sparse. In this example, there are 16 cells but only 7 are filled. In a real
system, there might be millions of cells with only a small percentage filled. Rather than
waste all that space, we compress the matrix either by columns or by rows.!
Collapsing the matrix by columns gives us access control lists (ACLs). For each
resource we have a list of users and what permissions each has to that resource.
When Alice wants to read File3, she presents proof she is Alice, so the system knows
which entry to check.
File1
File2
File3
File4
Alice
RW
R
Bob
RW
RW
Carol
R
RW
Dave
RW
File1
File2
File3
File4
Bob(RW)
Alice(RW)
Alice(R)
Carol(RW)
Carol(R)
Bob(RW)
Dave(R)
I’ve italicized the word to denote that it has a special meaning in this context. We normally
1
use the word capabilities to denote the set of things you are able to do or the services you
provide. As you can tell from the definition, here it means the set of things you are permitted to
do. You may also come across object capabilities, a term coined to avoid having to write a
paragraph like this one.
1
Collapsing the matrix by rows gives us capability lists (c-lists). For each user we have a
list of resources and what permissions that user has to each. Each entry is a capability.!
At first glance, it appears that there is no reason to pick one compression over the
other. In fact there are two.!
Making Easy Things Safer
Say that Bob wants to replace the contents of File3 with the contents of File1. In
Linux, which uses ACLs for access control, Bob would enter the command!
cp File1 File3!
on the command line. The problem is that the process running the cp command needs
all of Bob’s permissions in order to read and write any file Bob might specify. What
could possibly go wrong? For one, the cp program might have been corrupted to run
CryptoLocker, so Bob will be out buying Bitcoin to pay the ransom. It wouldn’t be so
bad if cp was the only program that needed all of Bob’s permissions, but using ACLs
requires that every program Bob runs does. That’s why a virus can do so much
damage.!
The cat command takes open file handles instead of strings representing the file
names. Bob would enter the command!
cat <File1 >File3!
Here, “<“ denotes a Linux file handle opened with read permission, and “>” denotes
one opened with write permission. The process running cat doesn’t need any of Bob’s
permissions; they get passed in as part of the invocation. If cat runs CryptoLocker,
only File3 gets encrypted, and Bob wanted to replace its contents anyway. !
It turns out that a Linux open file handle is an unforgeable, transferable permission to
use the resource it designates, i.e, it is a capability. !
Alice
File2(RW)
File3(R)
Bob
File1(RW)
File3(RW)
Carol
File1(R)
File4(RW)
Dave
File4(RW)
2
Making What You Want to Do Easy
If the access matrix was static, there wouldn’t be much more to say about the
differences. However, you do need to make changes to get your work done. Alice
would like Carol to edit File2, and Carol would like Dave to help her. When the work is
done, Alice would like to remove Carol’s permission. !
A big problem with ACLs is that the model doesn’t include updates to the access
matrix. New mechanisms had to be added. That’s why Linux has the concept of root,
a special user with the ability to change ACL entries.!
Alice has to find someone with root privileges in order to give Carol read and write
permission to File2. One problem is that the audit log shows that root made the
change. Nowhere does it say the change was made because Alice asked. When Alice
asks root to revoke Carol’s permission, how does root know whether or not Alice has
that permission? The answer is not part of the ACL model.!
There’s another problem. Carol asks the root user to give Dave read permission to
File2, and root will almost certainly do that, since Carol has read permission. The
problem comes when Alice revokes Carol’s permission. There’s nothing to say that
Dave’s permission should be revoked too. If you don’t, Dave could give permission
back to Carol, subverting Alice’s revocation request.!
Sure, you say, but at least root has ultimate control over these delegations. In fact, that
control is an illusion. If root refuses Alice’s request, and Alice thinks it’s really
important, she’ll just share her credentials with Carol. Now, you’ve got worse security,
because Carol has all of Alice’s permissions when she only needs one of them. All of
this has become so complex as to be completely unmanageable. !
Using capabilities makes it all simple. I’ll use some pseudo code to illustrate.!
main() {!
let a = A::new(); // a is an object reference and a capability!
let b = B::new(a); // capability b has a capability to a!
}!
The variable a is an object reference. In a language like C or C++ that has pointer
arithmetic, a is not a capability because it’s not unforgeable. In a memory safe
language, such as Java or JavaScript, a is a capability.!
The next snippet shows delegation.!
3
Class B {!
A a;!
fn new(a) {!
this.a = a; // b is born with a capability to a!
c = C::new(); // b has a capability to an object it creates!
a.introduce(c); // a has a capability to c by introduction!
}!
}!
This snippet shows the three ways to get a capability. Note that object b needs a
capability to a and one to c to do the introduction.!
Chained delegation is shown in the next snippet.!
Class A {!
D d;!
fn new() {!
this.d = D::new(); !
} !
fn introduce(c) { !
d.introduce(c);!
}!
}!
The example shows that blocking chained delegation is as silly as having a
programming language with only one level of function call.!
If you don’t want object d to have all of c’s permissions, you can introduce a level of
indirection as in the next snippet.!
Class B {!
A a;!
fn new(a) {!
this.a = a; !
c = C::new();!
r = RO::new(c)!
a.introduce(r);!
}!
}!
Instead of delegating object c, you delegate a read-only facet, which forwards only
read requests.!
You can use the same trick for revocation as shown in the next snippet.!
4
Class RO isa C {!
C c;!
fn new(c) { this.c = c; }!
fn read(arg) { this.c.read(arg); }!
fn write(arg) {}!
}
Class B {!
A a;!
fn new(a) {!
this.a = a; !
c = C::new();!
p = Proxy::new(c)!
a.introduce(p);!
p.revoke();!
}!
}!
When object a invokes any method on the proxy, the proxy forwards the request until
the proxy’s revoke method is invoked. After that, invoking a method on the proxy
results in a null pointer exception.!
Across Machines
All the examples in the previous section assume the objects are on the same machine.
Fortunately, you can use the same patterns across machines, but there’s a significant
difference. Since you can only send bits on the wire, you can’t have unforgeable
capabilities. That means, a distributed capability is an unguessable, transferable
permission to use the object it designates. Nevertheless, all the patterns shown in
the previous section have distributed analogs.!
You may not know it, but you’ve probably used distributed capabilities. The Dropbox
link https://www.dropbox.com/s/g1gpwz2vbas2zdb/Capabilities-101.pdf?dl=0 has all
the properties of a distributed capability. It’s unguessable, transferrable, and a
permission. You even get it the same three ways. It also combines the designation of
the resource with the permission to use it. Unfortunately, Dropbox doesn’t support
attenuated delegation or revocation by anyone other than the owner of the file. It
makes you wish they had understood capabilities when they designed their system.!
Unfortunately, the most widely used form of authorization tokens, OAuth 2 bearer
tokens, are not capabilities, as shown in the following command line. !
curl -H "Accept:application/json"
-H “Authorization:Bearer 2wRlsRCT2SYjCCJP91kwo2EFzj5qg4O3I3aC09"
“https://example.com/service
The authorization token is separated from the designation of the resource. The most
obvious risk is giving up a permission by sending the authorization token to the wrong
URL. Another problem was that originally OAuth 2 did not support attenuated chained
delegation or revocation, but recent developments have added these features. !
5
Class Proxy isa C {!
C c;!
fn new(c) { this.c = c; }!
fn any() { this.c.any(); }!
fn revoke() {!
this.c = null;!
}!
}!
Since it’s still better to use authorization tokens than ACLs, we give such systems a
name, authoriZation-Based Access Control (ZBAC).!
The Rest of the Story
There are several proposals for making the patterns shown in the code snippets work
across machines, but I can’t honestly say that they belong in a gentle introduction.
Check out sources such as “What Are Capabilities?” at Habitat Chronicles. If you want
a deep dive, you’ll find everything you need at http://erights.org/ and pages it links to. I
particularly recommend Mark Miller’s Ph.D. thesis.!
Alan Karp!
Palo Alto!
7 April 2018
6
