[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Brian Warner]

On 2/11/14 7:21 PM, Trevor Perrin wrote:

> If that rendezvous address is a function of the secret, then offline
> and online guessing attacks against the rendezvous address could be
> used to recover the secret, undermining the value of PAKE or SMP.

The way we handled this in Firefox Sync (the original J-PAKE version)
was to have the "pairing code" generated by computer, and internally
split into two parts. The first part was a channel identifier, and let
the two nodes find each other (specifically it pointed to a short-lived
message queue on a baked-in rendezvous server). The second part was used
as the PAKE secret. We were exceedingly conservative in FF Sync, and
used 20 bits (4 base32 characters) for the channel id, and 40 bits (8
chars) for the PAKE secret.

If/when we re-introduce pairing, we'll use an email address to identify
the account, so I'm hoping we can cut that down to a 4 or 5 char code.

>>> So now the bootstrapping problem has been reduced to exchanging an
>>> "introduction secret".

Yeah, there are a few basic categories of solutions:

* remember/record some non-secure public identifier of the other person
  (e.g. email address), do DH, then do an after-the-fact verification
  step (either against something static like a pubkey fingerprint, or
  PAKE/SMP with a per-meeting agreed-upon secret)

* agree upon one low-entropy secret and a separate unique non-secret
  channel id, do PAKE with a rendezvous server

If you both have computers/phones with you, things get a lot easier: the
goal then becomes to have the humans safely introduce the computers to
each other. My current preference is to use short-range networking
(either bluetooth LE, ad-hoc wifi, camera/QR-code, or old-school modem
tones) to identify the nearest device, do DH, then use the generated key
to derive a synchronized random pattern, show it on both screens, and
ask the user to confirm that they match. There are some other tricks you
can do (SAS) to make it harder to blindly approve a mismatched
connection, but I'd start small.

It's worth exploring what you can do if only one of you has a computer
with you too.

>>> How much entropy does the introduction secret need? [...]

If you have an independent channel ID of some sort, then 20 bits would
get you one-in-a-million protection, which seems like a reasonable goal.
Especially if you can couple it with some measurements that safely
inform people when a large-scale attack is underway, and respond by
increasing the length of the codes.

If you can get to 40-60 bits, then it may become safe to do a bunch of
key-stretching, combined with a "day salt" (aka "Common Reference
String"), and use derivatives as both channel-id and an HMAC on a DH
exchange. It's a race against a high-powered adversary building a big
dictionary every day, but one that you can probably tune to be
uneconomical, especially if you can be patient (e.g. spend an hour doing
a big fat scrypt).

If you can get 128 bits, then simple HMAC of DH components is plenty.

If you can get more than that (e.g. bidirectional QR codes), then you
can remove some roundtrips and exchange all the necessary ratchet keys,
etc, up front, instead of using a rendezvous server.

BTW, remember that the goal is to let *both* parties correctly bind the
resulting session to the act of introduction. Ideally the UI would give
you enough information to remind you exactly how you met any particular
correspondent, maybe including the secret phrase you used for the
invitation. There are some shorter protocols that might only give this
assurance to Alice, but not Bob, which wouldn't be enough.

cheers,
 -Brian