Do well-known hash functions have any “impossible” output values?

What I'm wondering is whether the codomain and image of common hash functions are strictly equal… or whether there are any known values which have no possible preimage.

For example, SHA-1 outputs a 160-bit digest. Can it be proved that every possible sequence of 160 bits is a possible output of SHA-1 (even though corresponding preimages cannot be easily computed, by design), or are there certain outputs which can be demonstrated to be impossible based on the construction of the hash function?

This question about uniformity of hash function output seems related, though what I'm interested in has less to do with overall uniformity, and more with provable existence/non-existence of any preimage for specific outputs.

• There are two separate aspects to this question. One is whether there might be an impossible output due to some flaw in, or the structure of, the has function -- there's one or more special output(s) that due to structure cannot be produced. The other is whether it's likely/possible to have an impossible output by just pure bad luck -- there just happens to be one or more random-looking output(s) that it just so happens no input can produce. – David Schwartz Jan 21 '18 at 18:41
• Right, that's why I asked about provable non-existence of any pre-image for certain outputs. Given that preimage resistance is an important property of hash functions, it'd be impossible to identify random-bad-luck gaps. I'm thinking about something analogous to the DES weak keys, where the behavior of those keys is straightforwardly demonstrated in terms of the structure of the cipher. – Dan Lenski Jan 21 '18 at 18:53

• For a hash modeled as a random function, the probability that there is such value is lower than $1/2$ for a $n$-bit hash when there are more than $n\,2^n$ inputs; and that probability lowers with larger message input sets. See this for details.
• In that formula in the linked answer, what exactly does $o(1)$ mean? What is it equal to? – lyrically wicked Jan 21 '18 at 11:45
• @lyrically wicked: In the formula $2^n\cdot(n\cdot\ln(2)+\gamma)+1/2+o(1)$ giving the expected (average) number of inputs to reach all $n$-bit value under the assumption that the hash is a random function, $o(1)$ designates a quantity that converges to $0$ when $n$ increases to infinity. We can safely say that for large $n$, this quantity is much less than $1$ (in absolute value). See little-o notation. – fgrieu Jan 21 '18 at 14:21