Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
THEOREM 7.3
Suppose h : is a strongly collision-free hash function, where m ≥ t + 2. Then the function h* : , as constructed in Figure 7.4, is a strongly collision-free hash function.
PROOF Suppose that we can find x ≠ x′ such that h*(x) = h*(x′). Given such a pair, we will show how we can find a collision for h in polynomial time. Since h is assumed to be strongly collision-free, we will obtain a contradiction, and thus h* will be proved to be strongly collision-free.
Denote
and
where x and x′ are padded with d and d′ 0s, respectively, in step 2. Denote the values computed in steps 4 and 5 by g1,...,gk+1 and , respectively.
We identify two cases, depending on whether or not |x| ≡ |x′| (mod m-t-1).
Here d ≠ d′ and . We have
which is a collision for h since .
It is convenient to split this into two subcases:
Here we have and . We begin as in case 1:
If , then we find a collision for h, so assume . Then we have
Either we find a collision for h, or and . Assuming we do not find a collision, we continue working backwards, until finally we obtain
If , then we find a collision for h, so we assume . But then for 1 ≤ i ≤ k + 1, so y(x) = y(x′). But this implies x = x′ since the mapping is an injection. Since we assumed x ≠ x′, we have a contradiction.
Figure 7.5 Extending a hash function h to h* (m = t + 1)
Without loss of generality, assume |x′| > |x|, so . This case proceeds in a similar fashion as case 2a. Assuming we find no collisions for h, we eventually reach the situation where
But the (t + 1)st bit of 0t+1 || y1 is a 0 and the (t + 1)st bit of is a 1. So we find a collision for h.
Since we have considered all possible cases, we have the desired conclusion.
The construction of Figure 7.4 can be used only when m ≥ t + 2. Lets now look at the situation where m = t + 1. We need to use a different construction for h*. As before, suppose |x| = n > m. We first encode x in a special way. This will be done using the function f defined as follows:
The algorithm to construct h* (x) is presented in Figure 7.5.
The encoding , defined in step 1, satisfies two important properties:
THEOREM 7.4
Suppose h : is a strongly collision-free hash function. Then the function h* : , as constructed in Figure 7.5, is a strongly collision-free hash function.
PROOF Suppose that we can find x ≠ x′ such that h* (x) = h* (x′). Denote
and
We consider two cases.
As in Theorem 7.3, either we find a collision for h, or we obtain y = y′. But this implies x = x′, a contradiction.
Without loss of generality, assume . This case proceeds in a similar fashion. Assuming we find no collisions for h, we have the following sequence of equalities:
But this contradicts the postfix-free property stated above.
We conclude that h* is collision-free.
We summarize the two constructions of in this section, and the number of applications of h needed to compute h*, in the following theorem.
THEOREM 7.5
Suppose h : is a strongly collision-free hash function, where m ≥ t + 1. Then there exists a strongly collision-free hash function
The number of times h is computed in the evaluation of h* is at most
where |x| = n.
So far, the methods we have described lead to hash functions that are probably too slow to be useful in practice. Another approach is to use an existing private-key cryptosystem to construct a hash function. Let us suppose that is a computationally secure cryptosystem. For convenience, let us assume also that . Here we should have n ≥ 128, say, in order to prevent birthday attacks. This precludes using DES (as does the fact that the key length of DES is different from the plaintext length).
Suppose we are given a bitstring
where . (If the number of bits in x is not a multiple of n, then it will be necessary to pad x in some way, such as was done in Section 7.5. For simplicity, we will ignore this now.)
The basic idea is to begin with a fixed initial value g0 = IV, and then construct g1,...,gk in order by a rule of the form
where f is a function that incorporates the encryption function of our cryptosystem. Finally, define the message digest h(x) = gk.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC