Although hash functions should not be able to go from hash to original (they should not be able to be reversed, and they should be one way), it is not possible to know with certainty that a particular hash function is, in fact one-way. In the past, encryption algorithms that were thought to be unbreakable have been broken by cryptographers.
maybe im misunderstanding something.
if i take one megabyte (or 8 megabits) chunk of data and hash it down to a 128 bit hash, how can that be reversed? ie there are more bits information in the original than in the hash. therefore information is irretrievably thrown away, yes?
That’s the
Pigeonhole Principle. It is the same reason why it is
mathematically impossible to build a lossless compressor that produces a shorter output for every input, recursively apply it to its own output, and thus,
reductio ad absurdum, losslessly compress all data in the universe down to 1 bit of information.
All lossless compressors produce outputs longer than the input for some inputs;
all compressors that produce a shorter output for every possible input are lossy compressors, whose outputs cannot all be decompressed with bit-for-bit identical roundtrip results.
Crackpots perennially annoy or entertain us with new designs for compressors that claim to violate the Pigeonhole Principle. It is the information-theoretic counterpart to teaching those stupid physicists that a
true genius can harvest free energy from the Earth’s rotation, or build a perpetual motion machine. (Reviewing recent threads, I am just waiting for stereotypical crackpot SapphireSpire to invent a way to compress the blockchain with recursive lossless compression. Not a few have tried that.)
A cryptographically secure hash function is also called a compression function. Needless to say, it is a very lossy compressor that irretrievably discards most of the input information.
As I noted, it should not be possible to reverse a hash function. If there was some kind of pattern in the output of the hash function, in theory, the function could be reversed.
No, even CRC-32 cannot be inverted to retrieve the input. Even CRC-8 cannot be inverted to retrieve the input.
Some hash functions also have limits as to how much data can be hashed. In theory, a hash function could be reversed in a way such that you can take the hash and calculate every potential input with a range the input having a data size of 0 through the maximum.
Even a cryptographic hash with a finite domain of preimages (inputs) will map an
astronomically huge set of different preimages to each possible image (output). Even if the hash is ridiculously broken, the image does not and cannot contain sufficient information to distinguish each possible preimage uniquely, or even to a practically useful degree of probability. Not if your only starting information is the hash image!
It would be easier to address this, if you were to state what concrete goal you are trying to achieve. Your post about this did not quote or reference any prior posts. OT here, but I note as a precaution just in case if it was in reference to anything I said, or any reader may be confused to assume so: Proving a statement in zero knowledge as I proposed
does not rely in any way, shape, or form on inverting the hash. That would be obvious to anyone who knows
how modern zero-knowledge proof systems work. (Maxwell’s description in that blog post is a good bird’s-eye overview, but it describes the state of the art in early 2016; nowadays, the trusted setup has been replaced with something trustless, and ZK proof systems now require orders of magnitude less CPU and memory.)