27
$\begingroup$

This question already has an answer here:

I'm curious, how can for example SHA-256 be unique if there are only a limited number of them?!

For clarification:
how many MD5 hashes are there?
$16^{32}$ MD5 hashes can be produced. $16^{64}$ SHA-256 hashes can be produced.
while there are $16^{128}$ just SHA-512 hashes, let alone long texts.

For more clarification:
assume we want MD5 of all the SHA-256 hashes.
we can have $16^{32}$ number of MD5 hashes, while there are $16^{64}$ SHA-256 hashes.
we will have 3.4*$10^{38}$ duplicate MD5 hashes!

And so is for SHA-256 hash, if we calculate SHA-256 of all the SHA-512 hashes, we will have 1.15*$10^{77}$ duplicate SHA-256 hashes!

Edit: This is not limited to a particular hash like SHA-256.

$\endgroup$

marked as duplicate by e-sushi Apr 12 '18 at 2:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 22
    $\begingroup$ Due to the pigeonhole principle, you will never be able to avoid collisions when you are accepting input larger than the output. Hashes are not unique, they are just designed to make it difficult to find collisions (so while yes, there are duplicates, you aren't going to find any, at least not for SHA-2). $\endgroup$ – forest Apr 8 '18 at 22:30
  • 26
    $\begingroup$ What makes you think hashes are unique? In fact, them being not unique is pretty much part of the definition of "hash function", which is a function that maps a large, potentially infinite input space into a smaller, fixed output space. $\endgroup$ – Jörg W Mittag Apr 9 '18 at 7:45
  • 1
    $\begingroup$ Duplicate of SHA-256 “almost unique”? – The fact the accepted answer here handles exactly the same things (SHA-256, uniqueness, etc.) as the accepted answer of the other Q&A underlines this one is a duplicate, so I’m putting this Q&A on hold accordingly. $\endgroup$ – e-sushi Apr 9 '18 at 16:46
  • $\begingroup$ Hash is not supposed to be unique. When I change a configuration file in a ~1 GB image, sha1 and compressed size of it does not change. However, if I wanted to change a smaller image in a specific way to comply with the config file format that will work and produce the same hash, there would not be a mathematically provable, generic and fast (as in faster than it should be considering the number of bits in the hash) way to do it. That is the purpose of the cryptographically secure hash functions. It is where MD5 fails and most of SHA family prevails. $\endgroup$ – Etherealone Apr 10 '18 at 18:26
49
$\begingroup$

how can for example SHA-256 be unique if there is only a limited number of them?!

Where your issue occurs is that they're not unique. It's just very improbable that they'll reoccur. Unique in this context is not a mathematical definition, it's a humanist one.

In terms of human numbers, $ 2^{256} $ = 115792089237316195423570985008687907853269984665640564039457584007913129639936 which is 0.1% of the number of atoms in the visible universe. So that's a lot of them.

There's a better answer @ Why haven't any SHA-256 collisions been found yet?, but you should get the gist from the lengthy 116 quattuorvigintillion number.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Apr 12 '18 at 3:16
28
$\begingroup$

You are right, hashes won't be all unique as you already have shown. The important part are practical collisions - how many SHA-512 hashes can the whole earth generate in its lifetime? Definitely much less than $2^{512}$, it's even less than $2^{128}$.

Let's guess unrealistically high and say we generate these $2^{128}$ hashes from perfectly random input, no two inputs the same. How high is the probability that any two of them will be the same? It is not guaranteed that they will all be different, but the chance for a collision will be so extremely small that you can ignore it. It's so small, even winning the lottery, five times in a row, has a higher chance. That's why we say that the hashes are unique (as long as the hash function is secure) - there will never be a collision in the lifetime of the Earth because it's so unlikely.

$\endgroup$
  • 1
    $\begingroup$ With $2^{128}$ hashes produced, the birthday paradox would kick in and produce a collision with a 50% chance, if the hashes had size 256 instead of 512 bits. So the risk is really very low: It's like picking the one collision among truncated-to-256 parts of the hashes, and then by pure chance all remaining 256 bits have to match. So it's literally like tossing 256 heads with a fair coin in a row on first attempt $\endgroup$ – Hagen von Eitzen Apr 11 '18 at 6:33
8
$\begingroup$

A 256-bit hash has about one million times as many numbers as the Milky Way has atoms (give or take a few hundred atoms...). So that's not just a limited number, it's a pretty big limited number.

What are your chances of picking any two atoms in the Milky Way (not just our solar system) and accidentially getting the same one?

So it is indeed technically wrong to say they're unique, but it is a reasonable, practical assumption. You will not live to prove the opposite.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Apr 12 '18 at 3:17
3
$\begingroup$

Correct, although we say hash functions produce "unique" outputs that will, no matter how hard you try, never be replicable with different inputs, it is theoretically possible to create a hash-collision, where two different inputs give a single matching output. For example string:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

And string:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

will produce an identical MD5 hash even though there are several digits that are different. This is particularly significant due to the use of MD5 for verifying data-integrity, for both intentional and unintentional corruption since it's common that a few bits of data may have been corrupted.

When MD5 was first published in 1992, it was considered to produce "unique" outputs, but in that time, computers had significantly less processing power and it was extremely inefficient to search for MD5 hash-collisions. In 2018, it's now possible to find an MD5 collision within seconds.

In terms of SHA-256 and the rest of the SHA-2 family, they're are currently no known collisions, (however there are some for SHA1, more information here: https://shattered.it/) but since SHA hashes all have a limited output length, (256 bits, 512 bits) the Pigeonhole Principle (https://en.wikipedia.org/wiki/Pigeonhole_principle) states that if the input is greater than that of the predefined output length, for example a 300 bit input hashed using SHA-256, there must be another input that is 256 bits or less that gives the same output as the hash of the 300 bit string. No matter how hard you try, you won't be able fit more data into your hash than your hash will spit out.

Back to your original question, since almost all hash algorithms produce hashes of predefined lengths, independent of input size, there will always be the possibility of having two different inputs having the same hash as long as your hash function permits inputs of any size (which is true for almost all hash functions).

For the impatient, the answer to

I'm curious, how can for example SHA-256 be unique if there are only a limited number of them?!

Is: They can't. There are a limited number of outputs and the rules of math say that we can't fit more data into a smaller space without overlapping (aka a hash collision). Any 'fixed output size' hash is not unique by math, but rather by our ability to compute things. A sort of 'pseudo-unique', if you will, just like 'pseudo-random'. And we only say hash functions produce unique outputs because we aren't powerful enough to find two identical hashes of different strings. Just like how we call fingerprints unique. It may be theoretically possible for two people to have identical fingerprints, but it's very hard to find.

Then what's the solution to this?

For now, we should be totally fine using current hash algorithms, but in theory, if there actually is a problem of hashes not being 'unique' enough, we could turn to hash algorithms that produce infinitely long outputs (or outputs that were of variable size). As far as I know, none of these exist, but I'm sure it is possible to do. And if we always make our hashes longer than our data, we're theoretically guaranteed to have a hash function that produces truly unique outputs every time.

So that's just my two bits on that. There are much bigger problems in cryptography than this, but it's something worth talking about. Cheers!

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.