10
$\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?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
4
  • 1
    $\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
    Commented Jun 26, 2017 at 8:36
  • $\begingroup$ @tylo Isn't that consideration proven beyond any reasonable doubt? We can verify the collision rate with just a few lines of code. It tallies (at high certainty) with an avalanche characteristic of $\mu = \frac{\text{block-width}}{2}, \sigma = \frac{\sqrt{\text{block-width}}}{2}$. Ergo, 37% of bins must remain empty. $\endgroup$
    – Paul Uszak
    Commented Mar 30, 2021 at 15:23
  • $\begingroup$ @PaulUszak I don't think that's proven at all. On the contrary - it is proven in theory that there are some constructions are secure in the random oracle model (which is a random function in a blackbox) but insecure with any real hash function. There is a difference between the two, and it's impossible to estimate how close the actual result with a specific function is to the random function. It's like drawing a value from a probability distribution. $\endgroup$
    – tylo
    Commented Mar 30, 2021 at 20:47
  • $\begingroup$ I must side with @tylo on this. We do not know for a fact SHA1 behaves like a PRF. Even with recent attacks we did not find sufficiently many collisions. But the evidence is significant we do have some collisions yet they are not plentiful and we can easily analyze truncated versions and see they behave as expected. Most importantly however the question said " any hash function like SHA-1" so a generic answer seemed in order and not focus on SHA-1. $\endgroup$
    – Meir Maor
    Commented Mar 31, 2021 at 4:46
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @ThomasM.DuBuisson Yellow. $\endgroup$
    – Paul Uszak
    Commented Mar 28, 2021 at 1:46

Your Answer

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

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