From:
Zooko <zooko@zooko.com>

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
claimed!
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
object.)
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
prose.
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...
Regards,
Zooko
_______________________________________________
e-lang mailing list
e-lang@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/e-lang
```