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

272 6 HASHING

D in 128 bits

D out

Fig. 6.16. General scheme of HAVAL

Table 6.1. Message word processing order

cation is to create 3 \independent" variants of HAVAL depending on the chosen

number of passes. The permutations are shown in Table 6.2. HAVAL uses the chaining vector D = (D0; : : : ; D7) 2 256, where Di is a 32-bit word. It applies

16 Feistel permutations in each pass. Pass 1 (Figure 6.17)

x0 x1 x2 x3 x4 x5 x6

3;1 x4 x2 x6 x5 x3 x0 x13;2 x6 x3 x5 x0 x1 x2 x43;3 x0 x5 x4 x3 x2 x1 x6

4;1 x0 x3 x5 x4 x1 x6 x24;2 x4 x6 x1 x0 x2 x5 x34;3 x5 x2 x0 x6 x3 x4 x14;4 x3 x1 x2 x5 x0 x4 x6

5;1 x6 x2 x5 x0 x1 x4 x35;2 x5 x4 x3 x0 x1 x2 x65;3 x5 x1 x3 x4 x0 x6 x25;4 x6 x4 x0 x2 x3 x5 x15;5 x1 x3 x4 x6 x0 x5 x2

Table 6.2. HAVAL permutations

>>

+

R

Fig. 6.17. A single pass in HAVAL

(1)Let Ti = Di (i = 0; : : : ; 7)

(2)For j = 0; : : : ; 15

8 F1 Æ 3;1(T0; T1; T2; T3; T4; T5; T6) if PASS=3, P = <> F1 Æ 4;1(T0; T1; T2; T3; T4; T5; T6) if PASS=4, >: F1 Æ 5;1(T0; T1; T2; T3; T4; T5; T6) if PASS=5,

R = (P 7) + (T7 11) + mj;

274 6 HASHING

T1 = T0; T2 = T1; T3 = T2; T4 = T3;

T5 = T4; T6 = T5; T7 = T6; T0 = R;

where (A s) means rotation of A by s positions to the right. The addition + is modulo 232.

Pass 2.

(1)The sequence T0; : : : ; T7 comes from Pass 1.

(2)For j = 0; : : : ; 15, repeat the following:

8 F2 Æ 3;2(T0; T1; T2; T3; T4; T5; T6) if PASS=3; P = <> F2 Æ 4;2(T0; T1; T2; T3; T4; T5; T6) if PASS=4; >: F2 Æ 5;2(T0; T1; T2; T3; T4; T5; T6) if PASS=5; R = (P 7) + (T7 11) + mord2(j) + 2;j; T1 = T0; T2 = T1; T3 = T2; T4 = T3;

T5 = T4; T6 = T5; T7 = T6; T0 = R;

where = ( 2;0; : : : 2;15) are constants generated from the fraction part of is the message word de ned by Table 6.1.

Pass 3.

(1)The sequence T0; : : : ; T7 comes from Pass 2.

(2)For j = 0; : : : ; 15, repeat the following:

8 F3 Æ 3;3(T0; T1; T2; T3; T4; T5; T6) if PASS=3, P = <> F3 Æ 4;3(T0; T1; T2; T3; T4; T5; T6) if PASS=4, >: F3 Æ 5;3(T0; T1; T2; T3; T4; T5; T6) if PASS=5,

R = (P 7) + (T7 11) + mord3(j) + 3;j; T1 = T0; T2 = T1; T3 = T2; T4 = T3; T5 = T4; T6 = T5; T7 = T6; T0 = R;

where = ( 3;0; : : : 3;15) are constants generated from the fraction part of is the message word de ned by Table 6.1.

Pass 4.

(1)The sequence T0; : : : ; T7 comes from Pass 3.

(2)For j = 0; : : : ; 15, repeat the following:

