Is every output of a hash function possible?

Question

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?

Answer 1

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.

Answer 2

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