Can two files/strings have the same SHA-256 value?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

Theoretically yes, but practically... We are talking about very huge numbers. Even if we started to search collisions just after Big Bang (less than 10¹⁸ seconds ago) and did it on 10⁹ computers with 10⁹ hashes per second each, then we have made less than 10³⁶ ~ 2¹²⁰ hashes that is far beyond 2²⁵⁶. 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 :-)