Issues with Open Whisper Systems approach to Private Contact Discovery
Context: I am currently researching Private Contact Discovery in attempt to determine if there’s a feasible way to bring an API to enable this to the Web Platform. I believe it’s important for us to enable social applications such as future messaging clients to be built on the Open Web, and for these to be able to bootstrap their social graph from the local contact book.
This short post discusses the Open Whisper Systems post ‘The Difficulty Of Private Contact Discovery’, a classic in this space that I have referred to often and am very grateful to them for publishing.
TL;DR on the problem we’re trying to solve
A user, Alice, is signing up to a social service run by Bob, and would like to discover which contacts in her contact book have signed up to Bob’s service, so Alice can add/follow/message them etc.
An attack on the Open Whisper Systems (OWS) proposals
So far as I’m aware, most privacy-preserving intersection schemes assume that each participant has a set of private data, not known to the other participant. If this was true in the Private Contact Discovery case, then I think the suggested OWS approaches would work well, but this is not the case.
Consider for illustrative purposes an attack where a malicious actor, Mallory, provides a social service that Alice wishes to sign up to and perform Private Contact Discovery with.
Mallory, noticing that the phone numbers are enumerable (they’re just numbers with special formatting, after all), enumerates every valid phone number and “pretends” (for the purposes of these schemes) they every phone number is associated with a user signed up to the service.
Regardless of the scheme proposed in the OWS post, I believe that Alice’s entire contact set would be exposed to Mallory.
Does this attack work?
What do you think? Does this attack work? Did I miss something?
I note that the OWS approach does protect against the threat model of malicious eavesdroppers and National Security Letters, so perhaps my threat model (malicious service) was simply implicitly not the same threat model considered by them, but naturally I don’t want to have to trust services run by strangers online.
My personal conclusions
I have spent a long time exploring potential solutions to this problem and am fairly convinced that phone numbers have a few properties, such as their enumerability, that mean no system will ever be able to perform anything like perfect Private Contact Discovery.
That said, I believe there are a number of OK-to-pretty reasonable approaches that do better than simply sharing contact books directly. I believe that we as a community are going to have to come to a conclusion about whether the value of being able to discover people we know on social services is worth the risk.
I personally believe that if a platform can guarantee users give explicit permission then the value is worth the risk imposed by OK schemes to solve this problem.
I hope to share some of these alternate approaches that I’m aware of in a follow up post when I get time, but for now wanted to open the discussion on the above and hear what you all think.