Cryptographic Invitation Protocols

For a while now, I’ve been noodling around with a cryptographically-secure "invitation protocol" of sorts. I want something that can start with Alice sending an Invitation Message to Bob, and end with fully secure bidirectional communication.

The use cases I have so far are:

  • secure file-transfer tools, as a browser plugin or standalone application. The program would have an address-book, each entry would have an "Inbox" for that person, you would send them a file by drag-and-dropping it onto the Inbox. This invitation protocol would be used to populate the address book.
  • secure communication tools, like Petmail or an encrypted email/IM client, in which you want to add address-book entries so you can later exchange messages with the right correspondent.
  • Tahoe grid membership tools: you would use an Invitation to securely add another person’s client/server node to your grid, maintaining enough information to perform Accounting and server-selection properly.

but there are lots of others. Most applications with any sort of social component need a way to add "buddies" or correspondents. There are plenty of centralized systems (like IM networks, where the namespace is controlled by a single company), and a handful of insecure decentralized systems (like email addresses). I want this protocol for secure decentralized systems, in which the primary identifier for each participant is a public key of some sort.

Read on if you’re interested in cryptographic protocols..

A big usability-barrier for such systems is the bootstrapping problem: getting from a casual (insecure) everyday channel to the persistent secure long-term channel. A lot of tools punt on this and assume the keys are distributed ahead of time, or managed by some administrator. I’m interested in systems for which the only mode is "secure" mode, and which are as easy to use as traditional insecure systems. The usability standard is that the humans do not need to do anything more than they’re already doing: the system would look no simpler if you ripped out the security, so we might as well leave it in.

Imagine you’re chatting with someone at a conference, or at lunch, or in an IRC channel, and you want to send them a file, or pick up the conversation later, or whatever. You want your user agent to learn about their user agent, so that you can use it to send them a message later on. I’d like this to be properly secure, so every message is signed and encrypted, which means the agents need to learn each other’s keys. What can the two humans exchange that will let their agents establish that cryptographic connection?

The usual (worst case) pattern, with something like PGP, is that both people must pre-arrange for some common server to hold copies of their public keys, indexed by an email address, and to have secure hashes of those keys on something transferrable in their pocket (frequently printed on business cards). They can exchange business cards and type in their contents later (downloading the keys, computing the hashes, and comparing against the cards). Or, if they have an online connection already, they can paste large key files to each other, and perhaps paste+compare fingerprints. But we have plenty of experience showing that these schemes aren’t sufficiently usable, and needing to type in all that material discourages casual real-time use.

In the protocol I have in mind, one of these people sends an "Invitation" to the other, and the second person accepts it. Alice, the inviter, asks her computer for the invitation object (a file or a short string), and she somehow hands it to Bob: maybe she emails it to him, or pastes it to him over an IM channel, or recites it to him in person or over the phone. Bob drags or pastes or types this invitation into his computer. Then the two computers talk to each other, exchange keys, and at the end of the process, each computer has an address-book entry for the other. Later, their applications can use these keys to perform secure message exchanges with each other.

The ground rules for this protocol (including some assumptions and basic engineering tradeoffs) are:

  • Alice has a "secure-enough" channel to Bob already. "secure-enough" means we’re comfortable pretending that whatever she emails or pastes or speaks to him will remain secret and intact (not modified by an attacker) long enough for Bob to use it. Alice and Bob can take extra steps to make it more secure, if they want.
  • The channel isn’t long-term secure: we assume that the contents will become public eventually, so we aren’t allowed to put any long-term secrets in it
  • The channel is one-way and one-shot: if Alice sends her invitation via email, the protocol isn’t allowed to use email to get the response back. (this would impose burdens on the users, and require more complex interaction between the protocol implementation and existing tools)
  • The Invitation is thus single-use and only valid for a limited time, maybe 24 hours. We’re comfortable with a "Trust On First Use" policy: an attacker who both learns and acts upon the invitation early can impersonate Bob. But there will be a way to do an out-of-band comparison later, to completely rule out a man-in-the-middle.
  • Since the Internet is no longer a network of computers that can all talk to each other, we assume that either agent may be behind a NAT box. We allow applications to bake-in the address a publically-reachable "Relay Service", which helps them exchange messages for the duration of the protocol. We don’t allow this service to affect the security of the system: it could mount a DoS attack, but otherwise is no more powerful than any other MitM.
  • The goal of the protocol is to securely get Alice’s address-book entry into Bob’s address-book, under a petname for "Alice" that Bob picks when he accepts the invitation: we call this entry Ealice. We also need symmetry: to get Bob’s entry into Alice’s address-book under a petname that Alice picks when she sends the invitation, which we call Ebob. Part of these entries is the address of a relay-service or other helper to exchange subsequent application-specific messages.
  • All these address-book entries are public knowledge: no need to keep them confidential during the protocol (this turns out to affect the protocol in significant ways)
  • We have a secure/fast/short public-key signature scheme: Ed25519. We want a 128-bit security level.

I’ll post more later about the protocol I’m building to satisfy these constraints. Let me know what you think!

