From: Zooko <>
Date: Mon, 02 Dec 2002 07:42:14 -0500
Subject: Re: [e-lang] Commentary on "A State Transition Model of Trust Management and Access Control"

about:  [Chander01] Ajay Chander, Drew Dean, John Mitchell, "A State Transition 
Model of Trust Management and Access Control", 14th IEEE Computer Security 
Foundations Workshop.

 Jonathan Shapiro wrote:
> Speaking for myself, I would argue that the paper has a more fundamental
> flaw. Mathematically, the paper appears basically correct, but its
> conclusion has almost nothing to do with the math, 

Your criticism is quite apt, Jonathan.   Moreover, the math actually *disproves* 
some important parts of the conclusion, for example in section 6.5, it says 
"Capability systems modeled as unforgeable references present the other extreme, 
where delegation is trivial, and revocation is infeasible.".  At the end of 
section 5.1, they write "Note that we don't allow a 'Revoke' action for 
capabilities.  The nature of capability based systems makes it infeasible in 
general to implement revocation unless the Pass action is somehow monitored.  
This is formalized in Lemma 6.5."

But in Lemma 6.5 (in Section 6.2) what is proven is that M_acl (their model of 
ACLs) cannot simulate the "Remove" action of M_c_ref  (their model of 
capabilities-as-references) in constant time.  This is the opposite of what was 

Section 6.2 as a whole proves that M_c_ref can simulate M_acl including M_acl's 
"Revoke" action.   (They accomplish this by generating a fresh capability for 
each principal to whom they grant access, so that they can later revoke that 
particular principal's access by "Remove"'ing that capability.  Their model 
explicitly allows for multiple separate capabilities to refer to the same 

When I met Dr.  Mitchell at the Workshop on Information Security and Economics, 
he said that they had begun the project while under the impression that 
capabilities were simply rows of the Lampson access matrix, and that doing the 
math had shown them that capabilities modelled as unforgeable references were 
not the same.  My suspicion is that at some point in writing the paper they 
updated all the math, but accidentally left incorrect statements in the English 

At the time I wasn't familiar enough with the paper to effectively bring the 
contradictions to Dr. Michell's attention.   (Instead I waved my arms 
enthusiastically and said that POLA a la MarcS's story about trying out a text 
editor was really important.  He appeared to be interested in the idea.) marcs

Now, despite its flaws, there are valuable contributions offered by this paper, 
which are  (a) a mathematical model of capabilities modelled as rows of the 
Lampson access matrix, (b) a mathematical model of capabilities modelled as 
unforgeable bitstrings, (c) a proof that the former is equivalent to ACLs (okay, 
so we all knew that), and (d) a proof that the latter is strictly more 
expressive than the former.

The M_c_ref model does not enforce the restriction that the granter of a 
capability (c_o) must have a capability to the *recipient*  (c_r) in addition to 
having c_o itself.  I believe this is what MarkM calls "compositional" in his 
new document.

There is an opportunity here for someone to define M_c_granovetter and show 
mathematically how it differs from M_c_ref... 



e-lang mailing list