How to figure out the size of the output of a cryptographic checksum function

Question

In Bishop's Introduction to computer security, on page 118, we see the following:

Definition 8–2. A cryptographic checksum function (also called a strong hash function or a strong one-way function) $h: A → B$ is a function that has the following properties:

1. For any $x ∈ A$, $h(x)$ is easy to compute.
2. For any $y∈B$,it is computationally infeasible to find $x∈A$ such that $h(x)=y$.
3. It is computationally infeasible to find $x, x' ∈ A$, such that $x ≠ x'$ and $h(x) = h(x')$. (Such a pair is called a collision.)

The third requirement is often stated as:

4. Given any $x ∈ A$, it is computationally infeasible to find another $x' ∈ A$ such that $x ≠ x'$ and $h(x') = h(x)$.

However, properties 3 and 4 are subtlely different. It is considerably harder to find an $x$ meeting the conditions in property 4 than it is to find a pair $x$ and $x'$ meeting the conditions in property 3. To explain why, we need to examine some basics of cryptographic checksum functions.

Given that the checksum contains fewer bits than the message, several messages must produce the same checksum. The best checksum functions have the same number of messages produce each checksum. Furthermore, given any message, the checksum it produces can be determined only by computing the checksum. Such a checksum function acts as a random function.

The size of the output of the cryptographic checksum is an important consideration owing to a mathematical principle called the pigeonhole principle.

Definition 8–3. The pigeonhole principle states that if there are $n$ containers for $n + 1$ objects, at least one container will hold two objects. To understand its application here, consider a cryptographic checksum function that computes hashes of three bits and a set of files each of which contains five bits. This yields $2^3 = 8$ possible hashes for $2^5 = 32$ files. Hence, at least four different files correspond to the same hash.

Now assume that a cryptographic checksum function computes hashes of 128 bits. The probability of finding a message corresponding to a given hash is $2^{–128}$, but the probability of finding two messages with the same hash (that is, with the value of neither message being constrained) is $2^{–64}$ (see Exercise 20).

How to get the final $2^{-64}$ mathematically?

Answer 1

The question states that the probability of finding a collision is $2^{-64}$. This is incorrect. The probability depends on the number of available messages, as we will see below.

If you take two random messages, the probability of them having the same $m$-bit hash is $2^{-m}$. So you're going to have to try around $2^{m}$ pairs before you find a collision.

But you can do this without generating $2^m$ messages.

Consider this:

With $n$ different messages, you can generate $C(n,2)$ different pairs of messages

$C(n,2) = \dfrac{n!}{2(n-2)!}$

$= \dfrac{n(n-1)(n-2)!}{2(n-2)!}$

$=\dfrac{n(n-1)}{2}$

$=\dfrac{n^2 -n}{2}$

So with $n$ different messages, we can generate $\dfrac{n^2 - n}{2}$ unique pairs.

Now we need to figure out how many messages are required to have a good probability ($\geq$50%) of finding two colliding messages.

$\dfrac{\frac{n^2 - n}{2}}{2^m} \geq 0.5$

$\dfrac{n^2 - n}{2^{m+1}} \geq 0.5$

$n^2 - n \geq 2^m$

So it turns out we need just over $2^{m/2}$ messages. This is usually simplified to exactly $2^{m/2}$ since we're dealing with such large numbers that the difference is negligible. There are other ways of calculating it, but they all work out to the same approximation (see Birthday Problem, Birthday Attack).