Hacker News Reader

Comment by marginalia_nu | Hacker News Reader

> we need to keep a copy in our block list.

If only there was a function that was deterministic, but somehow incredibly difficult to invert, that would sure make a hash of this requirement to store things you're required not to store.

View on HN

Sure, there are hashing functions, but with a search space that is as small as a 10 digit phone number it is easy to create rainbow tables that covers them all.

Signal has spent some time thinking about this problem, see https://signal.org/blog/private-contact-discovery/

Multiple hashing rounds or bcrypt would likely be a fine solution for this

Pray tell the details.

Yeah I initially thought as GP, perhaps some salting, hence my comment above. But the only salt worth its salt (sorry, had to) would be the number itself. Otherwise, you’d need a database associating the number with its salt. And if you use the number itself as the salt, then rainbow tables it is.

Even if you tweak your hashing algorithm to take 1 second on a fast CPU, you get 31 years of CPU time to search the entire space. That's simply not enough! And going beyond 1 second is probably also not practical.

Apple does this. It is even more frustrating! If you ever had two Apple accounts, and close one, you can _never_ add the e-mail from the deleted account as an alias to the remaining account.

You can imagine the headaches this causes.

I ran into this myself. It's even more frustrating that they don't warn you about it upfront when closing the account (at least they didn't back when I ran into this).

I was hoping to start over with a fresh account and instead ended up having to create a new email alias in Outlook to use to create a new Apple account - luckily I used an alias the first time as well so the impact wasn't as bad.

Apple support suggested I "simply change my e-mail address". Sure! I will just contact everyone I have ever known, and ask them to update it. Oh and every website I have ever created an account on! sigh

Hash functions are only incredibly difficult to invert when the input domain is large, which is not the case with phone numbers. Even if you use a password hashing function that takes 1s to run (and if you need to frequently compare the hash, that's on the high side), you could practically invert the hash of an individual phone number. For this use case making it relatively expensive to obtain a single number in the clear would probably be good enough though.

Salting exists for this reason.

even with salting it'd be trivial

And how exactly would salting fit into matching plaintext phone numbers against a large blacklist?

How would that work if someone re-uploads your phone number? If it's not hashed with the same salt, then that wouldn't be blocked?

Well, quite :) I don't see how the thing is supposed to work, given that people get other people's phone numbers when they change number. The only way to actually fix it is to stop uploading a user's contacts to their servers in the first place.

Spot on, “need a copy for blocking purposes” just preys on public computer illiteracy.[1]

In the devil’s defense, the explanation was probably written by a computer illiterate person.

Then again, there may very well have been this one meeting, where a dev went “hold on, I got an idea to avoid storing the number!”, before being politely but briskly advised to stfu. Not impossible.

[1] littera : illiteracy :: numera : innumeracy :: digita : ildigitacy? Iddigitacy?

Go and calculate how much time would it take to hash every 9-11 digit number...

Salts are a thing for this very reason. And some hashes like scrypt can be parametrized to take time no matter what.

There is no rainbow table entry for 0123456789+=i=i_fy82dnuf720g%2+70)(k$0@*qsijyn9&19n@1r0-l4ee) with 10000 scrypt rounds.

We are not in 2005 anymore, and we have better tools than md5, or even sha1 to do the job.

Salting won't work in this particular case. You need to match plaintext against a blacklist. Salt per entry is too expensive, salt per blacklist is exploitable.

Were it be a small company, we would try sharding salts + increasing the number of rounds of scrypt or some mix with a bloom filter.

However, this is facebook. It's not too expensive for them.

how does a salt help?

a salt for a password is when we know the username and the salt so can combine the salt and provided password to compare against the generated hash value.

in this case all we know is the phone number, how does a salt help us look up a given phone number in a set of salted / hashes if we dont know what salt to combine it with?

You shard the number into groups with a salt for each, until you reach a number of combinations that is computable for FB size on a check request, but way too long pre-generate. You can combine it with some bloom like filter to increase efficiency.

Can you more explain that as an example. I understand the words, but doesn't extend to me seeing the design of it.

you are forgetting that this is not just a technical problem.

For GDPR you need to legally prove that you have taken reasonable steps to remove and keep out of your system, the data the user has requested. This means that you need to be able to legally prove you've got a system in place.

Keeping a hash is fine technically, but its a pain in the dick to defend in court, especially as its really simple to shower a jury/judge with FUD to make it look like its not a reasonable step.

Reply on news.ycombinator.com