/ elib / capability / horton

Mailkeys as a Horton-like protocol

At http://www.xs4all.nl/~rmeijer/mailkeys.pdf Rob Meijer explains Mailkeys, a proposal for "Fighting spam with capability keys". He asked on cap-talk how mailkeys and Horton compare. A discussion at HP Labs concluded mailkeys works, first, for its original problem domain: email spam with legacy compatibility constraints. Additionally, we believed that mailkeys could be modeled in pure object-capability terms, and that the result could be used as a Horton-style intermediation.

This page shows such a Horton-style pure object-capability re-packaging of the mailkeys proposal. It is derived from and comparable to the lexically nested presentation of Horton shown here.

? pragma.syntax("0.9")

Unchanged from the original:

? def c {
>     to hi(_) {
>         println("hi")
>     }
> }
# value: <c>
 
? c.hi(c)
# stdout: hi
#
 
? def b {
>     to foo(c) {
>         c.hi(c)
>     }
> }
# value: <b>
 
? b.foo(c)
# stdout: hi
#
 
? def makeA(b, c) {
>     def a {
>         to start() {
>             b.foo(c)
>         }
>     }
>     return a
> }
# value: <makeA>
 
? def directA := makeA(b, c)
# value: <a>
 
? directA.start()
# stdout: hi
#

In the earlier Horton code, the inter-principal Horton protocol consists mostly of the protocol of Who objects (seal) and the protocol of Stub objects (deliver/intro). The stubs provide the fine-grain specificity needed to know what specific app-object is being addressed, and Who to blame for such access. The Who (like a public key in many cryptographic protocols) provides the coarse-grain identity respresenting a responsible party. An important attribute of Who objects is that they can be reliably compared for equality. In our draft paper, for brevity, we say only

Should Bob and Carol ever come to know each other independently of Alice, they can then blame each other, rather than Alice, for actions logged by P3 and S3. Say C is a wiki page. If Carol believes that Bob is not a pseudonym for Alice, and Carol decides that Bob has abused this page, Carol should then revoke Bob’s access without revoking Alice’s access by shutting off S3.
[emphasis added]

Unexplained is how such knowledge of independence could ever come about. How can Carol validly believe that Bob is not a pseudonym for Alice? Remember that, by "Bob" here, we mean simply the entity identified by the Who object labeled "Bob" in the diagrams. In the scenario presented in the paper, Carol has received Bob's Who object only from Alice. Within only this scenario, Carol indeed has no evidence that Bob is independent of Alice, and there's nothing that either Alice or Bob can do by themselves to repair this situation (short of out of band channels such as a face to face meeting). Until Carol does have such evidence of independence, Carol should rationally hold Alice responsible for all actions taken by Bob.

But let's say that Carol has a pre-existing relationship with Dave, i.e., with a responsible party identified by a Who object we will label "Dave" in our diagrams. By pre-existing, we mean in the sense that we already assume that Carol has a pre-existing relationship with Alice. Now, if Dave also tells Carol about Bob, and if Carol can tell that this is the same Bob, and if Carol believes that Alice and Dave are independent, then Carol might be able to derive some sense that this Bob is independent from both. (Of course, whether Carol has evidence that Bob is independent depends on what Alice and Dave told Carol about Bob when they introduced her to Bob. Horton does not itself standardize the form of such statements.)

Many object-capability systems provide a controversial equality primitive, EQ, that says whether both arguments directly designate the same object. (In E, the EQ primitive is spelled "==".) EQ does its job primitively without sending messages to the argument objects. The answer is according to the local platform (TCB), not according to the objects being asked. Given such a primitive, Carol can simply ask whether the Who objects she received from Alice and Dave are EQ. If they are, then Alice and Dave are talking about the same other party.

Mailkeys makes use of email addresses in ways that seemed at first to require something more than EQ. In mailkeys, the email addresses "bob+3a66fo@op.nu" and "bob+4d7fb1@op.nu" represent different ways of reaching Bob. The field between the "+" and the "@" are unguessable swissnumbers, providing the same specificity are the Stub objects in the Horton protocol. However, if Carol hears about the first address from Alice, and she hears about the second address from Dave, it seems (based on email conventions) that Carol can conclude, by comparing the addresses excluding these fields, that these both represent addresses for directly contacting the same party.

To model this in object-capability terms, we take the "bob+@op.nu" part to correspond to an EQ-able Who object. We'd then represent the role of the unguessable swissnumber instead by an unforgeable EQ-able key object with no behavior of its own. (One is easily created in E by evaluating "def key {}".) For Alice to effectively send a "foo" message to Bob's B, she'd actually send a "deliver" message to Bob's Who carrying a key in addition to the rest of the encoding of the "foo" message. The key provides all the specificity in this system that the Stub objects provide in Horton: It identifies for Bob both which of his app-objects the message is intended for, and it identifies for Bob who should be held responsible for sending the message.

