[cap-talk] How data can you get? A challenge

[Jed Donnelley]

How data can you get and still qualify as the purest of pure 
object-capability system?

This is the topic that I've concerned myself with for the last few days.

I believe I've architected (adapted actually) a system that's pure 
data and distributed but is as functionally object-capability as any 
we've discussed (considering implausible guessing to be as likely as 
a hardware failure - i.e. not failure).

Consider a system in which each active object (process, domain) is 
associated with a public/private key pair.  The TCB knows the private 
key (with suitable randomness) and the public key.

Now consider a capability (by protocol assumption of the TCB) to be 
the following:

Public key, address hint, data:  where "data" is assumed to have a 
sufficiently large section of recognizable data (could be an initial 
block of, say, 128 zero bits) so that it's encrypted form can't be guessed.

The only send operation is "invoke".  The invoke operation uses the 
essential procedures in:

http://www.webstart.com/jed/papers/Managing-Domains/#s13

In a diagram:

http://www.webstart.com/jed/papers/Managing-Domains/Figure-6-50.gif

In this diagram:

X <down arrow> indicates the encryption operating with the public key and
X <up arrow>   indicates the signing or decryption operation with the 
private key

In this email message I indicate these as Xd and Xu.

I now describe the "invoke" operation on a capability that's asked to 
transfer a block consisting of an arbitrary number of data and 
capability 'tokens' (recognizable data blocks, defined by a framing 
convention of the TCB, where each block of data is indicated by the 
framing to be either simple data or a capability).

1.  The TCB first checks the data block of the capability by applying 
SdXu where Xu indicates the decryption/signing application of the 
domains private key and Sd indicates the encryption/public key 
operation (using the public key that's the first part of the 
capability).  If the appropriate recognizable block of data (the 128 
zero bits) isn't in the capability then the invocation fails and goes 
no further.

Note that in the case that S==X (namely that this is a local object 
and the active object has it's own public key) then this is an 
identity operation that simply checks for the appropriate data 
block.  An attempt to send to self fails.

If the recognizable data block is in the transformed capability then 
the operation continues.  In that case it transforms the data block 
of the capability with:

SdXuXu

2.  Sending: The TCB does a nonce handshake with the system at the 
address hint (issues much like with YURLs) to try to communicate there.

If that succeeds it continues:

The communicated message consists of the data blocks that were 
requested to be transferred, untouched.  For the capability blocks 
the same operation as in #1 happens for each capability (check and if 
OK transform).  Any failure terminates the communication.  Otherwise 
the communication continues until either it ends or until any normal 
communication terminating event occurs (network failure, capability 
failure, etc.).

3.  Receiving:  Doing a receive operation requires no capability, but 
receiving can only happen from active objects/domains that have a 
proper capability to the receiving active object.  When receiving the 
TCB goes through the dual of the nonce handshake with the public key 
as noted for sending.  If that succeeds then it transfers data into a 
receiving buffer with data transferred literally and capabilities 
transformed as:

XdSdXu

In this case X denotes the key(s) for the receiving (local, hence Xu 
is known) domain and Sd is the public key of the sending domain (note 
that in general Sd is different from the server public key).  As in 
the sending case, on receiving capabilities are also checked for the 
appropriate redundancy by protocol and rejected if the check fails - 
terminating the receive.  In the case where the public key for the 
capability is the same as the public key for the sender, the sending 
address can be checked (a fine point tied into the address hint, 
naming/finding servers, etc.).


Perhaps I'm just being stubborn about this and I'm missing something 
important, but I don't know of any pure object-capability properties 
that this system doesn't have.  In this system the functions of a 
capability TCB and that of a "vat" (e.g. DCCS) are effectively combined.

I'm very interested to hear any "attacks" on this system.  That is 
demonstrations of object-capability functional properties that this 
system doesn't have.  There may be simplifications possible and 
certainly optimizations, but I'd very much like to have the 
"object-capability"ness of its functionality attacked.

Ground rule - Implausible guessing is considered as likely as a 
hardware failure, i.e. not considered in any failure scenario.

I wonder if an interactive discussion at HP on this topic might be 
worthwhile?  I know we had a brief discussion on this basic mechanism 
considered in a different context.  Now the keys are maintained by 
the TCB (actually as I suggested in my Managing Domains paper) and 
I'm claiming all object-capability properties.

If there are simple problems that can be clarified on the list with 
no equally simple fixes (i.e. fundamental), then any such early 
fatality should of course derail any interactive 
discussion.  Otherwise I'd be interested in participating in a 
discussion of this topic.

For me exploring such a mechanism is one way to get at the essential 
aspects of whatever trust is needed in a capability distribution 
mechanism (like the vats).

--Jed  http://www.webstart.com/jed-signature.html