[cap-talk] Mailkey works!

[David Hopwood]

Mark Miller wrote:
> There was one critical fact about email that I hadn't known, that was
> preventing me from understanding [the mailkey] protocol. You are implicitly
> making use of the ability of Bob to compare
> 
>     alice+3a66fo at op.nu
> 
> to
> 
>     alice+4d7fb1 at op.nu
> 
> and conclude that they both communicate to the "same" entity, for some
> meaning of same. The comparison here needs the security properties of
> an authenticating grant-matching equality primitive (EQ), even though
> these represent two different capabilities which grant different
> authority.

The methods of doing this that we discussed were:

 - having the system provide a "weak equality" operation primitively;
 - using (Token, reference) pairs in place of plain references.

The code below implements "weak equality" nonprimitively, and without changing
the implementation of references.


pragma.syntax("0.9")

def makeBrand := <elib:sealing.makeBrand>

# Object-capability implementation of addresses similar to mailkey's
# <name+key at domain>. Any mailkey-like protocol can be implemented on top
# of this fairly easily.
#
# (I'm not entirely sure that this is what we need, and I can't test it at the
# moment because my E installation is broken, but I thought I'd post it anyway
# so we can discuss it at the Friday meeting.)
#
# An address object acts as a forwarder to an arbitrary target object. We
# can generate a new address for any target, and compare two addresses to
# see whether they forward to the same target. We can also separately revoke
# any address (for simplicity, this uses the caretaker pattern rather than a
# membrane).

# Start with the non-distributed case, where we can assume that the address
# comparer is universally trusted.

def nonDistributedCase {
   # E doesn't have built-in sibling communication; simulate it using a
   # sealer/unsealer.
   def [siblingSealer, siblingUnsealer] := makeBrand("sibling")

   to makeAddressAndRevoker(var target) :[any, Thunk] {
      def address {
         to getSealedTarget() :any { return siblingSealer.seal(target) }
         match [verb, args] { return E.call(target, verb, args) }
      }
      def revoker() { target := null }

      return [address, revoker]
   }

   to weakEq(a, b) :boolean {
      try {
         return siblingUnsealer.unseal(getSealedTarget(a)) ==
                siblingUnsealer.unseal(getSealedTarget(b))

      } catch _ {  # FIXME: more specific catch
         return false
      }
   }
}

# To remove the assumption of a universally trusted comparer, we have each domain
# do comparison for its own objects. A domain can be any unit of distribution.
#
# For simplicity, this code is written to use immediate calls, even though it
# really only makes sense in a distributed setting. In practice this functionality
# would probably be built-in to the distribution protocol, making use of vats'
# public/private keys instead of [domainSigner, domainVerifier].

def distributedCase {
   to makeDomain(name :String) {
      # Sealer/unsealer pairs can be used either with the unsealer private, for
      # encryption, or with the sealer private, for authentication. Here we are
      # using them for authentication.
      def [domainSigner, domainVerifier] := makeBrand(name)

      # Same as the non-distributed case.
      def [siblingSealer, siblingUnsealer] := makeBrand(`$name sibling`)

      def domain {
         to getVerifier() :any { return domainVerifier }

         to makeAddressAndRevoker(var target) :[any, Thunk] {
            def address {
               # If we seal [x, y] using domainSigner, we are asserting that x and y
               # both belong to this domain and are (forever) weakly equal.

               # I'm sure there is probably a simpler way of doing this.

               to getProofOfDomain() :any {
                  return [domainVerifier, domainSigner.seal([address, address])]
               }
               to getProofOfWeakEqualityTo(other) :any {
                  def [otherVerifier, otherProof] := other.getProofOfDomain()

                  try {
                     if (otherVerifier != domainVerifier ||
                         otherVerifier.unseal(otherProof) != other ||
                         siblingUnsealer.unseal(address.getSealedTarget()) !=
                           siblingUnsealer.unseal(other.getSealedTarget())) {
                        return null
                     }
                     return [domainVerifier, domainSigner.seal([address, other])]

                  } catch _ {  # FIXME: more specific catch
                     return null
                  }
               }
               to getSealedTarget() :any { return siblingSealer.seal(target) }

               match [verb, args] { return E.call(target, verb, args) }
            }
            def revoker() { target := null }

            return [address, revoker]
         }
      }
      return domain
   }

   to weakEq(a, b) :boolean {
      try {
         def [aVerifier, aProof] := a.getProofOfDomain()
         def [bVerifier, bProof] := b.getProofOfWeakEqualityTo(a)

         return aVerifier == bVerifier &&
                aVerifier.unseal(aProof) == [a, a] &&
                bVerifier.unseal(bProof) == [b, a]

      } catch _ {  # FIXME: more specific catch
         return false
      }
   }

   to getDomainVerifier(a) :any {
      def [aVerifier, aProof] := a.getProofOfDomain()
      if (aVerifier.unseal(aProof) != a) {
         throw `$a failed to prove membership of $aVerifier`
      }
      return aVerifier
   }
}

# My current E installation is too old for 'pragma.syntax("0.9")' to work,
# and I can't download a new one because cypherpunks.to is down. Still, here
# are some tests for how it's supposed to work:

def x := "x"
def y := "y"
def domA := distributedCase.makeDomain("A")
def [x1, x1revoke] := domA.makeAddressAndRevoker(x)
def [x2, x2revoke] := domA.makeAddressAndRevoker(x)
def [y1, y1revoke] := domA.makeAddressAndRevoker(y)

def domB := distributedCase.makeDomain("B")
def [x1b, x1brevoke] := domB.makeAddressAndRevoker(x)

distributedCase.weakEq(x1, x2)
# true
distributedCase.weakEq(x1, y1)
# false
distributedCase.weakEq(x1, x1b)
# false

# Try (and fail) to create a fake "x" weakly equal to x1, without using domA.
[verifier, proof] := x1.getProofOfDomain()
def fakex {
   # these are the wrong proofs; we can't create the right ones without
   # access to domA's domainSigner.
   to getProofOfDomain() :any { return [verifier, proof] }
   to getProofOfWeakEqualityTo(_) :any { return [verifier, proof] }
   match [verb, args] { println "bwahaha!" }
}
distributedCase.weakEq(x1, fakex)
# false
distributedCase.getDomainVerifier(fakex)
# should throw exception

x1revoke()
x1
# should throw exception

-- 
David Hopwood <david.hopwood at industrial-designers.co.uk>