[cap-talk] an access control matrix model of capabilities

[Zooko]

In this note, I describe a principle of access control: The Principle of 
Higher-Order Least-Privilege.  I argue that an "unextended" ACL system cannot 
conform to this principle.  I then describe a simplified access control model 
and make two modifications to it in order to implement Higher-Order 
Least-Privilege.  The end result is the capability access control system, as 
modelled by a two simple rules governing changes that can be made to an 
(extended) Lampson access control matrix.  My primary objective in posting this 
note to this list is to find out if this model is novel (not to mention to 
verify if it is correct).

[For those who don't want to read the model-building and rationale, you can skip 
down the "The Punchline", below.]


A salient feature of capability access control is that it can implement the 
"Principle of Higher-Order Least Privilege".  The (first-order) Principle of 
Least Privilege is that an object X should be able to use an object Y, while 
extending to Y only the minimal set of privileges necessary for Y to do its 
work.  This Principle can (at least in theory) be implemented by an ACL system.

The "Higher-Order Principle of Least Privilege" states that object X should be 
able to impose Least-Privilege constraints on object Y without X using any more 
than the minimal authority necessary to do so.

Only if an access control system supports Higher-Order Least-Privilege can an
object Y be simultaneously constrained (Y can have a subset of the authorities 
of its user X) and constraining -- a third object Z can have a subset of Y's 
privileges.

I will now take a simple access control matrix model and extend it in the 
attempt to achieve Higher-Order Least-Privilege.  I assert that the end result 
is the capability access control model.

The access control matrix consists of rows which are "subjects" -- things able 
to wield authority, and columns which are "resources" -- things to which we can 
control access.

In the first system, "S_0", there is a distinguished entity (the "admin") who is 
able to create new subjects.  Subjects can extend privileges that they own to 
other subjects, but they cannot create other subjects.  Subjects can also 
"switch" (setuid) to other subjects in order to execute code.  If a subject X 
wants to execute some code while allowing that code only a subset of X's 
privileges, X could extend a subset of X's privileges to another subject Y and 
then execute the code after setuid to Y.  However, X would have no way to 
guarantee that Y didn't hold other dangerous privileges.

As an example, X may hold the privilege to read a certain sensitive file and the 
privilege to send data to the network.  X may want to execute code with the 
former privilege but not the latter, in order to preserve the file's 
confidentiality.  X could extend the former privilege to a different subject Y, 
setuid to Y, and then execute the code, but X would have no guarantee the 
Y didn't have the "send to the network" privilege from a different source.  So 
X cannot safely enforce Least-Privilege on the code.

The only way to achieve Least-Privilege in model S_0 is for the admin to create 
a new subject T, grant to T the minimal necessary rights, take away all other 
rights from T, and enforce that T cannot receive any other rights while 
executing the code.  T cannot then extend a subset of those rights to another 
subject without also using the admin's powers.  Therefore, S_0 can implement 
Least-Privilege, but cannot implement Higher-Order Least-Privilege.  

We extend S_0 into S_1 by making it possible for ordinary subjects to create new 
subjects without recourse to "admin power".  A subject X can now create a 
subject T, extend a subset of X's rights to T, setuid to T, and execute the code.
T could in turn create another subject U, extend a subset to T's rights to U, 
and so forth.

Unfortunately S_1 still has the problem that T might gain privileges from 
another source.  X cannot grant T the privilege of reading the confidential file 
because X can't be sure that someone else won't grant T the privilege of sending 
data to the network.

The final change to the model then is to constrain which subjects can grant 
privileges to which other subjects.  We extend the Lampson access control matrix 
with a new column for each row.  This column represents the privilege of 
granting privileges to each individual subject.  In this new system, S_2, a 
subject X can grant privileges to a subject Y only if X has the privilege in 
question *and* has the "privilege to grant privileges to X".  When a new subject 
is created, only its creator has the privilege to grant privileges to it.  The 
"privilege-to-grant-privileges" can be granted just like other privileges.

S_2 implements the Higher-Order Principle of Least Privilege.  It is also 
identical to the capabilities system of access control.


The Punchline

In an ACL system, subject X can grant privilege P to subject Y only if X holds 
privilege P -- that is, only if X can access the P column of the (original) 
Lampson access control matrix.  In a capability system, subject X can grant 
privilege P to subject Y only if X holds privilege P and the privilege-to-
grant-privileges to Y -- that is, only if X can access both the P column and 
the Y row of the (original) Lampson access control matrix.


I would be very grateful to have your comments on this model and pointers to 
related work in the literature.

Regards,

Bryce "Zooko" Wilcox-O'Hearn

http://zooko.com/
         ^-- under re-construction: some new stuff, some broken links