Re: Amoeba's approach to capabilities

[Jonathan S. Shapiro]

On Fri, 2005-10-07 at 14:02 +0200, Ludovic Courtès wrote:
> Hi Bas,
> 
> Bas Wijnen <address@hidden> writes:
> 
> > I think anything protected by sparsity is fundamentally flawed and
> > unacceptable, especially for something as critical as the kernel.
> 
> I think I understand what you mean.

This note is in answer to Ludovic's question, but I think that it is
worth answering in a general framework.

Capability systems can be divided broadly into two types: protected and
unprotected.

A protected capability system is one in which the representation of a
capability is guarded by some form of partitioning. There are two common
methods for this partitioning:

1. Protection by separation, either by the OS, as in EROS, KeyKOS, and
Coyotos, or by the hardware as in the i432 or the fourth layer of the
original i960 architecture. In the OS form, the process uses an index
into an OS-maintained table (or equivalently: an address relative to an
OS-maintained capability address space).

2. Protection by a language runtime, as in Ree's W7 or (less strongly)
Java. Pointers in these systems cannot be fabricated arbitrarily from
data.

The key characteristics of a protected capability system are:

  + There is no way for applications to fabricate capabilities
    out of data. This is often stated as "capabilities are unforgeable".
  + Transfers of capabilities are performed in collaboration with
    the runtime system (OS: via IPC, Runtime: via pointer copy).
  + In consequence, it is possible to construct system designs s.t.
    capabilities initially held by an application cannot be "hidden"
    from security monitors.
  + It is also possible to construct systems in which, by virtue
    of authority confinement, capabilities cannot be transferred.

Because of these properties, Boebert's famous claim that "unmodified"
capability systems cannot enforce the *-property (and in fact cannot
enforce security policies in general) is incorrect for protected
capability systems (Boebert agrees).

Unprotected capability systems include all systems where the capability
is expressed as data. This is attractive because it simplifies the
interprocess communication transport, but it is not securable for
reasons I will discuss below. There are two common methods for this
partitioning:

1. Protection by encryption (as in SPKI/SDSI)
2. Protection by sparse allocation (as in Amoeba)

Both approaches have the problem that a capability can be precompiled
into the data space of the program in an undetectable way (e.g. by
compressing the bits), and that capability transfer can be hidden in a
similar fashion.

Boebert's claim that "unmodified" capability systems cannot enforce the
*-property is correct for unprotected capability systems.

There are some further complications when one begins to think about
distribution. The right way to think about this is that a distributed
capability system is one in which the TCB has been distributed. Exposing
the capability bits within the TCB (or within two collaborating TCBs) is
not a problem. This implies that building an encrypted connection
between two mutually trusting kernels doesn't violate my definition of
"protected". The "protected" part only concerns interactions between
applications and the TCB.

> I don't understand how [sparsity] relates to Amoeba's capability
> implementation, summarized like this:
> 
>      A capability typically consists of four fields as illustrated in Fig. 2.
>   1. The put-port of the server that manages the object
>   2. An object number meaningful only to the server managing the object
>   3. A rights field, containing a 1 bit for each permitted operation
>   4. A random number, for protecting each object
> 
> (1) is a globally-unique identifier returned by the kernel, (2) is
> computed by the server managing the object, and (4) is computed using a
> secret random number known only to the server (the random number itself
> is not part of the capability, unlike one might think from the above
> description).
> 
> How _this_ is protected by sparsity?

The random number is sparsely allocated from a large space.

Andy (Tannenbaum) was a bit optimistic in his belief that this was good
enough. Sparsity does not protect these capabilities at all, and cannot.

When Andy made his design choice, he was asking "How hard is it for a
client to make one of these things up, or to guess one?" You need to
remember that computers were a lot slower then. I thought that the
amoeba 80-bit random number was too small even then, but it wasn't
obvious.

What Andy failed to consider was the problem of hostile or collusive
programs, such as:

  1. Authorized program A intentionally hands a capability out to
     someone who shouldn't have it, or

  2. Hostile developer D precompiles some capability bits into an
     application so that they can leak information.

     [By the way, this really happens! Eric Allman is known to have
      installed a root backdoor into early versions of sendmail
      for purposes of remote administration.]

Beating these problems requires the ability to enforce authority
confinement, which is why the Boebert quote is relevant. If you can't do
the *-property, you cannot do confinement (and vice versa).

> However, my understanding of this is that capabilities are
> computed using information known only to the server implementing them,
> which makes it "hard" to forge new capabilities.... Maybe the whole
> difference is here: I consider that "hard" means "next
> to impossible" (if you know that a given server implements an object on
> a given port, you still have to guess 80 bits, which is not something
> that can reasonably be performed by brute force), but you seem to
> believe that it's not that hard.  Is that correct?

Yes, this was the underlying assumption in Andy's design, and given the
hardware of the time it was reasonable as far as it went. The essential
deficiency in the approach is that Andy didn't consider other ways in
which capabilities might be abused.

Of course, 20 years from now people will probably say the same thing
about EROS.

shap