[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Trevor Perrin]

On Wed, Feb 12, 2014 at 11:05 AM, Brian Warner <warner at lothar.com> wrote:
> On 2/11/14 11:43 PM, Brian Warner wrote:
>
>> Yeah, there are a few basic categories of solutions:

Your emails have great descriptions, let me try to group things into a
few cases:

(A) Both parties bring their communication device with short-range
comms to the meeting.  They pair the devices, which exchange the
necessary secrets then and there.

But it's reasonable for parties to use a computer for secure comms
which they *don't* carry around to secret meetings, so...


(B) At least one party brings a computer.  The computer runs a
"password generator" to create a good secret with enough entropy, and
transfers it to the other party (manually or short-range comms).  The
"passwords" are later transferred to the main communication devices,
which do a rendezvous.

But it's reasonable for parties to have chance meetings without their
computer around, or high-security meetings where computers aren't
allowed, so...


(C) With no computers, there's various ways to agree on enough entropy
for an unlinkable online rendezvous:
 1. People invent passwords on-the-fly, and hope that a bunch of
key-stretching will make them strong enough.
 2. Shuffling / splitting decks of cards (Adam's idea for Pond).
 3. Exchanging printed "tickets" with one-time codes which you tear in
half, as you mention in your other email.
 4. Exchanging public-key fingerprints used to retrieve Diffie-Hellman
public keys (my suggestion).


Is that it?

Of these options, I think I still prefer C4 (Diffie-Hellman
rendezvous).  Since it doesn't require exchanging secrets it's less
vulnerable to problems with insufficient entropy or the secrets being
mishandled.  And since it's based on the public-key, the rendezvous is
tied into strong authentication, and can be done flexibly based on
published info.  For example, if I can query (via Tor) some trusted
directory associating your email address and fingerprint, then we only
need to exchange email addresses at the meeting, which would be quite
nice.


> 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)

Good point.  I'd distinguish between "unlinkable communications" and
"unlinkable pseudonyms".  This notion of "unlinkable communications"
is similar to how [Feigenbaum] and [Hevia] use "unlinkability", though
[Pfitzmann] and [Backes] use "relationship anonymity".


> 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.

[Pfitzmann] would call those "relationship pseudonyms", meaning
participants create a different unlinkable pseudonym for each
relationship.

AIUI one of the differences between Pond and Petmail is that [Petmail]
uses relationship pseudonyms by default (though the scope of the
pseudonymity is limited to pseudonyms sharing the same mailbox
server).

I argue that using relationship pseudonyms by default is undesirable,
since it makes it harder for parties to leverage public information to
authenticate each other or perform a "Diffie-Hellman rendezvous".

Preventing pseudonyms from being linked requires a lot of discipline,
so it's reasonable for users who want multiple pseudonyms to
explicitly create them.  For most users having an easily-fetched and
easily-authenticated public-key seems more valuable.


Trevor


[Feigenbaum] 2007
http://www.cs.kent.edu/~javed/class-P2P12F/papers-2012/PAPER2012-Tor-iomodel.pdf

[Hevia] 2008
http://cseweb.ucsd.edu/users/daniele/papers/AnonChannel.pdf

[Pfitzmann] 2000...2010
http://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf

[Backes] 2013
http://petsymposium.org/2013/papers/backes-anonymity.pdf

[Petmail]
https://github.com/warner/petmail/blob/master/docs/mailbox.md