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.

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.

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.

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.

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.

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.

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.