Are SHA-256 hashes of user emails guaranteed to be unique?

Question

I'm working on a website that will require users to insert a valid email address, which will work as their unique user id. This email will not be used for communicating with the user, it is only ever used to verify that a particular user id exists.

I've read a lot about storing emails to a database and about how they should be hashed to improve security and my plan is to use SHA-256 with pepper to store all emails. In pseudo code, something like: sha256( "example@email.com", "peppermintTea" ) => "62d989abbca458c2616acddfbf45a364037a70ebd941568c9ee8f5d923e38c4f"

While reading up on SHA-256 and hashing emails, I've run into several different posts discussing the possibility of hash collisions. Some posters go to ridiculous lengths of saying "it's more probably to be hit by an asteroid twice than it is for two files to have the same hash", but what about email addresses? Email addresses can be relatively short and I haven't been able to find any answer on whether or not it is possible for two hashed emails to return the same hash?

For argument sake, if there would be 5 billion email addresses in the world, is there a non-zero chance that two of these emails would return the same hash? If there is, then how should I prepare for these possible collisions?

Answer 1

Collisions on SHA256 are statistically improbable. The chances of two emails colliding are so small that you can safely ignore collisions. If you don't want to ignore, you can just use two different hashes at the same time: SHA256 and MD5, for example. The situation is "turtles all way down": chances of two emails colliding both on SHA256 and MD5 are small, but not zero. So you use another hash: SHA3. And the chances of colliding SHA256, MD5 and SHA3 are even smaller, but not zero...

Don't overdo the collision processing, you may end up spending a lot of time on a piece of code that is almost certain to never ever be used at all. This should be on the bottom of your TODO list, and you should spend little time on it.

Spend more time securing your application against real world issues, like Cross Site Scripting, SQL Injection, Authentication Bypass, things like that. SHA256 collision prevention on email is like protecting your basement against a meteor hit: it will cost you time and money, the probability is too small, and you will divert resources that could be used protecting it against theft, flood, fire, things that really happen.

Answer 2

Hashes are not unique. This is easy to prove: a SHA256 hash is only 256 bits long, so if you hash all the possible inputs that are 264 bits long, some of them will have to have the same hash because there aren't enough possible hashes for them to all be different.

However, for all practical purposes they are unique. You can't hash all possible 264-bit inputs because it takes way too long. And we're not talking just "it's unlikely" - we're talking that with the fastest theoretically possible computer, you'd have to use up the entire energy of several billion stars and you still probably wouldn't find the same hash twice. The probability is so dang low that it may as well be impossible for all practical purposes. Believe me, if someone does manage to find a SHA256 hash collision, your website will be so far down the priority list of things they could attack.

If billions of stars isn't good enough for you (you need your site to remain secure even after humanity advances to a Kardashev type 3 civilization?), use SHA512 instead and you would need to use the entire energy of gazillions of universes.

But unfortunately the probability isn't zero which is why you get all these Internet arguments. It can't possibly be 0.00%, no matter how good your hash algorithm is, so how many zeroes do you have to have before the inevitable 1, before it's okay to pretend it's 0.00%?

---

Now, what is practically possible is that someone finds a bug in SHA256 and they find a way to reverse it - or at least, to change the input without changing the hash. That's quite possible and it's happened to other hash functions before, including MD5 and SHA-1.

Still, what's the impact if that happens? Someone can sign up with an email and block another email from signing up? Then you change your hash algorithm to SHA-3. You keep the SHA-2 hashes from before that date, but you change the new ones to SHA-3. You hash the email with both SHA-2 and SHA-3 and if either one is found then the user can't sign up. No real problem.

Answer 3

Let's look at it this way: for a hash of that length, if anyone ever were able to find two different messages that came to the same hash, it would be a probable indication the hash algorithm is broken, because that would be a much more likely explanation than stumbling upon a collision by accident or by brute force.

You can and should treat all such hashes as if they are unique.

Of course, collisions are possible. It's easy to say through reasoning that two messages may generate the same hash - this is necessarily the case. But it is necessarily practically impossible to show it by producing two such messages. We are in the domain of things where this would never happen in practice even if all the computers in the world tried doing this for a long time - unless a flaw in the hashing algorithm is discovered.

In terms of "how unique" you need before you can stop worrying about collisions, consider that UUIDv4 identifiers, which have only around 122 bits of randomness, are generally considered to be "globally" unique - enough not to have to code around the possibility of collisions, in most applications. And here we are talking about not 122 but 256 bits. If 122 bits can uniquely represent all atoms in the human body, 256 bits can uniquely represent all atoms in the galaxy.

Answer 4

The problem that you describe is known as the Birthday Attack Problem.

It is often posed by asking - if there are 23 people in a room, then what is the probability that any two of them have the same birthday? As you can see in the page linked above, the math is based on the assumption that each of the N samples are distributed uniformly and at random over some space H. In the example above, N is 23 for the number of people in the room, and H is 365 for the number of days in a year. It turns out that in this case, there is a 50% chance that two of the 23 people have the same birthday.

Being that the hashed email addresses in your case would be distributed uniformly and at random over the space of the SHA256 hash function, the same math can be applied to your problem. So, in your case H is 2^256 and N is 5 billion. If you apply the math using the above inputs, you'll find that the probability of a collision (i.e. any two different user email addresses resulting the same SHA256 hash) is approximately 1 in 10^58.

So, while the SHA256 hashes of any two different user email addresses are not guaranteed to be unique - the likelihood of this happening is incredibly small. 10^58 is an astronomically large number. To put this in perspective, the number of water molecules in the earth's oceans is 'only' ~10^46. So, the chance of a collision in your case would be like tagging a molecule of water, throwing it in the ocean, then later randomly choosing a molecule of water from the ocean, and it being the same one that you tagged - then, repeating this over a trillion times consecutively, and then some.

I agree with @ThoriumBR and @CBHacking - you don't need to worry about this. Your valuable time as a coder would be much better applied to other more productive things - even if it only takes you a few minutes to implement this check.

Answer 5

TLDR

1. No, there is no guarantee that hashes will be unique.
2. Despite hashing, emails can easily be restored, if contained in leaked databases.

Details

In a big set of values collisions are unavoidable because of pigeonhole principle.

Despite SHA-256 was designed in such way that the probability of collisions is very low, there is no guarantee that in any small set of email addresses there will be no collisions.

How can you guarantee the uniqueness? Ask users to pick up some login name and allow it only if it is not yet used, or generate a login name for them.

I've read a lot about storing emails to a database and about how they should be hashed to improve security

This will not necessarily provide what you expect. Storing only hash of (user + password) will make it hard to analyze the cases when user cannot login. You will not know if the user entered a wrong password or a wrong email or both. You will not be able to check if particular user exists in your database at all. That's why you will need to store email without password.

Suppose you store a hash of the email without password. You can also use some salt, but it needs be global, because again you don't have further info like user ID, and cannot use separate salt for each user.

The attacker can take a relatively big spam database with emails and compute your hash function for every email in this database. Since SHA-256 is very quick, some GPUs can compute more than 10 000 000 hashes per second. Suppose this database contains 10 email addresses for every person in the world. Computing hashes for all of them will take just about 8 000 seconds, which is just about 2 hours. If the email is known in the spam database, the attacker will know that this user is registered at your web site. Thus, if you want to use emails and want to hash them, you may need a slower hash algorithm, for instance, PBKDF2 or Argon2, depending on what is available on your platform.

What can you do instead? If your goal is to prevent correlation of user accounts with leaked data from other web sites, you can generate a unique login name for every user during registration. For 8 billions users (current world population) just 7 English letters will be sufficient.