[cap-talk] Is this attack feasible in any real ocap systems?

[Toby Murray]

On Thu, Apr 03, 2008 at 03:29:34PM -0700, Bill Frantz wrote:
> toby.murray at comlab.ox.ac.uk (Toby Murray) on Friday, March 28, 2008 wrote:
> 
> >I've been working recently on modelling ocap patterns in CSP. I've found
> >a potential attack on the Stiegler sealer-unsealer implementation, but
> >it exists only in ocap systems with the following properties:
> >
> >  1. when A sends a message to B, B is given a "use once" capability,
> >ba, to be used for sending back the reply
> >  2. B can call ab during  a later invocation to return back to A.
> >  3. The system is single-threaded (which is required or else thee
> >sealer-unsealer implementation is easily broken)
> >
> 
> It seems on the surface that the KeyKOS et.al. group of systems
> meet the basic requirements 1-2 above, and are single threaded
> within a single object, so they may meet requirement 3 as well.

Thanks so much for the reply Bill. I'm not overly familiar with the
concurrency semantics of KeyKOS. Hopefully you can answer my questions
below.

Firstly, when you say "are single threaded within a single object",
does an object correspond to a domain?

> 
> Let my try to translate the attack to an implementation in these
> systems:

It seems there the following domains: Thread, Alice, Alice-helper,
Unsealer, Bob, Box.

Does each domain run concurrently to all others?

i.e. can Bob be executing at the same time that Alice is, for example?

(If so, then there is a simpler attack that involves Bob invoking the
Box just before the Unsealer is about to check the contents of the
shared location between Box and Unsealer. Anyway...)

> 
> 1. Alice is CALLed by a domain of thread (leaving that domain busy,
> with Alice holding a resume key (c1) to that domain).

It appears as if domains can only perform a CALL directly after they
have been RETURNed to that they can perform a RETURN only directly
after they have been CALLed. Is that the case?

> 
> 2. Alice starts a helper (Alice-helper) by returning to it (so
> Alice becomes ready). The helper CALLs the unsealer domain passing
> Alice as the box.
> 
> 3. The unsealer CALLs Alice, thinking she is a box, and Alice saves
> the resume key (c2) to the unsealer.
> 
> 4. Alice RETURNs to c1, allowing Thread to resume execution.
> 
> 5. Thread CALLs Bob.
> 
> 6. Bob calls box(divulge ==>...) [note that box and unsealer must
> be different domains otherwise Bob would block on the busy domain.
> This requirement may violate requirement 3.] Box puts its contents
> into a location shared with unsealer. and RETURNs to Thread
> 
> 7. Thread CALLS Alice.
> 
> 8. Alice RETURNs to c2, causing the unsealer to resume execution.
> 
> 9. The unsealer finds something in the shared location (channel),
> and RETURNs it to Alice-helper
> 
> 10. Alice_helper gets the contents of box, which it shares with
> Alice.
> 
> If I were to fix this problem using KeyKOS facilities, I would make
> it so the unsealer doesn't need to invoke box. Probably the
> unsealer would hold a key to the instance of domain_creator[1]
> which is used to build all the instances of box.

Each unsealer would need a different domain_creator, no?

> Box would keep its
> contents in a well-defined capability register, and the unsealer
> would use the domain-creator capability to make a domain key[2] to
> box and use that domain key to fetch the contents of the
> well-defined capability register.

In this way, domain_creator appears to offer some sort of primitive 
(i.e. in-built) rights amplification mechanism. Of course, this could
be implemented by having domain_creator use DISCRIM (i.e. EQ) to
compare the given Box capability to ones that it has created and
return the corresponding domain key. But this again requires a
primitive discrimination mechanism (i.e. DISCRIM/EQ).

The trick of this Sealer/Unsealer implementation is to try be able to work
without the use of a primitive rights amplification mechanism, nor a
primitive discrimination mechanism.

Cheers

Toby