[E-Lang] Hash Chaining & Capabilities, Proposal #2a: Active Off-Line Messages

[Mark S. Miller]

While Alan Kay was heaping criticism on the early Macintosh, 
he also quipped that the Mac was "the first computer good enough to 
criticize".  Such reminders are important, when one singles out the 
best of a field for intense criticism, while ignoring its crappy cousins.

Similarly, SPKI is the only PKI/Certificate system I know of that's good 
enough to criticize.  As explained in the Ode:

>The enforceable subset of SPKI can be seen as an off-line, auditable, 
>heavyweight, non-confinable, semi-capability system, as opposed to E's 
>on-line, repudiatable-by-default, lightweight, confinable, full-capability 
>system. Perhaps, by comparing these, we may figure out how to build systems 
>with some of the best of both.

SPKI-like certificate technology and real capabilities clearly should be 
able to get along, but until now it wasn't clear how.  The following 
proposal is inspired by Nikita Borisov's "Active Certificates" 
http://www.cs.berkeley.edu/~nikitab/papers/acert-retreat.ppt , although 
Nikita wasn't explicitly thinking in capability terms either, he 
nevertheless provided the bridge.

Development note: I plan to complete hash chaining proposal #1, and its 
application to simplify persistence and Pluribus, for the next release of E. 
Indeed, the reconstruction of Pluribus is the gating item for this next 
release.  The proposal in this note (#2) is more long term.  Neither E nor 
E's current users currently require it, though it would add significant 
value.  So don't expect it anytime soon.  However, because it makes a second 
use of hash chaining to represent cryptographic capabilities, 
it would be good to know early whether it can co-exist with our 
other cryptographic representations of capabilities.  I want to leave the 
door open to implement this proposal later as an upward compatible extension 
of E.  If you see any possible problems on this horizon, please fire away.

Before we get to the "active" stuff, let's strip from SPKI everything that 
isn't capability logic.  It's ok if the result isn't usable at this stage, 
as long as we get back to a usable result once we put the "active" stuff in.


                                        Deconstructing SPKI


After signature checking and expansion, we see from Section 6 of 
http://www.ietf.org/rfc/rfc2693.txt that there are only two kinds of SPKI 
certificates: Authorization Certificates (or 5-tuples) and Name Certificates 
(4-tuples).  Although the SPKI perspective on names is more capability-like 
than the other PKIs, it is still not the true capability perspective on 
names, so we get rid of the Name Certificate.

We state in the Ode that a SPKI Authorization Certificate corresponds to a 
capability message, but this isn't quite right.  A capability message not 
only authorizes Bob to access Carol, but it packages this authorization 
with information that should communicate to Bob why he's being given the 
argument authorizations (the label "foo"), and in which each individual 
authorization occupies a distinct argument position, corresponding to its 
role in the "why".

So a SPKI Authorization certificate corresponds to an argument in a 
capability message.  An argument in a capability message is normally 
understood to simply be a capability, so what distinction am I drawing?  At 
the capability layer of abstraction, there are no certificates, and the 
arguments of capability messages are simply capabilities.  While at the 
crypto-implementation layer of abstraction, SPKI is a non-bearer protocol.  

An individual SPKI Authorization Certificate implements a capability as 
passed specifically from Alice to Bob.  If Bob then further authorizes Dana, 
this next authorization is the same capability but a different certificate.  
If E's current SturdyRefs are off-line bearer capabilities, we might say 
that authorization certificates are SturdyArguments -- off-line per-message 
capabilities.

So now let's examine the parts of a SPKI Authorization Certificate with 
regard to representing an argument in a capability message.

1) Issuer:  Fingerprint of the public key corresponding to the private 
signing key of the party sending the message.  The tuple as a whole is also 
signed with the Issuer's signing key.  Great.  We'd keep this.  For us, the 
Issuer would be the Vat, and this fingerprint is the VatID.  In the standard 
example, this is VatID(A).  It's not yet clear whether this field needs to 
be expanded to uniquely designate Alice within VatA.

2) Subject: Fingerprint of the public signature key of the party the message 
is being sent to.  In the standard example, this is VatID(B).  It's not yet 
clear whether this field needs to be expanded to uniquely designate Bob 
within VatB.

