Will SHA1 of Email Addresses Always be Unique?

Question

We want to store data about a person without storing their email address, but we want to latter connect that person with their data upon them supplying their email address.

Storing a SHA1 of their (lowercased) email address will accomplish that, but is it possible that two different email addresses would result in the same SHA1? If so, what's the probability?

Cesl

Answer 1

• The chance of this happening by accident is negligible. It's approximately n²/2¹⁵⁹ when you have n email addresses. For example if you have a billion emails, the chance is 2^-99 or 10^-30.

  So assuming that it doesn't happen by accident is a pretty safe bet.

• Somebody will be able to craft two email addresses that have the same hash, but he won't be able to craft an email that matches the hash of another person that's not identical to that person's email.

  Or as a cryptographer would say, collision attacks against SHA-1 are feasible, but pre-images are not.

  But collision attacks seem irrelevant for your application. Since I don't see how an attacker would take advantage of owning two emails with a matching hash.

• Guessing the email and confirming it against a hash is possible. The main problem here is that SHA-1 is fast.

  I ran such an attack against the MD5 gravatar hashes stackoverflow publishes, and recovered around 28%. Somebody who puts in more effort will probably be able to recover a bit more.

---

My recommendation is to use an expensive hashing construction such as PBKDF-2-HMAC-SHA-2 with a per-application salt.

Answer 2

If you take n addresses, probability of a collision (two distinct addresses hashing to the same value) is close to n²*2^-159 (for practical values of n). In practice, you can totally ignore the risk of a collision (your risk of being munched to death by a rabid bear is way higher than that).

Note though that:

• SHA-1 has some cryptographic weaknesses, which make it somewhat easier for an ill-intentioned individual to create on purpose two distinct email addresses which will hash to the same value. This is still a theoretical weakness, because while the described method is faster than the theoretical cost of 2⁸⁰, it still entails the substantial number of 2⁶¹ hash function evaluations. Also, it might be difficult to retrofit the computed collision into the format of email addresses. Anyway, you might be a bit more cautious to use SHA-256 instead of SHA-1 (and it will look better if you are audited).

• Email addresses can be case-insensitive. In particular, the domain name (after the '@') is, by statute, case insensitive, so example.com, Example.COM and exAmPLE.cOM are all equivalent. For what appears before the '@' sign, this is site-dependent. You may want to do some normalization before hashing, and it is possible that there is no good solution which will work for all existing email addresses.

Edit: although this answers your exact question, you would be well advised to look at @CodeInChaos' answer, which tries to see a bit further in your problem: if it is possible to supply an email address and verify that it matches a stored hash, then it makes it possible to "try" potential email addresses against the hash value, and it tends to work. This is a variant of the dictionary attack and it may or may not be a big issue with your security model.

Answer 3

The term for this is (SHA1) collision and there are numerous resources on the internet about it.

The number of email addresses and the birthday problem will increase the chances of a collision but for this practical use, the chances are you will never have a collision.

You should expect different problems like email addresses with dots. Gmail will ignore any dot in the email address so first.name.lastname@gmail.com is the same as firstnamelastname@gmail.com but the hash will be different.