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

262 6 HASHING

jmj; s; t) = (B + ((A + G(B; C; D) + mj + t) s); B; C; D) ;

HH(A; B; C; d j mj; s; t) = (B + ((A + H(B; C; D) + mj + t) s); B; C; D) ; KK(A; B; C; D j mj; s; t) = (B + ((A + K(B; C; D) + mj + t) s); B; C; D) ;

where (A; B; C; D) 2 128 is an input while (mj; s; t) are current parameters that determine the form of the permutation and + stands for addition modulo 232. The rst parameter is the current message block mj; j = 0; : : : ; 15. The second parameter s speci es the number of positions in the rotation. The third parameter t is a constant. (A s) means that the binary string A is rotated to the left by s positions. The hashing proceeds through the four rounds:

Round 1:

Round 2:

MD5 was meant to be fast on machines with a little-endian architecture. By the way, for a 32-bit word (a0; : : : ; a31), a machine with little-endian architecture

converts the string into integer a31231+: : :+a1 2+a0. In big-endian architecture, the same integer is a0231 + : : : + a30 2 + a31.

As MD4 is a weaker version of MD5, it was apparent that the main e ort will be concentrated around analysis of MD4. den Boer and Bosselaers [135] successfully analyzed two last rounds of MD4. Merkle successfully attacked therst two rounds of MD4. In 1996 Dobbertin [156] broke the whole MD4. He also extended his attack on MD5 [157] and showed that MD5 is not collision resistant.

6.6.2 SHA-1

SHA-1 is closely related to MD5 and shares with MD5 many common features. It is a standard recommended by the US National Institute for Standard and Technology (NIST). SHA-1 hashes arbitrarily long messages using the serial method. The message block of 512-bits is compressed into 160-bit digest using a 160-bit chaining input.

SHA-1 main features includes the following:

