[cap-talk] Encrypted delegation via membrane [was: In Defense of Identities - not]

[Jed Donnelley]

At 02:23 PM 12/6/2006, coderman wrote:
>On 12/6/06, Jed at Webstart <donnelley1 at webstart.com> wrote:
> >...
> > >The main issue I see is the inability of Alice to delegate to Bob a
> > >responsibility-tracked capability right to use Carol without involving
> > >Carol.  I think that's unavoidable.
> >
> > This seems mostly an implementation issue.  The problem seems a bit
> > like the one I solved with the public key mechanism for safely
> > communicating capabilities as data in Managing Domains:
> >
> > http://www.webstart.com/jed/papers/Managing-Domains/#s13
> >
> > I'll be interested to see if there is a comparable implementation
> > approach that uses cryptography and needn't involve the server
> > when a permission is delegated, even with responsibility tracking.
>
>the public key capability communication mechanism would indeed do the
>trick, and does not require the server (or Carol) to be in the loop,
>although you can elect for such a constraint if desired.

This claim sounds hopeful to me.  However, I have to admit that
I don't understand how the rest of this message justifies the claim.

>for example:
>- Admin delegates a permissive capability (perhaps read, write, create
>and delete capability on a public web sub directory) to Carol.
>
>- Carol obtains the complex permissive capability which contains
>component capabilities (represented via public keys per Jed's
>description) such as: issueRWCD(), issueRWC(), issueRW(), issueR(),
>audit(), and revoke() for distinct delegate-able capabilities tied to
>the parent web storage capability Carol is responsible for.

There seems to be more complexity in the above than I believe is
necessary or useful for the problem description or solution.

I believe all we need consider is a simple Granovetter diagram, e.g.
as from the Managing Domains paper (just to suggest cryptography):

http://www.webstart.com/jed/papers/Managing-Domains/Figure-6-50.gif

We could of course make the server be Carol, the delegator be Alice, and
the delegatee be Bob as per our oft used convention (sorry I didn't know
Alice, Bob, and Carol back then..., but at least I got the A and B right ;-).

Still, I like the distinguished nature of S as the server and the shortness
of A and B for this application, so let me stick with them.

The requirements of this protocol might seem pretty high.  We've got to
communicate something (perhaps with a handshake) between A
and B (not involving S) that will enable B to exercise a permission that
A has, possibly reduced, and with the understanding that this is
a permission that is labeled as having been delegated from A to B.
Also our mechanism must insure that A can't access this same
permission but that A can revoke it.  Whew!

Seems somewhat daunting.  However, having thought about it
just a bit I think there is a simple solution.  Perhaps others can
check me on it.  I think it's really just a simple matter of getting
the right parties to (cryptographically) make the right statements.

We start with AdSuc in the memory of A.  (Note, I don't have
a convenient down arrow character, so I use "d" as down arrow,
and "u" as up arrow.  That is, Xd indicates an encryption with
X's public key and Xu indicates a 'decryption' with X's private
key - i.e. a signing).

A needs to say, "I'm delegating this permission from A to B.
Let's write that A->B with the understanding that it's just a
string.  The identities could be public key hashes or the
full public keys if you prefer to leave out any lookup mechanism.
Personally I think a lookup is fine for brevity, though of course
such lookups should be cached for performance and I do
realize the reliability/performance consequences of relying
on such a remote lookup - I'll not get into that here.

For 'us' (specifically S and A) to ultimately trust this statement we
need to have A sign it.  So we have:

Au(A->B.Suc).  (I had A remove the internal Ad to start
the communication as that's only needed for internal
protection from data theft).

A can now apply Bd to this whole thing to put it on the wire.

BdAu(A->B.Suc)

Now what about when B receives it (as of course only B can)?

At that point B may transform it by signing it into:

BuAu(A->B.Suc) .  This data if received by S would indicate
that the data A->B.Suc was signed by A and then the resulting
data was signed by B.  I believe this data should suffice for
the server S to be able to safely determine that this is indeed
a permission that was delegated from A to B.  No need for
any handshaking!  Hurray!

Interestingly (for me anyway) B can protect this block in memory
by applying Bd - transforming it into:

Au(A->B.Suc)

I.e. removing the outermost Bu.  This might seem to be giving something
away to data theft.  However, notice that with the meaning of this data
block these bits are worthless without B's signature.

When B transforms it for communication to S (for access) it goes
out on the wire as:

SdBuAu(A->B.Suc).

S pulls off the Sd and inside finds BuAu(A-B.Suc)
(along presumably with some control text that describes
what it claims to be).  S can then properly log this access.

Also I think it's easy to see that A could have reduced the
permission before starting.  That reduction need only be
communicated to S along with A->B.  S can then properly
reduce the permission before deciding how to respond to
B's request.  I'll also note here (described more fully
below) that it's helpful for revocation if A adds a
swiss number to this data block, "SN", that will
distinguish this particular delegation for possible
future revocation (along with all it's descendents).


Since I've gone this far, perhaps I should also address
Jonathan's concern about how the membrane works
through this protocol:

Any request coming in via a delegated permission
may end up returning some other permission to the
requestor.  We assume that the server can distinguish
such a permission in the outgoing data (this may be
Jonathan's concern - we will see).  If not then by the protocol
it will end up being useless noise (as we know every process
must transform permissions [capabilities] from their
internal form or transmission).

When a server must send a permission in reply to a
request on a delegated capability it just needs to
indicate that this permission was so returned through
an access to the delegated capability.  It can do simply
by adding the string A->B to the capability and signing
it, e.g., suppose the capability is S'uc' which I'll simply
indicate as X.  Then S would simply return:

Su(A->B.X).


Regarding revocation:  Revocation is a bit difficult (awkward)
with this model.  I can see that I should have the delegator
add a swiss number to the delegation string.  This swiss number,
SN, would pass through all the derived capabilities.  The delegator
can create a revocation capability just by saying what it is, e.g.:

<I won't bother to add "SN" in all the text above>

"revoke"(SN.A->B.Suc)

and then signing it:

Au("revoke"(SN.A->B.Suc))

On the server side is where the awkwardness of this scheme for
revocation shows up.  It works sort of like certificate revocation
lists and unlike most capability mechanisms for 'destroying'
an object where you simply remove a swiss number that was
originally created by the server.  If the delegated permission is
evoked then the server must store something like:

"revoke"(SN.A->B.Suc)

with the object designated by c.  This is a bit awkward, but I
don't see any alternative with this approach.  Note that of
course the server needs to find Au around any such
revocation capability (matched with the "A" public
key or hash inside) to insure it's authenticity.  Naturally
such a permission can itself be delegated using the
normal capability rules.


I'll be interested to hear if others follow the discussion
above and perhaps if people see any holes or other
problems with it.

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