[E-Lang] Hash Chaining & Capabilities, Proposal #2b: Off-Line Invocation Certificates

[Mark S. Miller]

                                    Message vs Invocation:
                                  A Terminology Correction.  


In the previous note, when I referred to "Message" I usually should have 
said "Invocation".  An invocation is a pair of a Message and a reference to 
the object that will receive the Message -- the Recipient.  In the 
Granovetter diagram, the fat arrow is a Message containing a reference to 
Carol as an argument.  The fat Message arrow combined with the thin reference 
arrow on which it rides -- the reference to Bob -- together constitute an 
Invocation.  With these definitions, it is clear that an authorization 
certificate represents an Invocation Argument rather than a Message 
Argument, since it authorizes only the Recipient.

The canonical example is a certificate from Alice authorizing Bob to invoke 
Carol.  If it were a Message Argument, then it would authorize whoever the 
Message were sent to, without that having been determined yet.



           Why we need off-line Invocations, not just off-line Arguments:
                     Another Lesson from the Confused Deputy



The punch line we all know from the Confused Deputy paper is "Don't separate 
designation from authority."  But this paper has enough punch lines to last 
a conventional lifetime.  Here's another.

Let's define authorization as the granting of authority.  One may conclude 
from the same tale that, even if designation and authority are kept 
together, "one must not separate authorization from invocation".  Why?  In a 
normal message-based capability system, the deputy only receives new 
authority as arguments of messages he receives asking him to do something.  
Each new authority has a separate position in the request, which represents 
its intended role in this request.  Only this context information gives the 
Deputy enough information to know what to do and what NOT to do with the new 
authority he's just been granted.

When authorization is communicated without such context, it's like receiving 
a key in the mail with no hint about what to do with it.  Or it's like an 
object system in which objects respond to the message

    hereIsSomethingYouMayFindUseful(arg)

After an object receives this message, she can invoke arg if she chooses, 
but why would she ever choose to do so?  Were the separation of 
authorization from invocation truly this silly, no one would have thought to 
separate them.  Instead, no one seems to question separating them.  Why?  I 
can think of two reasons, both derived from the ACL paradigm:

1) Ambient Authority.  The following chain of reasoning seems very 
plausible, especially if it's not articulated or examined closely:  If 
object A attempts to perform action X, and object A has enough authority to 
perform action X, then object A's attempt to perform action X should be be 
permitted.  The implicit assumption is that, if A attempts X, then A must 
want to perform X.  If it wants to and it's allow to, clearly it should be 
permitted to.  In such a system, a hereIsSomethingYouMayFindUseful() message 
could simply add arg to the object's ambient authority.

The flaw is the assumption that it wants its attempt to succeed.  A deputy 
only brings to bear on an action those authorities that should be applied to 
the action, because it wishes the action to fail if these authorities are 
inadequate -- even if the deputy itself has further authority.  How does a 
deputy determine which authorities to apply to an action?  In a capability 
system, only according to how the deputy came to hold these authorities -- 
by initial endowment and by receiving them as invocation arguments.

2) Labelling.  In SPKI, an authorization certificate not only authorizes, it 
names the resources that it authorizes access to.  It's like receiving a key 
in the mail that's labelled with the name of the thing it opens.  This 
presumes a namespace that's meaningful among the various parties, 
necessitating that we solve a harder problem before we can solve the easier 
problem.  Our invocation perspective is much like the labelling perspective: 
the message carries a message name (in E, the verb) used by the receiver to 
understand why he's receiving the arguments.  However, the verb labels the 
reason for interacting, not the resource being authorized.  The latter needs 
no name -- the capability is all the designation we need, and all the 
designation we can trust.

Of course, once Alice is invoking Bob rather than just authorizing Bob, now 
Bob, like Carol, is something to be invoked.  Just as Alice or Bob must be 
authorized in order to invoke Carol, so must Alice be authorized to invoke 
Bob.  If invoking is the only means of authorizing, then Alice must be 
authorized to invoke Bob in order for Alice to be able to authorize Bob.  In 
situations where this is enforceable, this both provides the reference arrow 
missing from http://www.erights.org/elib/capability/ode/images/spki.gif and 
removes the asymmetry between Subject and Resource.  Both would simply be 
objects, and shown as circles.  The full Granovetter diagram would be restored.


                          The Parts of an Invocation in E



So let's examine and give names to all the parts of an inter-vat Invocation 
in E.  Inter-vat Invocations in E may only be asynchronous, so we examine 
only the eventual ("<-") send expression:

       recipient <- verb(args...)

which acts like two different expressions depending on context:

a)    define result := recipient <- verb(args...)
b)    recipient <- verb(args...); null

Both of these asks the recipient to eventually perform the verb-named action 
using the provided arguments.  The request is queued on the vat of the 
recipient to be performed to completion when that vat is done with all prior 
requests.  

#a is the general case: When the send expression occurs in a static context 
where its value is needed (evaluated for value), the send expression 
immediately returns a promise for the outcome of performing the request.  
This is a tail of a reference arrow whose head is encapsulated in the 
Message.  (This head serves a role much like a lambda continuation, expect 
that it normally provides only data-flow, not control-flow.)  We call this 
arrowhead the Resolver.