{Padding is identical to that in MD5 except the length of the original message ` = (`1232 + `0) is appended as 64-bit sequence in the order (`1; `0) (compare

with the Figure 6.8).

{The chaining input is initialized as in MD5 with the additional input E = 0xc3d2e1f0.

{The collection of round functions includes

f (x; y; z) = xy _ xz;

g(x; y; z) = xy _ xz _ yz; h(x; y; z) = x y z:

Denote F; G; and H as the word equivalents of functions f; g; and h, respectively. The function F is used in the rst round (iterations from 0 to 19). The function H is used in the round 2 and 4 (iterations from 20 to 39 and from 60 to 79). The function G is used in the round 3 (iterations 40 to 59).

{The message bu er (X0; : : : ; X79) of 80 words (80 32 bits) is initialized by storing the 512-bit message into rst 16 entries and the remainder words are computed according to

Xj = Xj 3 Xj 8 Xj 14 Xj 16;

for j = 16; : : : ; 79. Note that the word Xj is used in the ith iteration, j = 0; : : : ; 79.

{The jth iteration is based on a Feistel permutation controlled by the message word Xj and the constant t where

80x5a827999 Round 1,

>0x6ed9eba1 Round 2, t = <0x8f 1bbcdc Round 3, >:0xca62c1d6 Round 4.

The Feistel permutation F : 160 ! 160 takes the 5-word input and outputs the 5-word output or

(A; B; C; D; E) := F (A; B; C; D; E);

where indicates the currently employed round function (either F; G, or H). The form of the iteration is as follows (Figure 6.11)

F (A; B; C; D; E) = ( (B; C; D) + Xj + t + E + (A 5); A; (B 30); C; D) ;

266 6 HASHING

A B C D E

X j

<< 30

Fig. 6.11. An iteration in SHA-1

where (A s) stands for rotation s bits to the left and + is addition modulo 232.

Hashing of a single message block runs through 4 rounds each containing 20 iterations as shown in Figure 6.12. More precisely, the round 1 (iterations j = 0; : : : ; 19) applies the function F so

(A; B; C; D; E) := FF (A; B; C; D; E):

The rounds 2 and 4 (iterations j = 20; : : : ; 39;60; : : : ; 79) use the function H. Thus

(A; B; C; D; E) := FH (A; B; C; D; E):

The round 3 (iterations j = 40; : : : ; 59) employ the function G, or (A; B; C; D; E) := FG(A; B; C; D; E):

SHA-1 is believed to be more secure than MD5. Note that the digest space is larger than this o ered by MD5 (note additional word E in the chaining variable).

6.6.3 RIPEMD-160

RIPEMD is an outcome of the European RACE Integrity Primitives evaluation (RIPE) project. RIPEMD-160 is a strengthened version of the RIPEMD algorithm [158]. It applies 5 rounds (instead of 3 in RIPEMD) and the size of digest (and the chaining variable) is 160 bits (instead of 128 bits). Unlike

268 6 HASHING

rst 16 words of the bu er X is initialized to the 16 words of the message (m0; : : : ; m15). So

{ Rounds in the left and right lines apply the following constants:

{ The ith iteration (Feistel permutation) is controlled by a message word M (from either X if the iteration is used in the left line or Y , in the right line); see Figure 6.13. The value

v = (( (B; C; D) + M + A + t) s) + E

is generated and the input (A; B; C; D; E) is transformed according to (A; B; C; D; E) := F(A; B; C; D; E; ; t; s) = (E; v; B; C 10; D);

where the constant t is either t` or tr.

The hashing process is depicted in Figure 6.14. The input vector (initialized to the xed values for the rst message block or taking on digests obtained from the previous message block) is used in both lines of execution. Each line includes 5 rounds each round has 16 iterations. The rounds in the left line of execution apply functions F; G; H; K, and L while the rounds in the right line of execution use functions in the reverse order. Constants t`; tr and the rotation parameters s`; sr are used accordingly. The parameters s` and sr are chosen as follows:

A B C D E M

α t

<< S

<< 10

v

Fig. 6.13. An iteration in RIPEMD-160

6.6.4 HAVAL

HAVAL or a one-way hashing algorithm with variable length of output [548]. It compresses an arbitrarily long message into a digest of the length either 128, 160, 192, 224, or 256 bits. HAVAL allows to trade speed versus security by the optional number of passes: 3 (fast and least secure), 4 (moderate speed and security), and 5 (slowest and highly secure). HAVAL uses a 3-bit VERSION eld which indicates the version number of HAVAL { the current number is 1. A 3-bit PASS eld speci es the number of passes chosen by the user. A 10-bit FPTLEN eld de nes the requested length of the digest. A 64-bit MSGLEN eld is used to store the length of the processed message.

Fig. 6.14. General diagram of RIPEMD-160

Hashing starts from padding. A message is appended bit 1 followed by enough 0s so it becomes congruent 944 modulo 1024. An 80-bit string (VERSION, PASS,FPTLEN,MSGLEN) is appended to the padded message. The resulting message is a multiple of 1024 bits. The hashing proceeds in a block-by-block fashion (Figure 6.15). The folding tailors the length of the digest to the requested one.

A 1024-bit message m is divided into thirty-two 32-bit message blocks (words) so m = (m0; : : : ; m31). The general steps executed in HAVAL are depicted in Figure 6.16. The addition modulo 232 performed on corresponding words, completes the process. Each pass H1; H2; H3; H4, and H5 employs a Boolean function in seven variables. They are

F1(X0; : : : ; X6) = X0 (X0 ^ X1) (X1 ^ X4) (X2 ^ X5) (X3 ^ X6); F2(X0; : : : ; X6) = X0 (X0 ^ X2) (X1 ^ X2) (X1 ^ X4) (X2 ^ X6)

(X3 ^ X5) (X4 ^ X5) (X1 ^ X2 ^ X3) (X2 ^ X4 ^ X5);