4 ms·

Hashing phone numbers doesn't do much since the space is so small.

by bdr 15y ago

jd 15y ago
Not that small. It's comparable to a weak password. There are about 5 billion active phone numbers in the world [1]. Besides, a small search space can only be searched quickly if it takes little time to a hash a phone number. Doing a few billion MD5-sums is not so difficult. If the hashes are computed with an expensive bcrypt then it's just a matter of increasing the number of iterations to make brute force attacks unfeasible. Edit: I realize that the hashes can't be salted (because different phones must produce the same hashes for the same phone numbers), so a rainbow table can be created for the entire database. [1] http://www.cbsnews.com/stories/2010/02/15/business/main6209772.shtml http://www.cbsnews.com/stories/2010/02/15/business/main62097...
- maxerickson 15y ago
  The client could do 'signed' hashes using the local phone number and the friend number (sending the server both the local:friend pair and the friend:local pair). That wouldn't really stop anybody from reversing the hashes, but it would make a global rainbow table useless.
  - TylerE 15y ago
    At that point it's also useless for matching.
    - maxerickson 15y ago
      It wouldn't be a strong signature, it would simply be the other half of the number pair. Numbers A and B both have easy access to A:B and B:A. The hashes for a given user could still be attacked using their phone number, but a global table wouldn't work.
      - jd 15y ago
        That's clever. You can then even improve the algorithm by only sending the hash of A:B for every phone number, where A < B (numerically). Then you don't have to worry about whether it's Friend:Local or Local:Friend.
  - gmac 15y ago
    It would make reversing the hashes substantially harder for any given hash function, though, right? Thanks very much for this idea. I'd thought about tracking social connections by sending hashes (on an explicit and opt-in basis) for my research app, Mappiness[1], but gave up the idea mainly because hashing seemed so hopelessly weak. But I think this + bcrypt might make it workable. 1. mappiness.org.uk
pork 15y ago
PBKDF2 with a high iteration count.
jrockway 15y ago
Key strengthening can help. If you do a bcrypt-style hash and set the cost so as to take one second on a modern CPU, brute-forcing each phone number would take about 57,000 days :) I would be more comfortable with this than giving them my entire address book, anyway.
- gizzlon 15y ago
  But how long would it take to bcrypt your entire contact-list on an IPhone? (no idea.. but might be too long..)

Hashing phone numbers doesn't do much since the space is so small.

by bdr 15y ago

Hashing phone numbers doesn't do much since the space is so small.

jd 15y ago

Not that small. It's comparable to a weak password. There are about 5 billion active phone numbers in the world [1]. Besides, a small search space can only be searched quickly if it takes little time to a hash a phone number. Doing a few billion MD5-sums is not so difficult. If the hashes are computed with an expensive bcrypt then it's just a matter of increasing the number of iterations to make brute force attacks unfeasible. Edit: I realize that the hashes can't be salted (because different phones must produce the same hashes for the same phone numbers), so a rainbow table can be created for the entire database. [1] http://www.cbsnews.com/stories/2010/02/15/business/main6209772.shtml http://www.cbsnews.com/stories/2010/02/15/business/main62097...

maxerickson 15y ago
The client could do 'signed' hashes using the local phone number and the friend number (sending the server both the local:friend pair and the friend:local pair). That wouldn't really stop anybody from reversing the hashes, but it would make a global rainbow table useless.
- TylerE 15y ago
  At that point it's also useless for matching.
  - maxerickson 15y ago
    It wouldn't be a strong signature, it would simply be the other half of the number pair. Numbers A and B both have easy access to A:B and B:A. The hashes for a given user could still be attacked using their phone number, but a global table wouldn't work.
    - jd 15y ago
      That's clever. You can then even improve the algorithm by only sending the hash of A:B for every phone number, where A < B (numerically). Then you don't have to worry about whether it's Friend:Local or Local:Friend.
- gmac 15y ago
  It would make reversing the hashes substantially harder for any given hash function, though, right? Thanks very much for this idea. I'd thought about tracking social connections by sending hashes (on an explicit and opt-in basis) for my research app, Mappiness[1], but gave up the idea mainly because hashing seemed so hopelessly weak. But I think this + bcrypt might make it workable. 1. mappiness.org.uk

pork 15y ago

PBKDF2 with a high iteration count.

jrockway 15y ago

Key strengthening can help. If you do a bcrypt-style hash and set the cost so as to take one second on a modern CPU, brute-forcing each phone number would take about 57,000 days :) I would be more comfortable with this than giving them my entire address book, anyway.

gizzlon 15y ago
But how long would it take to bcrypt your entire contact-list on an IPhone? (no idea.. but might be too long..)