There aren't great simple solutions to this issue AFAIK, but here's my take since I had a similar android app feature:
Want to find friends using contacts in phone:
Snapchat solution: pass number(s), return user info if number(s) in DB. +rate limit
Problem: rate limiting is not enough in this case.
Other solution:
Save contact lists of two users. If user requests friend look up, compare contact lists.
Basically return user info if the two numbers have each other in contact list, thus a verification they know each other.
Duping the snapchat system with the old method won't work, but drawbacks are that you have to store
a copy of user sensitive information, and if that gets out from your servers in some other hack, that would be
really bad, as bad if not worse than the first since it has more information, i.e. who knows who. Also less efficient,
space and time wise.
HN maintains that this is unethical because the users in your contact list have not consented to having their phone numbers shared with a social networking service.
You could use a key derivation function (scrypt or pbkdf2) to expand it out and make it quite difficult to even rainbow table it. You could also compound the effort by only storing a hash of the pairs (one hash or derived key of two phone numbers) with no associated metadata directly linked to it, only as an access gate. Collisions may occur but at least the positive results from a total search space would be significantly reduced.
I Am Not A Cryptographer, so I admit there is likely faulty reasoning in there somewhere, though.
The point is that the hash is effectively reversible at that scale. 10 numeric digits is 10 billion possibilities. It's actually far less than that because area codes don't span the entire 3-digit number range, and most area codes are not heavily populated. But even so, creating a lookup table by computing 10 billion hashes is today a comparatively easy task, even for expensive hash algorithms. It's a matter of only a few seconds to minutes work with relatively common hardware (high performance GPUs).
Comments
There aren't great simple solutions to this issue AFAIK, but here's my take since I had a similar android app feature:
Want to find friends using contacts in phone:
Snapchat solution: pass number(s), return user info if number(s) in DB. +rate limit
Problem: rate limiting is not enough in this case.
Other solution:
Save contact lists of two users. If user requests friend look up, compare contact lists.
Basically return user info if the two numbers have each other in contact list, thus a verification they know each other.
Duping the snapchat system with the old method won't work, but drawbacks are that you have to store a copy of user sensitive information, and if that gets out from your servers in some other hack, that would be really bad, as bad if not worse than the first since it has more information, i.e. who knows who. Also less efficient, space and time wise.
HN maintains that this is unethical because the users in your contact list have not consented to having their phone numbers shared with a social networking service.
Hash the numbers and compare hashes instead.
10 digits isn't long enough for that to work.
really? there are no hashing algorithms where 10 digits is enough?
10 numeric digits is only 10 billion, so, no, even if the algorithm took many hundreds of milliseconds.
You could use a key derivation function (scrypt or pbkdf2) to expand it out and make it quite difficult to even rainbow table it. You could also compound the effort by only storing a hash of the pairs (one hash or derived key of two phone numbers) with no associated metadata directly linked to it, only as an access gate. Collisions may occur but at least the positive results from a total search space would be significantly reduced.
I Am Not A Cryptographer, so I admit there is likely faulty reasoning in there somewhere, though.
https://whispersystems.org/blog/contact-discovery/
The point is that the hash is effectively reversible at that scale. 10 numeric digits is 10 billion possibilities. It's actually far less than that because area codes don't span the entire 3-digit number range, and most area codes are not heavily populated. But even so, creating a lookup table by computing 10 billion hashes is today a comparatively easy task, even for expensive hash algorithms. It's a matter of only a few seconds to minutes work with relatively common hardware (high performance GPUs).