Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
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 220 (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 264 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
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 (x1, x2) ≠ (x3, x4). 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(x4 - x2, 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(x4 - x2,p - 1) = q; in other words, this case does not arise.
The final possibility is that d = p - 1. This happens only if x2 = x4. But then we have
so
and x1 = x3. Thus (x2, x2) = (x3, x4), 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 x1 = 5692, x2 = 144, x3 = 212 and x4 = 4214. Now, gcd (x4 - x2, 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α β.
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 yk is formed from xk by padding on the right with d zeroes, so that all the blocks yi (1 ≤ i ≤ k) are of length m - t - 1. Also, in step 3, yk+1 should be padded on the left with zeroes so that |yk+1| = m - t - 1.
In order to hash x, we first construct y(x), and then process the blocks y1, y2,...,yk+1 in a particular fashion. It is important that y(x) ≠ y(x′) whenever x ≠ x′. In fact, yk+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.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC