[E-Lang] Hash Chaining & Capabilities, Proposal #1

[Mark S. Miller]

Capabilities are a security abstraction whose definition is independent of 
cryptography.  To implement distributed capabilities on mutually suspicious 
machines communicating on open networks, one must map cryptographic concepts 
onto capability concepts.  (Just as the right type of hardware engineer must 
map digital logic gate concepts on analog circuit concepts.)  However, many 
such mappings are possible.  This note proposes two additional mappings 
based on 1-level deep hash chaining that may be used to augment the E 
system, and in so doing, make some crucial parts of E simpler and/or more 
flexible.

With hash chain proposal #1, it seems we could have persistence before we have
orthogonal persistence, and we can simplify the part of Pluribus protocol 
that seems too messy.  With hash chain proposal #2, it seems we could have 
off-line "active" messages in the spirit of Nikita Borisov's "Active 
Certificates" http://www.cs.berkeley.edu/~nikitab/papers/acert-retreat.ppt . 
These can be seen a generalization of SPKI, using safe code to subset 
authority, rather than a special purpose data language.  This note explains 
proposal #1.  A later note will explain proposal #2.

However, I'm not sure 1) whether these additional mappings are secure by 
themselves, or, even if they are, 2) whether they are secure in combination 
with the existing mapping and with each other.  Please help spot flaws in 
these proposals before I implement them.  Thanks.


                          Two Ends of the Arrow


In cryptography, only knowledge of secrets conveys authority.  A capability 
is an arrow, and an arrow has two ends.  Each end is a kind of authority.  
The tail of the arrow is the authority to invoke the object the arrow points 
to.  The head of the arrow is the right to be the object the arrow points to 
-- the right to be invoked by those invoking the tail of the arrow.

Perhaps the most straightforward mapping of capability concepts to crypto 
concepts is Norm's http://www.cap-lore.com/CapTheory/Dist/PubKey.html .  A 
capability corresponds to a public-key-system encryption key pair.  The tail 
would be represented by the encrypting key and the head by the the 
decryption key.  (Conventionally, one would call the encrypting & decrypting 
keys the "public" and "private" keys, respectively, but we avoid that 
terminology since this mapping relies on neither key being public.)  
Invocation would encrypt the message using the encrypting key, followed by 
delivery to the location of a party allegedly holding the decrypting key.  
To be invoked, one would need to decrypt the message, and therefore one 
would need to know the decryption key.  The asymmetry of public key 
encryption perfectly matches the asymmetry of the two ends of a capability 
arrow.

In this protocol, when Alice performs the Granovetter operator, the 
representation she sends to Bob of the tail of arrow that points at Carol is 
the same cryptographic information that she herself uses to point at Carol.  
We define a representation with this property to be a "bearer protocol" for 
capabilities.

If we were using a hypothetical public-key-system in which the encryption 
key could be calculated from the decryption key, but not vice versa, we'd 
still consider this proposal a valid implementation of capabilities, since 
we allow an object to implicitly have the ability to designate itself 
without requiring any explicit authorization.


                          Non-Bearer Protocols


By contrast, the Unibus proposal 
http://www.erights.org/elib/object-pluribus/unibus.html maps a capability 
onto a secret shared at both ends of the capability, but with a new secret 
generated per introduction.  Because the secret is per-introduction, not per 
arrow tail, it is not a bearer protocol.  Likewise, SPKI and both E-Speaks 
are capability-like systems that are not bearer protocols.  In SPKI (and 
theSPKI-based E-Speak), a capability is like a check that has to be 
counter-signed as it passes from hand to hand, accumulating a chain of 
signatures.  Unibus and E-Speak 2.2 are online non-bearer protocol, while 
SPKI (and therefore E-Speak 3.0) are off-line non-bearer protocols.


                                   Pluribus


Unfortunately, the above public-key-based mapping requires a key pair per 
capability, and so has a terrible efficiency cost.  E's Pluribus protocol 
maps a capability onto a <vatID, swissNumber> pair, as explained at 
http://www.erights.org/elib/capability/ode/ode-protocol.html .  Pluribus is 
also a bearer protocol.  If knowledge of <vatID, swissNumber> provides the 
authority to hold the tail of the arrow, what of the head of the arrow?  For 
all swissNumbers, sn, knowledge of vat-private-key(C) provides the authority 
to be the object designated by <vatID(C), sn> (and therefore, equivalently, 
the authority to determine what object is designated by <vatID(C), sn>).  
This is the case even without prior knowledge of sn, since Bob's vat will 
present Carol's sn to anyone that demonstrates knowledge of vat-private-key(C).

We have all examined Pluribus long enough to have some confidence that it 
works. However, some of the assumptions that enable it to work aren't 
obvious.  In particular, the assumption that only VatC (ie, VatC's TCB) 
generates the swissNumbers that it will honor, and that only VatC binds 
these swissNumbers to objects.

This assumption turned into a painful limitation when MarcS nagged me about 
shortcuts to persistence.  He pointed out that none of the competing 
platforms provide orthogonal persistence (except Droplets -- congrats 
Tyler!), so my users are unlikely to demand it.  Instead, they'd expect to 
save and restore state the old fashion way -- manually, with hand written 
code to save and restore app state of interest.  Perhaps the details could 
be largely automated using serialization, but the superstructure would be 
specific to the semantics of each app.  MarcS pointed out that the 
persistent state needed for EDesk and EChat is trivial, and such manual 
reading and writing would be a small part of the effort.

I replied, because of our reliance on the above assumption, that manual 
restoration creates a fatal security problem:  If a Vat hosts several 
mutually suspicious subsystems, each of whom save and restore themselves 
separately, how does a given subsystem, on restoration in a new empty 
incarnation of VatC, establish that some re-created object is the one that 
<vatID(C), sn> should designate?  Knowledge of sn is clearly insufficient, 
since clients of the object could know sn.


                            Crypto Hashes Have a Similar Asymmetry


When we say "hash(x)", we always mean cryptographic hash.  In E, this means 
an SHA1 hash resulting in a 160 bit number, though this proposal requires 
only the abstract properties of a cryptohash.  If "hash(x) == y", then, 
abusing terminology from trigonometry, we may also say that "x == arcHash(y)".

For all vatIDs V, we propose that knowledge of x convey authority to be the 
object designated by <V, hash(x)>, but only at the price of revealing x to 
Vat V (ie, to the TCB of Vat V).  Now, a subsystem in VatC could generate 
the unguessable numbers x for the objects in the subsystem that others 
sturdily designate, and use knowledge of x to ask VatC to establish the 
mapping from <vatID(C), hash(x)> to the manually restored object.  Clients 
of the object would only know hash(x), and so would not have the power to be 
the object. The subsystem would have the power to synthesize an arrow tail to 
one of its own objects, since it could calculate hash(x) from x, but this is 
ok by the earlier assumption that an object may be its own client without 
needing explicit authorization.



                       Why Granovetter + Pipelining Was Awkward
                                      and how to fix it


More later.


        Cheers,
        --MarkM