What are the implications of reversing hashes

Question

Today it was posited to me that

1. sha256 has a domain large enough to never encounter a collision and
2. that because it is such a large domain and given that a reverse function was created for it, that it would make current compression obsolete. Large files could be created by reversing a sha256.

I understand that hashes are one way, deterministic functions but if there were a reversible hash would this hold true, or is the potential of collision to great to ever really create unique hash?

Answer 1

Reversible hashes aren't compression

Even hashes which we can reverse cannot be used as a compression. Assuming that we could reverse sha256 wouldn't make current compression obsolete, because there are infinitely many large files, but finitely many (2^256) sha256 values, so infinitely many large files will have the same sha256 hash - this is known as the pigeonhole principle. Reversing the hash would get you one or all of the possible large files, but you can't ensure or realistically hope that this is the exact one you compressed.

For a trivial example, if you'd want to compress files of 33 bytes (264 bits) then there are 2^256 different sha256 hashes, and 2^264 possible different 33 byte files - on average every 2^8 such files will have the same sha256 hash. While it's implausible that you'll accidentally get a collision (1/2^256 chance), it's also unlikely that on a "reverse" you'll accidentally get the same file that you compressed (1/2^8 chance). In cryptography saying "collision proof" doesn't mean that there aren't collisions (of course there are, there must be) but rather that the collisions are hard/slow to find and manipulate.

Answer 2

I don't have the mathematical background to properly explain this, but no fixed-size hash is big enough to provide a unique output for every single input. Therefore, there would be collisions, and it would be impossible to tell which input was provided initially.

But even if we ignore that, the property of the large output space and the property that it cannot be reversed is unrelated. Even MD5 can't be mathematically reversed. It's just that MD5 is small and fast enough that we can build reverse dictionaries to map hashes to potential inputs. You could do this too with SHA1 or SHA256.

The part that makes it impractical to use this for compression is that you would still have to store the input somewhere to do the reversal, which is completely missing the point.