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?

  • 1
    I'm pretty sure en.wikipedia.org/wiki/Shannon's_source_coding_theorem could be used to show the limits of that (essentially, what you're thinking of would be a compression schema rather than a hash function).
    – JAB
    Jan 18, 2017 at 0:20
  • That what I thought, but it was purposed using md5 and sha as the base algorithms. Thanks
    – virus.cmd
    Jan 18, 2017 at 2:01
  • It doesn't matter what algorithm you use. If there are only n bits of output, there are only 2^n possible outputs. Therefore, after 2^n+1 inputs, at least one output can no longer be uniquely matched to its input. Jan 18, 2017 at 10:30
  • For some algorithms, we can't even prove that all output hashes are possible for a given input. If that's the case, you need even fewer inputs (but we currently can't prove how many...)
    – Matthew
    Jan 18, 2017 at 10:52
  • 2
    Note that the reason why compression algorithm works without violating Shannon's Theorem is because compression algorithm actually would cause most files to become larger than the original file. There's a one to one (or one to many) mapping between every possible bitstream and their compressed version, but most random bitstream that gets compressed is slightly larger than the original file. Compression works because we optimize it to reduce the size of the files that we care about, which usually are those with lots of structural redundancy (nobody compresses file containing random noise sample
    – Lie Ryan
    Jan 18, 2017 at 12:07

2 Answers 2


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.

  • 3
    TL;DR, the pigeonhole principle (en.wikipedia.org/wiki/Pigeonhole_principle) makes this type of compression impossible in principle and in practice. Jan 18, 2017 at 7:00
  • 1
    @StephenTouset: Exactly. I took the liberty of editing that into the answer - hope you don't mind.
    – sleske
    Jan 18, 2017 at 8:16

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .