[messaging] Masking contact addresses with ECDH

[Tony Arcieri]

On Mon, Feb 29, 2016 at 1:06 PM, Nick Badger <nbadger1 at gmail.com> wrote:

> Is the authorization step considered a direct interaction? I can't
> personally think of a way to do this privately unless the "authorization to
> create contact set intersection" step is ignored. Otherwise, best case
> scenario, an adversary wishing to discover the contacts list can just
> iterate across all known contacts, correct? If you have a single directory,
> that implies that the directory has the capability to unmask everyone's
> contacts.
>

Lots of questions! Maybe I can back up a bit.

When you say: "Is the authorization step considered a direct interaction?"

Do you mean: do Alice and Bob both need to be online at the same time for
Alice to authorize Bob as a contact?

The answer is certainly no, and this is a pretty basic feature of most
messaging systems: these authorization requests can happen asynchronously
when either contact is online or offline. The request is made *to the
directory*, as all users typically delegate contact management to the
directory to keep contacts in sync across devices. That is to say: Bob asks
the directory: "Can you ask Alice to authorize me as a contact?" When Alice
is online, the directory will send her this request, which she can either
approve or deny, which changes the directory's state.

Next: "If you have a single directory, that implies that the directory has
the capability to unmask everyone's contacts."

Indeed, this is a first-class feature of a directory: it knows everyone's
contacts, and needs this information to authorize viewers of the directory
as to whose contact information they're allowed to view. But beyond that,
directories are typically a rather horrific single-point-of-failure in
pretty much every E2E encrypted messaging system out there: they advertise
the public keys clients use to encrypt messages E2E, so they can be used to
recover plaintexts, barring things like CONIKS helping prevent that. Beyond
that though, even if the directory weren't implicated here, hiding contact
information from the messaging system is extremely difficult, as typically
this information is provided directly to the messaging system just to route
the message, and even if you try to hide that as part of message delivery,
they can still do traffic correlation.

The threat here certainly isn't hiding contacts from the directory (or by
extension the overall messaging system). It's hiding them from everyone
else...


> That being said, just because I can't think of one, doesn't mean one
> doesn't exist. That's also something you could potentially mitigate through
> an expensive one-way function like scrypt/argon2/etc. But now we're talking
> risk management and not provable security, if that's what you're going for.
>

The thing I thought was somewhat attractive about this scheme (where you
have to do some sort of O(m^n) operation on all contacts shared between
users) was the sort of Metcalfe's Law-style explosion of potential
combinations of contacts. In a system with a million users there are
half-billion possible contact relationships between users.

Between that and a system with some sort of proof-of-work for validating
contacts, it should be usable for the set intersection between two users
case, but difficult for bulk-unmasking.

-- 
Tony Arcieri
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20160229/48ec259d/attachment.html>