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? In other words, are hash functions surjective?

If so, what guarantees this? If not, is it possible to discover such impossible outputs via an attack faster than brute force?


2 Answers 2


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.

  • 4
    $\begingroup$ Even H(H(m)) will likely not reach a lot of the output space. $\endgroup$ May 30, 2012 at 19:54
  • 1
    $\begingroup$ Yes, but not demonstrably so :-) $\endgroup$
    – fgrieu
    May 30, 2012 at 23:04
  • 2
    $\begingroup$ @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. $\endgroup$
    – dr jimbob
    Jun 9, 2013 at 7:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jun 9, 2013 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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.