[cap-talk] NDAs

[Toby Murray]

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.

Cheers

Toby