8
$\begingroup$

I was wondering whether, theoretically, 2 files can have the same SHA-256 value.

Since there are only $16^{256}$ or $2^{1024}$ SHA256 sums, all 1024-bit files (with $2^{1024}$ different combinations) will have to have different SHA256 sums (if I'm not mistaken).
Additionally, for files with larger file sizes (such as, let's say, 2048-byte files, where there are $8^{2048}$ = $2^{6144}$ different combinations), there will have to have 2 files with the same SHA256 sums.

And, once there are two files with the same SHA256 sums, what then? Will that mean that SHA256 sums are broken?

Thanks for feeding my curiosity.

$\endgroup$
3
  • 1
    $\begingroup$ The argument in your question proves the existence of collisions, using the Pigeonhole principle. $\endgroup$ Mar 23, 2016 at 13:52
  • $\begingroup$ there are $16^{128}$ SHA-256 hashes not $16^{256}$ $\endgroup$
    – M D P
    Apr 8, 2018 at 22:48
  • $\begingroup$ excuse me, $16^{64}$ SHA-256 hashes and $16^{128}$ SHA-512 hashes $\endgroup$
    – M D P
    Apr 8, 2018 at 22:57

3 Answers 3

13
$\begingroup$

I'm not sure where you're getting $16^{256}$. SHA-256 produces a hash that is $256$ bits long, so there are $2^{256}$ possibilities.

So, let us consider all $256$-bit inputs. Will they map onto the set of $256$-bit SHA-256 outputs, one-to-one, no collisions? Almost certainly not.

If we were encrypting $256$-bit blocks, then yes, they would, because by definition encryption has to be reversible, so encryption algorithms do map things one-to-one. But secure hash algorithms are not designed in this way.

So, instead of thinking there are $2^{256}$ inputs, and $2^{256}$ outputs, and therefore they're one-to-one, instead think that you are selecting from a set of $2^{256}$ items, randomly, with replacement. There will probably be many collisions. Some inputs will map to the same output.

And, of course, once you start considering longer inputs, there are more inputs than outputs and collisions are inevitable, by the pigeonhole principle.

However, this does not mean that SHA-256 is broken. Not at all. This problem of collisions is inherent in any secure hashing system, but still, we use secure hashes and they work. We wouldn't be able to buy things online if they didn't work.

In theory, there are collisions, yes. But a hash is only broken if there is a practical way to generate collisions on purpose. Thus far, no one has published any such attack on SHA-256, or any of the SHA-2 family of hashes.

$\endgroup$
3
  • 3
    $\begingroup$ Nice answer. Just a form suggestion: use the equation environment to improve the readability of formulas (surrounding the "equation" with the symbol $). $\endgroup$ Mar 23, 2016 at 10:54
  • $\begingroup$ How can we know for sure that 256-bit or less inputs cannot create uniform, collision-free SHA-256 outputs? Couldn't a hash function be an irreversible block cipher in this situation? Or would a property of 1:1 mapping of all inputs < 256 bits weaken the algorithm? $\endgroup$
    – bryc
    Mar 7, 2017 at 14:46
  • 1
    $\begingroup$ We can’t know for sure without trying all inputs and comparing all the outputs. However, secure hashes are not designed to be injective and are highly unlikely to be injective by accident. See also random oracle, and this question and its answers. $\endgroup$
    – Tom Zych
    Mar 8, 2017 at 13:01
1
$\begingroup$

I am not sure about how do you obtain your numbers, but part of the intuition is correct: since the length of the hash is fixed, but the length of the possible message space is variable, there is an infinite amount of values that map to the same hash. Collisions happen.

That is why the feature that is pursued in the design of cryptographic hashes is collision resistance. There are several definitions of collision (it is much easier to find any collision than a value that produces a specific hash), but the target is, in general, to make the collision attack overwhelmingly hard.

Perhaps this and this answer can give you some insight about commonly asked questions regarding hashes and collisions.

$\endgroup$
1
$\begingroup$

Theoretically yes, but practically... We are talking about very huge numbers. Even if we started to search collisions just after Big Bang (less than 1018 seconds ago) and did it on 109 computers with 109 hashes per second each, then we have made less than 1036 ~ 2120 hashes that is far beyond 2256. And we cannot count on the Birthday Paradox because storing results in order to detect collisions is also impossible because of the same concerns: too big numbers. So, with "good" hashing function of 256 bit length there is very low probability to find even one collision in the real world.

So let's do it on 256-qubit quantum computer :-)

$\endgroup$
1
  • 1
    $\begingroup$ I understand that I am not original in my answer. Related links are already mentioned. Also link $\endgroup$
    – pandrew
    Dec 8, 2021 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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