This birthday attack imposes a lower bound on the sizes of message digests. A 40-bit message digest would be very insecure, since a collision could be found with probability 1/2 with just over 2²⁰ (about a million) random hashes. It is usually suggested that the minimum acceptable size of a message digest is 128 bits (the birthday attack will require over 2⁶⁴ hashes in this case). The choice of a 160-bit message digest for use in the DSS was undoubtedly motivated by these considerations.

Figure 7.3  Chaum-van Heijst-Pfitzmann Hash Function

7.4 A Discrete Log Hash Function

In this section, we describe a hash function, due to Chaum, van Heijst, and Pfitzmann, that will be secure provided a particular discrete logarithm cannot be computed. This hash function is not fast enough to be of practical use, but it is conceptually simple and provides a nice example of a hash function that can be proved secure under a reasonable computational assumption. The Chaum-van Heijst-Pfitzmann Hash Function is presented in Figure 7.3. We now prove a theorem concerning the security of this hash function.

THEOREM 7.2

Given one collision for the Chaum-van Heijst-Pfitzmann Hash Function h, the discrete logarithm log_α β can be computed efficiently.

PROOF  Suppose we are given a collision

where (x₁, x₂) ≠ (x₃, x₄). So we have the following congruence:

or

Denote

Since p - 1 = 2q and q is prime, it must be the case that d ∈ {1,2,q,p - 1}. Hence, we have four possibilities for d, which we will consider in turn.

First, suppose that d = 1. Then let

We have that

so we can compute the discrete logarithm log_α β as follows:

Next, suppose that d = 2. Since p - 1 = 2q where q is odd, we must have gcd(x₄ - x₂, q) = 1. Let

Now

for some integer k, so we have

since

So we have

It follows that

or

We can easily test which of these two possibilities is the correct one. Hence, as in the case d = 1, we have calculated the discrete logarithm log_α β.

The next possibility is that d = q. But

and

so

So it is impossible that gcd(x₄ - x₂,p - 1) = q; in other words, this case does not arise.

The final possibility is that d = p - 1. This happens only if x₂ = x₄. But then we have

so

and x₁ = x₃. Thus (x₂, x₂) = (x₃, x₄), a contradiction. So this case is not possible, either.

Since we have considered all possible values for d, we conclude that the hash function h is strongly collision-free provided that it is infeasible to compute the discrete logarithm log_α β in .

We illustrate the result of the above theorem with an example.

Example 7.1

Suppose p = 12347 (so q = 6173), α = 2 and β = 8461. Suppose we are given the collision

Thus x₁ = 5692, x₂ = 144, x₃ = 212 and x₄ = 4214. Now, gcd (x₄ - x₂, p -1) = 2, so we begin by computing

Next, we compute

Now it is the case that log_α β ∈ {y′, y′ + q mod (p - 1)}. Since

we conclude that

As a check, we can verify that

Hence, we have determined log_α β.

7.5 Extending Hash Functions

So far, we have considered hash functions with a finite domain. We now study how a strongly collision-free hash function with a finite domain can be extended to a strongly collision-free hash function with an infinite domain. This will enable us to sign messages of arbitrary length.

Suppose h : is a strongly collision-free hash function, where m ≥ t + 1. We will use h to construct a strongly collision-free hash function h* : , where

We first consider the situation where m ≥ t + 2.

We will think of elements of X as bit-strings. |x| denotes the length of x (i.e., the number of bits in x), and x || y denotes the concatenation of the bit-strings x and y. Suppose |x| = n > m. We can express x as the concatenation

where

and

where 0 ≤ d ≤ m - t - 2. Hence, we have that

We define h* (x) by the algorithm presented in Figure 7.4.

Figure 7.4  Extending a hash function h to h* (m ≥ t + 2)

Denote

Observe that y_k is formed from x_k by padding on the right with d zeroes, so that all the blocks y_i (1 ≤ i ≤ k) are of length m - t - 1. Also, in step 3, y_k+1 should be padded on the left with zeroes so that |y_k+1| = m - t - 1.

In order to hash x, we first construct y(x), and then “process” the blocks y₁, y₂,...,y_k+1 in a particular fashion. It is important that y(x) ≠ y(x′) whenever x ≠ x′. In fact, y_k+1 is defined in such a way that the mapping will be an injection.

The following theorem proves that h* is secure provided that h is secure.