[messaging] Proposal for anonymous contact discovery

[Joseph Bonneau]

Here's a protocol sketched over lunch today with Ian Goldberg and Nik Unger:

Goal: Earl (an early adopter) downloads and installs the newest
SecureChatApp, which creates a new public key for Earl and uploads this to
the SecureChatApp servers. Later on, Earl's friend Layton (a late adopter)
downloads SecureChatApp which, recognizing Earl in Layton's contact book,
fetches Earl's key from the SecureChatApp servers. Of course we want not
only for the servers to not learn that Earl and Layton are friends, but not
to learn that Earl and Layton are using the app at all (which may require
the communication all happens over Tor for high assurance). So the app
shouldn't learn any identifying info about Earl, even though Layton has to
later be able to find Earl. Also, Layton doesn't want to bother all hundred
of his contacts by asking if they're using SecureChatApp, or maybe actively
doesn't want to broadcast that he's using it except to people already using
it.

Non-solution: Have Earl upload a hash of his phone number, email address,
or other known identifier. These can be searched over.

Potential solution: Use shared entropy Earl and Layton already both know.
Suppose they're already communicated over SMTP. Earl takes the most recent
email message he sent to Layton and uses this to derive a master key K.
We're assuming here the email has enough entropy (should hold, esp. with
the Message-ID) that it can't be searched over.

Using this key K, Earl encrypts and MACs his public key and other
addressing info (maybe an ID) and posts it to the server. When Layton signs
up, he derives the same key K by hashing the most recent email received
from Earl and checks to see if this exists at the server. This can be done
in a few ways: downloading the whole (or part of) the database, PIR, or
generating a lookup index by another hash of K. If K exists, Layton can
decrypt Earl's info and they can now talk.

Efficiency improvement: Obviously, Layton may have a more recent received
email from Earl by the time he signs up. Solution: Layton scans forward
from the beginning of time and hashes every email received from Earl.
Derive K from the email with the lowest hash. If that K doesn't exist, it
may simply mean Earl joined before that email was sent. So, recursively do
this for all earlier emails than that. This should take lgN queries at most
if N emails have been received.

Security improvement: This is vulnerable to Earl and Layton's email
providers. You could also design this over SMS. Perhaps you can use both
(if available) to make it harder for anybody but Earl/Layton to derive K.

Thoughts?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140724/8b135ba8/attachment.html>