# Is every output of a hash function possible?

Is every output of a hash function (e.g. SHA1, MD5, etc) guaranteed to be possible, or, conversely, are there any output values that cannot possibly be created from any input? If so, what guarantees this? If not, is it possible to discover such impossible outputs via an attack faster than bruteforce?

-
Related (but not the same, as you don't have a limited input length): Is SHA-512 bijective when hashing a single 512-bit block? –  Paŭlo Ebermann May 23 '12 at 17:51

There is no proof that every output of common hash functions is reachable for some input, but it is expected to be true. No method better than brute force is known to check this, and brute force is entirely impractical.

By the coupon's collector argument, it is expected to require $2^n\cdot(n\cdot\ln(2)+\gamma)+1/2+o(1)$ random values to reach all $n$-bit values, with $\gamma\approx 0.577216$.

Translated to hashes, about $2^{134.5}$ (for MD5) or $2^{166.8}$ (for SHA-1) distinct messages are expected to be required to reach all output values, on the assumption that these hashes behave as random functions. This assumption is reasonable, as it is the design goal of the round function of these hashes.

Update: as stated by Jon Callas in an other answer, it is possible to construct hash functions which demonstrably do not reach all their output; and even some that are computationally secure. One example is $\mathcal{H'}=\mathcal{H}(\mathcal{H}(m)|1)$ where $|$ is bitwise OR, and $\mathcal{H}$ is a common hash function. $\mathcal{H'}$ reaches markedly less than half of its output space, but is likely as fine as $\mathcal{H}$ by all other experimental metrics except speed.

-
Even H(H(m)) will likely not reach a lot of the output space. –  CodesInChaos May 30 '12 at 19:54
Yes, but not demonstrably so :-) –  fgrieu May 30 '12 at 23:04
@fgrieu - No its demonstratable. H(m) maps {0,1}^infinity to {0,1}^N for an N-bit hash function. So, H(H(m)) at the outer function call takes {0,1}^N as input and maps it to {0,1}^N. Thus if we assume one single collision exists (which we expect with overwhelming probability for any hash function -- they intend to attack as random oracles not as permutations), then by the pigeonhole principle the whole output space is not reachable. –  dr jimbob Jun 9 '13 at 7:47
@dr jimbob: odds of a random oracle $R$ being such that $R(R(m))$ reaches all output space are overwhelming low. But one can't demonstrably (in the sense used in mathematics) go from that to a result for a concrete hash function $H$ such as SHA1 or MD5. –  fgrieu Jun 9 '13 at 10:55

There is no general answer, because there's no general statement you can make about all hash functions. It depends on the hash function, and how it compresses.

If you found that this was true for a given hash function, that it didn't generate some outputs, then this would be a flaw. It is at least a distinguisher, and most likely is indicative of some larger flaw, but how large the flaw is depends on many, many things.

Consider this 512-bit hash function G = SHA512(MD5(M)).

It cannot generate all the 512-bit possible outputs, because its inputs are limited to the outputs of MD5. It will also collide with any M and M' that have an MD5 collision. But for other purposes, e.g. getting a key from a password with PBKDF2, it would work fine. Ish.

Jon

-