[messaging] Proposal for anonymous contact discovery

[Tom Ritter]

On 24 July 2014 16:01, Joseph Bonneau <jbonneau at gmail.com> wrote:
> Thoughts?

This assumes Earl and Layton have a perfect record of all emails
between them. In practice, I remove sensitive emails from the server
to prevent an attacker who compromises the server from retroactively
getting all the good stuff[0]. Also in practice, my parents use POP3
instead of IMAP[1]. Also in practice, companies have a policy of
archiving emails after N months into long-term difficult-to-access
storage. By hearsay, I think some people aggressively delete emails
instead of filing them away somewhere.

The general idea of establishing a source of high-entropy, shared,
secret data between two people is the hard one. Figure that out, and
that entropy can be used in near _any_ protocol to achieve [long term]
[ratcheting] [key exchange] [symmetric cryptography] [whatever].  It's
why there's Key Extractors in TLS: agreeing on key material is hard,
let's use this other key material we agreed on already.

But it occurs to me the SMTP message-id approach is not completely
sunk because of the assumptions - we just need to open it up to lots
more messages.  This problem is essentially trying to perform set
intersection.  I have a bunch of 'secret' bitstrings I think you share
some of, let's figure out if we do in fact share some. If we do, that
bitstring can be used as keying material to authenticate a longer-term
key.

>From an algorithm point of view, the work being done in Bitcoin to
minimize P2P data transfer seems relevant[2]. From a security point of
view, I don't believe they're trying to protect the bitstrings - but
if they are in fact random bitstrings, it seems safe to hash them and
as long as you can't invert the hash you can't learn the bitstring.

-tom


[0] Obviously there are degrees of compromise - an attacker who gets
my IMAP password is less strong than one who has root on a machine
with the disks.
[1] They apparently carry the state of {emails I've read, emails I've
responded to, emails I need to reread, etc} in their heads at all
times as they move between phone, laptop, and desktop.
[2] http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/CAPkFh0thLcaAPaa7Xswu2vSxossRDziMCoStzTDWw%2Be0c3WqTw%40mail.gmail.com/
 But those algorithms are also interactive. (At least some of them, I
think they also talk about non-interactive ones).