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

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:

1. 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?

migrated from stackoverflow.comOct 31 '14 at 10:49

This question came from our site for professional and enthusiast programmers.

• Study the Birthday attack, that will explain it. – Dan Sep 16 '14 at 1:43
• @Dan's lead's solid - see en.wikipedia.org/wiki/Birthday_attack, particularly "To avoid this attack, the output length of the hash function used for a signature scheme can be chosen large enough so that the birthday attack becomes computationally infeasible, i.e. about twice as many bits as are needed to prevent an ordinary brute-force attack.". – Tony D Sep 16 '14 at 4:20
• Welcome to Cryptography Stack Exchange. It looks like your question is actually to be answered in exercise 20 – the text before it doesn't really explain it. – Paŭlo Ebermann Nov 2 '14 at 20:35
• Your question in the title and in the final sentence of the body don't seem to match. The output of the hash function in the text is 128 bits (answer of the question in the title). The security provided by that output size with regards to collisions is 64 bits even if the output is 128 bits. – Maarten Bodewes Nov 2 '14 at 22:49

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).

• Thanks for your answer, and it's quite an easy way to understand the birthday problem. But I think my question is different from birthday problem. Birthday problem states that what's the probability that "there exist" a collision among n messages to n hashes. While what confuses me is that what's the probability that if you uniformly randomly pick up two messages from a sample space with size of n, there happens to be a collision of their hashes. That is, quoted from your words, If you take two random messages, the probability of them having the same m-bit hash is 2^−m. – Neo Apr 29 '15 at 11:11
• And I do agree with you that the probability from the book is wrong. My way to think this question is that there are 2^m hash values, and the probability of one message was hashed into a specific hash value is 2^-m. Thus the probability of uniformly randomly picking up two messages and sharing the same hash value is 2^m * ( 2^-m * 2^-m) = 2^-m. Is it right? – Neo Apr 29 '15 at 11:33
• I don't understand where you're getting 2^m * ( 2^-m * 2^-m) from. But you are correct that the probability of selecting two random hashes with the same value is 2^-m. – user13741 Apr 29 '15 at 17:12