8

I just read a help page by a mail provider in which they state that all mobile phone numbers will be stored as a salted hash. This strikes me as interesting, since phone numbers don't contain a lot of entropy: about 31 bits by my calculations.

Depending on the hashing function, generating 231 hashes should be quite fast. Adaptive hash functions like bcrypt allow to increase the number of iterations. Cracking such a hash would take considerably longer, but using too many hashing iterations will slow down the application as a whole.

Long story short: is there such a thing as a lowest amount of entropy below which hashing becomes either pointless or harmful?

tarleb
  • 1,200
  • 9
  • 22

2 Answers2

3

For a login function, you should aim to get the hashing process to take around a second.

If you take this post as a guide, 1170ms requires around 8,192 iterations of bcrypt (cost of 13).

This means that your iterations add around 13 bits of effective entropy.

If you have only 31 bits of entropy in a secret, hashed value, then this bcrypt configuration would give you 44 bits of entropy.

As a guide, 47 bits of entropy would take 0.223 Hours maximum to crack per phone number (assuming at 350 billion guesses/Sec). Even if the attacker didn't have these type of resources and they guessed at 2 billion guesses/Sec using a single home PC, this would take 39 hours per phone number to crack.

So, to answer your question, it doesn't make sense when you either need to increase the hashing time to an unacceptable level (a cost of 16 to add 16 bits would be over 9 seconds, what you would describe as harmful to your application), or that the cracking time per secret is below your goal for the sensitivity of the information it is protecting and the resources of your perceived attacker.

If it is acceptable for each phone number to take 39 hours to crack by a casual attacker, then there's no problem with bcrypt at a cost of 13 . This is assuming they are using bcrypt with said cost and not simply storing SHA1(salt + number).

Community
  • 1
SilverlightFox
  • 33,408
  • 6
  • 67
  • 178
  • Does your answer presume that the attacker knows the hash is for a phone number? – Stone True Feb 04 '16 at 13:54
  • My answer presumes that the hash is over a value with 31 bits of entropy and the attacker knows this. In this case, they know the keyspace used is for phone numbers. – SilverlightFox Feb 04 '16 at 14:00
  • Great answer, thank you! Would using scrypt instead of bcrypt change anything here? – tarleb Feb 04 '16 at 14:13
  • 1
    @tarleb: Not really - it would still boil down to amount of time required to key-stretch the phone number into something that would be inefficient enough to crack by iterating the hash. – SilverlightFox Feb 04 '16 at 14:17
0

There isn't a magic line beyond which hashing is useless. Rather, as you reduce the entropy of the input, the output becomes easier to guess.

In this mail provider's case, they can add entropy using the salt. The larger the salt, the more entropy it will add.

ztk
  • 2,247
  • 13
  • 22
  • 2
    The salt doesn't add entropy because it is known (otherwise it's a pepper). Remember, if the hashes can be read then so can the salts. – SilverlightFox Feb 03 '16 at 23:19
  • Don't think the salt length helps against a brute force on a single password. – Neil Smithline Feb 03 '16 at 23:20
  • Salt does not add entropy, it just makes it harder to use an attack based on already-cracked hashes. – Alfred Armstrong Feb 04 '16 at 12:02
  • @SilverlightFox From a defender's perspective, the salt is known. If the attacker doesn't know if there is a salt, pepper, or any other data included in the hash, it is effectively entropy. Once a single password is cracked and the salt discovered, the remaining passwords lose the added entropy. – ztk Feb 04 '16 at 14:56
  • If the attacker can read the hashed value, you should assume that they already have access to the salt. It is foolish to base your security on the fact the salt is hidden, since the site itself will need it in order to determine that the provided phone number matches. – SilverlightFox Feb 04 '16 at 15:01