[messaging] Unlinkable rendezvous via human-sized keys (was: Re: Human sized keys)

[Trevor Perrin]

(Context for this discussion:

https://moderncrypto.org/mail-archive/messaging/2014/000086.html
https://moderncrypto.org/mail-archive/messaging/2014/000113.html
)


On Wed, Mar 19, 2014 at 7:20 PM, Watson Ladd <watsonbladd at gmail.com> wrote:

> Dear all,
>
> I was recently thinking about the introduction problem: how do two
> people meet find each other on a messaging system and bootstrap to a
> trusted situation?
>
> There seem to be two kinds of question: one is a low-entropy shared
> secret, the other involves exchange of key material. The first would
> involve cut the deck or two-dollar call trick (each person gets a half
> with a serial number, or half a deck), and we have 48 bits in the case
> of the deck or some number I haven't calculated yet in the case of the
> bills.
>
> With the low-entropy shared secret the issue is rendezvous without
> exposing the secret. I don't have a solution for that.
>

Me neither.

I've heard proposals to have a rendezvous server return all messages to
every client, within some time window.  The client would respond to every
1st-round PAKE message by calculating the potential shared secret and
sending a trial 2nd-round message.  Only one received 2nd-round message
would match.

But this doesn't eliminate the online-guessing risk.  And it provides a
large DoS amplification against the clients and server, so seems
impractical.



> In the exchange mechanism I propose printing entire 160 bit ECC public
> keys on the card. With QR codes we could go to curve25519, but 160 bit
> ECC=32 character strings of letters and numbers = 5 groups of 6
> letters and numbers + 1 check group containing 2 more characters. If
> you've used Xbox Live cards, you've entered things this long, and that
> is on a console.
>
> Using this we can derive a shared secret, and from that two parts for
> a distributed rendezvous protocol.
>
> The idea is that each party determines a shared identifier F and
> shared key K. Using F as a key in a DHT they can insert and retrieve
> messages authenticated and encrypted with K. These messages can set up
> a more permanent system. Anonymity can be preserved either by running
> the DHT over Tor, or building it into the DHT.
>
> This way the PIR step is removed. Attackers have 2^80 work to break
> this scheme, but we can rotate keys (at the cost of being online) or
> use bigger keys (with the cost of QR reading).
>

OK, so comparing to my proposal above:

You'd have users exchange ~160-bit ECDH keys directly.  I'd have users
exchange (introduction server name, ~128-bit fingerprint) and use these to
lookup an "introduction cert" where the fingerprinted long-term key signs a
short-term ECDH key.

Your approach eliminates the need to mask the intro-cert lookup via PIR or
dummy traffic.  But it lowers the security of your long-term key from ~128
bits to ~80 bits, and reduces "forward-secrecy of linkages", since
compromise of the long-term ECDH key (which you've printed on your business
card, so you're not going to rotate it frequently) allows going through
published rendezvous messages and linking correspondents for the key's
lifetime.

Also, your approach requires a global server (or DHT) to store the
rendezvous messages, whereas my approach allowed each user to indicate
their rendezvous server in the intro cert, eliminating the need for a
globally-agreed infrastructure there.

Weighing all that, I think I still feel that the benefits of intro-certs
(higher security level and forward-secrecy, no central rendezvous server)
justifies the complexity and costs of anonymizing the lookup...


Trevor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140320/537daf5c/attachment.html>