Assuming you want to try every phone number in the US, that would be almost 10 billion phone numbers. An above average user may have about 1,000 contacts. We wa

Assuming you want to try every phone number in the US, that would be almost 10 billion phone numbers. An above average user may have about 1,000 contacts. We want this to run on phones in a reasonable time for 1000 contacts, but be infeasible for 10 billion using any hardware the attacker uses. Bitcoin gives an idea of the relative speeds. I looked up the speeds of some Android bitcoin miners. All were on the order of 10Khash/s. The attacker is not constrained to use phones. Custom hardware for BitCoin mining can be on the order of 1Thash/s. This means that the custom hardware can reach 10^8 times faster, but the work to be done -- 10 billion hashes vs. 1000, is only 10^7 times as much. If the slow hashing algorithm used was anything like the one for BitCoins, a determined attacker could calculate the entire table faster than the person looking up their contacts. This is not the whole story -- this could be mitigated using better hashing algorithms that are designed to not scale well with better hardware, but the user will only wait maybe a minute, while an attacker could spend weeks.