The three different variables can take on one of four possible values, so there are 64 total schemes of this type. Bart Preneel studied them all [1262].

Fifteen are trivially weak because the result does not depend on one of the inputs. Thirty-seven are insecure for more subtle reasons. Table 18.1 lists the 12 secure schemes remaining: The first 4 are secure against all attacks (see Figure 18.9) and the last 8 are secure against all but a fixed-point attack, which is not really worth worrying about.

The first scheme was described in [1028]. The third scheme was described in [1555, 1105, 1106] and was proposed as an ISO standard [766]. The fifth scheme was proposed by Carl Meyer, but is commonly called Davies-Meyer in the literature [1606, 1607, 434, 1028]. The tenth scheme was proposed as a hash-function mode for LOKI [273].

The first, second, third, fourth, ninth, and eleventh schemes have a hash rate of 1; the key length equals the block length. The others have a rate of k/n, where k is the key length. This means that if the key length is shorter than the block length, then the message block can only be the length of the key. It is not recommended that the message block be longer than the key length, even if the encryption algorithm’s key length is longer than the block length.

If the block algorithm has a DES-like complementation property and DES-like weak keys, there is an additional attack that is possible against all 12 schemes. The attack isn’t very dangerous and not really worth worrying about. However, you can solve it by fixing bits 2 and 3 of the key to “01” or “10” [1081, 1107]. Of course, this reduces the length of k from 56 bits to 54 bits (in DES, for example) and decreases the hash rate.

The following schemes, proposed in the literature, have been shown to be insecure.

Figure 18.9  The four secure hash functions where the block length equals the hash size.

This scheme [1282] was broken in [369]:

H_i = E_Mi(H_{i - 1})

Davies and Price proposed a variant which cycles the entire message through the algorithm twice [432, 433]. Coppersmith’s attack works on this variant with not much larger computational requirements [369].

Another scheme [432, 458] was shown insecure in [1606]:

Hi = E_Mi⊕ _{Hi- 1} (H_{i- 1})

This scheme was shown insecure in [1028] (c is a constant):

H_i = E_c (M_i ⊕ H_{i - 1}) ⊕ M_i ⊕ H_{i- 1}

Modified Davies-Meyer

Lai and Massey modified the Davies-Meyer technique to work with the IDEA cipher [930, 925]. IDEA has a 64-bit block size and 128-bit key size. Their scheme is

H_o = I_H, where I_H is a random initial value

H_i = E_{Hi- 1,Mi}(H_{i- 1})

This function hashes the message in blocks of 64 bits and produces a 64-bit hash value (See Figure 18.10).

No known attack on this scheme is easier than brute force.

Figure 18.10  Modified Davies-Meyer.

Preneel-Bosselaers-Govaerts-Vandewalle

This hash function, first proposed in [1266], produces a hash value twice the block length of the encryption algorithm: A 64-bit algorithm produces a 128-bit hash.

With a 64-bit block algorithm, the scheme produces two 64-bit hash values, G_i and H_i, which are concatenated to produce the 128-bit hash. With most block algorithms, the block size is 64 bits. Two adjacent message blocks, L_i and R_i, each the size of the block length, are hashed together.

G₀ = I_G, where I_G is a random initial value

H₀ = I_H, where I_H is another random initial value

G_i = E_Li⊕ H_{i- 1}(R_i ⊕ G_{i- 1} ) ⊕ R_i ⊕ G_{i- 1} ⊕ H_{i- 1}

H_i = E_Li⊕ R_i(H_{i- 1} ⊕ G_{i- 1} ) ⊕ L_i ⊕ G_{i- 1} ⊕ H_{i- 1}

Lai demonstrates attacks against this scheme that, in some instances, make the birthday attack trivially solvable [925, 926]. Preneel [1262] and Coppersmith [372] also have successful attacks against this scheme. Do not use it.

Quisquater-Girault

This scheme, first proposed in [1279], generates a hash that is twice the block length and has a hash rate of 1. It has two hash values, G_i and H_i, and two blocks, L_i and R_i, are hashed together.

G₀ = I_G, where I_G is a random initial value

H₀ = I_H, where I_H is another random initial value

W_i = E_Li(G_{i - 1} ⊕ R_i) ⊕ R_i ⊕ H_{i- 1}

G_i = E_Ri(W_i ⊕ L_i) ⊕ G_{i- 1} ⊕ H_{i- 1} ⊕ L_i

H_i = W_i ⊕ G_{i- 1}