0

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 '17 at 0:20
  • That what I thought, but it was purposed using md5 and sha as the base algorithms. Thanks – virus.cmd Jan 18 '17 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. – Stephen Touset Jan 18 '17 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 '17 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 '17 at 12:07
5

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. – Stephen Touset Jan 18 '17 at 7:00
  • 1
    @StephenTouset: Exactly. I took the liberty of editing that into the answer - hope you don't mind. – sleske Jan 18 '17 at 8:16
1

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.

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.