3 ms·

> This would be a great problem to really solve well. If anyone develops any insight into a practical > privacy preserving mechanism for achieving this type of

> This would be a great problem to really solve well. If anyone develops any insight into a practical > privacy preserving mechanism for achieving this type of contact discovery, or notices something > we’ve missed, please let us know here, on twitter, or on our development mailing list. > – Moxie Marlinspike, 03 January 2014 This idea is probably full of holes, but there might be something useful here... Could you use layered system of bloom filters of shards of the hash(telno) space? (Figures are made up, but are roughly the right order of magnitude for millions of service users.) The filters could be made smaller, at the expense of having more of them. Layer 0 is a 1MB bloom filter with a 10% error rate, for all hashes of telnos Layer 1 are 16 1MB bloom filters with 1% error rates, sharded by the last nibble of the telno's hash Layer 2 are 256 1MB bloom filters with 0.1% error rates, sharded by the last byte of the telno's hash Layer 3 are 4096 1MB bloom filters with 0.01% error rates, sharded by the last 12 bits of the telno's hash ... A newly installed app uses the following algorithm to determine which of its contacts are already users of the service, without disclosing the phone's contact list to the service: The app makes a copy of the list of contacts' telephone numbers (E164 format). Request the L0 bloom filter. Using L0, 90% of non-member telnos are removed. Request only the required L1 shards, for the remaining telnos. Using the necessary L1 shards, more non-member telnos are removed (99% are gone now). Request only the required L2 shards, for the remaining telnos.. Using the necessary L2 shards, more non-member telnos are removed (99.9% are gone now). Repeat until required error rate is reached. i.e. The list only contains telnos of other service users. The benefit of this method is that bloom filter shards are only requested for numbers which are probably service users, thus disclosing much less information to the service provider. 90% of contacts' numbers will never be used to request a Layer 1 bloom filter, and those that are, will only disclose 4 bits of the hash to the service provider, narrowing them to 6% of the worlds telnos. 99% of contacts' numbers will never be used to request a Layer 2 bloom filter, and those that are, will only disclose 8 bits of the hash, narrowing them to 0.4% of the worlds telnos. 99.9% of contacts' numbers will never be used to request a Layer 3 bloom filter, and those that are, will only disclose 12 bits of the hash, narrowing them to 0.02% of the worlds telnos. (240 million telnos, if there are 10 billion telnos, as per the webpage.)

geocar 11y ago
The server can cheat. If I provide an L0 with numbers that begin with `1` and you don't download an L1, I learn you don't have any numbers that begin with `1`. Facebook says they get 5 new profiles every second[1], so it may be justifiable to query too often. [1]: https://zephoria.com/top-15-valuable-facebook-statistics/ https://zephoria.com/top-15-valuable-facebook-statistics/
- chrisdew 11y ago
  Good catch. This is a weakness, but it may not be relevant to WhisperSystems' use case. If you provide an L0 with numbers whose hashes end with '1' (hex), and I don't request L1/..1 shard, then you learn that I don't have any numbers whose hashes end with '1' (hex). I have 1024 contact telno hashes. Assuming I request only when the app is installed, and daily after that, it will take you: 16 days to learn which final nibbles my contact hashes have - probably all of them. 256 days to learn which final bytes my contact hashes have - probably all of them. 4096 days to learn which final 12 bits my contact hashes have - probably around a quarter of them. Three years in, you know which 900-1024 of the 4096 12 bit combos match the last twelve bits of one or more of the telno hashes. ~950 * 4096 = 15,200 days to learn the final two bytes of hashes, of which there will probably be ~1000 unique values. You now know 1000 buckets of 6 million numbers which contain one or more numbers from my contacts. If you update the app, over the air, to query every second, this would take just a few hours. But then, you could just update the app to grab all my contacts and send it instantly. The "server cheating" is a valid attack, but it may not be important, as there are easier attacks if we assume a malicious service. I assumed that WhisperSystems were trying to limit the information they had, as a good actor, rather than ensuring complete app safety vs a malicious service provider. i.e. their motivation is not to have the information to turn over, rather than to not be able to get it when compelled to modify their app. This is an important legal distinction in some jurisdictions.
  - cvwright 11y ago
    I think it's a bit worse than that. Suppose the server wants to learn whether you have a certain number in your contacts. Then they simply put that number into your lower-level Bloom filters for L0, L1, L2, ... even if that number is not really a member of the service. To prevent a final match, they only need to keep the target number out of the final BF. Then they passively watch which BF's you retrieve at L1, L2, ... etc. If you never retrieve the BF for Ln, despite the bits for the target number being present in the L(n-1) Bloom filter, then they know you don't have the target as a contact. Does that make sense? Of course, this attack and the previous one both go away if we assume the server is "honest but curious".

geocar 11y ago

The server can cheat. If I provide an L0 with numbers that begin with `1` and you don't download an L1, I learn you don't have any numbers that begin with `1`. Facebook says they get 5 new profiles every second[1], so it may be justifiable to query too often. [1]: https://zephoria.com/top-15-valuable-facebook-statistics/ https://zephoria.com/top-15-valuable-facebook-statistics/

chrisdew 11y ago
Good catch. This is a weakness, but it may not be relevant to WhisperSystems' use case. If you provide an L0 with numbers whose hashes end with '1' (hex), and I don't request L1/..1 shard, then you learn that I don't have any numbers whose hashes end with '1' (hex). I have 1024 contact telno hashes. Assuming I request only when the app is installed, and daily after that, it will take you: 16 days to learn which final nibbles my contact hashes have - probably all of them. 256 days to learn which final bytes my contact hashes have - probably all of them. 4096 days to learn which final 12 bits my contact hashes have - probably around a quarter of them. Three years in, you know which 900-1024 of the 4096 12 bit combos match the last twelve bits of one or more of the telno hashes. ~950 * 4096 = 15,200 days to learn the final two bytes of hashes, of which there will probably be ~1000 unique values. You now know 1000 buckets of 6 million numbers which contain one or more numbers from my contacts. If you update the app, over the air, to query every second, this would take just a few hours. But then, you could just update the app to grab all my contacts and send it instantly. The "server cheating" is a valid attack, but it may not be important, as there are easier attacks if we assume a malicious service. I assumed that WhisperSystems were trying to limit the information they had, as a good actor, rather than ensuring complete app safety vs a malicious service provider. i.e. their motivation is not to have the information to turn over, rather than to not be able to get it when compelled to modify their app. This is an important legal distinction in some jurisdictions.
- cvwright 11y ago
  I think it's a bit worse than that. Suppose the server wants to learn whether you have a certain number in your contacts. Then they simply put that number into your lower-level Bloom filters for L0, L1, L2, ... even if that number is not really a member of the service. To prevent a final match, they only need to keep the target number out of the final BF. Then they passively watch which BF's you retrieve at L1, L2, ... etc. If you never retrieve the BF for Ln, despite the bits for the target number being present in the L(n-1) Bloom filter, then they know you don't have the target as a contact. Does that make sense? Of course, this attack and the previous one both go away if we assume the server is "honest but curious".