[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Trevor Perrin]

On Mon, Feb 17, 2014 at 11:51 PM, Brian Warner <warner at lothar.com> wrote:
> 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.

Yeah, all of that.


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

PAKE/SAS is great in a pairing situation where user(s) will notice
each connection failure, so a bad guy will only get a few guesses.

But for an online rendezvous, the meeting ID (derived from the shared
secret) is the weak point:  An attacker can try to guess the shared
secret by making a large number of online queries for the meeting ID,
and the rendezvous server can try to crack the meeting ID with offline
search.

You earlier suggested that users could agree on separate meeting IDs
and shared secrets.  But I'm not sure that gains anything.  (Ex: if
users can agree on 60 shared secret bits, splitting that into a 30-bit
meeting ID and 30-bit shared secret weakens resistance against the
offline attack to 30 bits).


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

For the rendezvous case I'm imagining you want users to agree on, I
dunno, 60 or 80+ bits to resist offline guessing, even with key
stretching.  That's still a lot for people to come up with in
face-to-face meetings and write down.


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

Good question.

Another question:  Is it easier to have a default of "linkable
pseudonyms" and require users to create different keys if they want to
partititon their identities, or have a default of "relationship
pseudonyms" and require users to issue cross signatures if they want
to link their identities.

My guess is that the former is technically simpler and more intuitive
to users.  But I could be wrong.


Trevor