[messaging] Comparing introduction secret schemes (was Re: Unlinkable rendezvous via human-sized keys)

[George Kadianakis]

Trevor Perrin <trevp at trevp.net> writes:

> On Sun, Mar 23, 2014 at 5:56 PM, Daniel Kahn Gillmor
> <dkg at fifthhorseman.net> wrote:
>>
>> I think the proposal i mentioned earlier (one-use strong DH keys that
>> users print a stack of beforehand) is worth including in this bestiary.
>> Even if we decide ultimately that it is logisitically too expensive,
>> it's a useful contrast to the others.
> <snip>
>
> Different methods and their disadvantages -
>
> 1) Secret exchange
>  - asking people to think up sufficient entropy on the fly seems risky
> and low useability
>  - using non-computer tools to generate entropy seems low useability
> (shuffling cards, rolling dice, tearing "tickets" in half, etc.)
>  - central rendezvous server / DHT needed
>  - fingerprints must be exchanged separately (if desired)
>
> 2) "Human-sized" ECDH key exchange
>  - smallish keys (32 base32 chars = 80 bit security)
>  - low "forward secrecy for linkages" unless you change the key frequently
>  - central rendezvous server / DHT needed
>  - needs user preparation before meeting
>  - doesn't provide "unlinkable pseudonyms" - users can figure out
> they're corresponding with the same party
>
> 3) "One-time cards" ECDH key exchange
>  - not great useability (print / carry / exchange card halves, type in
> ~256 bits ECDH key per contact)
>  - central rendezvous server / DHT needed (unless printed on card?)
>  - needs user preparation before meeting
>  - fingerprints must be exchanged separately (if desired)
>
> 4) Fingerprint exchange
>  - needs PIR (??) to make "intro-cert" lookups unlinkable
>  - needs user preparation before meeting
>  - doesn't provide "unlinkable pseudonyms" - users can figure out
> they're corresponding with the same party
>

This seems to be one of those situations, where different approaches
satisfy different use cases and no approach is strictly better than
the other,

Personally, I'm quite intrigued by approach (1) (rendezvous using
human-memorable password) because I'm not good at preparing stuff
beforehand (I don't even have a printer!), and also because it
satisfies the Cryptonomicon threat model (if you carry computer/crypto
stuff with you, you get busted).

I was thinking the other day that introduction schemes like Pond's
might be a good place to try out ideas like Rivest's/Juels'
Honeywords [0].
Because of the anonymity and unlinkability of introduction requests,
an attacker who bruteforces passwords offline will have a hard time
figuring out which password belongs to the person he was trying to
attack, and whether a password is real or a honeyword. Of course,
honeywords is not really a complete solution; just a funny trick that
makes the work of the attacker harder.

Also, it is the case that if you flood the server with fake
introduction requests everytime you do a real introduction request,
you can increase the workload of an attacker.It's only a
polynomial-time increase, but it might be sufficient for some real
life applications :)

PS: I didn't manage to read through the whole thread so I might not be
    using proper terminology here. BTW, this thread has been getting
    mad big, nested and hard to follow. Maybe it's time to summarize
    the discussion in a wiki or something? :)

[0]: http://people.csail.mit.edu/rivest/pubs/JR13.pdf