Find matching phone numbers without actually knowing them

Question

We have a mobile app that, given two users, needs to let them see what common contacts they have based on their phone numbers. How can we do this in a cryptographically secure way and respecting the users' privacy (i.e. without sharing the numbers in plain-text between them or with a server)?

---

Our current solution is:

1. (On phone A) Generate a single random salt.
2. (On phone A) Take all phone numbers from phone A and generate a SHA512 hash with multiple rounds for each phone number using the salt generated from step 1. Something like sha512(sha512(sha512(phonenumber + salt) + phonenumber + salt) + phonenumber + salt).
3. (On phone A) Send these hashes along with the salt to phone B (via a server).
4. (On phone B) Repeat step 2 to generate hashes for its own phone numbers using the same salt generated on phone A.
5. (On phone B) Compare the two list of hashes - a matching hash means a matching phone number, and therefore a common contact.

---

Is this a flawed approach, prone to rainbow-tables/brute-force attacks, and if so is there any other solution that is more suitable? Maybe using bcrypt with a given salt is better than doing multiple rounds of sha512?

Answer 1

bcrypt would be a somewhat better approach because it is designed to be (programmably) slow.

Using a large enough salt and a reasonable complexityFactor, bcrypt(salt + number, complexityFactor) should yield a viable hash and you avoid "rolling your own cryptography", which could possibly turn out to be a difficult sell. To increase security you just crank up complexityFactor.

An attacker would now have to generate the bcrypt not only of every 10-digit phone number (which could be feasible: there are only 10¹⁰ numbers after all), but of every possible salted sequence. With a 10-character base64 salt (60 bits of entropy), the complexity increases of twenty orders of magnitude.

Brute forcing

Suppose you have 1,000 contacts . The CPU of your average phone seems to be two orders of magnitude slower than a server core array. I think it's reasonable to say that it will be three orders of magnitude slower than a semi-dedicated GPU implementation of bcrypt, which is said not to be so efficient.

So we tune bcrypt to take 100 milliseconds for each encoding. This means that we need 1 minute 40 seconds to generate our 1,000 hashes, which is a reasonable time for one thousand contacts (a progress bar seems in order). If the user only has 100 contacts, he'll be done in 10 seconds.

