Re: Amoeba's approach to capabilities

[Jonathan S. Shapiro]

On Fri, 2005-10-07 at 17:16 +0200, Ludovic Courtès wrote:
> Hi Jonathan,
> 
> "Jonathan S. Shapiro" <address@hidden> writes:
> 
> > Capability systems can be divided broadly into two types: protected and
> > unprotected.
> 
> [...]
> 
> > 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.
> 
> I understand that having capabilities which are not representable as
> bits (like references in Java, Scheme, etc.) is a very strong property.
> In particular, transfer can only occur with the cooperation of the
> trusted kernel, as you said.
> 
> Yet, practically, what impact does it have?  File descriptors, within a
> Unix process, can be easily guessed for instance, because they are known
> to be allocated incrementally starting from 3.  It would be harder if
> they were randomly allocated...

Calling these numbers "file descriptors" was a very bad choice of UNIX
terminology. It is the file table entries that are the true descriptors.

Rather than argue with the terminology, let me give a new set of terms
so that we can un-confuse the discussion.

In a protected capability system, the capabilities themselves are in the
kernel. They are referenced by some form of address relative to a
capability address space. The correspondence to UNIX ideas is the
following:

    UNIX                  CAPABILITY SYSTEM
    file descriptor       capability index (or address)
    file table entry      capability
    file table            capability registers (or C-address space)

The capability index (file descriptor) is NOT a capability. It is a
*name* for a capability. The ability for you to guess the names that I
use for my capabilities is harmless. What is important is that you
cannot obtain copies of the capabilities themselves.

One qualifier to this statement: guessing the names is harmless
*provided* we are using private name spaces. (In L4sec speak: "local
names"). If we are using a globally shared namespace, then the ability
to guess names provides a channel for communication. This is because you
can detect names that I have bound, and the presence or absence of a
binding can be used to signal a 0 or 1. The resulting channel is
actually a very high bandwidth channel. Thus: local name spaces are a
foundational idea in secure systems.


>   Pointers to valid data within a 32-bit
> address space are also not that easy to guess (provided one doesn't have
> any knowledge of the underlying OS internals).

There is pretty overwhelming documentation in the literature that this
statement is incorrect. In fact, it is incorrect for 64 bit pointers
also. Address space randomization has been shown to be entirely
ineffective because of this.

> How about capabilities
> on top of L4 X.2 containing one field which is the (globally unique)
> thread ID of the server thread (the original proposal of Marcus)?

This would be a good example of (a) an unprotected capability system
that (b) uses a globally shared namespace. Bad on both counts. Ignoring
the security issue, exposing the thread ID also makes it very difficult
to alter the server implementation to be multithreaded.

If this had a prayer of working safely the L4 people would not be
building L4sec.

> Also, the idea of being able to implement a capability system without
> relying at all on a trusted kernel (i.e. real distributed capabilities)
> is quite attracting.  But this comes at the cost of losing confinement,
> indeed.  I'm starting to understand those ideas and tradeoffs.  ;-)

Yes you would lose confinement, but there is no possibility of
implementing a capability system without a trusted kernel (or runtime).
*Something* has to provide basic isolation enforcement. If you don't
have this, then you cannot protect the cryptography, and if you can't
protect that you have no protection at all in the kind of system you are
contemplating.

> 
> > 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.
> 
> So this is the lack of confinement, right?

Yes. If you dig in to Boebert's paper, you find an assumption buried in
the work: he assumes that capability transfer and data transfer cannot
be distinguished. His conclusion was correct if you proceed from this
assumption, but it should be noted that even the capability systems of
the time did not actually have this weakness.

[In fairness to Earl, he was required by the DoD to make a last-minute
edit to the paper prior to publication, removing a final sentence that
would have clarified this.]

> > 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.
> 
> Right.  This corresponds to what's advocated in [0]: a distributed
> protected capability system /can/ be implemented provided both machines
> run a "trusted" language runtime that hides the network representation
> of capabilities to the code that uses it.

Or equivalently, a trusted kernel might be used instead of a trusted
runtime.

> 
> > 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.
> 
> Well, it does not allow to control their transfer (no confinement).
> Yet, they are hardly forgeable or guessable in actuality.

Actually, they are pretty well guessable

More importantly, the inability to restrict their transfer is not a
little thing. It's more of a "this architecture is completely and
unfixably broken" sort of a problem.

> If we look at [1], A and "someone" are "not supposed to speak"; however,
> due to the lack of confinement, A is able to pass a capability to
> "someone", right?

I can't answer that, because I do not see any reference on that page to
"A", and the phrase "are not supposed to speak" does not appear. Can you
clarify the question?

> >   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.]
> 
> I'm not sure I understand what you mean by "precompile".

Suppose I am a developer. I am writing code for a system where
capabilities are unprotected (i.e. they are just data). I want to build
a program that can send me your credit card number. Here is what I do:

1. I construct the capability (the bits) that represents the right to
make a network connection. I store this into a file.

2. To prevent you from doing a "scan" for this capability, I now
compress this file with gzip, or simple permutation, or anything else
that makes it look unlike a capability.

3. I take the resulting bits (which I know how to decode) and compile
them into the program as a constant byte string.

4. At runtime, I decompress them and invoke the capability.

Yes, this particular example can be circumvented. The Mungi PDX design
is one really interesting way to do so (which was adapted from an
earlier system by Pose). However, all of the strategies that can
eliminate this scenario fall into two categories:

  1. Re-introduce protected capabilities
  2. Engage in a war of escalation.

When you engage in a war of escalation in computational systems, the bad
guy *always* has a fundamental advantage, because he can use more power
in the attack than you can in the defense.

> Thanks for your explanations!

Hey, confusing people is what I do for a living!

shap