Why can't I reverse a hash to a possible input?

Question

I'm going to provide “proof” why a hash function can be reversed, and I hope you can tell my why I'm wrong

So, a hash function can be implemented as a series of logic gates. All logic gates can be implemented using only NOT and OR gates. (I'm fairly sure about both of these, but please correct me if I'm wrong.)

Therefore, a hash function can be implemented as a series of NOT and OR gates.

A NOT gate can be easily reversed by going through another NOT gate.

An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output.

Therefore, I should be able to construct a possible input given an output from a set of logic gates, including from a hash function.

What have I gotten wrong here?

Answer 1

What you're missing is the fact that multiple logic gates can share the same input(s). So you can't look at each logic gate individually and "reverse" the entire circuit that way, because choosing the inputs of a logic gate may constrain the outputs of other logic gates (so not all possible choices of input for any logic gate will work, only some will).

So you still need to "search" for a satisfying set of inputs in some way, you can't just locally reverse each logic gate because they are all interconnected. And this search space is exponentially large.

Answer 2

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction of gates is a function, rather than depending on some internal state. And the number of gates is manageable (perhaps in the order of $n=10^{5\pm1}$ OR gates for the SHA familly and single-block message).

This does give a constructive way to find an input corresponding to a given output, as outlined in the question: try every possible inputs for a gate with an output that's a given output, or has been hypothesized in an earlier step. For NOT, there's only one possible input (the complement of the output). If the output of OR is 0, its inputs are 00. If the output of OR is 1, there are 3 possibilities for its inputs: 01, 10, 11. When a new hypothesis conflicts with an earlier hypothesis (which occurs since inputs of different gates can be connected to the same output), eliminate the new hypothesis. If all new hypothesis for a gate's input(s) are eliminated, eliminate the old hypothesis. When all the circuit is covered, and if there's a possible input, any hypothesis not eliminated gives a possible message input.

That works. But critically: new hypothesis are dependent on earlier ones, thus when we meet an OR gate with a 1 output, it multiplies by 3 our number of hypothesis to keep track of (in a breadth-first approach) or explore later in case of failure (in a depth-first approach). If we examine the maximum number of hypothesis to be examined as a function of the number $n$ of OR gates, it grows as $\mathcal O(c^n)$ for some constant $c$ that can be significantly above 1. Using that a XOR can be built with 3 OR gates (and some NOTs), we have an argument that $c\ge\sqrt[3]2\approx1.26$ for some large portion of some possible circuits (adding a XOR gate on an unknown input transforms it into 2 unknown inputs).

Thus the argument in the question proves that a hash can be reversed with enough effort, but it gives no lower bound for the corresponding effort; and the best bound we know to derive is exponential w.r.t. the gate complexity. It turns out that for hash constructions used in cryptography (e.g. SHA-1 with 160-bit output and 176-bit input), the cost of this method is much higher that trying all possible hash inputs (e.g. $2^{176}$).

Answer 3

Because a hash function essentially destroys the inputs, or information. For example, a common operation in hashing is modular math, which is basically the remainder after the division. 9 mod 2 = 1 (9 / 2 = 4, remainder 1). The 1 moves on in the hashing function. But the modular operation is irreversible - all that is left is the output of 1, but there is an infinitude of potential inputs that result in an output of 1. Even if you have one of the inputs, in this example let's say 9, x mod 2 = 1 still has an infinitude of potential values of x (basically every odd number). This is distinct from many other operations (+, -, *, /, etc.) where if you have the output and one input you can calculate the other input.

Answer 4

The mathematical one-way function is irreversible whichever way you program it. As there is no inverse of the mathematical function it is impossible to program it. So the answer is no.

You can of course cause side effects to happen, other than outputting the hash. E.g. timing information can be used to retrieve some intermediate functions. As hash functions are usually pretty resistant to side channel attacks you'd probably have to program it deliberately. But in that case you might as well print out the input of the hash function before you apply the algorithm.

One thing that is always possible with any hash function is trying all possible inputs until you find a match. With a cryptographic hash with sufficient strength and output (such as RIPEMD-160 or SHA-256), if you find a match you can be sure you found the original input.

The fact that you use two different hash functions in succession doesn't make a difference at all.

Answer 5

Your error is here:

An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output.

A set of possible inputs can be derived from any given output. For each output that is a 1, there are three possible combinations of input (01, 10, and 11). If you add enough gates in sequence, the combination of inputs becomes huge. For instance, with 100 gates OR gates with output value 1, you'd be looking at 515377520732011331036461129765621272702107522001 combinations (that's $3^{100}$).

A hash algorithm typically involves repetitively applying the same algorithm hundreds or thousands times, and we can assume that half the bits are going to be 1 at any stage. So the number of possible input values is going to be combinatorial explosion, and is probably not going to to be any less than the total number of combinations of the input domain (e.g. if you are hashing a 1000 byte sequence, that's 8000 bits, i.e. $2^{8000}$ possibilities). We can see that by the fact the hash samples each input bit at least once.

Further more, we don't know the layout of the 'circuit' we're trying to reverse. We don't know how many input bits there are, so we don't know how many 'gates' there are in the circuit to calculate the hash.

So yes, you are right, in a sense you can reverse a hash. But it will take more operations than iterating through every combination of input data, and requires knowing various things about the input data that you don't know.

Answer 6

Why can't I reverse a hash to a possible input?

Actually, depending on the individual hash and explicitly ignoring all computational feasibility issues, you could. Just don’t expect the result of your reversal to be the same as the “original input”.

Furthermore you should be aware of the fact that, depending on the type of hash and depending on the cryptographical security of its design, reversing the hash function might be as unfeasible and/or unpractical as a brute-force attack.

Keeping that in mind and looking at the fact that it is well known that “one should not hash secrets”, your hash-reversal will not do any magic like cracking passwords. That is, unless someone really messed up application and/or website security and (for whatever reason) ignored well vetted recommendations like the ones that you can find at the OWASP Password Storage Cheat Sheet.

What have I gotten wrong here?

Not much… well, except that – as I already indicated – it seems as if you forgot (or simply ignored) that 99.9% of all hash functions out there include a compression step, which loses information and therefore can not be reversed (unless someone messed up the hash function design really badly). That prevents reconstructing the original input. As said: all you might be able to get is “some possible input, which is bound to differ from the original input”.

As an example: MD5’s compression function can be reduced to 45 steps using a meet-in-the-middle attack taking only $2^{100}$ function evaluations ^[1], but that won’t help reproducing the majority of potentially original inputs. (Though, it might help on the way to create pre-images.)

Practically, your attempts will be limited to finding “could have been” inputs (read: some possible input) not larger than the hash output size, but there is no way to prove that those were indeed the original inputs, nor is it safe to assume so as there is no upper bound on a hash input. So, in the end, your “proof” boils down to the discovery that – if you are able to reverse the whole hash function – it is possible to find inputs which produce some expected output when applying the hash function. That’s neither magic, nor a real breakthrough… rather the result of simple logic… somewhat like a hard way to create a one-to-one mapping by working your way back through a hash function (which is build to make that aspect hard).

Wrapping it up: your “proof” only makes sense and applies to inputs not larger than the output of the related hash function – think: pre-image attack. Since cryptographically secure hashes (the ones we tend to handle at Crypto.SE) are build to provide preimage-resistance, it raises the question if your approach is feasible enough to be practical – which strongly depends on the individual scenario. Practically, chances are rather low you’ll be shortcutting your way into “secrets”.

On the other hand, you might have some valid reasons making you want to reverse hash strings of whatever data to (for example) be able to fake the input of that whatever data. In the end, it is up to you to decide if you really want to invest the according time and resources on reversing hashes of “non-secrets”. In a worst case, you’ll be spending more time and efforts on it as you would spend on the application of an optimized brute-force attack… of course, depening on the individual scenario and/or the individual hash function involved. (I’m only adding the later since simpler, checksum-alike, non-cryptographically secure hashes exist which might provide the base for more feasible scenarios).

---

_{^[1] Selected Areas in Cryptography: 15th Annual International Workshop, SAC 2008 – page 121}

Answer 7

You try to dis-prove something that is not a feature of a hash function. You can always brute-force a hash function by trying all possible inputs upto a given length until you find a preimage of a given hash.

The claim for a cryptographic hash function is that it is computationally difficult to find such a preimage. In fact, this claim is not proven for any hash function in practical use (it depends on the conjecture the the complexity classes P and NP are not the same).

Answer 8

A different way to see the problem would be through the communication point of view.

If you were able to revert any hash, then you could hash a 1GB file resulting if a 128 bit hash for SHA1 for instance. Then it could mean that you could send the hash through a channel and revert it at the other side. That would be almost unlimited transference of data through a channel and unlimited compression.

That would be a violation to the Shannon's theorem which states that there is limit to the amount of data could be transferred in a channel. This theorem is also applied to compression and it limits the maximum compression ratio that can be achieved. Beyond that limit, is not possible to transfer or compress more data.

Answer 9

Imagine a simple hash function. Like take one I've seen used to hash strings when building a dictionary: add up the ASCII or Unicode values of all the characters and take the remainder modulo some fairly large n, usually the maximum value that will fit in an integer.

I could easily write a function to generate an ASCII string that would be a "possible input" for any given output: Pick any character, say "z". Divide the hash value by the ASCII for "z". Use the quotient to generate that many z's. Use the remainder to generate one more character. If we want printable ASCII, than if that character is less than 32, remove one z, add the ASCII value for z, divide by two, and add two of this character. If there's a remainder, add one to the second one. I'm spinning this off the top of my head so if I missed a detail, fine, I'm sure one could work it out.

Yes, the nature of a hash function is that it is not possible to definitively find the original input. In an example like the string hash I just discussed, the modulo arithmetic step means that there are an infinite number of possible strings that map to the same value. If the hash value is 16 bits and our input strings can be more than 16 bits, then there are more possible inputs than outputs, so clearly multiple inputs must map to the same output, so it cannot be definitively reversed. But if you're a hacker trying to find a password, you don't care if you have the "real" password. Any string of characters that hashes to the right value will get you in, and that's all you need. Hence a "possible input".

Obviously more complex hash functions would require a more complex approach to reversal. But the question is: Is it possible to construct a hash function that is so complex that any reversal function would inherently require more computation than a brute-force approach, i.e. trying every possible input until you find one that gives the desired output?

It is my understanding that the hash functions used for passwords indeed do meet such a condition. But I've never seen the proof of this. Is it really mathematically proven that it's impossible, or is it just that no one has found a way to do it?

Answer 10

You can find an input that will have the same hash as the original input. But depending on the hash in question and luck it might require the computing power of an entire universe an trillions or more years to do so. If the input was truly random and large enough, the hash has no known vulnerabilities and is hard to compute you will have to hash every possible input until you find one that gives the same output. Unless you are extremely lucky or have an infinitely fast computer or use some tricks like travelling at 0.99999999999c for a few years while a computer on a planet stationary relatively to you is guessing (a few years (or whatever) of your time will approach infinity as you approach light speed, you can't (as far as we know reach light speed nor have time flow at an infinite rate but you can get arbitrarily close and arbitrarily close to infinity and infinity is for most intents and purposes the same) this will take forever.

If the hash vulnerable to a much faster attack or if the input/output are very small or if you do happen to have infinite compute resources, it can be done faster than in 1 second.

What is impossible however is (at least generally speaking... the hash could be bad and guarantee the same out put for one input value and if the original one is that one.. or you could have extra information regarding the input... it you know the input was a 4 letter English word hash all 4 letter English words and if only one has the same hash as your unknown input then that was the input) proving that the input you calculated is the same as the original one.

You can try this at home if you want with some of the obsolete hashes that are actually vulnerable to a brute force attack on an average pc. Download something like MDcrack and try.

Answer 11

Here is a very simple way to disprove your "proof".

I have a 2-input OR gate. The output is '1'. Tell me how to reverse the exact input combination of inputs A and B. Is it 01, 10, or 11? It is only deterministic when the output of the gate is '0'.

You can use this methodology to eliminate a few possible bit conditions, but the complexity quickly becomes far too great to make it worthwhile.