Cryptography: Theory and Practice:Hash Functions

cryptography: theory and practice 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

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 (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α β.

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 mt + 1. We will use h to construct a strongly collision-free hash function h* : , where

We first consider the situation where mt + 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 ≤ dm - 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* (mt + 2)

Denote

Observe that yk is formed from xk by padding on the right with d zeroes, so that all the blocks yi (1 ≤ ik) 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 xx′. 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net