[cap-talk] Confused Deputies and Rights Amplification

[Jed Donnelley]

At 08:14 PM 2/19/2008, Charles Landau wrote:
>At 1:48 PM -0500 2/4/08, Jonathan S. Shapiro wrote:
> >Norm will jump in if I get this wrong, but I think it is safe to say
> >that both of us feel that no rights amplification operation should exist
> >in a properly designed capability system.
> >
> >Or at least, that was his initial position, which gave both of us some
> >discomfort about the can-opener operation in KeyKOS/EROS.
> >
> >Subsequently, I have modified my stance on this. It seems fairly clear
> >that:
> >
> >   Any rights amplification operation that could, in principle, have
> >   been accomplished in the absence of the amplification operation
> >   (perhaps with a much higher storage or computational cost). Is
> >   not, strictly speaking, a rights amplification operation at all,
> >   and MAY be acceptable if it is implemented with sufficient care.

To me the above sounds a bit like my working guideline of only
"hidden" rights amplifications.  I think of this a bit like I
do about functional computing.  Composing functional (deterministic
dataflow) elements will always produce a functional result.
However, one can construct functional results from non-functional
pieces.  As long as those non-functional pieces have adequate
justification (e.g. cost) and can be hidden at a fairly low
level so that higher level compositions can ignore them, then
it seems to me architectural composability requirements can
be satisfied (i.e. no worries about non determinism/timing
dependence at the higher level).

I feel about the same with regard to rights amplification.  As
long as they can be hidden within higher level constructs that
don't amplify rights, then the obvious assumptions about
permissions in communicated capabilities being available to
the source are satisfied and no deputy "confusion" is possible
even with the simplest code.

> >I guess I would add one other qualifier. There are certain patterns,
> >such as seal/unseal, that CAN be implemented without an amplify
> >operation, but can only be implemented sensibly if 'eq' is available,
> >and can only be implemented efficiently if something like "keybits" is
> >available.  The decision to admit EQ into a design is a fairly
> >fundamental decision.
>
>That has always been my belief. Indeed, I don't know how to show that
>any rights amplification operation is safe, if it doesn't obey the
>above.

By "safe" in the above do you mean safe from Deputy Confusion?

Something like Horton uses rights amplification internally
(sealer/unsealer pairs) and can in principle result in any
sort of rights amplification when a capability is communicated
through a Horton tunnel.  However, if the policies inside the
Horton tunnels result in no amplification (less or equal permissions),
then I believe Horton can be composed with other "confused
deputy safe" capability facilities with no fear of deputy
confusion when used in the 'obvious' way - that is, if I
received this capability from that source, then I can assume
the source had the permission and I can exercise that permission
on its behalf.

>And this is the reason I believe EQ is a necessary operation.

Sorry, I don't follow.  EQ is a necessary operation for what?
I'm not disagreeing in that it seems to me that EQ is necessary
for any reasonably efficient membrane mechanism (how else to
check to see if a new capability being passed from inside to
outside can use the same extension capability it previously
used?), but I just don't see how it follows from what was
said above.

> >One view of the debate is that EQ, by virtue of
> >violating identity encapsulation, is itself a rights amplifying
> >operation.
>
>We said above that in a system with EQ but without other rights
>amplification primitives, you can theoretically implement rights
>amplification.

Certainly "MyCap?" (i.e. access to "private" data) is a strictly
weaker subset of EQ in that with EQ one can implement "MyCap?" (just
keep copies of all extended capabilities in a table and generate
the "key info" by searching the table and indexing).  This might
not be the most efficient way to implement "MyCap?", but it
would work.  "MyCap?" provides a basis for rights amplification,
so I would say the above (with EQ you can theoretically implement
at least some rights amplification) is certainly true.  However,
regarding:

>It would be interesting if it were possible to show that in a system
>with rights amplification but without EQ, you can theoretically
>implement EQ.

In general this can't be the case because, again using the "MyCap?"
example (needed to access "key info" data), one can see that EQ is strictly
stronger than "MyCap?".  There is no way to compare two arbitrary capabilities
with "MyCap?".  One can in principle compare any two "private" capabilities
by comparing their "key info" after successful "MyCap?" queries, but
non private capabilities will simply return "no" (i.e. not a private
capability) whether they happen to be "EQ" or not.  Therefore there
is at least one rights amplification example that cannot be used to
implement EQ.  This was the sense in which "MyCap?" without EQ
provides mildly better membrane "transparency" (transparent insertion).
If somebody gives me a capability and a membraned version of the
same capability, unless one is private to me (i.e. "I" am the
server), then I can't distinguish them with "MyCap?", but I
can with EQ.

Still, "MyCap?" by itself is inadequate to implement an efficient
membrane as multiple instances of the same capability passing
"out" of the membrane would have to inefficiently use distinct emulated
("key info") capabilities.

> >Oh. The essence of the user-mode implementation of canopener...

The "canopener" discussion was lost on me.  Perhaps somebody could
point to a motivational discussion/example on the Web?

--Jed  http://www.webstart.com/jed-signature.html