[cap-talk] Comments on a paper

Karp, Alan H alan.karp at hp.com
Tue Jul 5 20:27:42 EDT 2005


Kevin Reid wrote:
> 
> By Alice building the forwarders, which Bob would otherwise host and 
> give to David and Edward, into her service.
> 
>    interface SpaceProvider {
>      to claim() :Space
>      to subdivide(portion :Number, label :String) \
>        :Tuple[SpaceProvider, Log, Revoker]
>    }
> 
> The 'subdivision' SpaceProvider, hosted by Alice, remembers its 
> 'parent', and so Alice can note the complete 'delegation' 
> path for each 
> request.
> 
This works, but it requires that Alice be online when anyone does a
delegation.  That's a significant difference from a system based on
certificates.

David Hopwood wrote:
> 
> Indeed, for example:
>   - Alice provides a random challenge, which Bob forwards to Dave
>   - David seals/brands it together with his resource request, 
> and sends it
>     back to Bob who forwards it to Alice.
> 
Why does Bob have to forward the request from David?  Is there some way
for David to submit the request directly to Alice?  Does David have to
seal it or is proving knowledge of the challenge sufficent?  

David's suggestion triggered the following idea.  According to Tyler, it
works but may be a reinvention of something MarkM did a few years back.
It's an off-line protocol based on MACs.  The notation is pretty
standard.

Let (A,B,C) be the concatenation of strings A, B, and C.
Let M(A,s) be the MAC of string A with some secret s.
Using the LaTeX notation that MarkM now knows so well, P_{xy} is P sub
xy.

Here are the steps for the example I described earlier.

1. Alice has 100 units to allocate.  She gives Bob a delegatable
authority to 50 units by giving him the result of 

	P_{AB} = (A,B,50,M(A,B,50,s)), 

where s is Alice's reference to the resource or some other secret.  The
allocation to Carol is 

	P_{AC} = (A,C,50,M(A,C,50,s)).  

2. Bob delegates 25 units to each of David and Edward, Edward's
capability being

	P_{BE} = (B,E,25,A,B,50,M(B,E,25,A,B,50,P_{AB}))

3. Edward delegates 25 units to each of Fred and George, George's
capability being

	P_(E,G} = (E,G,25,B,E,25,A,B,50,M(E,G,25,B,E,25,A,B,50,P_{BE}))

4. George can claim the resource by submitting P_{E,G} to Alice, who has
all the information to recompute the value from s and the information
passed in by George.

Other points.

1. P_{AB} is a capability to 50 units of the resource because it
combines designation with authorization and is freely transferrable.
It's really not much different from a certificate, but it doesn't
require a key pair at each step.  (The corresponding certificate is also
a password capability; there's no reason to check whether the submitter
of a certificate knows the private key it was issued to, but it seems
that everyone does.)

2. We have all the information needed to determine who is responsible
for the over allocation that led to a claim being rejected.  In the
example, Alice can tell Bob that his Edward is responsible.

3. Bob can revoke P_{BE} by sending it to Alice and telling her to
ignore it.

4. Although the P_{xy} need to be kept secret, they're all rooted in the
one secret assigned by Alice.  That seems to be substantively different
from an approach that requires each party to have a key pair.  

5. Time outs can be included by putting them into the strings being
MACed.

Thoughts?

________________________
Alan Karp
Principal Scientist
Virus Safe Computing Initiative
Hewlett-Packard Laboratories
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-7029
https://ecardfile.com/id/Alan_Karp
http://www.hpl.hp.com/personal/Alan_Karp
  

> -----Original Message-----
> From: cap-talk-bounces at mail.eros-os.org 
> [mailto:cap-talk-bounces at mail.eros-os.org] On Behalf Of Kevin Reid
> Sent: Friday, July 01, 2005 5:41 PM
> To: General discussions concerning capability systems.
> Subject: Re: [cap-talk] Comments on a paper
> 
> On Jul 1, 2005, at 19:22, Karp, Alan H wrote:
> > David Hopwood wrote:
> > A whole bunch of stuff that I agree with and
> >>
> >>   - a complete record of delegations is not needed. 
> Capability systems
> >>     can support the kind of auditing that is actually useful.
> >>
> > That's what I'm trying to figure out how to do.  First of all, what 
> > kind of auditing are you talking about?  Second, how do you do it?  
> > Let me give an example of what I don't understand.
> > ...
> > In order to illustrate what I don't know how to do, we need to add 
> > another level of delegation.  Say that Alice has 100 GB of 
> disk space. 
> > She grants Bob the right to claim 50 GB for one week and Carol the 
> > same.  Bob grants David the right to claim 25 GB for that week and 
> > Edward the same.  So far, so good.  Now, Edward grants Fred 
> and George 
> > each the right to claim 25 GB.  Carol submits her claim and gets a 
> > lease on the space; David and Fred do the same.  When 
> George submits 
> > his claim, Alice must reject it, but she wants to know if 
> Bob or Carol 
> > is responsible for the oversubscription, and Bob wants to 
> know if it's 
> > Fred or George. SwissNumber tracking can answer Alice's 
> question, but 
> > how does Bob know whether to blame David or Edward?
> >
> > The system described in the paper uses digital 
> certificates.... I can 
> > figure out how to do the same by forwarding Fred's and George's 
> > requests through Bob, but how does it work if Bob can be 
> off line when 
> > those requests are made?
> 
> I haven't been paying much attention to this thread, but this 
> seems to 
> be a straightforward capability problem, so I'll attempt to answer it:
> 
> By Alice building the forwarders, which Bob would otherwise host and 
> give to David and Edward, into her service.
> 
>    interface SpaceProvider {
>      to claim() :Space
>      to subdivide(portion :Number, label :String) \
>        :Tuple[SpaceProvider, Log, Revoker]
>    }
> 
> The 'subdivision' SpaceProvider, hosted by Alice, remembers its 
> 'parent', and so Alice can note the complete 'delegation' 
> path for each 
> request.
> 
> (Without further protocol, Alice has only Bob's word for who the 
> subdivision is being given to. This can be changed.)
> 
> The Log object would provide Bob with the ability to review past 
> requests without requiring Bob to be accessible by Alice at 
> the time of 
> the request.
> 
> Have I missed anything?
> 
> -- 
> Kevin Reid                            
> <http://homepage.mac.com/kpreid/>
> 
> _______________________________________________
> cap-talk mailing list
> cap-talk at mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/cap-talk
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Karp, Alan H.vcf
Type: text/x-vcard
Size: 433 bytes
Desc: Karp, Alan H.vcf
Url : http://www.eros-os.org/pipermail/cap-talk/attachments/20050705/33077b3f/KarpAlanH.vcf


More information about the cap-talk mailing list