5
$\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$
  • 1
    $\begingroup$ The argument in your question proves the existence of collisions, using the Pigeonhole principle. $\endgroup$ – CodesInChaos Mar 23 '16 at 13:52
  • $\begingroup$ there are $16^{128}$ SHA-256 hashes not $16^{256}$ $\endgroup$ – M D P Apr 8 '18 at 22:48
  • $\begingroup$ excuse me, $16^{64}$ SHA-256 hashes and $16^{128}$ SHA-512 hashes $\endgroup$ – M D P Apr 8 '18 at 22:57
7
$\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
    $\begingroup$ Nice answer. Just a form suggestion: use the equation environment to improve the readability of formulas (surrounding the "equation" with the symbol $). $\endgroup$ – Sergio Andrés Figueroa Santos Mar 23 '16 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 '17 at 14:46
  • $\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 '17 at 13:01
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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