[e-lang] "Capability Myths Demolished" (was: Software security workshop)

Tyler Close e-lang@mail.eros-os.org
Thu, 28 Nov 2002 14:09:51 -0400


On Tuesday 26 November 2002 06:15, Mark Miller wrote:
> At 12:56 AM 11/26/2002 Tuesday, David Wagner wrote:
> >For fun, take a look at the list of sample topics for the Outrageous
> >Opinions session
> > (http://dimacs.rutgers.edu/Workshops/Software/program.html). Here's a
> > great chance to advocate for capabilities!
>
> At 08:42 PM 11/25/2002 Monday, Mark Miller wrote:
> >(I stupidly delayed announcing these pages until they were less rough,
> >which never happened.)
>
> These remind me of another very preliminary draft I never announced but
> should have:
>
>                "Capability Myths Demolished"
> at http://www.erights.org/elib/capability/duals/index.html
>
> As the red text at the top explains, I already know this essay is broken in
> some ways. But without more feedback I'm not getting around to fixing it,
> so fire away.  Even in its current flawed state, I think many of you will
> still find it quite interesting -- perhaps even outrageous.

I think your paper could do a better job of taking apart Lampson's
"Protection" paper. The concept of the "access matrix" is at the
root of most of the misconceptions surrounding ACLs and
capabilities.  To be completely effective, I think we must point
out how misguided the core access matrix concept is.

The main point of confusion is the belief that Lampson's access
matrix models both the ACL and capability systems. This is plainly
false to anyone who understands capabilities and how a C-list is
used. In the "Protection" paper, Lampson clearly demonstrates a
misunderstanding of the C-list mechanism.

The purported equivalence of the ACL and capability models is
established in the section titled "Some implementation
techniques". The purpose of the section is to suggest some methods
for efficiently storing the sparse access matrix A. In this
section, Lampson claims that the ACL and capability models are
just two different ways of storing A. It should be obvious that
this method cannot yield an equivalence, since the difference
between the two models is in how the access matrix is used and
grown, not how it is stored. Nevertheless, I'll go through
Lampson's argument in detail and show exactly where his confusion
arises.

After explaining the efficiency concerns, Lampson suggests storing
the table T of triples <d, x, Adx> as a list of pairs <x, Adx>
attached to Domain d. He then says:

"One of these pairs is usually called a capability".

Here is where Lampson demonstrates his misunderstanding of
capabilities. These pairs are *NOT* capabilities. A capability is
*used* for both designation and authorization. Lampson's access
matrix model does not *use* the <x, Adx> pair for designation, and
so is still an ACL model, not a capability model.

It would appear that Lampson became confused because of a
familiarity with the implementation of capabilities using C-lists.
The memory structure that Lampson proposes is exactly the same as
that used for a C-list. This likely led Lampson to believe that he
was implementing a C-list. He is not. The difference between the
Lampson mechanism and an actual C-list is in how the memory
structure is *used*.

I'll demonstrate the difference between the two structures using
the notation of the Lampson paper:

http://research.microsoft.com/%7Elampson/09-protection/WebPage.html

and the example of the Confused Deputy problem demonstrated by
Norm Hardy at:

http://www.cap-lore.com/CapTheory/ConfusedDeputyM.html

First, I'll briefly setup the scenario. There are 2 domains: Dc,
the compiler domain; and Du, a user domain. There are 3 objects:
F1, the compiler log file; F2, a user input file; and F3, a user
output file. Initially, the access matrix A is:

            F1          F2          F3
            ----        ----        ----
    Dc      write
    Du                  *read       *write

The <x, Adx> pairs stored at Dc and Du are:

    Dc              Du
    ----            -----
    <F1, write>     <F2, *read>
                    <F3, *write>

In the expected scenario, Du wishes to compile F2 to create output
file F3. In order to bill Du for the service, Dc will append an
entry to log file F1.

In the Lampson mechanism, this exchange would be setup by Du
giving Dc read access to F2 and write access to F3. This changes
the <x, Adx> pairs to:

    Dc              Du
    ----            -----
    <F1, write>     <F2, *read>
    <F2, read>      <F3, *write>
    <F3, write>

Using the Lampson mechanism, the compilation task would proceed
as:

1.  Du asks Dc to compile F2 to F3.
2.  Dc receives request message (Du, F2, F3).

3.  Dc tries to read from F2.
4.  F2 receives a request message (Dc, read).
5.  F2 checks that Dc has the <F2, read> entry in its pair list.

6.  Dc tries to write a log entry to F1.
7.  F1 receives the message (Dc, write, somedata).
8.  F1 checks that Dc has the <F1, write> entry in its pair list.

9.  Dc tries to write the compilation output to F3.
10. F3 receives the message (Dc, write, somedata).
11. F3 checks that Dc has the <F3, write> entry in its pair list.

The execution in the capability model is slightly different, but
in an important way. First, there would be no setup phase.
Instead, in step 2 Dc would receive the request message
(<F2, read>, <F3, write>). The lookup in the Du pair list would
happen immediately, as a result of sending the request to Dc. Dc
would never be aware of the object identifiers F2 and F3. Dc would
only work *using* the <x, Adx> pairs to designate the compilation
files. At each step in the above process, the object identifier
would be immediately replaced with the corresponding <x, Adx> pair,
*before* any message is sent. The target object would not need to
consult the pair list itself after receiving the message. The
validation step always comes before the request step.  A request
cannot be made without the validation step coming first, since the
target of the message is determined by the validation step. This
is the essense of the capability model. A request is made using a
capability that both designates and authorizes access to the
target object. In the ACL model, a request is made using only a
target object identifier. The target object must then validate the
request *after* receiving it.

A C-list is the name of a mechanism used to implement message
dispatch in a capability system. The Lampson data model is *not* a
C-list, it is just a different way of storing an access control
list.

At this point it should be clear that the Lampson model does *not*
encompass the capability model. To date, the misunderstanding of
this basic fact has been a severe stumbling block to the
understanding of capability based security.

This difference between the ACL and capability models is very
important. It is because of this difference that the ACL model is
vulnerable to a class of attacks known as the Confused Deputy.
The capability model is not vulnerable to this type of attack.

If in step 1, Du sends message (F2, F1), then in step 9, Dc will
try to write to F1, not F3. In step 11, F1 will validate the
request because Dc has the <F1, write> entry it its pair list.
This will result in the billing log being overwritten with the
compilation output. In this case, Dc is said to be a confused
deputy.

At runtime, Dc is running on behalf of both Du and the software
billing company. In step 9, Dc could not tell if the authority it
was exercising came from Du or the billing company. This is a
systemic flaw in the ACL model. The flaw is directly attributable
to the fact that the ACL model separates designation and
authorization.  A request is delivered with the full authority of
the sending domain. The sending domain has no way of specifying
what part of its authority should be used for the request.

There are a number of other really bad errors in the Lampson model
and in the Lampson paper. I think if we beat on these, the
misconceptions resulting from the Lampson paper will automatically
dissipate. Or, at least I hope so. I cannot believe that this
thing has lasted over 30 years.

Tyler