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

[Bill Frantz]

Toby.Murray at comlab.ox.ac.uk (Toby Murray) on Friday, April 4, 2008 wrote:

>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?

In KeyKOS jargon, a domain is an object.


>> 
>> 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...)

Each domain can execute concurrently, but in my translation of the
scenario, there is only one thread of control active.


>> 
>> 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?

Not quite. A domain may be in three states: ready, running, or
calling. (In general, you can't tell from outside whether a domain
is running or calling, but separating them makes it easier to think
about.)

There are two kinds of key to a domain: start keys, and resume
keys. Start keys can enter a ready domain, but the user of a start
key stalls if the domain is running or calling. Resume keys are
(almost always) created by the CALL invocation, and allow
resumption of a domain in the calling state.

There are three invocations: CALL, which puts the issuing domain
into the calling state, RETURN, which makes the issuing domain
ready, an FORK which leaves the issuing domain running, while
starting another thread of execution in the target domain. (N.B. My
example did not use FORK.)

Note that any of the three invocations may be used on either type
of key, and all six combinations make sense.


>> 
>> 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?

Yes. (Domain creators are cheap. (Three nodes, and a shared code
page in the 370 version.))


>> 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).

Exactly. KeyKOS is strongly on the side of providing EQ. Since the
domain creator could keep copies of every domain key it created,
and use them to recognize keys to those domains, we invoked the
implementation philosophy of: If a domain could do it anyway, and
the result is useful, make it efficient. See
DOMAIN_CREATOR__IDENTIFY_ENTRY
<http://www.agorics.com/Library/KeyKos/Gnosis/67.html#iden>.


>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.

I'll let the anti-EQ people try to come up with a fix for the
KeyKOS box that doesn't use EQ. :-)

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | gets() remains as a monument | Periwinkle
(408)356-8506      | to C's continuing support of | 16345 Englewood Ave
www.pwpconsult.com | buffer overruns.             | Los Gatos, CA 95032