Understanding calculation of collisions in hash-functions

Question

I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:

How many collisions would you expect to find in the following cases?

a) Your hash function generates a 12-bit output and you hash 1024 randomly selected messages.

b) Your hash function generates an n-bit output and you hash m randomly selected messages.

The teacher's only answered a) like so:

We expect to find one collision every $2^{n/2}$ hashes. There are $2^{(n/2) * 2} = 2^n$ comparisons. Since the output is 12-bit the answer is $2^{10 * 2}/2 ^{12} = 2^{8} = 256$ collisions.

However I don't quite understand how he got this?

I get that the expected number of collision after n hashes would be $2^{n/2}$. But the rest doesn't make sense to me. I mean if the output is 12 bits (4096 arrangements), why would we expect to get 256 collision after only hashing 1024 messages (1/4 of the possible outputs)?

Answer 1

I suspect you are misrepresenting what your professor actually said.

Since I'm not certain exactly what he said, here is how I would explain it:

• With 1024 outputs, there are $\binom{1024}{2} \approx 1024^2/2$ pairs of outputs.

• For each pair of output, that pair has a $2^{-12}$ probability of being a collision (that is, those two outputs being exactly the same).

• Hence, the expected number of collisions would be about $1024^2/2 \times 2^{-12} = 128$

The exact expected number would depend how you count a multiway collision (where 3 or more outputs have the same value); it turns out that, if you count it right, $\binom{1024}{2} 2^{-12}$ is the correct answer.