[messaging] Human sized keys

[Watson Ladd]

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.

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

My other thought, for another email, is about overlays of high latency
message routing over a low-latency anonymity network. I know research
has been done in this area, but feel free to suggest additional
reading offlist.

Sincerely,
Watson Ladd