# Private contact discovery - calculating probability of false positive [closed]

I'm working on contact discovery for a service and want to do it in a way that maintains privacy as much as possible, without using Signal's Private Contact Discovery Service (https://signal.org/blog/private-contact-discovery/), due to hardware/infrastructure limitations.

A user will grant access to their contacts and the mobile apps will generate a SHA-256 hash for each phone number and email address found. The first N characters of each hash will be sent to the server, where they will be compared with the hashes of the contact details of users who use the service.

For each partial match, the server will reply with the next M characters, returning N+M characters, where N+M is less than the length of a SHA-256 hash.

The mobile will then compare these more complete hashes with the ones it generated and mark any users with a match as being a user of the service.

How can I calculate the required values for N and M, so that the chance of a false positive (marking a user as a user of the service when they are not) is 1/1,000,000,000?

• How many unique people do you anticipate will use the service? Jun 27 '19 at 14:08

# The mathy bit

Let's play with the numbers, but correctly. SHA-256 outputs a 256-bit hash. An n-bit string can represent 2n possible values, so the odds of randomly guessing a given n-bit string are one in `2**n`. Therefore, to get under any probability P of colliding with any given hash, we need to get `ceil(log2(P))` and send at least that many bits. How many characters that is depends on how you represent the bits.

But notice my wording there: "any given other hash". That means you need, at minimum, 30 bits to ensure less than one-in-a-billion odds of collision with a single other hash. To ensure no collisions within your database at all, we need to account for the fact that we're not just comparing one hash against one other hash, but one hash against every other hash. So... do the same math I did, but instead of `ceil(log2(P))`, it's `ceil(log2(P * C))`, where C is the count of other hashes. It doesn't affect the value all that much, frankly; another few zeroes will only add a few more bits on to the end. Exponents scale really fast.

As a fun side note, even if you had 1 000 000 000 000 (1012, "one trillion" to Americans) contacts in your system, using the full 256-bit hash, the attacker would have to guess on average 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 (1065) hashes before getting a match.

# The frame-challenge bit

But I think you're going about this wrong. You say you want to maintain privacy by avoiding sending data. But... there's no way1 to extract data from a hash. Why not just have the client send all of their hashes to the server and the server sends back the ones that match? It'll be simpler to implement and leak insignificantly more information. Plus, that way you don't trust the client to be honest about which contacts they have; the server, which you control, is doing all the validation. In total, I think that'd actually leak less data to a malicious user than your current scheme.

Otherwise, consider this scheme:

1. Attacker produces a random prefix and sends it to the server, claiming it's a contact of his.
2. Server sends back all of the matching hashes.
3. Attacker sends back a confirmation for all of them.
4. Server now allows Attacker to claim everyone with any partial match as a contact.