The attacker, given the salt of one number, has to generate perhaps 10⁸ numbers to reasonably cover the mobile number space (the first number, and possibly the first two, aren't really 10 or 100 -- I count them as 1). It will take three orders of magnitude less than 10⁸ times 100 milliseconds, i.e. than 10⁷ seconds. This is down to 10⁴ seconds, or around two hours and a half (or a whole day if the GPU optimization thingy turns out not to work).

In less than four months, the whole 1,000 contacts will have been decrypted - using one optimized server. Use ten such servers, and the attacker will be done in two weeks.

The problem, as pointed out by Ángel's answer and Neil Smithline's comments, is that the key space is small.

In practice user A will produce something (a hash block, or whatever) to be made available somehow to B. User B must have a method that works like

matches = (boolean|NumberArray) function(SomethingFromA, NumberFromB)

(little changes if the second parameter is a set of N numbers, since UserB can build a set using one true number and N-1 numbers known to be fake or not interesting. It can lengthen attack time by a factor of N).

This function works in a time T... actually this function must work in a time T short enough that user B, in a commercial real world application, is satisfied.

Therefore one bound we can't easily dodge is that M numbers must be checked in an acceptable time on an average smartphone. Another bound we can't reasonably dodge is that User B can supply fake numbers to the algorithm (i.e. people that aren't really contacts, and possibly do not even exist).

Both bounds also are enforced if the checker is on a third server; this only assures a lower execution time limit that can thwart some scenarios, such as "decrypt all UserA's numbers", but not others such as "verify who has this number", as in drewbenn's answer).

From these two bounds arise the fact that using a smartphone (or a third party server with minimum execution time enforcement), cycling through all 10⁸ reasonable numbers takes about 10⁸ smartphoneTime time, or on the order of one thousand months.

Attack strategies to decrease this time are distributing the attack between several verifiers, or running it on a non-throttled and faster server (this requires the algorithm being available, but assuming the contrary is security through obscurity), and they look both feasible and affordable.

A loophole?

One possibility could be to introduce a small probability of false positives. I.e., the above oracle function will occasionally (say once every ten thousand contacts), and deterministically on UserA's input, return true to one of UserB's numbers.

This means that the brute force attack on 10⁸ numbers will yield UserA's contacts mingled with 10⁴ other numbers. Determinism on UserA's input means that two successive checks on these 10⁴ found items won't further whittle them. Unless UserB's can grab a different copy of UserA's input, which will yield a different set of false positives and allow filtering the true contacts as the intersection of the two sets, this may make the bruteforced answer less appealing. This comes at a cost - honest UserBs will have to get the occasional false hit.

We really can't win

If UserB must be able to answer the question "Is number X among UserA's contacts?" in a reasonable time with certainty, the time expenditure is linear, because the system cannot prevent two such requests from being made against numbers X1 and X2, and time for request X2 will be the same for request X1. Therefore, solving two numbers will require double that reasonable time; by induction, solving for N numbers will entail N times that reasonable time (not, say, N²).

The difference between a legitimate request and an attack is that the attack will work on a space ten to a hundred thousand times larger. Being linear, it will require a time up to one hundred thousand times longer... but it also may run on a machine or group of machines one hundred to one thousand times faster.

Therefore, our attacker will always be able to decrypt all of UserA's contacts in a "still not unreasonable" time. The only serious check to this would be for the checks to be run on a third, trusted machine with rate limiting and the means of detecting a likely attack.

To thwart an attacker we need something bad to increase with the increase of N, and since it can't be running time (which doesn't increase enough), I think the only resort left is the probability of false positives. The attacker will still get the answer, but we might still succeed in making a bruteforced answer less usable.

One simplistic implementation (poor man's Bloom filter)

To answer Mindwin's comment, the local algorithm can't work by hiding information - the information must be missing in the first place, otherwise we'd be still be doing security through obscurity.

One method would be for UserA (Alice) to send over the bcrypt salt for her (say) 1000 contacts, followed by 1000 incomplete bcrypt hashes. If the hashes are truncated at the i-th byte, there will be pseudo-random collisions. Among UserB (Bob)'s contacts, which are few, collisions will be very rare (unless i is really small). Among the attacker(Eve)'s whole number space, collisions will be significant.

Note that phone number distribution is not flat, so Eve can have ways of whittling those collisions by removing, say, unused numbering sequences.

If every contact hash has a probability of collision of one in a thousand, Bob, checking his one thousand contacts, has a probability of (1 - 1/1000)¹⁰⁰⁰ of having no collisions at all - that's 70%, not so good. If collision probability is 1/10000, Bob with one thousand contacts will have 90% chances of not getting even one collision. On a hundred contacts only, no-coll probabilities for Bob are 90% and 99% respectively.

Eve, verifying 10⁸ numbers, even with p = 1/10000, will always get ten thousand collisions no matter what.

Sending two or more hashes with higher collision probability does not change things much for either Bob or Eve, in comparison to sending a single hash with collision probability equal to the product of the separate hashes.

For example instead of 1 round with p = 1/10000, use two rounds with p = 1/100, since 1/100*1/100 = 1/10000.

So Alice sends two sets of unordered incomplete hashes, with different seeds, and higher collision probability of 1%; Bob will test his 1000 contacts and get positive matches for the 100 contacts he has in common; the remaining 900 shouldn't match, but since the hash is incomplete, 1% of them will, that means 9 spurious contacts, and Bob will end up with 109 likely candidates after running 1000 tests. He now has to test those 109 with the second hash, which also has 1% probability. The 100 true intersections will still match. Of the remaining 9, likely none will pass. The chance of a contact passing two such rounds is 1% of 1%, i.e. 1 in 10000, and the chance of having not even one false positive on 1000 nonmatching contacts is (1-1/10000)¹⁰⁰⁰, or 90.48%, exactly as before.

With the same numbers, Eve will get one million false positives on her first round, and will have to run one million extra tests. 1% of those will match the second round, leaving Eve with ten thousand false positives mixed up with the one thousand contacts from Alice.

Eve has had to run 101 million tests instead of 100, and Bob had to run 1109 tests instead of 1000. In proportion, the double-hash scheme impacts Bob harder than Eve. It would be better to use a single hash with higher complexity.

The privacy problem of answering the question "Does Alice know number N?" will remain unaddressed - the time to answer that is the same for Bob and Eve.

Answer 2

There are potentially other privacy issues you're not considering yet. By design your app makes it easy to see who is connected to a certain target. So an attacker creates one contact on their phone (the activist/informant/terrorist/victim they are interested in) and then connects to many other users through your app, to create a list of the target's contacts. So for example a DV abuser could use this app to make a list of people still in contact with his ex: even Google has had problems getting this right.

Answer 3

Yes, it is (a bit) flawed. The problem is that the space is too small, so even with the multiple rounds and salts, it's relatively easy to bruteforce.

Open Whisper Systems had a witty system where they provided an encrypted bloom filter that can be queried locally using blind signatures. They explain the process (as well as providing a good discussion of the private information retrieval problems) at https://whispersystems.org/blog/contact-discovery/

Sadly, they had to discontinue this on TextSecure due to practical issues with a big user base. In your case, as you are sharing numbers between two final users, it should be feasible, either with their same method or using another protocol like those published ones that are mentioned by Moxie.

Answer 4

How can we do this in a cryptographically secure way and respecting the users' privacy (i.e. without sharing the numbers in plain-text between them or with a server)?

tldr: You can't.

Hashing is great for certain uses, but this is probably not one of them. The reason is that an attacker would know that there are only 10 billion possibilities (for 10 digit phone numbers), and this makes it too easy to brute force any discovered hashes.

Instead, you could accomplish what you want if:

• one of the phones is willing to trust the other. One phone shares it's contact list with the other, and the other one does the compare. The second phone does not need to share its list with the first.
• you are willing to use a trusted mediator, i.e. a server. This is the best approach from the users point of view because neither party needs to share their contact list with the other. Both would share their lists with the mediator and it would report back with the matches, and promise not to save anything. Communication with each involved party would use standard public/private encryption key pairs, and no one's data would be at risk. Of course this assumes your users will trust you when you promise not to retain their contact lists. But if you can get your users to trust you enough to install your app in the first place, then you've already earned their trust.

Answer 5

Let's do some tests!

I started with a naive bash implementation, and calculated 10k numbers in 33 seconds:

#!/bin/bash

phone="2125551212"
salt="abcdefghijklmnopqrstuvwxyz"

shasalt() { echo "$* $phone $salt" | sha512sum; }

for f in {1..10000}
do
    shasalt $(shasalt $(shasalt)) >/dev/null # or write to a file...
    ((phone++))
done
echo $phone>&2

Then using a SHA512 C++ algorithm I found online I wrote some ugly sample C++ code. I generated hashes for an entire area code in 84 seconds, or about 160 seconds when I wrote them out to a file (generating a 1.4GiB rainbow table):

#include "sha512.hh"
#include <iostream>
#include <sstream>
#include <string.h>
using namespace std;

int main(int argc, const char* argv[])
{
  char salt[10] = "liviucmg";
  int x = 2120000000; // won't work above 2^31 i.e. past area code 213
  char y[21];
  snprintf(y, 21, "%010d,%s", x, salt);
  const int len = strnlen(y, 21);

  for (int i = 0; i < 10000000; i++, x++) {
      snprintf(y, 21, "%010d,%s", x, salt);
      //cout << y << "," << sw::sha512::calculate(y, len) << endl;
      string FIRST(sw::sha512::calculate(y, len));
      string FIRST_GO(FIRST + y);
      string SECOND(sw::sha512::calculate(&FIRST_GO, 1+FIRST_GO.length()));
      string SECOND_GO(SECOND + y);
      // uncomment this line to generate a hash table:
      //cout << y << "," << sw::sha512::calculate(&SECOND_GO, 1+SECOND_GO.length()) << endl;
  }
  return 0;
}

This was all on my 3-year-old laptop, which can be found online in a similar configuration for about $300. So for a pretty minimal expense an attacker could brute force any 10-digit number and unique salt combination in about a day (less if they only tested real area codes), or all the interesting numbers (those in the target's area code and physically adjacent area codes) in about 5 minutes. I didn't try to tune (or debug!) my test code, so I imagine those times could be cut in half by tuning the code. Running it on better hardware like a graphics card or FPGA would also cut down the time significantly: I would assume any number+salt could be brute-forced in about an hour or less by any competent attacker.

Answer 6

With Isemis mention of "probability of false positives" I thought about Zero-knowledge proof. This answer makes no claims to be secure as it was never reviewed, so others should review and comment it. I am no professional security expert either and I didn't have the time to make sure the low number of possible phone numbers might be a problem.

1. User A and User B connect to each other (directly or via server) and assign a random identifier (RI) to each contact their contacts and stores it in a list (LA and LB) together with the phonenumber padded with the nonce and after applying a Key derivation function. LA stays at A and LB stays at B.
2. User A proves one round of knowlege (see Zero-knowledge proof) for each of the numbers in list LA together with RI. User B has to find out by bruteforce to which of the contacts in LB each RI of A might fit. Each contact without fit is dropped out of LB. Possible fits are stored in the list for next round to improve bruteforce speed.
3. User B proves one round of knowlege for each of the numbers in list LB together with RI. User A has to find out by bruteforce to which of the contacts in LA each RI of B might fit. Each contact without fit is dropped out of LA. Possible fits are stored in the list for next round to improve bruteforce speed.
4. Repeat step 2 and 3 often enough to be statistically secure that each one has proven each of the numbers to the other user.
5. Optional: exchange the remainings in lists LA and LB in a secure way mentioned by others or via a secure channel between User A and User B to be sure the matching of RIs was correct.

With this algorithm the server or an observer never learns any relevant information about the contacts of A or B except their count and how many they have in common. User A and B only learn the same information as the server and the common contacts.

Since the first steps of the algorithm are exponential and ressource intensive one should include protection against DOS in implementations.

Answer 7

This method should have following properties:

• Probability of false positives can be made as small as desired
• Server learns only the (approximate) number of items on each person's phone book, but not numbers themselves and cannot brute-force them
• Client-side brute-force attacks are impossible, as server can enforce policies against them
• Phones do not learn the number of other phone's contacts

Suggested steps:

1. Phones A and B generate a shared secret S by using a Key-agreement protocol (authentication would be nice here to defend against MitM)
2. Bloom filter size and number of hashes can be hard-coded, protocol could enforce that at max 10.000 phone numbers are allowed / person (to midigate against hash collisions and abuse)
3. S is used to salt hashes of Bloom filter by some suitable method
4. A and B store their phone numbers to a Bloom filter and submit them to the server
5. Server confirms that estimated cardinality of filters isn't too high, nobody can claim to know all possible numbers
6. Server calculates the intersection of sets and sends the result to A and B
7. Now A and B know (fairly accurately) which numbers they have in common by checking which numbers went to intersected bins.

Actually the Bloom filter could be replaced by submitting plain SHA-256 hashes of numbers to the server and matching hashes can be submitted to clients. This simplifies the logic a lot and has lower chance for false positives.

Answer 8

Why hash them? Why not encrypt instead, and send them to your own server. That way neither client device has to have access to each other's contacts, and the server does most of the work.

This does introduce a single point of failure though, the server. If it was compromised, the attackers could potentially access all numbers. This could be controlled if nothing is really stored and everything is done in memory.