That's just not true when the "original input" is constrained enough, like, for example, a phone number.
It really makes no difference what algorithm you use - if it's fast enough for you to hash all the phone numbers in my contact list on my phone, I can have a set of rainbow tables for every possible phone number. There's just not enough entropy in 10 digit numbers for that to be an effective solution.
Unless I'm missing something, either
1) you're using a "common salt" across all the hashes, which means I might need to generate my own rainbow tales with your common salt - but for only 10 digits worth of phone-number-space that's probably only a few bucks worth of EC2 time and S3 space to store it.
or 2) you're using a random salt for each phonenumber/hash, in which case you cant identify matching phone numbers.
It seems a little ridiculous to me that we don't completely blame Apple for leaving the door wide open for developers to do whatever the hell they wanted with your entire address book. Think about that for a moment. Any application you've ever downloaded on the app store could have archived your contacts.
Apple has already demonstrated they're capable of securing sensitive user details, yet the faint calls from informed users and ethical developers to expand that security to cover the address book has been conveniently ignored (to the benefit of "guilty" developers, questionable iPhone UX, and of course Apple) for years.
Not cool Apple.
The Watergate scandal was called that, because the hotel was called the Watergate.
Using "gate" as a suffix for any scandal just makes you look stupid.
