Cryptography: Theory and Practice:Hash Functions | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

7.9 Notes and References

The discrete log hash function described in Section 7.4 is due to Chaum, van Heijst, and Pfitzmann [CvHP92]. A hash function that can be proved secure provided that a composite integer n cannot be factored is given by Gibson [GIB91] (see Exercise 7.4 for a description of this scheme).

The material on extending hash functions in Section 7.5 is based on Damgård [DA90]. Similar methods were discovered by Merkle [ME90].

For infomation concerning the construction of hash functions from private-key cryptosystems, see Preneel, Govaerts, and Vandewalle [PGV94].

The MD4 hashing algorithm was presented in Rivest [RI91], and the Secure Hash Standard is described in [NBS93]. An attack against two of the three rounds of MD4 is given by den Boer and Bossalaers [DBB92]. Other recently proposed hash functions include N-hash [MOI90] and Snefru [ME90A].

Timestamping is discussed in Haber and Stornetta [HS91] and Bayer, Haber, and Stornetta [BHS93].

A thorough survey of hashing techniques can be found in Preneel, Govaerts, and Vandewalle [PGV93].

Exercises

7.1 Suppose h : X → Y is a hash function. For any y ∈ Y, let

and denote s_y = |h^-1(y)|. Define

Note that N counts the number of unordered pairs in X that collide under h. Answer the following:

(a) Prove that

so the mean of the s_y ’s is

(b) Prove that

(c) Prove that

Figure 7.13 Hashing 4m bits to m bits

(d) Using the result proved in part (c), prove that

Further, show that equality is attained if and only if

for every y ∈ Y.

7.2 As in Exercise 7.1, suppose h : X → Y is a hash function, and let

for any y ∈ Y. Let ∈ denote the probability that h(x₁) = h(x₂), where x₁ and x₂ are random (not necessarily distinct) elements of X. Prove that

with equality if and only if

for every y ∈ Y.

7.3 Suppose p = 15083, α = 154 and β = 2307 in the Chaum-van Heijst-Pfitzmann Hash Function. Given the collision

compute log_α β.

7.4 Suppose n = pq, where p and q are two (secret) distinct large primes such that p = 2p₁ + 1 and q = 2q₁ + 1, where p₁ and q₁ are prime. Suppose that α is an element of order 2p₁q₁ in

(this is the largest order of any element in

). Define a hash function h : {1,...,n²} →

by the rule h(x) = α^x mod n.

Now, suppose that n = 603241 and α = 11 are used to define a hash function h of this type. Suppose that we are given three collisions for h: h(1294755) = h(80115359) = h(52738737). Use this information to factor n.

7.5 Suppose h₁ :

is a strongly collision-free hash function.

(a) Define h₂ :

as in Figure 7.13. Prove that h₂ is strongly collision-free.

(b) For an integer i ≥ 2, define a hash function h_i :

recursively from h_i-1, as indicated in Figure 7.14. Prove that h_i is strongly collision-free.

7.6 Using the (original) expansion function of the SHS, Equation 7.1, express each of X[16],..., X[79] in terms of X[0],..., X[15]. Now, for each pair X[i], X[j],

Figure 7.14 Hashing 2ⁱ m bits to m bits

where 1 ≤ i < j ≤ 15, use a computer program to determine λ_ij, which denotes the number of X[k]’s (16 ≤ k ≤ 79) such that X[i] and X[j] both occur in the expression for X[k]. What is the range of values λ_ij?

Table of Contents