[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Brian Warner]

On 2/14/14 10:38 AM, Trevor Perrin wrote:

>  4. Exchanging public-key fingerprints used to retrieve Diffie-Hellman
> public keys (my suggestion).
> 
> Of these options, I think I still prefer C4 (Diffie-Hellman
> rendezvous).

Yeah, if you don't need the unlinkability, then DH exchange has some
nice things going for it. In particular, you can print a batch of
identical business cards that contain enough information to connect
safely to the right key. And, as you pointed out, it becomes possible to
delegate trust to other parties, like a directory server that will map
email->pubkey (that's how I did Petmail the first time around, in 2004).
More importantly, you can get additional verification of the pubkey
after the fact, e.g. by asking mutual friends what pubkey they're using.

> Since it doesn't require exchanging secrets it's less vulnerable to
> problems with insufficient entropy or the secrets being mishandled.

True, but it is still vulnerable to folks who don't compare enough of
the pubkey bits, specifically if the comparison/transcription mechanism
is standardized enough that an attacker can compute near-misses offline.

The PAKE/SAS approaches have an "incremental security" property, where
your chances of losing to a MitM are generally N*2^-k, where "k" is the
length of the string you manage, and "N" is the number of times that the
attacker gets to guess. The attacker's computational abilities don't
matter.

Whereas doing DH with (parameters validated by) public keys, against a
high-CPU attacker, requires that you validate like 128 bits of the
hashed key, because you have to protect against an offline attacker (who
gets to start their pre-image attack the moment you publish your
pubkey). Validating fewer than 40 bits is basically worthless, unless
there's some serious key-stretching involved. But a 40-bit PAKE key
would be great.

I believe our best chance to achieve usable security will come from a
system which is kinda-secure now, but which can be made more secure by
spur-of-the-moment small-size verification steps. If the minimum bar is
pretty high ("you want me to compare how many bits?"), then users may
balk.

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

I keep going back and forth on that one. Some days, I think that it's
better to make relationship pseudonyms be the default, because you can
always voluntarily link pseudonyms together later (by publishing a
cross-signed message) if you feel the need to prove something. Whereas
if you use a single pubkey per user, then you've already committed to
that linking, for anyone you connect with.

> Preventing pseudonyms from being linked requires a lot of discipline,

Yeah, then on other days, I remember this truism, and figure that very
few people will actually keep them unlinked, and golly it makes the
protocol messy, so why bother :).

(one UI feature which might help is to show your conversations as a big
append-only log, so that you can see exactly what you've revealed to the
world under that pseudonym).

It might come down to the question: when people care about
unlinkability, do they tend to use these pseudonyms in a group, or in a
bunch of independent 1x1 conversations? Is it easiest to manage a small
number of distinct identities (e.g. "remember, each time I write as
'Deep Throat', use this kind of writing style, stick to these topics,
etc")?

And, tragically, the few people with enough real experience to answer
this question for us, can probably not speak up about what they've
learned, without outing their pseudonyms.

But yeah, today is one of those days where I'm leaning towards your
position of abandoning the relationship-pseudonyms and going with
long-term per-pseudonym public keys used for multiple relationships. I'm
still not convinced that copying pubkeys (for a given security level) is
easier than exchanging ephemeral PAKE secrets, but it certainly makes
some aspects of the protocol easier.

I'm hoping to get Petmail far enough to be a testbed for
invitation/introduction techniques. It'd be nice to have a real
communication app with switchable key-exchange mechanisms, so maybe we
can do some proper usability testing.

cheers,
 -Brian