Sebery J.Cryptography.An introduction to computer security.1989

6.3 Serial and Parallel Hashing

The design of hash functions with arbitrarily long inputs poses some diÆculties related to their implementation and evaluation. Arbitrarily long messages can be compressed using a xed input-size hash function by applying two general methods:

{ serial and { parallel.

The serial method [120] (also called by Merkle meta method [342]) applies the

The result d is the digest of the whole message m. Damgard [120] proved that the hashing induced by the serial method is collision resistant if the underlyingxed input-size hash function h : 2n ! n is collision resistant.

The parallel method is illustrated in Figure 6.4. The hashing in this method starts from splitting the message m 2 into ` blocks of size n, i.e. m = (m1; m2; : : : ; m`). The last block is padded to the full length if necessary. Assume that the number of blocks is 2k 1 < ` 2k. The number of 2k ` blocks all with zero bits are appended to the message m. The resulting message m~ = (m1; : : : ; m`; : : : ; m2k ) is processed as follows:

h1i = h(m2i 1; m2i) for i = 1; : : : ; 2k 1

h

d

Fig. 6.4. Parallel hashing

hji = h(hj2i 11; hj2i 1) for i = 1; : : : ; 2k i and j = 2; : : : ; k 1 (6.3) d(m) = h(hk1 1; hk2 1)

The nal result of hashing is d(m). Again Damgard [120] proved that the parallel hashing is collision resistant if the underlying xed input-size hash function h : 2n ! n is collision resistant.

Needless to say that parallel hashing is faster than the serial one as the layers of intermediate digests can be generated independently. Also the extra blocks padded with zeros can be preprocessed so their digests enter the hashing process when needed.

6.4 Theoretic Constructions

It is interesting to investigate the relation of hash functions to other cryptographic primitives such as one-way functions (including one-way permutations), signature schemes, and pseudorandom bit generators. The main result in this area was obtained by Rompel [433] who proved that universal one-way hash functions can be constructed from any one-way function.

The notion of one-way function is central in theoretical computer science. It is the basic cryptographic primitive which can be used to construct other cryptographic primitives. Intuitively, a one-way function f is a family of instance

functions fn indexed by the size of the function domain. The computation of y = fn(x) is easy, while nding the preimage x knowing y = fn(x) is diÆcult. Formally, the instance functions are

fn : n ! `(n)

where `(n) is a polynomial in n. The family of functions is a collection f = ffn j n 2 Ng. The family f is said to be polynomially computable if the evaluation of fn(x); x 2 n can be done in time O(nt) for some t 2 N.

De nition 19. Let the family f = ffn j n 2 Ng be polynomially computable. We say that f is one-way function if for each probabilistic polynomial time algorithm A, for each polynomial and for all suÆciently large n, the probability

where x is chosen randomly and uniformly from the set n.

Hash functions can now be formally de ned. For any index n, there is a collection of hash functions Hn : `(n) ! n where `(n) is a polynomial in n. The family H of hash functions is H = fHn j n 2 Ng. The family H is accessible if there is a probabilistic polynomial time algorithm that on input n 2 N returns a description of h 2 Hn chosen randomly and uniformly from all instance functions of Hn. The family H is polynomially computable if there is a polynomial time algorithm that evaluates any function h 2 H.

Let F be a collision nder, i.e. a probabilistic polynomial time algorithm F

and h(x) = h(y)). The universal one-way hash function (UOWHF) is de ned as follows.

De nition 20. Let H be a polynomially computable and accessible hash function compressing `(n)-bit input into n-bit output strings and F be a collisionnder. H is a universal one-way hash function if for each F, for each polynomial, and for all suÆciently large n

where x 2 `(n) and h 2R Hn. The probability is computed over all h 2R Hn, x 2 `(n) and the random choice of all nite strings that F could have chosen.

254 6 HASHING

Note that UOWHF is 2nd preimage resistant. The main di erence between UOWHF and OWHF is the way hash function is chosen. In the case of OWHF, the hash function is xed. For UOWHF, the hash function is randomly chosen.

Let R be a probabilistic polynomial time algorithm that on an input h 2 Hn returns either `?' (cannot nd) or a pair of colliding strings x; y. The algorithm R is called the collision-pair nder. The collision resistant hash function is de ned below.

De nition 21. H is a collision resistant hash function if for each R, for each polynomial , and for suÆciently large n

P (R(h) 6=?) < 1 (6.6)

(n)

where h 2R Hn. The probability is computed over all h 2R Hn, and the random choice of all nite strings that R could have chosen.

Naor and Yung [366] introduced the concept of an UOWHF and suggested a construction based on a one-way permutation. In their construction, they took advantage of the universal hash function family with collision accessibility property [523]; see the de nitions given below.

De nition 22. Let G = fg j A ! Bg be a family of functions. G is a strongly universalr hash function family if given any r distinct elements a1; : : : ; ar 2 A,

(#G)

and any r elements b1; : : : ; br 2 B, there are (#B)2 functions that take ai to bi;

i = 1; : : : ; r. Where #G and #B stand for the cardinality of sets G and B, respectively.

De nition 23. A strongly universalr hash function family G has the collision accessibility property if it is possible to generate in polynomial time a function g 2 G that satis es the equations

g(a1) = b1 g(a2) = b2

.

.

.

g(ar ) = br

where a1; : : : ; ar or b1; : : : ; br are given.

An example of strongly universalr family of hash functions with collision accessibility property, is a collection of polynomials of degree r 1 over GF (q).

Naor and Yung showed that the existence of a secure signature scheme reduces to the existence of a UOWHF. They also used the serial method to construct UOWHF, which hashes arbitrary long messages using a UOWHF with axed size input. Their family of UOWHFs is constructed by the composition of a one-way permutation and a family of strongly universal2 hash functions with the collision accessibility property. In Naor and Yung's construction, the oneway permutation provides the one-wayness of the UOWHF. While the strongly universal2 family of hash functions compresses the input. When a member is chosen randomly and uniformly from the family, the output is distributed randomly and uniformly over the output space. The construction is given in the following theorem:

Theorem 26. Let f : n ! n be a one-way permutation and let Gn be a strongly universal2 family Gn : n ! n 1, then Hn = fh = g Æ f j g 2 Gng is

a UOWHF compressing n-bit input strings into (n 1)-bit output strings.

The above construction is not very eÆcient as it compresses a single bit only. This can be improved when a strongly universalt (t > 2) family of hash functions is used.

Zheng, Matsumoto, and Imai [547] de ned a hashing scheme that was based on the composition of a pairwise independent uniformizer and a strongly universal hash function with a quasi-injection one-way function. De Santis and Yung [451] built up a hash function assuming the existence of a one-way function with an almost-known preimage size.

Rompel managed to construct a UOWHF from any one-way function [433]. His construction is rather complicated and elaborate, and a detailed explanation is beyond the scope of this book. However, the idea is to transform any one-way function into a UOWHF through a sequence of complicated procedures. First, the one-way function is transformed into another one-way function such that, for most elements of the domain, it is easy to nd a collision, except for a fraction of them. Next another one-way function is constructed such that, for most of the elements, it is hard to nd a collision. Subsequently, a length increasing one-way function is constructed such that it is almost everywhere hard to nd any collision. Finally this is turned into a UOWHF, which compresses the input such that it is diÆcult to nd a collision.

In some applications, it may be useful to have a hash scheme with an easy tond collection of colliding messages. The calculation of other collisions should

256 6 HASHING

Fig. 6.5. The Rabin hashing scheme

be computationally intractable. The construction given in [545] called sibling intractable function families or SIFF provides hashing with a controlled number of easy-to- nd collisions.

6.5 Hashing Based on Cryptosystems

To minimize the e ort, many designers of hash functions tend to base their schemes on existing encryption algorithms. Hashing is done using the serial method by applying encryption algorithm on blocks of the message. The message block size has to be equal to the input size of the encryption algorithm. If the length of the message is not a multiple of the block size, then the last block is usually padded with some redundant bits. To provide a randomizing element, an initial vector (IV ) is normally used. The vector IV is public. The encryption algorithm is E : K M ! C. The security of such schemes relies on the collision resistance of the underlying encryption algorithm and the immunity of the scheme against the birthday attack and its variants.

Rabin [424] argued that any private-key cryptosystem E : 2n ! n can be used for hashing. The Rabin scheme is depicted in Figure 6.5. First the message is divided into blocks with n bits. Suppose that we wish to hash a message m = (m1; m2; : : : ; m`). The hashing is performed according to

h0 = IV

hi = E(mi; hi 1) for i = 1; 2; : : : ; ` d = h`

where hi are intermediate results of hashing, and d is the nal digest of m. Note that messages mi are used in place of the key for the encryption E. Although the Rabin scheme is simple and elegant, it is susceptible to the birthday and meet-in-the-middle attacks when the size of the hash value is 64 bits. This scheme can be used only if the size of inputs in the encryption algorithm is larger or equal to 128 bits; see Equation (6.1).

Fig. 6.6. The Davies hashing scheme

The meet-in-the-middle attack in the Rabin scheme works because it is possible to reverse hashing by using the decryption function. Winternitz [538] suggested to design a one-way function from a block cryptosystem E. The one-way function

(6.7)

Davies used the one-way function E to design the following hash scheme (Figure 6.6):

h0 = IV

hi = E(mi; hi 1) hi 1 for i = 1; 2; : : : ; ` d = h`

The Davies scheme is immune against the meet-in-the-middle attack but may be subject to attacks based on key collision search [420] and weak keys [414].

Based on the one-way function E , Merkle proposed several schemes [341, 342, 343]. These schemes use DES and produce digests of the size 128 bits. The construction of these schemes follows the serial method. The message to be hashed is rst divided into blocks of 106 bits. Each 106-bit block mi of data is concatenated with the 128-bit block hi 1. The concatenation xi = mi k hi 1 contains 234 bits. Each block xi is further divided into halves, xi1 and xi2. The description of the method is as follows:

h0 = IV

xi = mi k hi 1

hi = E (00 k rst 59 bits offE (100 k xi1)g krst 59 bits offE (101 k xi2)g) k

E (01 k rst 59 bits offE (110 k xi1)g krst 59 bits offE (111 k xi2)g)

258 6 HASHING

In this scheme, E is a one-way function de ned by Equation (6.7) and the strings 00, 01, 100, 101, 110 and 111 have been included to prevent against attacks based on weak keys.

As most encryption algorithms have weak keys and possible colliding keys, the key input of encryption systems E should be used for partial hash values rather than for messages. If we modify the Davies scheme accordingly we get the following scheme:

h0 = IV

hi = E(hi 1; mi) mi for i = 1;2; : : : ; ` d = h`

Another variant used by Miyaguchi, Ohta, and Iwata [349] in their N-hash algorithm applies di erent chaining method hi = E(hi 1; mi) mi hi 1. Two other possible chaining methods are: hi = E(hi 1; mi hi 1) mi hi 1 and hi = E(hi 1; mi hi 1) mi. For discussion of other less secure chaining methods, the reader is referred to [414].

6.6 MD (Message Digest) Family

Hashing algorithms can also be designed from scratch. Typically, it is required the design to be

1.Secure, i.e. collision resistant { this immediately forces the digest to be at least 128 bits long (to prevent the design against the birthday attack and its variants).

2.Fast and easy to implement both in software and hardware.

Feistel permutations can be used as the basic component in the design. Clearly, they need to be modi ed. Let the n-bit input and output be divided into `

B3 = A2; : : : ; B` = A` 1:

Fig. 6.7. A modi ed Feistel permutation

The function fm(A2; : : : ; A`) is indexed by the message m. The hash scheme would employ many rounds each based on the modi ed Feistel permutation. To prevent the birthday attack, the size n 128. If we use 32-bit machines for a software implementation, it is reasonable to assume that r = 32.

Rivest used the above approach to design his MD4 [430] and MD5 [431] hashing algorithms. The other members of MD family are the Secure Hash Algorithm (SHA) also called Secure Hash Standard (SHS) [368], RIPEMD [51], and HAVAL [548]. We will describe MD5, SHA-1, RIPEMD-160, and HAVAL.

6.6.1 MD5

MD5 is a strengthened version of MD4. It compresses 512-bit messages into 128-bit digests using the 128-bit chaining input. A message of arbitrary length is rst appended bit 1 and enough 0s so it is congruent 448 modulo 512. A 64-bit string ` = `1232 + `0, which is the binary representation of the length of the original message, is appended to the padded message (Figure 6.8). Now the message length is a multiple of 512. Hashing is done as in the serial method { block-by-block and each block is 512 bits long.

The hashing of a single message block proceeds as follows. First the message block m is divided into sixteen 32-bit long words so m = (m0; : : : ; m15). The chaining input contains four 32-bit registers (A; B; C; D). They are initialized as

A = 0x67452301;

260 6 HASHING

512 bits

64 bits

Fig. 6.8. Padding of a message

A B C D

Round

1

Round

2

Message m

Round

3

Round

4

A B C D

Fig. 6.9. MD5 hashing algorithm

B = 0xefcdab89;

C = 0x98badcfe;

D = 0x10325476;

where the strings are written in hexadecimal. Next the four rounds of MD5 are executed (Figure 6.9). The four outputs of the last round is added modulo 232