# E sample
 
def makeQuoteln := <elang:interp.makeQuoteln>
def makeWeakKeyMap := <unsafe:org.erights.e.elib.tables.makeWeakKeyMap>

def makePrincipal(label :String) {
    def reportln := makeQuoteln(println, `$label said:`, 77)
    def proxyAmps := makeWeakKeyMap()
    def tokenAmps := makeWeakKeyMap()
    def giftAmps := makeWeakKeyMap()
    def provideAmps := makeWeakKeyMap()
    
    def makeProxy(whoBlame, tokenKey) {
        def log := makeQuoteln(reportln,
                               `I ask $whoBlame to:`,
                               75)
        def proxy {
            # as P1: whoBlame=Bob, tokenKey=T1
            match [verb, [p2]] {
                log(`$verb/1`)
                def [t2, whoCarol] := proxyAmps[p2]
                def gt3 := whoCarol.intro(t2, whoBlame)
                def p3Desc := [gt3, whoCarol]
                whoBlame.deliver(tokenKey, verb, [p3Desc])
            }
        }
        proxyAmps[proxy] := [tokenKey, whoBlame]
        return proxy
    }
    
    # as Carol
    def wrap(t3, whoBob) {
        # t3 is the tokenKey for only Bob to use, for Bob to know only Carol
        # could have provided. wrap needs to return a key that Alice sees,
        # that Alice therefore could misuse as well, so this needs to be a
        # key that only Bob can successfully use to obtain t3.
        def provideKey {}
        provideAmps[provideKey] := t3
        return whoBob.store(provideKey)
    }
    
    # as Bob
    def unwrap(gt3, whoCarol) {
        def provideKey := giftAmps[gt3]
        return whoCarol.obtain(provideKey)
    }
    
    def makeToken(whoBlame, targ) {
        def tokenKey {}
        tokenAmps[tokenKey] := [targ, whoBlame]
        return tokenKey
    }
    
    def whoMe {
        to __printOn(out :TextWriter) {
            out.print(label)
        }
        # as Carol
        to obtain(provideKey) {
            return provideAmps[provideKey]
        }
        to intro(t2, whoBob) {
            def [targC, whoAlice] := tokenAmps[t2]
            def log := makeQuoteln(reportln,
                                   `$whoAlice asks me to:`,
                                   75)
            log(`meet $whoBob`)
            def t3 := makeToken(whoBob, targC)
            return wrap(t3, whoBob)
        }
        # as Bob
        to store(provideKey) {
            def giftKey {}
            giftAmps[giftKey] := provideKey
            return giftKey
        }
        to deliver(t1, verb, [p3Desc]) {
            def [targB, whoAlice] := tokenAmps[t1]
            def log := makeQuoteln(reportln,
                                   `$whoAlice asks me to:`,
                                   75)
            log(`$verb/1`)
            def [gt3, whoCarol] := p3Desc
            def t3 := unwrap(gt3, whoCarol)
            def p3 := makeProxy(whoCarol, t3)
            E.call(targB, verb, [p3])
        }
    }
    
    def principal {
        to __printOn(out :TextWriter) {
            out.print(label)
        }
        to who() {
            return whoMe
        }
        to encodeFor(targ, whoBlame) {
            def tokenKey := makeToken(whoBlame, targ)
            return wrap(tokenKey, whoBlame)}
        to decodeFrom(giftKey, whoBlame) {
            def tokenKey := unwrap(giftKey, whoBlame)
            return makeProxy(whoBlame, tokenKey)
        }
    }
    return principal
}

Unchanged:

? def alice := makePrincipal("Alice")
# value: Alice
 
? def bob := makePrincipal("Bob")
# value: Bob
 
? def carol := makePrincipal("Carol")
# value: Carol

Unchanged:

? def gs1 := bob.encodeFor(b, alice.who())
 
? def gs2 := carol.encodeFor(c, alice.who())
 
? def p1  := alice.decodeFrom(gs1, bob.who())
? def p2  := alice.decodeFrom(gs2, carol.who())
? def a := makeA(p1, p2)

Unchanged:

? a.start()
# stdout: Alice said:
#         > I ask Bob to:
#         > > foo/1
#         Carol said:
#         > Alice asks me to:
#         > > meet Bob
#         Bob said:
#         > Alice asks me to:
#         > > foo/1
#         Bob said:
#         > I ask Carol to:
#         > > hi/1
#         Carol said:
#         > Bob asks me to:
#         > > meet Carol
#         Carol said:
#         > Bob asks me to:
#         > > hi/1
#         hi
#