7
$\begingroup$

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:

surjective

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So to be clear, 37% or 2^158.6 bins remain empty? $\endgroup$ – Paul Uszak Jun 25 '17 at 20:37
  • $\begingroup$ @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. $\endgroup$ – tylo Jun 26 '17 at 8:36
2
$\begingroup$

The size of the possible input domain is $2^{160}$ if we stick to the block size

Ah but we don't stick to the digest size (the "digest size" is the term for the size of a hash). That's the point of hash functions. To take an arbitrary length input and output a pseudorandom string of a fixed length. Because of this, the true input domain is infinite. An infinite input domain with a finite output domain (no matter how large) always means there will be infinite collisions. Even if you assume an ideal cryptographic hash, there are infinite collisions.

The real trick is making those collisions hard to find.

$\endgroup$
  • 2
    $\begingroup$ SHA1's block size is 512 bits. It's digest size is 160 bits. Pick one. $\endgroup$ – Thomas M. DuBuisson Jun 25 '17 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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