[E-Lang] Hash Chaining & Capabilities, Proposal #2a: Active Off-Line
Mark S. Miller
Tue, 17 Oct 2000 14:55:48 -0700
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.
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
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
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
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.
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
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