[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Brian Warner]

On 2/11/14 11:43 PM, Brian Warner wrote:

> Yeah, there are a few basic categories of solutions:

This also depends upon what sort of unlinkability you want w.r.t. shared
correspondents. If Alice and Bob meet up, then later Alice and Carol
meet up, should Bob and Carol be able to compare their resulting
keys/whatever and learn that they're both talking to the same person?
(maybe that doesn't make sense for face-to-face introductions, but there
are probably other scenarios where it might: think about two reporters
wondering if they're talking to the same anonymous source)

You can do a secure pairing by just exchanging static public keys (no
secrets necessary), but then this linkability is trivial. To avoid it,
you need something that changes with each run of the introduction
protocol.

You could pre-print some cards, each with two copies of a random string:
you tear it in half and give one to the other person. You could
structure the strings to get a separate channel-id, letting you safely
use PAKE with the rest. Having those random strings sitting in your
wallet for a long time increases the opportunity for someone to snoop
them: you could make things marginally better by having *both*
participants print cards, exchange halves, then combine the two strings
for the resulting PAKE protocol.


Incidentally, I found two papers that were really useful for thinking
about pairing systems:

 The Ephemeral Pairing Problem (Jaap-Henk Hoepman):
http://arxiv.org/abs/0802.0834

 The Pairing Problem with User Interaction (Peyrin and Vaudenay):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.230.6262


The Peyrin/Vaudenay paper builds on Hoepman's work and describes what
sorts of narrow k-bit unidirectional channels (between various agents
and users) that you need to correctly build a secure shared key, where
each channel might provide both authenticity and confidentiality ("AC"),
just authenticity ("A"), just confidentiality ("C"), or neither ("0").
By "narrow" I mean that they aren't necessarily large enough to carry a
whole group element, but you still want the attacker's chance of success
to be 2^-k (i.e. don't enable an offline brute-force search).

It turns out the whole matrix of possible channels collapses into three
categories, with protocols to pair them safely:

* Alice -A-> Bob, Bob -A-> Alice : use SAS over these channels to verify
  DH elements sent over an unsecured channel

* Alice -AC-> Bob, Bob -0-> Alice : alice sends a PAKE secret to Bob

* Alice -C-> Bob, Bob -C-> Alice : send random strings to each other,
  XOR them together, use the result for PAKE

For anything less than these three, it can only be safe if the
attacker's computational bounds prevent them from exhaustively searching
the k-bit space during whatever time window they get. So you need longer
strings to increase the search space, key-stretching to make it
expensive, and changing salts (CRS/daysalt) to shrink the window.

cheers,
 -Brian