6

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( "[email protected]", "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?

6
  • Even 5 billion emails is too little to a collision to be likely. The hash space of SHA256 is 2²⁵⁶, and that's larger than the number of atoms on the Universe.
    – ThoriumBR
    Dec 27, 2022 at 19:10
  • @ThoriumBR Are you saying it's literally impossible for there to be a collision if 5 billion emails are hashed using SHA-256? Or is "to be likely" referring to a tiny possibility that there could be 2 identical hashes among the 5 billion emails?
    – Tommy
    Dec 27, 2022 at 19:29
  • 1
    @ThoriumBR: Consider Email addresses consisting of English letters and digits only, ignore "@", "." and TLD. For the strings of length 50 there are 36^50 = 2^258 possible values. This is more than the number of hashes. Thus there will be collisions. The probability of collisions is low. But there is no guarantee that there will be no collisions even if the set of values is small.
    – mentallurg
    Dec 27, 2022 at 19:34
  • 1
    Yes, there can be collisions, but the probability is too small to you to have to care about. So small it's even hard to quantify.
    – ThoriumBR
    Dec 27, 2022 at 19:58
  • By choosing a better hashing algorithm you might need more computing power and by processing too long e-mail addresses (if the backend and frontend don't minify the length) could potentially cause DoS. Also, it would be nice to quantify the probability, even though it's let's say 0.001% or something like that... Dec 27, 2022 at 20:09

5 Answers 5

7

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.

5

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.

5
  • This answer is the only one, besides mine, that believes that the process should be deterministic and suggests handling in case of hash collisions. There can be different ways to handle it (change hash function as you suggest, or change login name as I suggested), but it is good that your view of the process is deterministic.
    – mentallurg
    Jan 3, 2023 at 19:21
  • @mentallurg what does determinism have to do with it? all hash functions are deterministic. Nondeterministic hash functions are totally useless Jan 3, 2023 at 20:15
  • The others refuse to define what their process should do in case of hash collision. Thus their process is non-deterministic. Whereas your description contains handling of the case when hash collision happens, no matter how small the probability is. If you roll out such process, it is very important that it is deterministic. For instance, a help desk should know what to do in such case, even in reality it may never happen. The others just ignore that. You have defined it, and I find it good.
    – mentallurg
    Jan 3, 2023 at 20:25
  • @mentallurg there is no detection of hash collisions by chance. But when someone figures out a way to make them on purpose, it will be widespread news (just like it was for SHA-1) and then you will update to SHA-3. Jan 5, 2023 at 0:48
  • Sure. I mean that you defined the process completely: "Still, what's the impact if that happens? ... Then you change ..." You have defined a deterministic process. With a high probability this will never happen. But if happened, you defined what can be done. Whereas the other answers just refuse to define what should be done in case collision happened.
    – mentallurg
    Jan 5, 2023 at 0:53
2

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.

3
  • 1
    " to other more productive things" - This a bad advice. This should be addressed. As I wrote above, in this particular case it is a not big deal, because in case of collision user Email will be just not accepted. Despite use may be not happy about that, there will be no any serious problem for user. But it is wrong to say that this should be ignored in any other use cases.
    – mentallurg
    Jan 1, 2023 at 17:18
  • 2
    mentallurg I don't think you appreciate exactly the magnitude of a discovery that someone finding a collision in sha256 would be. Jan 3, 2023 at 6:02
  • 2
    He should be doing more productive things, like taking care of XSS, unsanitized input processing, file inclusion, direct object references, things that currently exist and pose a real-world risk. Spending a lot of time on SHA256 collisions and someone using <script src='xss.me/abc.js'></script> as email is a real fail.
    – ThoriumBR
    Jan 3, 2023 at 19:30
2

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.

-1

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.

11
  • 4
    This is technically correct but incredibly disingenuous; the odds of a collision are so low that English doesn't really have a word for it; "astronomically low" would be too weak. I would bet very good money that there are no SHA2-256 collisions at all in all the unique email addresses that have ever been used in the world.
    – CBHacking
    Dec 28, 2022 at 8:50
  • 4
    @mentallurg You don't seem to understand just how big 2^256 is. If anyone ever finds a collision, then SHA-256 is seriously broken since one of the basic properties of a cryptographic hash function is that finding a collision should be practically impossible. There are plenty of applications where security depends on the impossibility of finding collisions. If you're worried about probabilities that small, you should also be worried about someone guessing all of your passwords and encryption keys, or getting struck by lightning, etc.
    – eesiraed
    Jan 2, 2023 at 4:09
  • 3
    @mentallurg Count to 2^128 and then get back to us. Jan 3, 2023 at 5:15
  • 2
    @mentallurg 1) So what? The fact that the number of collisions is infinite has nothing to do with the probability of a collision. 2) I understand the birthday paradox. The probability is still so ridiculously small that there is no point in worrying about collisions happening by random chance. 3) Let's say we have access to some magical supercomputer that can compute 4*10^26 SHA-256 hashes per second (that's more than a million times the total hash rate of the Bitcoin network). Even if we run this supercomputer for one thousand years, the probability of a collision is still less than 0.001.
    – eesiraed
    Jan 3, 2023 at 5:18
  • 3
    If you're worried about SHA-256 collisions happening by random chance, maybe you should live in an underground bunker because a plane might just happen to crash into your house. Unlike a SHA-256 collision, this has actually happened before, and the price is your life.
    – eesiraed
    Jan 3, 2023 at 5:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .