Does every hash value have an inverse value?

Question

There are many different hash functions, md5, sha, and others. They take a value V and produce a H via transformation Function(V) = H, where Function is md5, sha, etc.

My question is: Does every hash value H have a value V?

For example, given md5 hash value f2c057ed1807c5e4227737e32cdb8669 (totally random), can we find what it was from?

In other words, if we list all hashes:

00000000000000000000000000000000
00000000000000000000000000000001
...
fffffffffffffffffffffffffffffffe
ffffffffffffffffffffffffffffffff

Can we find a value for each one of them?

Edit (from OP's comment): I want to know if there exists an input for each possible output. I'm not interested in finding inverse

Answer 1

My question is: Does every hash value H have a value V?

For example, given md5 hash value f2c057ed1807c5e4227737e32cdb8669 (totally random), can we find what it was from?

These are actually two very different questions: whether there is an input for each output, and whether we can find an input for each output.

For your first question: we do not know. For a given hash function, the number of possible inputs is a lot bigger than the number of possible outputs, so we would find it very surprising if the function was not surjective (i.e. if there was an output without any matching input). For instance, with MD5, there are 2¹²⁸ possible outputs, and 2^{18446744073709551616}-1 possible inputs, so we expect that each output has, on average, about 2^{18446744073709551488} corresponding inputs. It is rather implausible that there is an output with no corresponding input.

However, we do not know how to prove it. To a large extent, we expect that property to be very hard to prove for any concrete hash function (such a proof of surjectivity would not, per se, be a weakness of the function, but, handwavingly, the security of a hash function relies on the intractability of its structure with regards to that kind of analysis).

For your second question: we strongly hope that it is infeasible. This is what is called preimage resistance: for a given output y, it should not be computationally feasible to find a x such that h(x) = y. Even if it was mathematically proven that such an input must exist (it is not proven, but it is strongly suspected, as explained above), it should still be atrociously expensive to actually find it.

If the hash function is "ideal" then the best possible attack is luck: you try out possible inputs until a match is found. If the output has size n bits, then "luck" should work with an average effort of 2ⁿ; with n large enough (and n = 128 is large enough), this is way out of what can be done with existing computers. A hash function is said to be resistant to preimages if "luck" is still the best known attack.

It is known that MD5 is not ideally resistant to preimages, because an attack with effort 2^123.4 has been found -- about 10 times faster than 2¹²⁸, but still a long way into the realm of infeasibility, so that attack is theoretical only.

I would like to point out two things, though:

• If I give you h(x) for an unknown x, but you have some idea about the x that I used (e.g. you know that x is a "password" that a human user could choose and remember), then you can try possible x values that match that idea. The actual average effort for finding a preimage to h(x) is the smaller of 2ⁿ and M/2, where M is the size of the space of possible inputs x. For a "raw" preimage attack, all sequences of bits are possible inputs, so M is huge and the cost is 2ⁿ. However, if, in a specific context, x is known to be taken out of a relatively small space, then finding the "right" x can be substantially faster.

• As pointed out above, preimages are not supposed to be unique: for a given y, a large number of values x should exist, that hash to y. Thus, for a given output, you do not find "the" corresponding input, but "a" corresponding input, which may or may not be the "right" one.

---

And the third question ? Indeed, trying to make a complete map of inputs-to-outputs is yet something different.

As @Xander pointed out, the number of possible MD5 outputs (2¹²⁸) is too large to be stored anywhere on Earth; it exceeds the cumulated size of all hard disks that have ever been built. However, if you could solve that storage issue, then it is possible to think about the cost of making a complete map.

If you use the "luck" attack on all 128-bit outputs independently, you may expect an overall cost of 2²⁵⁶ (2¹²⁸ times a cost of 2¹²⁸). However, you can do much better by handling all outputs simultaneously, i.e. trying out random (or sequential) inputs and simply populating your big table as you obtain the outputs. With effort 2¹²⁸, you should get about 63% of your complete map, while the "independent luck" method would need an effort of a bit more than 2²⁵⁵ to achieve the same result.

---

Edit: as was pointed out by @Owen and @kasperd, the arguments on the number of inputs are not actually sufficient to induce surjectivity; the internal function structure matters. MD5 and SHA-1 are Merkle–Damgård functions, meaning that they are built as follows:

• There is an inner pseudorandom permutation P: for an input block b of a given size (512 bits in the case of MD5 and SHA-1), P_b is a permutation of the space of sequences of exactly n bits (n = 128 for MD5, n = 160 for SHA-1).

• A compression function is defined, as:

      f(b, x) = P_b(x) + x

  That is, for block b, we apply the permutation corresponding to b on the second input x, and then we "add" x to the output of that permutation. (In the case of MD5 and SHA-1, that addition is done on a 32-bit word basis, but the details do not matter here.)

• To process a complete input message m, the message is first padded with extra bits so that the total size becomes a multiple of the block size, and also encodes the original message length. The padded input is then split into successive blocks b₀, b₁, and so on. A register r is initialized to a conventional value of size n bits (the "IV", specified in the MD5 and SHA-1 standards). Blocks are then processed one by one: to inject block b_i, we compute f(b_i, r), and the output is the new value of r. When all blocks have been processed, r contains the complete hash function output.

The addition step in the compression function turns the pseudorandom permutation P_b into a pseudorandom function. A relevant consequence is that, for a given value b, f(b, x) is very unlikely to be surjective. In fact, we expect values f(b, x), for all 2ⁿ inputs x, to cover only about 63% of all possible 2ⁿ sequences of n bits.

This processing has interesting consequences. First, consider all inputs of size exactly 1 GB (the "traditional" gigabyte of exactly 1073741824 bytes): there are 2^8589934592 such sequences, i.e. a lot more than 2¹²⁸. However, when applying MD5 on all these messages, they will all be padded with exactly one extra block (8589934592 = 16777216×512, so an extra block of size 512 will be appended), and, furthermore, this final block will be the same for all 1 GB inputs (it encodes the input length but is otherwise deterministic, with no randomness and no dependence on the values of the input bits). Let's call b_z that final block. MD5 on a 1 GB input message m thus begins with a lot of processing on the first 16777216 blocks, resulting in a 128-bit value x, and the hash output MD5(m) is equal to f(b_z, x).

Therefore, all 1 GB messages ultimately reduce to a single of the same compression function f(b_z, x). Thus we expect the hash outputs to cover only about 63% of all 128-bit sequences. This example demonstrates that the argument on the number of inputs to the hash function is incomplete (though it gives the right idea).

Conversely, if we consider all messages of exactly 300 bits in length, then they will all be hashed as f(b, IV), with 2³⁰⁰ distinct blocks b. We thus have 2³⁰⁰ pseudorandom permutations P_b, all applied on the same 128-bit input (the IV), yielding 2³⁰⁰ 128-bit results which are all, then, supposed to be uniformly distributed over the space of 128-bit values. Adding IV to all of them does not change that uniformity. In that case, the counting argument works and thus sujectivity becomes highly probable.

---

Edit 2: About the "63%". When you generate a random value, uniformly, in a space of size N, then the probability of hitting a given value x is 1/N; thus, the probability of not hitting a given value x is (N-1)/N.

Now try it N times: you generate N values randomly, uniformly and independently (in particular, you may generate several times the same value). For a given x, the probability of not being part of these N values is the probability of having been missed N times, i.e.:

    P = ((N-1)/N)^N.

This can be approximated as follows:

    P = e^{N ln (1-1/N)} = e^{N(-1/N + o(1))} = e^-1+o(1)

Thus, with big values of N, the probability of any given value being missed approaches 1/e. Therefore, the expected coverage of the space of size N, with N random values, would be close to 1-(1/e). This is approximately 63.21%.

Answer 2

These are actually very common questions that people ask about hash functions. I will give a more mathematical answer, including some terminology to help you with googling.

My question is: Does every hash value H have a value V?

The mathematical way to phrase this question is

For a hash function H = Function(V), does every output H have a pre-image V that maps to it?

or more compactly,

Is a hash function Function() surjective?

Whether MD5, SHA-1, SHA-256, SHA-3, etc, are surjective is a good question and one that has been asked many times on the internet (Google can find you some good discussions). The short answer is: we don't know. We strongly suspect that they are, but this is not something we've been able to prove either mathematically, or through experiments.

To give you an idea of why this is a hard question; this answer on CS.se talks about MD5 and points out that hash functions are designed to be very close to random and avoid any patterns, making any kind of mathematical analysis very difficult. You could always write a program to guess inputs until you have seen every possible output. MD5 has a 128-bit output, meaning there are 2¹²⁸ hashes you need to hit. Assuming you got them all on the first try, and you could check 1-per-second, it would take you about 10³¹ years and at least 10²⁸ gb of hard drive space to do the exhaustive check (note that the universe is estimated to be ~ 10¹⁰ years old, and the total hard drive capacity on earth is around 10¹² gb).

Hash functions in the SHA-family have larger output spaces, and are mathematically more complex, meaning that this kind of analysis is even less tractable for them.

Note also that since a hash function takes in an input of any size, and gives an output of fixed size, there could be (in theory) an infinite number of inputs that will map to any given hash. So a hash value H likely has large set of values {V1, V2, ...} that map to it.

---

For the second part of your question:

given md5 hash value f2c057ed1807c5e4227737e32cdb8669 (totally random), can we find [the set of inputs that would produce it]?

Finding a string that will produce a given hash is a form of crypanalysis called a Preimage Attack. As others have pointed out, for a hash function to be considered a Cryptographic Hash Function it must be resistant to preimage attacks - or in other words, it must be impossible to invert other than taking the list of all possible strings, hashing them, and seeing if they match.

If somebody finds a shortcut to invert a hash faster than checking all possible strings, this would be considered a vulnerability in that hash function and that hash function would be considered "broken". MD5 is considered broken and is no longer recommended for cryptographic use, so you may be able to find known preimage attacks against it. If you look those up, you may be able to find tools to help you invert your MD5 hashes. The SHA-family of hashes have not yet been broken, so you're out of luck for those.

Answer 3

That is the very purpose of one way hashes (ie md5, sha1, sha2, etc). They aren't supposed to be reversible. If you could reverse a hash lots of security would immediately become insecure. The hash doesn't contain the information from which it was hashed. The process of hashing is easy in one direction and really really difficult in the other direction is why.

Now if you had a lot of content and hashed it, then stored that content with it's hash in a big hashmap then you could quickly reverse things by looking it up by the hash, and find the content that you produced that hash with. This is what is called rainbow tables which has been a viable way to crack passwords in the past, but not so much anymore.

Even if you could, consider this. Say I produced an MD5 hash of a movie that is 100MB. If I could reverse this hash value and get my 100MB movie from it then I'd have an extremely powerful compression algorithm! Because that would mean I could take any content 1Mb, 100MB, 1Gb, 1Tb, etc. and turn that into a hash which is 32 bytes to represent anything I wished. Now could I really represent every content imaginable at any size in 32 bytes? That would be impossible as there's not enough information density in 32 bytes to represent every possible content we could ever dream up as 2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456. That would be the upper limit of unique content I could create too.

I think this answer explains it better than I can as to how the math makes this impossible (or at least very very difficult):

Why are hash functions one way? If I know the algorithm, why can't I calculate the input from it?

Answer 4

If you are talking about cryptohgraphic hashes, there is no way of recovering back the "V" value used to generate "H" hash. They are engineered in a way to prevent that.

What people do to discover the original "V" value is to generate various "V"s, calculate their respective "H" and compare these "H"s to see which one is equal to the original "H" hash. Yeah, just by bruteforcing it.