# Find matching phone numbers without actually knowing them

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`?

• "Is this a flawed approach, prone to rainbow-tables/brute-force attacks"... In my country, a mobile phone number is made of 10 digits. Therefore, it would be pretty easy to build a list of all the 10^10 possible combinations. In fact, since 10^10<28^8, it would be easier than to build a list of all possible 8-bit passwords with 6 letters and 2 digits. – A. Darwin May 5 '16 at 17:35
• @A.Darwin I think you are right. Let's say we make a hash take 0.001 seconds to compute. For a phone list of 1000 contacts, it would take 1 second which is acceptable. But for brute-forcing 10^10 numbers it would only take 115 days, possibly much less on a powerful CPU. Maybe this approach can work for emails, though. – liviucmg May 5 '16 at 18:48
• @drewbenn - if you made your comments an answer, I'd upvote it – Neil Smithline May 5 '16 at 21:04
• I'm pretty sure what you are looking for is called "private information retrieval" (PIR) which is feasible for small data- and userbases but gets too hard to be done for larger ones. – SEJPM May 6 '16 at 7:51
• You mentioned via server. Could you just have a server do the comparison? – paparazzo May 6 '16 at 11:57

## 8 Answers

`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 1010 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 108 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 108 times 100 milliseconds, i.e. than 107 seconds. This is down to 104 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 108 reasonable numbers takes about 108 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 108 numbers will yield UserA's contacts mingled with 104 other numbers. Determinism on UserA's input means that two successive checks on these 104 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, N2).

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)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 108 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)1000, 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.

• Are you proposing a unique salt per phone number? If not, how is what you said different from what the OP proposes? – Neil Smithline May 5 '16 at 19:06
• I don't believe that you can crank the complexity high enough to provide any real protection. As the client is a relatively weak device (a mobile), any complexity high enough to stop an attacker using a server to crack the hashes will be way too slow for the mobile. – Neil Smithline May 5 '16 at 19:31
• Hi @NeilSmithline , since the common `bcrypt` representation already contains the salt as well as the complexity factor, and it has to be sent, it's no storage cost and very little CPU cost to randomly generate a new salt for each new number. Otherwise yes, what I'm proposing is exactly what the OP was already concluding by himself... I'm just sort of voting between the options he presented. (update) thanks for your second insight too, you're right that it is a concern that needs addressing. I'll update my answer. – LSerni May 5 '16 at 19:37
• Separate salts greatly increases the complexity of doing comparison. Let's assume the received list has N phone numbers and my list has M phone numbers. I would need to run bcrypt on each of my M phone numbers using each of the N salts from the received list. That's M*N calls to bcrypt. That seems too costly. It was to avoid this computational explosion that led the OP to use only a single hash. – Neil Smithline May 5 '16 at 19:42
• I think it may be the case that there's not a hash-based solution. @Ángel's answer points to a solution by Wisper Systems, but it is non-trivial to understand, not to mention implement. You would really need a team of cryptographic developers to pull something like that together and have confidence that it is actually secure. – Neil Smithline May 5 '16 at 21:12

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.

• This doesn't answer the question but it's an excellent point. – TTT May 5 '16 at 22:31
• @TTT it does not fully answer the question because there are multiple points to the question. It does address the main issue: `Is this a flawed approach?` A: yes. drewbenn even goes further and points a new facet where it fails. +1'd - - - - P.S.: It is very common on SE sites once an authoritative user has made his answer to place these and to add to @ userAbove's answer... And to me it is very constructive. – Mindwin May 6 '16 at 13:47
• @Mindwin - I completely agree, which is why it earned my vote as well. – TTT May 6 '16 at 14:10
• +1 This was pretty much my exact thought when I read the question. Although.... it could just as easily be "her ex" – Justin Ohms May 6 '16 at 17:50

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.

• That's a very cool solution. – Neil Smithline May 5 '16 at 19:50
• There was another implementation called LOAF, but its site is currently down (loaf.cantbedone.org) so I fear it may be abandonware. It might be possible to find descriptions of it, though. It was by Maciej Ceglowski, Joshua Schachter, and Peter Gadjokov. Maciej has a semi-active blog so he can probably be questioned for details if required ;-) – Steve Jessop May 6 '16 at 9:51
• +1 Bllom filter was also whyt came to my mind as possible improvement. As in: Both ends send bloom filters (based on individual hash function) matching their contacts and with a false positives rate witin predetermined bounds, after that they exchange the underlying hash functions, and finally they may perform (encrypted) Q&A sessions where one ends asks about a specific number and the other replies yes or no, but refuses to answer if the queried number does not match the opponents Bloom filter – Hagen von Eitzen May 7 '16 at 10:17

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.
• Note that the two parties don't necessarily need to trust the mediator. Let both parties together pick a One Time Pad (each picks a random sequence, XOR'ed together), and then both XOR each number with this OTP. (Remember, it's an OTP - it must be long enough for all numbers!) The mediator receives two lists, and returns the intersection. (Bytes 17-27 match, bytes 36-46 match etc). The mediator provably cannot know what those bytes mean, lacking the OTP. – MSalters May 6 '16 at 8:37
• @MSalters For this to work you would need the same number beeing stored at the same position. So there must be an algorithm which says which phonenumber is stored at which position. If this algorithm is known to server, the server might get to know a match at bytes 17-27 means phonenumber +123456789. – H. Idden May 6 '16 at 10:14
• @HIdden no, the numbers are not concatenated and then crypted, but crypted before concatenation. In fact it isn't concatenation into a larger opaque stream at all, the boundaries are told to the server, so it can evaluate all pairwise comparisons. – Ben Voigt May 6 '16 at 16:26
• @MSalters, my point was that since the keys are XOR'ed together, each can figure out the other's key, so why bother having separate keys when they know each other's anyway? – TTT May 6 '16 at 19:33
• @MSalters - regarding your second point, you claim there is no reuse. So now you're saying there is a different OTP per number? How could that possibly work? (Perhaps we should start a chat so you can provide an example. I'm not seeing it...) – TTT May 6 '16 at 19:46

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.

• Fun fact: Brazil international phone numbers can begin with `555`. (country code 55, area code starting with a 5). So a 12 or 13 digit phone number beginning with 555 can be real. – Mindwin May 6 '16 at 17:46

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.

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.

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.