# Just how surjective is a cryptographic hash like SHA-1?

From “Are common cryptographic hashes bijective when hashing a single block of the same size as the output” and “How is injective, inverse, surjective & oneway related to cryptography”, it is suggested that cryptographic hashes are surjective. For avoidance of doubt, surjective means this: whereby all the hash inputs (X) correspond to a reduced set of outputs (Y). This forms holes in the continuity of the output range, and we call them collisions.

Consider any hash function like SHA-1. The size of the possible input domain is $2^{160}$ if we stick to the block size. My linked answers suggest that the output co-domain is less than $2^{160}$.

How much less exactly?

Are there any proofs or estimates to put a scale on this? I wonder if the avalanche effect has any bearing on this? This is probably extremely naive, but does anyone have anything better?

In this regard SHA-1 despite it's weaknesses can be viewed as a pseudo random function. This means we are are throwing $n$ balls into $n$ bins. An output bin remains empty if all the balls miss it. Which happens with probability $(1-1/n)^n$ which is $1/e$ and that is the portion of output bins which are empty. We also can estimate that the most populated bin has approximately $log(n)$ balls.
• @PaulUszak If you consider a random function as a proper model for SHA1, then yes, that's the answer. Probably it's a good approximation, but unless we can actually test all $2^{160}$ input values, we don't know how close it actually is. – tylo Jun 26 '17 at 8:36
The size of the possible input domain is $2^{160}$ if we stick to the block size