[cap-talk] NDAs

[Charles Landau]

Toby Murray wrote:
> On Fri, 2009-06-05 at 16:10 -0700, Charles Landau wrote:
>> Toby Murray wrote:
>>> As a side note, I realised recently that NDAs can be built in /any/
>>> object-capability system. One simply uses randomly generated nonces that
>>> are rescinded upon presentation to simulate EROS/KeyKOS style "resume"
>>> keys. The argument then proceeds exactly as in the case of EROS which is
>>> discussed in the last paragraph of Section 1 in
>>> http://www.comlab.ox.ac.uk/people/toby.murray/papers/NDA.pdf .
>> I don't follow this argument. The cited paragraph doesn't say that 
>> "resume" keys cannot be delegated. It says that in EROS a general 
>> authority to reply [to any current or future caller] cannot be 
>> delegated. The reason is that it cannot be built. In KeyKOS/EROS/CapROS, 
>> any authority that can be built can be delegated.
> 
> Indeed. In EROS/KeyKOS/CapROS there is no way to manufacture a
> capability that allows one to reply to all future invocations that
> arrive from a particular object. A resume key (AFAIK) allows one to
> reply to the current invocation and may be delegated. Hence, in order to
> "delegate" the authority to reply to all future invocations, an object
> must (re)delegate each new resume key it receives (from the kernel) in
> response to being invoked by other objects. Hence, the "authority to
> reply in general" is not delegatable (or delegable to use the Queen's
> Enligsh). 
> 
> Resume keys can be emulated using nonces. Suppose we live in a cap
> system that doesn't use resume keys. Instead, when A invokes B, B
> automatically receives a capability, c, that allows it to reply to A. c
> allows B to reply to all invocations that A may make of it, including
> future ones. Hence, were B to delegate c to object D say, then B has
> delegated the the authority to reply. Suppose A is an NDA. When A
> invokes B, it expects that only B can reply to it. However, now D can
> reply in B's place, without requiring B's collusion other than in the
> initial delegation of c from B to D. Hence, B has delegated the supposed
> "non-delegatable authority" that NDA gives him, by passing c to D. Here
> the NDA is broken.
> 
> Suppose we extend the NDA now, however. When it invokes B it creates a
> fresh unguessable nonce n. It passes n with the invocation to B. The NDA
> (which I was calling A before) waits to receive a reply. It rejects any
> reply that doesn't contain the nonce n. Hence, in order for B to
> delegate the authority to reply effectively to NDA, it must delegate n.
> 
> n must be delegated afresh each time the NDA invokes B, since the NDA
> creates a fresh nonce each time. Hence, the nonce n has now taken the
> place of the use-once resume capabilities of KeyKOS and its
> descendants. 
> 
> Hence, I argue that NDAs can be built on any capability system in which
> objects have access to a good source of randomness.

Forgive me, but I'm still not following. In your last sentence, what is 
the NDA that you say can be built, and how do you build it in KeyKOS?

If it is the authority to reply to all future invocations that arrive 
from a particular object, then I don't see how to build it in KeyKOS.