Can’t the steps be reversed one by one to get back the original?
In: Mathematics
Many commenters are invoking the idea of “multiple inputs could produce the same output,” and while that is true of hash functions (their whole purpose is to produce a fixed-size digest from a much larger message), it’s not the real reason cryptographic hash functions are difficult to reverse. After all, you can have a one-to-one cryptographic hash function that’s very difficult to reverse: take for example SHA-256 but restricted to an fixed input size of 256-bit messages. Assuming no collisions, it’s a one-to-one correspondence, with every input mapping uniquely to one output, and yet you still could not for the life of you reverse it.
The reason is because the hash functions are *designed* that way, intentionally. They are designed to maximize properties like the [avalanche effect](https://en.wikipedia.org/wiki/Avalanche_effect), minimizing linearity between input and output, using techniques like [diffusion and confusion](https://en.wikipedia.org/wiki/Confusion_and_diffusion). The avalanche effect means that flipping a single bit in the input should result in flipping roughly half the bits in the output. This makes it very difficult to find a preimage given an image besides using exhaustive search (bruteforce).
Also keep in mind we strongly *believe* SHA-256 can’t be reversed easily, meaning the best strategy our best minds have discovered so far is little better than just bruteforcing it, and with a search space of 2^(64)-1 bits (not 64 bits, but *2^64-1* bits, i.e. 18 quintillion bits), which is the maximum message size SHA-2 works on, there is no hope of bruteforce if outputs truly are effectively randomly distributed with no patterns or predictable structure in relation to the input.
But that’s just a belief. There’s not a mathemtical proof that SHA-256 doesn’t have structural weaknesses that could be attacked. Fundamentally, SHA-256 and other cryptographic hash functions are what we believe to be [one-way functions](https://en.wikipedia.org/wiki/One-way_function), functions that are easy to compute (taking polynomial time), but difficult (meaning super-polynomial time, e.g., exponential) to reverse. Whether one-way functions exist is an open question. If one-way functions exist, then P ≠ NP. Contrapositively, if P = NP, then one-way functions cannot exist, meaning no cryptographic hash function is fundamentally hard to reverse.
Latest Answers