6 comments

  1. As you said, there are numerous use cases, but I think an important one is that this could be the basis for a completely browser-based video conferencing solution (when combined with camera and video HTML, of course) as you need a way to establish a connection that others can’t just listen into.

  2. Hi,

    I am very interested in this Subject. Imho the “Invitation” encyrption already exist with
    https://github.com/flakes/mirc_fish_10
    or
    http://fish.secure.la/

    When you query a User on IRC you can ask him for Key exchange and after exchange the complete Conversation is crypted.

    This is what you want won’t you?

    • Thanks for the pointer. I may not be understanding that project correctly,
      but from what I can tell, they’ve got Blowfish-based IRC encryption (ECB?
      OMG!) keyed by a manual 1080-bit DH key exchange (the fact that they started
      with *128-bit* DH is not reassuring). If that’s the approach, then the
      workflow must be something like: you push a button which pastes your
      180-character base64-encoded DH message into the channel, they cut-and-paste
      it into their client, they paste back their DH message, you cut-and-paste it
      in, then finally both clients switch into encrypted mode.

      I’m looking for something more: not limited to IRC, shorter messages, a
      one-way message (instead of a bidirectional real-time exchange), and a higher
      security level. And a workflow where you send/paste/speak a single invitation
      code to me (via any channel that we have in common: email, IRC, IM, QR-code
      and a camera, or just sitting within earshot of each other), and our
      computers do the test.

  3. I’m no expert on this topic, but to me it seems “OTR” is quite similar to what you are trying to achieve. Wikipedia has an article with all the basics explained and it should link to the original paper somewhere:

    https://en.wikipedia.org/wiki/Off-the-Record_Messaging

    • OTR is brilliant: we all have a lot to learn from those folks. The
      subliminal-whitespace capability-discovery trick, their key negotiation
      scheme, the overall zero-config it-just-works usability, the single-value
      Socialist Millionaire’s Problem key-confirmation step, and the post-hoc
      deniable authentication system: these are absolutely the “next level” above
      everything else out there. It’s like spending a week free-climbing a
      mountain, to discover that not only did somebody else beat you to the top,
      but they brought a working 150ft ferris wheel with them. Some day, when I
      grow up, I aspire to incorporate some of those features into my scheme.

      But it’s not quite right for my goal. OTR is designed for IM-like
      connections, which means they can rely upon an existing medium-capacity
      bidirectional channel (enough to send arbitrary-sized keys to each other). I
      want something that’ll work even with a small unidirectional message (hence
      the need for a relay server, and SaS/PAKE-like crypto tricks to make dictated
      codephrases secure enough). I like their deniable authentication, but I’ve
      scoped this project to not provide secrecy of the invitation, so that part is
      overkill. And I’m not expecting to integrate this code into existing
      IM/IRC/email clients, so I need an easy way to get the invitation message out
      of the application that manages the address book (which I pretend is a web
      browser, because it’s becoming the User Agent for everything, and because
      everyone has one, but which might be a dedicated Contacts app of some sort),
      and into the communication channel, and one inter-application hop per user is
      bad enough, I need to avoid requiring two.

      In some ways, OTR fits into a different category of protocol than what I’m
      looking for. There are roughly three types of secure connection-establishment
      protocols (further varied by whether the secret/verifier is generated by a
      machine or by a human):

      * paste a secret, then connect
      * connect, then paste a verifier
      * connect, then compare a verifier

      OTR is in the second category, where you can use it safely against passive
      eavesdroppers even without the verification step, and the secure
      “out-of-band” channel for the verifier is your personal shared knowledge with
      the recipient (in OTR, you tell them a question like “where did we have lunch
      yesterday” insecurely, then you both type the answer into your local
      clients.. in a more-traditional less-cool system you’d need to call them up
      on the phone and read a key fingerprint to them). I’m looking for something
      that can establish a connection too, so 2 and 3 won’t work.

      In addition, I don’t want our active-MitM defenses to rely upon user
      behavior. Those protocols, where you have to actually do the verification
      step to be protected from a man-in-the-middle, usually wind up with confused
      user incentives. If I push the “yes the verifier matches” button, I can talk
      to my friend, if I push “no it doesn’t” then I can’t talk to my friend.. why
      should I ever push “no”?. It gets worse when you think about user
      conditioning: every previous time they’ve done this process, the verifiers
      have matched, so I’d argue that they’ll just stop paying attention.

      That’s why the Sync J-PAKE scheme has you paste a code instead of comparing a
      code. (well, that, and Sync needs to establish a channel too: obviously this
      Invitation project is similar to Sync). If something really needs to be a
      compare-afterwards protocol, I’d want to add some tricks to keep users
      engaged. Dan Walkowski and I were just talking about this yesterday.. more
      details in a later post.

      Anyways, yeah, I’m certain that the research that surrounds OTR (in
      particular the set of tools they drew upon when building that particular
      protocol, and the ones they didn’t end up using) is spot-on for this project,
      so I’ve got some more reading in my future.

Leave a Reply to Robert Kaiser Cancel reply

Your email address will not be published. Required fields are marked *