P = (F4 Æ 4;4(T0; T1; T2; T3; T4; T5; T6) if PASS=4,

F4 Æ 5;4(T0; T1; T2; T3; T4; T5; T6) if PASS=5,

R = (P 7) + (T7 11) + mord4(j) + 4;j;

T1 = T0; T2 = T1; T3 = T2; T4 = T3;

T5 = T4; T6 = T5; T7 = T6; T0 = R;

where = ( 4;0; : : : 4;15) are constants generated from the fraction part ofand mord4(j) is the message word de ned by Table 6.1.

Pass 5.

(1)The sequence T0; : : : ; T7 comes from Pass 4.

(2)For j = 0; : : : ; 15, repeat the following:

P = F5 Æ 5;5 (T0; T1; T2; T3; T4; T5; T6); R = (P 7) + (T7 11) + mord5(j) + 5;j; T1 = T0; T2 = T1 ; T3 = T2; T4 = T3; T5 = T4; T6 = T5; T7 = T6; T0 = R;

where = ( 5;0; : : : 5;15) are constants generated from the fraction part ofand mord5(j) is the message word de ned by Table 6.1.

After hashing, the sequence T is shortened to the requested length of digest (for details see [548]). HAVAL is believed to be stronger than MD5. A cryptanalysis of reduced version of HAVAL can be found in [271].

6.6.5 Hashing Based on Intractable Problems

Gibson [200] based his hashing scheme on the factorization problem. Assume

where g is a generator of the cyclic group ZN . The modulus N and the generator g are public. Note that if a collision can be found, then N can be factored. Let

276 6 HASHING

group ZN and the factors can be found (see Section 4.2.4). On the other hand, knowing factors of N it is easy to produce collisions.

An example of hashing whose collision-freeness relies on intractability of the discrete logarithm problem was given by Chaum, van Heijst, and P tzmann in

The generators g1, g2 and the modulus N are public. It can be proved that if a collision is found, then the corresponding instance of discrete logarithm can be solved [497].

Knapsack can also be used for hashing. The rst such scheme reported in [120] was broken in [74]. Impagliazzo and Naor proposed the scheme that is theoretically sound. The scheme is de ned by h : n ! ` where obviously ` < n. To design a scheme, n integers ai (i = 1; : : : ; n) are chosen randomly

a2Sm

Tillich and Zemor [508] designed a hash scheme based on SL(2; 2n) that is the group of two-dimensional unimodular matrices with entries in the Galoiseld GF (2n). In other words, elements of SL(2; 2n) are matrices

"a b # c d

whose determinant is equal to 1 and a; b; c; d 2 GF (2n). The hash function h operates on arbitrarily long binary messages and returns an element of SL(2; 2n) so h : ! SL(2; 2n). The core elements of the hash scheme are two public elements of SL(2; 2n), namely,

An r-bit message m = (b1; : : : ; br) is rst converted into the corresponding sequence of As and Bs according to the function :

0 to A and 1 to B. The digest of m is:

Finding collisions in the function h is equivalent to the diÆculty of nding short factorizations in the groups SL(2; 2n), which is known to be intractable. To be collision free, the hash function has to be determined for n in the range 130{ 170. If n < 130, the security may be compromised. On the other hand, schemes with n > 170 become slow. To do computations in GF (2n), the modulus { an irreducible polynomial p(x) (over GF (2)) of degree n { is chosen at random and made public.

It was shown in [83] that a careless selection of n or p(x) can result in an instance of the scheme, which is not collision free. The order of the group

6.7 Keyed Hashing

A message authentication code (MAC) is a relative short string which is attached to a message to enable a receiver to decide whether the message comes from the original sender. Clearly, to perform this role, the MAC must match the message and the sender. As the message can be long and the MAC is relatively short, it must directly or indirectly employ hashing. Additionally, the pair of communicating parties is uniquely identi ed by a secret key shared by them. To produce or verify a MAC, the parties must know the message and the shared key. An adversary, on the other hand, knows the message only. Application of MACs allows to create authentication channel where the contents of messages is public but the message source can be veri ed (the sender must share the same secret key with the receiver). Other names for MAC include integrity check value, cryptographic checksum, or authentication tag.

Keyed hash schemes produce digests that depend on not only messages but also secret keys, which are shared between the sender and receiver. Consequently, hashing can be done only by the holders of the secret key.

Given a family of hash functions:

278 6 HASHING

Any instance function hk is indexed by a secret key k shared by two parties. A

f j 2 Ng

keyed hash function H = Hn n is collision resistant if

1.Any instance function hk can be applied for messages of arbitrary length.

2.The function H is a trapdoor one-way function, that is

{Given a key k and message m, it is easy (in polynomial time) to compute

3.Without the knowledge of k, it is computationally diÆcult to nd a collision,

that is, two distinct messages m; m0 2 with the same digest d = hk(m) = hk (m0) (even if given a MAC oracle).

Hashing arbitrarily long messages can be done using either the serial or parallel methods (see Section 6.3). For a given n, the family of instance hash functions

For an ideal collision resistant keyed hashing scheme, nding a collision could be done by applying either the exhaustive search through the key space which takes on the average 2n 1 operations, or by employing a variant of the birthday attack which takes O(2n=2) steps.

6.7.1 Early MACs

First implementations of keyed hashing were based on encryption algorithms in CBC or CFB modes. An example of keyed hashing in CBC mode is given in Figure 6.18. For a message m = (m1; : : : ; mr), hashing involves r iterations and

h0 = IV

hi = Ek(hi 1 mi); i = 1; : : : ; r 1 d = Ek(hr 1 mr)

where IV is an initial value, Ek encryption function, and d digest.

The Message Authenticator Algorithm (MAA) is probably the rst dedicated MAC which is also an ISO 8731-2 standard. MAA takes a message

m = (m1; : : : :m`) (mi is a 32-bit word) and a 64-bit key k = (k1; : : : ; k8) and produces 32-bit digest.

MAA algorithm { produces 32-bit digests.

Key expansion: Take the key k and create six 32-bit words (A; B; C; D; E; F ). Bytes 0x00 and 0xff in k are replaced according to

The pairs (A; B), (C; D) and (E; F ) are checked whether they contain 0x00 or 0xff. If so, they are replaced as shown above.

Message processing: Each block mi of the message m is subject to the following transformations

h=A; g=B; v=C;

for i from 1 to ` f

280 6 HASHING

v=fv 1g; u=fv Eg;

t1=fh mig 1fffg mig+ug OR 0x02040801g AND 0xbfef7fdfg; gt2=fg mig 2fffh mig+ug OR 0x00804021g AND 0x7dfefbffg;

where i stands for multiplication modulo (232 i), + is addition modulo 232. The nal result is h = h g.

6.7.2 MACs from Keyless Hashing

Keyless hashing such as MD5 seems to be an attractive option of MAC generation. Tsudik [512] suggested to use a hashing algorithm which compresses arbitrary long messages into n-bit digests under control of n-bit chaining blocks so H : n ! n. The hash scheme H uses a hashing function (such as MD5) h : ` n ! n applied in the serial method. H also pads the message and appends the length so the resulting message is a multiple of `. For instance in MD5 ` = 512 and n = 128 bits. For a given message m 2 , keyed hashing can be built on the top of H using

{Secret pre x k 2 `. The digest is d = H(k k m).

{Secret suÆx k 2 `. The digest is d = H(m k k).

{Secret envelop k1; k2 2 `. the digest is d = MD(k1 k m k k2).

where k stands for concatenation. The secret pre x is equivalent to the keyless hashing with a secret initial value. For both secret pre x and suÆx, if the underlying hash algorithm is not collision resistant, the keyed hashing scheme is not collision resistant either [11].

Consider the secret pre x MAC. Let an attacker know a pair the message m and its MAC of the form H(k k m). Clearly, she can produce arbitrarily many valid MACs for the message (m; m0) with H(k k (m; m0)) where m0 is an arbitrary message selected by the attacker. Even if the padding of the message includes the length of the message, the security of MACs is determined by the collision resistance of the hash algorithm H rather than the length of the secret pre x.

Again, security of the secret suÆx MAC is determined by the length of digest rather than by the length of the secret. The attacker knows the message m and the MAC of the form H(m k k). If the hash function is not collision resistant,