#b is an important optimization: When the send expression occurs in a static 
context where the value is not needed (evaluated for effect only), then we 
can avoid creating the promise for the return result.  In both cases, these 
messages are one-way in a control flow sense.  #b is also one-way in a 
data-flow sense.

So, putting it all together, an E on-line Invocation consists of

Invocation
    Recipient (arrowtail)
    Message
        Verb (usually a String.  Always passed by copy.)
        Args (List of arrowtails conceptually, but may use any passing mode)
        Resolver (optional.  arrowhead for reporting outcome)

For off-line invocation certificates, let's tentatively make four semantic
changes.

1) Let's drop the optional Resolver.  It's hard to see any motivation for 
message pipelining in the off-line case.  In the absence of pipelining, most 
of the effects of the encapsulated Resolver can instead be provided with an 
explicit Resolver argument.  This decision does make it awkward to interface 
between the on-line and off-line worlds, so we may revisit it later.

2) Drop the requirement of order-preserving fail-stop at-most-once message 
delivery.  An on-line protocol can provide such guarantees cheaply.  For an 
off-line protocol, the expense would be too great to put at the foundations. 
Instead, we leave it up to the objects interacting via off-line invocations 
to deal with the problems resulting from the absence of these guarantees.  
I'm quite queasy with this, but it corresponds to the burden placed on the 
programmer by any of the other certificate systems.  Of course, this make it 
yet more awkward to interface the off-line and on-line worlds.

3) Do not provide built-in secrecy.  As with the other PKIs, invocation 
certificates are signed but not encrypted.  If their users wish to 
separately encrypt them, fine.

4) Provide built-in non-repudiation and some measure of auditability, at the 
price of a further loss of privacy.  Indeed, I believe this to be *the* 
tradeoff that should determine whether to use a certificate system or a 
bearer system.  Clearly, both have their place.


                Proposed Contents of an E Invocation Certificate


Since we've already got a notation for describing E invocations -- E -- I'll 
use it in the certificate proposal below.  A more politically acceptable 
proposal may use the XML representation of Kernel-E parse trees 
http://www.erights.org/elang/kernel/index.html , since this would be less 
readable and more verbose.  If you wish, consider all the E notation in what 
follows to be syntactic sugar for such XML.

As with any lambda language, E expressions are evaluated within a lexical 
scope.  *.emaker files are evaluated in the E "universal scope" -- a 
immutable scope containing only transitively immutable objects that provide 
no authority -- such as the binding of "true" to the appropriate boolean.  
The expression in our invocation certificate can be evaluated (for effect 
only) within this scope, but we needs more.  The authorization certificates 
provide further capabilities, but only in this context.  We need a form of 
expression available within this context that wraps the authorization 
certificate data and effectively evaluates to the corresponding object 
reference.  

Let's use E's syntactic sugar for URI expressions, and introduce a binding 
for "auth__uriGetter".  The expression <auth:...>, with an authorization 
certificate in place of the "...", evaluates to a capability to the 
authorized object.  Ignoring for a moment the issue of whether it evaluates 
to an on-line or an off-line reference, our standard example would now look 
like:

   def bob := <auth:...Alice's authorization (from somewhere) to invoke Bob...>
   def carol := <auth:...Bob's authorization from Alice to invoke Carol...>
   bob <- foo(carol)

The first authorization would be signed by whoever enabled Alice to invoke Bob.

The second authorization would be signed by Alice, and would include Alice's 
authorization to invoke Carol.

The expression as a whole would be signed by Alice.


                           An Aside: Enabling Stronger Auditing


Should Alice really sign the authorization for Bob to invoke Carol, given 
that she's signing the message as a whole?  Interestingly, we get much 
stronger auditability if the answer is no.  If the answer is yes, then this 
authorization by itself is what Bob would present when invoking Carol, or 
when authorizing someone else to invoke Carol.  If the answer is no, then 
only this invocation as a whole demonstrates Bob's authorization to Carol.

Likewise, one level back on the chain, Alice's inclusion of the 
demonstration that she is authorized to invoke Carol (necessary for her 
authorization of Bob to be valid) would not be an authorization certificate, 
but rather the entire invocation certificate showing why she came to have 
that authority.  

If the argument authorizations aren't signed, and therefore don't need to be 
standalone, then they also don't need to list the "Subject", since this must 
always be the Recipient (Bob).  They all must also have the same Issuer 
(Alice), so we could list this once rather than per-argument.  All that's 
left or SPKI's 5-tuple is the Carol designation: <vatID(C), 
hash(swissNumber(Carol))>.  The authorization data would consist of this 
plus a chain of earlier Invocation certificates.

The authorization chains are now more like stack tracebacks, whose utility 
for debugging is well known.  Auditing and debugging may be more similar 
than we think.  However, the space overhead may be unreasonable for many uses.



Next Message:  I finally get to the "Active" stuff