[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Trevor Perrin]

Following on the "fingerprints" and "short auth strings" discussions:

The secrets used to bootstrap a relationship in systems like Pond [1]
or Petmail [2] are another small string with security & useability
concerns.


Background
----
Messaging systems like Pond [1] and Petmail [2] require pairwise
secret state between communicating users, for a couple purposes:
 * Forward-secrecy ratcheting (e.g. [3])
 * Message authentication that allows the recipient's "mailbox" server
to accept messages only from recipient-approved senders without
learning the sender's identity (e.g. Pond's group signatures).

This sort of message authentication eliminates spam, which in turn
enables "unlinkable" communication techniques designed to prevent
third parties from learning who you are communicating with:
 * Users could send messages by contacting the recipient's mailbox
server via Tor.
 * Recipients could check their server for new messages at
predetermined intervals and alway download a fixed quantity of data,
thus defeating end-to-end correlation based on message size and
timing.

But there's a bootstrapping problem here:  How do we set up the
"pairwise secret state" necessary for these systems to work while
preserving "unlinkability"?


Physical meetings -> unlinkable online rendezvous
---
Assume Alice and Bob can meet secretly in person.  They could use this
meeting to bootstrap their "pairwise secret state", for example by
exchanging Pond's several-hundred byte KeyExchange messages via
Bluetooth or QR codes.

But what if they didn't bring computers?  This can be supported with
an online "rendezvous server".  The idea is that Alice and Bob agree
on some "introduction secret" in person (e.g. writing a passphrase on
napkins).

Later, both parties type the introduction secret into their client
app, which uses it to derive a "meeting ID" at the rendezvous server
where both parties can post and retrieve messages anonymously via Tor.

Both parties use this (rendezvous server + meeting ID) to exchange
messages.  In Pond's "PANDA" protocol, both parties first perform a
"DH-EKE" style password-authenticated key exchange (PAKE) using the
introduction secret, then use the PAKE key to encrypt KeyExchange
messages.  The DH-EKE step provides authenticated, forward-secure
encryption so that the rendezvous server can't link the participants
by seeing which long-term public keys are included in the KeyExchange,
even if the introduction secret leaks out afterward.


Entropy of introduction secret
--
So now the bootstrapping problem has been reduced to exchanging an
"introduction secret".

How much entropy does the introduction secret need?  At first glance a
password with low entropy (20+ bits) seems sufficient, since the PAKE
only allows an active attacker a single guess.  But note that the
meeting ID is also derived from the introduction secret, which exposes
the secret to offline guessing by the rendezvous server and online
guessing by anyone who can contact the rendezvous server.

Thus the PAKE is a bit of a red herring, and it seems prudent to make
the introduction secret ~128 bits.  Using something like scrypt to
stretch the secret lowers the entropy needed to resist offline attack
to perhaps ~100 bits, but this length is still a useability problem.

It would be great if we could make low-entropy passwords work here,
but it's not obvious that this can be safely done.


Diffie-Hellman rendezvous
---
Another approach might be to have Alice and Bob exchange public-key
fingerprints and derive the meeting ID via Diffie-Hellman, instead of
agreeing on an introduction secret:

During their in-person meeting, Alice and Bob could exchange
fingerprints for their long-term signing keys.  Later, each party
could look up the other's signing key and a short-lived (e.g. 1 week)
Diffie-Hellman public value signed by that key.  The meeting ID would
be calculated via Diffie-Hellman between the short-lived values.
(Short-lived DH private keys would be destroyed periodically to
prevent an attacker who compromises a short-lived key from using it to
link users based on old meeting IDs).

This requires additional infrastructure to publish keys and
signatures, but arguably simplifies the data that needs to be
exchanged in an offline meeting (while fingerprints are not small,
they are fixed and not secret, so can be printed on business cards,
looked up online based on email address, etc).


Other ideas?  Comments?


Trevor


[1] https://pond.imperialviolet.org/tech.html
[2] https://github.com/warner/petmail/blob/master/docs/invitations.md
[3] https://whispersystems.org/blog/advanced-ratcheting/