3) The infamous do-not-delegate bit.  We need to eradicate this and then 
find a strong cleanser to remove its stench.  (For those new to this list, 
see http://www.erights.org/elib/capability/conspire.html .)

5) Validity dates -- the interval during which the certificate is considered 
valid.  It's not clear whether or not this needs to be primitive.  Also, 
it's most peculiar to include an interval start time rather than just a 
deadline.  Since the deadline corresponds to the expiration time of our 
existing SturdyRefs, I'm inclined to keep the deadline for now.

4) Authorization.  An S-expression which states what rights are being 
authorized.  Intermediaries on the delegation chain can use this 
S-expression language to express subsettings of the rights being passed on.
Complex rules compose these expressed subsettings to calculate the 
intersection of allowed rights.  This item is where the action is.  

First, we remove everything extraneous from this item.  This S-expression 
language is assumed to bottom out in human readable names, and in wildcards 
over such a names.  From a capability point of view, this name space is 
misguided, and the wildcards are therefore pointless.  The rights at the 
bottom of a subsetting expression should simply be the right to invoke a 
particular object.  With this as the right to be subsetted, the SPKI 
S-expression language is clearly useless as a means to subset it.  This will 
be where Nikita's "Active" ideas become crucial, but for now let's just drop 
all the subsetting logic.  What's left?  A unique unambiguous designator of 
Carol.  

<misplaced-motivational-aside>

Till now, when we wanted a cryptographic representation for designating 
Carol, we always used the pair <VatID(C), swissNumber(Carol)>.  However, if 
we use this representation here, we lose one of the really cool properties 
of Certificates: they can communicate authority without communicating 
secrets.  Indeed, the only information they require one to keep secret is 
one's own private signing key.  Because they rely on signature chains rather 
than secrets, distributed computation stitched together with certificates 
has very strong non-repudiation and auditing properties.  OTOH, it's vastly 
more expensive than on-line secret-based protocols like Pluribus.  Which one 
to use depends on context, so it would be good to be able to switch from 
one to the other while keeping the abstract capability semantics constant.

</misplaced-motivational-aside>

So, instead, we need the designator of Carol in the certificate to uniquely 
and unambiguously designate Carol without itself granting the authority to 
invoke Carol.  The authority to invoke Carol comes from the signature chain 
that reflects the sequence of introductions, starting with VatC, by which 
VatB came to attempt to invoke Carol.  Yes, believe it or not, I am 
advocating a kind of separation of designation and authority, but I don't 
believe that this separation has any semantics or presents any dangers.


                                 Hash Chaining Again


So let's say that the Certificate's Authorization field contains, not 
<VatID(C), swissNumber(Carol)>, but <VatID(C), hash(swissNumber(Carol))>.  
Since we assume hashes are strongly irreversible, knowledge of 
hash(swissNumber(Carol)) provides no knowledge of swissNumber(Carol), and 
only the latter is a secret that provides authority.  This representation 
also makes it easier to see how to interface between the bearer and the 
certificate worlds:

Given a live (a bearer on-line) reference to Carol (and given another 
capability on VatC (the function sturdyRef() that grant the authority to 
burden VatC with a storage obligation), Alice may currently ask VatC for a 
corresponding SturdyRef to Carol that's good until the requested expiration 
date.  A SturdyRef is a bearer off-line reference, so Alice can pass to Bob 
in an on-line message either a live reference or a SturdyRef designating 
Carol.  When Bob wants to invoke Carol, in he hold a SturdyRef, he first 
obtains a live reference from his SturdyReference, and then invokes on it.

Similarly, given a live reference to Carol, we can enable Alice to ask VatC 
for a corresponding Authorization certificate, signed by VatC, authorizing 
VatA to invoke Carol.  Alice, being within VatA, may later use this 
certificate to obtain a live reference to Carol, which she can then invoke on 
directly.  If Alice passes to Bob a derived certificate, signed by VatA 
authorizing VatB to access Carol, and including the previous certificate, 
then Bob may likewise use this certificate chain to obtain from VatC a live 
reference to Carol, which he can then invoke.

The combination of the two hash chaining proposals together look surprising 
natural.  The three numbers correspond to a three level hierarchy of 
authority to a capability:

1) arcHash(swissNumber) provides the authority to be the object, and 
  therefore receive invocations.
2) swissNumber corresponds provides the authority to invoke the object.
3) hash(swissNumber) uniquely and unambiguously designates an invokable 
  object, but does not provide the authority to invoke it.  Curiously, it does 
  provide the ability to compare two of these for equality.

It seems fine that each authority implies the ones after it, but not the 
ones before it.


                       Why we need off-line Messages, 
                             not just off-line Arguments


More later...