ńňđ. 1 |

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 ................................................ 428

One-Way Hash Functions ........................ 428

BACKGROUND ........................................ 428

Length of One-Way Hash Functions ............. 429

Overview of One-Way Hash Functions ......... 430

Figure 18.1 One-way function. ....................... 430

SNEFRU ................................................... 431

Cryptanalysis of Snefru ................................. 431

N-HASH .................................................... 432

Figure 18.2 Outline of N-Hash. ....................... 432

Cryptanalysis N-Hash .................................... 433

Figure 18.3 One processing stage of ............. 433

Figure 18.4 Function f. ................................... 434

MD4 ........................................................... 434

MD5 ........................................................... 435

Description of MD5 ........................................ 435

Figure 18.5 MD5 main loop. ........................... 436

Figure 18.6 One MD5 operation. .................... 437

Security of MD5 ............................................. 439

MD2 ........................................................... 440

SECURE HASH ALGORITHM (SHA) ....... 441

Description SHA ............................................ 441

Figure 18.7 One SHA operation. .................... 443

Security SHA ................................................. 443

RIPE-MD ................................................... 444

HAVAL ....................................................... 444

OTHER ONE-WAY HASH FUNCTIONS ... 445

ONE-WAY HASH FUNCTIONS USING .... 445

Schemes Where the Hash Length Equals ..... 446

Figure 18.8 General hash function where ...... 446

Table 18.1 Secure Hash Functions Where ... 447

Figure 18.9 The four secure hash .................. 448

Modified Davies-Meyer .................................. 448

Figure 18.10 Modified Davies-Meyer. ............ 449

Preneel-Bosselaers-Govaerts-Vandewalle ... 449

Quisquater Girault ......................................... 449

LOKI Double-Block ........................................ 450

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Parallel Davies-Meyer ................................... 450

Tandem and Abreast Davies-Meyer .............. 450

Figure 18.2 1 Tandem Davies-Meyer. ............ 450

MDC-2 and MDC-4 ......................................... 451

Figure 18.12 Abreast Davies-Meyer. .............. 451

Figure 18.13 MDC-2. ...................................... 452

AR Hash Function ......................................... 452

Figure 18.14 MDC-4. ...................................... 453

GOST Hash Function .................................... 453

Other Schemes .............................................. 454

USING PUBLIC-KEY ALGORITHMS ....... 454

CHOOSING A ONE-WAY HASH .............. 454

MESSAGE AUTHENTICATION ................ 454

Table 18.2 Speeds of Some Hash ................ 455

CBC-MAC ...................................................... 455

Message Authenticator Algorithm (MAA) ...... 455

Bidirectional MAC .......................................... 456

Juenemans Methods .................................... 456

RIPE-MAC ..................................................... 456

IBC-Hash ....................................................... 457

One-Way Hash Function MAC ...................... 457

Figure 18.15 Stream cipher MAC. .................. 458

Stream Cipher MAC ...................................... 458

Page 428

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18

CHAPTER

One-Way

Hash Functions

18.1 BACKGROUND

A one-way hash function, H(M), operates on an arbitrary-length pre-image message,

M. It returns a fixed-length hash value, h.

h = H(M), where h is of length m

Many functions can take an arbitrary-length input and return an output of fixed

length, but one-way hash functions have additional characteristics that make them

one-way [ 10651:

Given M, it is easy to compute h.

Given h, it is hard to compute M such that H(M) = h.

Given M, it is hard to find another message, Mâ€™, such that H(M) = H(Mâ€™).

If Mallory could do the hard things, he would undermine the security of every pro-

tocol that uses the one-way hash function. The whole point of the one-way hash

function is to provide a â€śfingerprintâ€ť of M that is unique. If Alice signed M by using

a digital signature algorithm on H(M), and Bob could produce Mâ€™, another message

different from M where H(M) = H(Mâ€™), then Bob could claim that Alice signed Mâ€™.

In some applications, one-wayness is insufficient; we need an additional require-

ment called collision-resistance.

It is hard to find two random messages, M and Mâ€™, such that H(M) = H(Mâ€™).

Remember the birthday attack from Section 7.4? It is not based on finding another

message M: such that H(M) = H(Mâ€™), but based on finding two random messages, M

and Mâ€™, such that H(M) = H(Mâ€™).

Page 429

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18 One-Way Hush Functions

CHAPTER

The following protocol, first described by Gideon Yuval [1635], shows how-if

the previous requirement were not true-Alice could use the birthday attack to

swindle Bob.

(1) Alice prepares two versions of a contract: one is favorable to Bob; the other

bankrupts him.

(2) Alice makes several subtle changes to each document and calculates the

hash value for each. (These changes could be things like: replacing SPACE

with SPACE-BACKSPACE-SPACE, putting a space or two before a carriage

return, and so on. By either making or not making a single change on each

of 32 lines, Alice can easily generate 232different documents.)

(3) Alice compares the hash values for each change in each of the two docu-

ments, looking for a pair that matches. (If the hash function only outputs a

64-bit value, she would usually find a matching pair with 232versions of

each.) She reconstructs the two documents that hash to the same value.

(4) Alice has Bob sign the version of the contract that is favorable to him,

using a protocol in which he only signs the hash value.

(5) At some time in the future, Alice substitutes the contract Bob signed with

the one that he didnâ€™t. Now she can convince an adjudicator that Bob

signed the other contract.

This is a big problem. (One moral is to always make a cosmetic change to any doc-

ument you sign.)

Other similar attacks could be mounted assuming a successful birthday attack.

For example, an adversary could send an automated control system (on a satellite,

perhaps) random message strings with random signature strings. Eventually, one of

those random messages will have a valid signature. The adversary would have no

idea what the command would do, but if his only objective was to tamper with the

satellite, this would do it.

Length of One-Way Hash Functions

Hash functions of 64 bits are just too small to survive a birthday attack. Most

practical one-way hash functions produce 128-bit hashes. This forces anyone

attempting the birthday attack to hash 264random documents to find two that hash

to the same value, not enough for lasting security. NIST, in its Secure Hash Standard

(SHS), uses a 160-bit hash value. This makes the birthday attack even harder, requir-

ing 280random hashes.

The following method has been proposed to generate a longer hash value than a

given hash function produces.

(1) Generate the hash value of a message, using a one-way hash function listed

in this book.

Page 430

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.2 Snefru

(2) Prepend the hash value to the message.

(3) Generate the hash value of the concatenation of the message and the hash

value.

(4) Create a larger hash value consisting of the hash value generated in step (1)

concatenated with the hash value generated in step (3).

(5) Repeat steps (1) through (3) as many times as you wish, concatenating as

you go.

Although this method has never been proved to be either secure or insecure, var-

ious people have some serious reservations about it [ 1262,859].

of One-Way Hash Functions

Oueroiew

Itâ€™s not easy to design a function that accepts an arbitrary-length input, let alone

make it one-way. In the real world, one-way hash functions are built on the idea of

a compression function. This one-way function outputs a hash value of length n

given an input of some larger length m [ 1069,414]. The inputs to the compression

function are a message block and the output of the previous blocks of text (see Fig-

ure 18.1 J. The output is the hash of all blocks up to that point. That is, the hash of

block M, is

hi = f(Mi>hi - 1)

This hash value, along with the next message block, becomes the next input to the

compression function. The hash of the entire message is the hash of the last block.

The pre-image should contain some kind of binary representation of the length of

the entire message. This technique overcomes a potential security problem result-

ing from messages with different lengths possibly hashing to the same value

[ 1069,414]. This technique is sometimes called MD-strengthening [930].

Various researchers have theorized that if the compression function is secure,

then this method of hashing an arbitrary-length pre-image is also secure-but noth-

ing has been proved [ 1138,1070,414].

A lot has been written on the design of one-way hash functions. For more mathe-

matical information, consult [ 1028,793,791,1138,1069,414,91,858,1264]. Bart Pre-

neelâ€™s thesis [1262] is probably the most comprehensive treatment of one-way hash

functions.

ki Figure 18.1 One-way function.

Page 431

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One- Way Hash Functions

18.2 SNEFRU

Snefru is a one-way hash function designed by Ralph Merkle [ 10701. (Snefru, like

Khufu and Khafre, was an Egyptian pharaoh.) Snefru hashes arbitrary-length mes-

sages into either 128-bit or 256-bit values.

First the message is broken into chunks, each 5 12-m in length. (The variable m is

the length of the hash value.) If the output is a 128-bit hash value, then the chunks

are each 384 bits long; if the output is a 256-bit hash value, then the chunks are each

256 bits long.

The heart of the algorithm is function H, which hashes a 5 12-bit value into an m-

bit value. The first m bits of Hâ€™s output are the hash of the block; the rest are dis-

carded. The next block is appended to the hash of the previous block and hashed

again. (The initial block is appended to a string of zeros.) After the last block (if the

message isnâ€™t an integer number of blocks long, zeros are used to pad the last block],

the first 111bits are appended to a binary representation of the length of the message

and hashed one final time.

Function H is based on E, which is a reversible block-cipher function that operates

on 5 12-bit blocks. H is the last m bits of the output of E XORed with the first m bits

of the input of E.

The security of Snefru resides in function E, which randomizes data in several

passes. Each pass is composed of 64 randomizing rounds. In each round a different

byte of the data is used as an input to an S-box; the output word of the S-box is

XORed with two neighboring words of the message. The S-boxes are constructed in

a manner similar to those in Khafre (see Section 13.7). Some rotations are thrown in,

too. Originally Snefru was designed with two passes.

Cryptanalysis of Snefru

Using differential cryptanalysis, Biham and Shamir demonstrated the insecurity

of two-pass Snefru (128-bit hash value) [ 1721. Their attack finds pairs of messages

that hash to the same value within minutes.

On 128-bit Snefru, their attacks work better than brute force for four passes or

less. A birthday attack against Snefru takes 264operations; differential cryptanalysis

can find a pair of messages that hash to the same value in 228.5 operations for three-

pass Snefru and 244.5 operations for four-pass Snefru. Finding a message that hashes

to a given value by brute force requires 21z8operations; differential cryptanalysis

takes 256operations for three-pass Snefru and 2** operations for four-pass Snefru.

Although Biham and Shamir didnâ€™t analyze 256-bit hash values, they extended

their analysis to 224-bit hash values. Compared to a birthday attack that requires

2â€™i2 operations, they can find messages that hash to the same value in 212.5 opera-

tions for two-pass Snefru, 233operations for three-pass Snefru, and Zsl operations for

four-pass Snefru.

Currently, Merkle recommends using Snefru with at least eight passes [1073].

However, with this many passes the algorithm is significantly slower than either

MD5 or SHA.

Page 432

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.3 N-Hash

18.3 N-HASH

N-Hash is an algorithm invented by researchers at Nippon Telephone and Tele-

graph, the same people who invented FEAL, in 1990 [ 1105,1106]. N-Hash uses 128-

bit message blocks, a complicated randomizing function similar to FEALâ€™s, and

produces a 128-bit hash value.

The hash of each 128-bit block is a function of the block and the hash of the pre-

vious block.

Ho = I, where I is a random initial value

H,=g(Mi,Hi-,)OMiOH,-,

The hash of the entire message is the hash of the last message block. The random

initial value, I, can be any value determined by the user (even all zeros).

The function g is a complicated one. Figure 18.2 is an overview of the algorithm.

Initially, the 128-bit hash of the previous message block, Hi _ Ir has its 64-bit left half

EXG : Exchange of left and right half

PS : Processing stage

˜=˜lâ€™14;lllrillA˜˜lldllA˜3llrillA˜4

3;

(II: concatenation) PS

h .OOO...Oinbinary(24bits)

PS

Ajk =4*0â€™-I)+ =1,2,3,4,Ajk :&bitslong)

k(k

Hi =R (bf;,ff-˜)@Mi@ Hi-1

Page 433

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One- Way Hash Functions

and 64-bit right half swapped; it is then XORed with a repeating one/zero pattern (128

bits worth), and then XORed with the current message block, Mi. This value then cas-

cades into N (N = 8 in the figures) processing stages. The other input to the processing

stage is the previous hash value XORed with one of eight binary constant values.

One processing stage is given in Figure 18.3. The message block is broken into

four 32-bit values. The previous hash value is also broken into four 32-bit values.

The function f is given in Figure 18.4. Functions Soand Sr are the same as they were

in FEAL.

&(a,b) = rotate left two bits ((a + b) mod 256)

Sl(a,b) = rotate left two bits ((a + b + 1) mod 256)

The output of one processing stage becomes the input to the next processing

stage. After the last processing stage, the output is XORed with the Mi and Hi _ r, and

then the next block is ready to be hashed.

of N-Hash

Cryptanalysis

Bert den Boer discovered a way to produce collisions in the round function of

N-Hash [ 12621. Biham and Shamir used differential cryptanalysis to break 6-round

*+ ++

output: Y=Y *IIY2llY3llY4

Yl y2 y3 y4

Y=FJs(X,P )

Figure 18.3 One processing stage of N-Hash.

Page 434

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.4 MD4

Y = .So(X1.Xz)= Ror2((X,+X2)mod 256)

Y =S,(X,.X,) =RorZ((X˜+X2+l)mod2S6)

Y (8 bits) : output, X, IX, (8 bits) : inputs

RorZ(â€˜T3: a Z-bit left rotation on the 8-bit data T

Figure 18.4 Function f.

N-Hash [ 169,172]. Their particular attack (there certainly could be others) works for

any N that is divisible by 3, and is more efficient than the birthday attack for any N

less than 15.

The same attack can find pairs of messages that hash to the same value for 12-

round N-Hash in 256operations, compared to 264operations for a brute-force attack.

N-hash with 15 rounds is safe from differential cryptanalysis: The attack requires 272

operations.

The algorithmâ€™s designers recommend using N-Hash with at least 8 rounds [ 11061.

Given the proven insecurity of N-Hash and FEAL (and its speed with 8 rounds), I

recommend using another algorithm entirely.

18.4 MD4

MD4 is a one-way hash function designed by Ron Rivest [1318,1319,1321]. MD

stands for Message Digest; the algorithm produces a 128-bit hash, or message digest,

of the input message.

In [ 13 191,Rivest outlined his design goals for the algorithm:

Security. It is computationally infeasible to find two messages that

hashed to the same value. No attack is more efficient than brute force.

Direct Security. MD4â€™s security is not based on any assumption, like the

difficulty of factoring.

Page 435

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

One-Way Hash Functions

CHAPTER 18

Speed. MD4 is suitable for high-speed software implementations. It is

based on a simple set of bit manipulations on 32-bit operands.

Simplicity and Compactness. MD4 is as simple as possible, without large

data structures or a complicated program.

Favor Little-Endian Architectures. MD4 is optimized for microprocessor

architectures (specifically Intel microprocessors); larger and faster com-

puters make any necessary translations.

After the algorithm was first introduced, Bert den Boer and Antoon Bosselaers

successfully cryptanalyzed the last two of the algorithmâ€™s three rounds [202]. In an

unrelated cryptanalytic result, Ralph Merkle successfully attacked the first two

rounds [202]. Eli Biham discussed a differential cryptanalysis attack against the first

two rounds of MD4 [159]. Even though these attacks could not be extended to the

full algorithm, Rivest strengthened the algorithm. The result is MD5.

18.5 MD5

MD5 is an improved version of MD4 [1386,1322]. Although more complex than

MD4, it is similar in design and also produces a 128-bit hash.

Description of MD5

After some initial processing, MD5 processes the input text in 512-bit blocks,

divided into 16 32-bit sub-blocks. The output of the algorithm is a set of four 32-bit

blocks, which concatenate to form a single 128bit hash value.

First, the message is padded so that its length is just 64 bits short of being a mul-

tiple of 5 12. This padding is a single l-bit added to the end of the message, followed

by as many zeros as are required. Then, a 64-bit representation of the messageâ€™s

length (before padding bits were added) is appended to the result. These two steps

serve to make the message length an exact multiple of 512 bits in length (required

for the rest of the algorithm), while ensuring that different messages will not look

the same after padding.

Four 32-bit variables are initialized:

A = 0x01234567

B = Ox89abcdef

C = Oxfedcba98

D = 0x76543210

These are called chaining variables.

Now, the main loop of the algorithm begins. This loop continues for as many 5 12-

bit blocks as are in the message.

The four variables are copied into different variables: a gets A, b gets B, c gets C,

and d gets D.

The main loop has four rounds (MD4 had only three rounds), all very similar. Each

round uses a different operation 16 times. Each operation performs a nonlinear func-

Page 436

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.5 MD5

Figure 28.5 MD5 main loop.

tion on three of a, b, c, and d. Then it adds that result to the fourth variable, a sub-

block of the text and a constant. Then it rotates that result to the right a variable

number of bits and adds the result to one of a, b, c, or d. Finally the result replaces

one of a, b, c, or d. See Figures 18.5 and 18.6.

There are four nonlinear functions, one used in each operation (a different one for

each round).

F(X,Y,Z) = (X A Y) v ((7 X) A Z)

G(X,Y,Z) = (X A Z) v (Y A (7 Z))

H(X,Y,Z)=XOYOZ

I(X,YZ) = Y 0 (Xv (-l Z))

(0 is XOR, A is AND, v is OR, and --, is NOT.)

These functions are designed so that if the corresponding bits of X, Y and Z are

independent and unbiased, then each bit of the result will also be independent and

unbiased. The function F is the bit-wise conditional: If X then Y else Z. The function

H is the bit-wise parity operator.

If Ml represents the jth sub-block of the message (from 0 to 15) and <<<s repre-

sents a left circular shift of s bits, the four operations are:

FF(a,b,c,d,NI,,s,t,) denotes a = b + ((a + F(b,c,d) + Mj + tl) <cc s)

GG(a,b,c,d,M,,s,t,) denotes a = b + ((a + G(b,c,d) + Mi + ti) <<< S)

HH(a,b,c,d,M,,s,ti) denotes u = b + ((u + H(b,c,d) + Mf + ti) <<< S)

II(a,b,c,d,M,s,t,) denotes u = b + ((a +I(b,c,d) + M, + ti) <<< S)

Page 437

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One-Way Hash Functions

Ir d

Figure 18.6 One MD5 operation.

The four rounds (64 steps) look like:

Round 1:

FF (a, b, c, d, M,, 7, Oxd76aa478)

FF (d, a, b, c, Ml, 12, Oxe8c7b756)

FF (c, d, a, b, M,, 17, Ox24207Odb)

FF (b, c, d, a, Mar 22, Oxclbdceee)

FF (a, b, c, d, M4, 7, Oxf57cOfaf)

FF (d, a, b, c, M,, 12, Ox4787c62a)

FF (c, d, a, b, M6, 17, Oxa8304613)

FF (b, c, d, a, M,, 22, Oxfd469501)

FF (a, b, c, d, MS, 7, Ox698098d8)

FF (d, a, b, c, M,, 12, Ox8b44f7af)

FF (c, d, a, b, Mlo, 17, Oxffff5bbl)

FF (b, c, d, a, Mll, 22, Ox895cd7be)

FF (a, b, c, d, Mlz, 7, Ox6b901122)

FF (d, a, b, c, M13, 12, Oxfd987193)

FF (c, d, a, b, M14, 17, Oxa679438e)

FF (b, c, d, a, MIS, 22, Ox49b40821)

Page 438

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.5 MD5

Round 2:

GG (a, b, c, d, Ml, 5, OxfGle2562)

GG (d, a, b, c, M6, 9, Oxc040b340)

GG (c, d, a, b, Mll, 14, Ox265e5a51)

GG (b, c, d, a, M,,, 20, Oxe9bbc7aa)

GG (a, b, c, d, MS, 5, Oxd62f105d)

GG (d, a, b, c, Mlo, 9, 0x02441453)

GG (c, d, a, b, MIS, 14, Oxd8ale681)

GG (b, c, d, a, M4, 20, Oxe7d3fbc8)

GG (a, b, c, d, M,, 5, Ox2lelcdeb)

GG (d, a, b, c, M14, 9, Oxc33707db)

GG (c, d, a, b, M,, 14, Oxf4d5Od87)

GG (b, c, d, a, MB, 20, Ox455a14ed)

GG (a, b, c, d, MIS, 5, Oxa9e3e905)

GG (d, a, b, c, n/I,, 9, Oxfcefa3f8)

GG (c, d, a, b, M,, 14, Ox676f02d9)

GG (b, c, d, a, M12, 20, Ox8d2a4c8a)

Round 3:

HH (a, b, c, d, M,, 4, Oxfffa3942)

HH (d, a, b, c, MS, 11, Ox8771f681)

HH (c, d, a, b, Mll, 16, Oxbd9d6122)

HH (b, c, d, a, M14, 23, Oxfde5380c)

HH (a, b, c, d, Ml, 4, Oxa4beea44)

HH (d, a, b, c, M4, 11, Ox4bdecfa9)

HH (c, d, a, b, M,, 16, Oxfbbb4b60)

HH (b, G, d, a, Ml,,, 23, Oxbebfbc70)

HH (a, b, c, d, MIS, 4, Ox289b7ec6)

HH (d, a, b, c, M,, 11, Oxeaal27fa)

HH (c, d, a, b, MS, 16, Oxd4ef3085)

HH (b, c, d, a, Me, 23, Ox04881d05)

HH (a, b, c, d, M,, 4, Oxd9d4d039)

HH (d, a, b, c, M12, 11, OxeGdb99e5)

HH (c, d, a, b, MIS, 16, Oxlfa27cf8)

HH (b, G, d, a, Mz, 23, Oxc4ac5665)

Page 439

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

One- Way Hash Functions

CHAPTER 18

Round 4:

II (a, b, c, d, M,, 6, Oxf4292244)

II (d, a, b, c, M,, 10, Ox432aff97)

II (c, d, a, b, M14, 15, Oxab9423a7)

II (b, c, d, a, MS, 21, Oxfc93a039)

II (a, b, c, d, Mlz, 6, Ox655b59c3)

II (d, a, b, c, M3, 10, Ox8fOccc92)

II (c, d, a, b, Mlo, 15, Oxffeff47d)

II (b, c, d, a, Ml, 21, Ox85845ddl)

II (a, b, c, d, Ms, 6, Oxbfa87e4f)

II (d, a, b, c, MIS, 10, Oxfe2cebeO)

II (c, d, a, b, Mb, 15, Oxa3014314)

II (b, c, d, a, M13, 21, Ox4e0811al)

II (a, b, c, d, M4, 6, Oxf7537e82)

II (d, a, b, c, Mll, 10, Oxbd3af235)

II (c, d, a, b, M2, 15, Ox2ad7d2bb)

II (b, c, d, a, Mg, 21, Oxeb86d391)

Those constants, tip were chosen as follows:

i, ti is the integer part of ZJzl abs(sin(i)), where i is in radians.

In step

After all of this, a, b, c, and d are added to A, B, C, D, respectively, and the algo-

rithm continues with the next block of data. The final output is the concatenation

of A, B, C, and D.

Security of MD5

Ron Rivest outlined the improvements of MD5 over MD4 [ 13221:

1. A fourth round has been added.

2. Each step now has a unique additive constant.

3. The function G in round 2 was changed from ((X A Y) v (X A Z) v (Y A Z)) to

((X A Z) v (Y A T Z)) to make G less symmetric.

4. Each step now adds in the result of the previous step. This promotes a

faster avalanche effect.

5. The order in which message sub-blocks are accessed in rounds 2 and 3 is

changed, to make these patterns less alike.

6. The left circular shift amounts in each round have been approximately

optimized, to yield a faster avalanche effect. The four shifts used in each

round are different from the ones used in other rounds.

Page 440

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Tom Berson attempted to use differential cryptanalysis against a single round of

MD5 [ 1441, but his attack is ineffective against all four rounds. A more successful

attack by den Boer and Bosselaers produces collisions using the compression func-

tion in MD5 [203,1331,1336]. This does not lend itself to attacks against MD5 in

practical applications, and it does not affect the use of MD5 in Luby-Rackoff-like

encryption algorithms (see Section 14.11). It does mean that one of the basic design

principles of MD5-to design a collision-resistant compression function-has been

violated. Although it is true that â€śthere seems to be a weakness in the compression

function, but it has no practical impact on the security of the hash functionâ€ť [ 13361,

I am wary of using MD5.

18.6 MD2

MD2 is another 128-bit one-way hash function designed by Ron Rivest [801,1335]. It,

along with MD5, is used in the PEM protocols (see Section 24.10). The security of

MD2 is dependent on a random permutation of bytes. This permutation is fixed, and

depends on the digits of K. So,Si, St, . . . , Szss the permutation. To hash a message M:

is

(1) Pad the message with i bytes of value i so that the resulting message is a

multiple of 16 bytes long.

(2) Append a 16-byte checksum to the message.

(3) Initialize a 48-byte block: X0, Xi, X,, . . . , X,,. Set the first 16 bytes of X to

be 0, the second 16 bytes of X to be the first 16 bytes of the message, and

the third 16 bytes of X to be the XOR of the first 16 bytes of X and the sec-

ond 16 bytes of X.

(4) This is the compression function:

t=O

Forj=Oto17

Fork=Oto47

t=X,XORS,

Xk = t

t=(t+j)mod256

(5) Set the second 16 bytes of X to be the second 16 bytes of the message, and

the third 16 bytes of X to be the XOR of the first 16 bytes of X and the sec-

ond 16 bytes of X. Do step (4). Repeat steps (5) and (4) with every 16 bytes

of the message, in turn.

(6) The output is the first 16 bytes of X.

Although no weaknesses in MD2 have been found (see [ 1262]), it is slower than

most other suggested hash functions.

Page 441

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One- Way Hash Functions

18.7 SECURE˜˜˜SHL˜GOR˜THM(S˜˜˜˜)

NET, along with the NSA, designed the Secure Hash Algorithm (SHA) for use with

the Digital Signature Standard (see Section 20.2) [ 11541. (The standard is the Secure

Hash Standard (SHS); SHA is the algorithm used in the standard.)

According to the Federal Register [539]:

A Federal Information Processing Standard (FIPS) for Secure Hash Standard (SHS)

is being proposed. This proposed standard specified a Secure Hash Algorithm

(SHA) for use with the proposed Digital Signature Standard . . . . Additionally, for

applications not requiring a digital signature, the SHA is to be used whenever a

secure hash algorithm is required for Federal applications.

And

This Standard specifies a Secure Hash Algorithm (SHA), which is necessary to

ensure the security of the Digital Signature Algorithm (DSA). When a message of

any length c 264bits is input, the SHA produces a 160-bit output called a message

digest. The message digest is then input to the DSA, which computes the signa-

ture for the message. Signing the message digest rather than the message often

improves the efficiency of the process, because the message digest is usually

much smaller than the message. The same message digest should be obtained by

the verifier of the signature when the received version of the message is used as

input to SHA. The SHA is called secure because it is designed to be computa-

tionally infeasible to recover a message corresponding to a given message digest,

or to find two different messages which produce the same message digest. Any

change to a message in transit will, with a very high probability, result in a dif-

ferent message digest, and the signature will fail to verify. The SHA is based on

principles similar to those used by Professor Ronald L. Rivest of MIT when

designing the MD4 message digest algorithm [ 13 191, and is closely modelled after

that algorithm.

SHA produces a 160-bit hash, longer than MD.5.

of SHA

Description

First, the message is padded to make it a multiple of 512 bits long. Padding is

exactly the same as in MD5: First append a one, then as many zeros as necessary to

make it 64 bits short of a multiple of 512, and finally a 64-bit representation of the

length of the message before padding.

Five 32-bit variables (MD5 has four variables, but this algorithm needs to produce

a 160-bit hash) are initialized as follows:

A = 0x67452301

B = Oxefcdab89

C = Ox98badcfe

D = 0x10325476

E = Oxc3d2elfO

Page 442

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

The main loop of the algorithm then begins. It processes the message 512 bits at

a time and continues for as many 5 12-bit blocks as are in the message.

First the five variables are copied into different variables: a gets A, b gets B, c gets

C, d gets D, and e gets E.

The main loop has four rounds of 20 operations each (MD5 has four rounds of 16

operations each). Each operation performs a nonlinear function on three of a, b, c, d,

and e, and then does shifting and adding similar to MD5.

SHAâ€™s set of nonlinear functions is:

f,(X,Y,Z) = (X A Y) v ((-X) A Z), for t = 0 to 19.

f,(X,Y,Z) =X 0 Y 0 Z, for t = 20 to 39.

= (X A Y) v (X A Z) v (Y A Z), for t = 40 to 59.

f,(X,y,Z)

f,(X,Y,Z) = X 0 Y 0 Z, for t = 60 to 79.

Four constants are used in the algorithm:

K, = Ox5a827999, for t = 0 to 19.

K, = Oxbed9eba1, for t = 20 to 39.

K, = Ox8flbbcdc for t = 40 to 59.

K, = Oxca62cld6, for t = 60 to 79.

(If you wonder where those numbers came from: Ox5a827999 = 2â€™/â€˜/4, Oxbed9ebal

= 31â€™2/4, Ox8f lbbcdc = 5â€™12/4, and Oxca62cld6 = 101â€™2/4j all times 232.)

The message block is transformed from 16 32-bit words (M,, to MIS) to 80 32-bit

words (W, to WT9)using the following algorithm:

W,=M,, fort=Oto 15

W,=(W,-30Wt-80Wt-140Wt-16)<<<1,fort=16t079.

(As an interesting aside, the original SHA specification did not have the left cir-

cular shift. The change â€ścorrects a technical flaw that made the standard less secure

than had been thoughtâ€ť [543]. The NSA has refused to elaborate on the exact nature

of the flaw.)

If t is the operation number (from 0 to 79), W, represents the tth sub-block of the

expanded message, and <<< s represents a left circular shift of s bits, then the main

loop looks like:

FORt=Oto79

TEMP = (a <CC 5) + f,(b,c,d) + e + W, + K,

e=d

d=c

c=b<<<30

b=a

a = TEMP

Page 443

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER18 One-Way Hash Functions

Figure 18.7 One SHA operation.

Figure 18.7 shows one operation. Shifting the variables accomplishes the same

thing as MD5 does by using different variables in different locations.

After all of this, a, b, c, d, and e are added to A, B, C, D, and E respectively, and

the algorithm continues with the next block of data. The final output is the con-

catenation of A, B, C, D, and E.

of SHA

Security

SHA is very similar to MD4, but has a 160-bit hash value. The main changes are

the addition of an expand transformation and the addition of the previous stepâ€™s out-

put into the next step for a faster avalanche effect. Ron Rivest made public the

design decisions behind MD5, but SHAâ€™s designers did not. Here are Rivestâ€™s MD5

improvements to MD4 and how they compare with SHAâ€™s:

1. â€śA fourth round has been added.â€ť SHA does this, too. However, in SHA the

fourth round uses the same f function as the second round.

2. â€śEach step now has a unique additive constant.â€ť SHA keeps the MD4

scheme where it reuses the constants for each group of 20 rounds.

3. â€śThe function G in round 2 was changed from ((X A Y) v (X A Z) v (Y A Z))

to ((x A z) V (Y A T (Z))) to make G less symmetric.â€ť SHA uses the MD4

Version: ((x A Y) V (x A z) V (Y A z)).

Page 444

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.9 HAVAL

4. â€śEach step now adds in the result of the previous step. This promotes a

faster avalanche effect.â€ť This change has been made in SHA as well. The

difference in SHA is that a fifth variable is added, and not b, c, or d, which

is already used in f,. This subtle change makes the den Boer-Bosselaers

attack against MD5 impossible against SHA.

5. â€śThe order in which message sub-blocks are accessed in rounds 2 and 3 is

changed, to make these patterns less alike.â€ť SHA is completely different,

since it uses a cyclic error-correcting code.

6. â€śThe left circular shift amounts in each round have been approximately

optimized, to yield a faster avalanche effect. The four shifts used in each

round are different from the ones used in other rounds.â€ť SHA uses a con-

stant shift amount in each round. This shift amount is relatively prime to

the word size, as in MD4.

This leads to the following comparison: SHA is MD4 with the addition of an

expand transformation, an extra round, and better avalanche effect; MD5 is MD4

with improved bit hashing, an extra round, and better avalanche effect.

There are no known cryptographic attacks against SHA. Because it produces a

160-bit hash, it is more resistant to brute-force attacks (including birthday attacks)

than 128-bit hash functions covered in this chapter.

18.8 RIPE-MD

RIPE-MD was developed for the European Communityâ€™s RIPE project [ 1305) (see

Section 25.7). The algorithm is a variation of MD4, designed to resist known crypt-

analytic attacks, and produce a 128-bit hash value. The rotations and the order of

the message words are modified. Additionally, two instances of the algorithm, dif-

fering only in the constants, run in parallel. After each block, the output of both

instances are added to the chaining variables. This seems to make the algorithm

highly resistant to cryptanalysis.

18.9 HAVAL

HAVAL is a variable-length one-way hash function [1646]. It is a modification of

MD5. HAVAL processes messages in blocks of 1024 bits, twice those of MD5. It has

eight 32-bit chaining variables, twice those of MD5. It has a variable number of

rounds, from three to five (each of which has 16 steps), and it can produce a hash

length of 128, 160, 192, 224, or 256 bits.

HAVAL replaces MD5â€™s simple nonlinear functions with highly nonlinear 7-

variable functions, each of which satisfies the strict avalanche criterion. Each round

uses a single function, but in every step a different permutation is applied to the

inputs. It has a new message order and every step (except those in the first round)

uses a different additive constant. The algorithm also has two rotations.

Page 445

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One- Way Hash Functions

The core of the algorithm is

TEMP= (f(j,A,B,C,D,E,F,G) <<< 7) + (H <<< 11) +M[i][r(j)] + K(j)

H=G;G=F;F=E;E=D;D=C;C=B;B=A;A=TEMP

The variable number of rounds and variable-length output mean there are 15 ver-

sions of this algorithm. Den Boerâ€™s and Bosselaersâ€™s attack against MD5 [203] does

not apply to HAVAL because of the rotation of H.

18.10 ONE-WAYHASH FUNCTIONS

OTHER

MD3 is yet another hash function designed by Ron Rivest. It had several flaws and

never really made it out of the laboratory, although a description was recently pub-

lished in [ 13351.

A group of researchers at the University of Waterloo have proposed a one-way

hash function based on iterated exponentiation in GF(2593)[22]. In this scheme, a

message is divided into 593-bit blocks; beginning with the first block, the blocks are

successively exponentiated. Each exponent is the result of the computation with

the previous block; the first exponent is given by an IV.

Ivan DamgHrd designed a one-way hash function based on the knapsack problem

(see Section 19.2) [414]; it can be broken in about 232operations [290,1232,787].

Steve Wolframâ€™s cellular automata [1608] have been proposed as a basis for one-

way hash functions. An early implementation [414] is insecure [1052,404]. Another

one-way hash function, Cellhash [384,404], and an improved version, Subhash

[384,402,405], are based on cellular automata; both are designed for hardware. Boog-

nish mixes the design principles of Cellhash with those of MD4 [402,407].

StepRightUp can be implemented as a hash function as well [402].

Claus Schnorr proposed a one-way hash function based on the discrete Fourier

transform, called FFT-Hash, in the summer of 1991 [1399]; it was broken a few

months later by two independent groups [403,84]. Schnorr proposed a revised ver-

sion, called FFT-Hash II (the previous version was renamed FFT-Hash I) [ 14001,

which was broken a few weeks later [ 15671. Schnorr has proposed further modifica-

tions [ 1402,1403] but, as it stands, the algorithm is much slower than the others in

this chapter. Another hash function, called SL2 [ 15261, is insecure [3 151.

Additional theoretical work on constructing one-way hash functions from one-

way functions and one-way permutations can be found in [412,1138,1342].

18.11 ONE-WAY HASH FUNCTIONS USING SYMMETRIC

BLOCK ALGORITHMS

It is possible to use a symmetric block cipher algorithm as a one-way hash function.

The idea is that if the block algorithm is secure, then the one-way hash function

will also be secure.

Page 446

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.11 Symmetric Block Algorithms

The most obvious method is to encrypt the message with the algorithm in CBC

or CFB mode, a fixed key, and IV; the last ciphertext block is the hash value. These

methods are described in various standards using DES: both modes in [ 11431,CFB in

[ 11451, CBC in [55,56,54]. This just isnâ€™t good enough for one-way hash functions,

although it will work for a MAC (see Section 18.14) [29].

A cleverer approach uses the message block as the key, the previous hash value as

the input, and the current hash value as the output.

The actual hash functions proposed are even more complex. The block size is usu-

ally the key length, and the size of the hash value is the block size. Since most block

algorithms are 64 bits, several schemes are designed around a hash that is twice the

block size.

Assuming the hash function is correct, the security of the scheme is based on the

security of the underlying block function. There are exceptions, though. Differential

cryptanalysis is easier against block functions in hash functions than against block

functions used for encryption: The key is known, so several tricks can be applied;

only one right pair is needed for success; and you can generate as much chosen

plaintext as you want. Some work on these lines is [ 1263,858,1313].

What follows is a summary of the various hash functions that have appeared in

the literature [925,1465,1262]. Statements about attacks against these schemes

assume that the underlying block cipher is secure; that is, the best attack against

them is brute force.

One useful measure for hash functions based on block ciphers is the hash rate, or

the number of n-bit messages blocks, where n is the block size of the algorithm, pro-

cessed per encryption. The higher the hash rate, the faster the algorithm. (This mea-

sure was given the opposite definition in [1262], but the definition given here is

more intuitive and is more widely used. This can be confusing.)

Schemes Where the Hash Length Equals the Block Size

The general scheme is as follows (see Figure 18.8):

HO= IH, where IH is a random initial value

Hi = EA( 0 C

B)

where A, B, and C can be either Mi, Hi - 1,(Mi @Hi - I), or a constant (assumed to be 0).

HOis some random initial value: IH. The message is divided up into block-size chunks,

Mi> and processed individually. And there is some kind of MD-strengthening, perhaps

the same padding procedure used in MD5 and SHA.

Figure 18.8 General hash function where the

hash length equals the block size.

Page 447

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One-Way Hash Functions

Table 18.1

Secure Hash Functions Where the

Block Length Equals the Hash Size

Hi = EHi _ ,(M,) 0 Mi

H,=E,i_,(M˜oHi-,)OMiOH,-,

H,=EH,-,(Ml)@Hi-IBM,

H˜=EH˜-,(M˜@H˜-I)@M˜

Hl=E,i(Hl-,)OH,-,

Hi=E,˜MiOHi-,)OM,OH,-,

Hi=EMi(HI-,)OMiOHi-,

HI = EM,(Mi 0 Hi - 1)0 Hi - 1

Hi = EMU pi _ ,(Mi) @ Ml

e

Hi=Ehll˜Hi_1(Hi-1)OHi-1

Hi=EMi.Hi-,(Mi) @Hi-,

Hi=E˜l˜Hi-l(Hi-l)@Mi

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 [ 12621.

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 IS0 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 and3 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.

Page 448

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Hi-1

4

1 Key (

Mi Encrypt

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

hash size.

This scheme [ 12821was broken in [369]:

Hz = EM,(Hi- I)

Davies and Price proposed a variant which cycles the entire message through the

algorithm twice 1432,433). Coppersmithâ€™s attack works on this variant with not

much larger computational requirements [369].

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

Hi=EMleHi- l(Hi- II

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

H,=E,(MiOHi_1)OM,OHi-,

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

HO= IH, where IH is a random initial value

H˜=EH˜-˜*M˜(H˜ - 11

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.

Page 449

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One- Way Hash Functions

1 H;-1

LpbHi

Figure 18.10 Modified Davies-Meyer.

Preneel-Bosselaers-Govaerts-Vandewalle

This hash function, first proposed in [ 12661,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, Gi

and Hi, which are concatenated to produce the 128-bit hash. With most block algo-

rithms, the block size is 64 bits. Two adjacent message blocks, L, and Ri, each the

size of the block length, are hashed together.

G,, = Ic, where Ic is a random initial value

Ho = IH, where IH is another random initial value

Gi=ELi˜Hi_1(Ri8Gi-1)˜Ri8Gi-18Hi-1

Hi=ELi˜Ri(Hi-1˜Gi-1)OLi8Gi-18Hi-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.

QuisquaterGirault

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, Gi and Hi, and two blocks, Li

and Ri, are hashed together.

Go = IG, where IG is a random initial value

H,, = IH, where IH is another random initial value

Wi=ELi(Gi-l$Ri)$Ri$Hi-l

Gi=ERi(Wi˜Li)˜Gi-l˜Hi-l˜Li

Hi=WiOGi-1

This scheme appeared in a 1989 draft IS0 standard [764], but was dropped in a

later version [765]. Security problems with this scheme were identified in [ 1107,925,

1262,372]. (Actually, the version in the proceedings was strengthened after the ver-

sion presented at the conference was attacked.) In some instances the birthday

attack is solvable with a complexity of 239,not 264,through brute force. Do not use

this scheme.

Page 450

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

LOKI Double-Block

This algorithm is a modification of Quisquater-Girault, specifically designed to

work with LOKI [273]. All parameters are as in Quisquater-Girault.

Go = 16, where IG is a random initial value

Ho = IH, where IH is another random initial Vahe

(G,_1ORi)ORiOHi-1

W=&BG,_,

(WI 0 Li) 0 Gi - 10 Hz - 10 Li

G,=EIQw-˜

Hi=WlOGi-l

Again, in some instances the birthday attack is trivially solvable [925,926,1262,

372,736]. Do not use this scheme.

Parallel Davies-Meyer

This is yet another attempt at an algorithm with a hash rate of 1 that produces a

hash twice the block length [736].

Go = IG, where IG is a random initial value

Ho = IH, where IH is another random initial Vahe

G,=EL,dRi(Gi-1OLi)OLiOHi-1

Hi=EL,(Hi-1ORi)ORiOHi-1

Unfortunately, this scheme isnâ€™t secure either [928,861]. As it turns out, a

double-length hash function with a hash rate of 1 cannot be more secure than

Davies-Meyer [861].

Tandem and Abreast Davies-Meyer

Another way around the inherent limitations of a block cipher with a 64-bit key

uses an algorithm, like IDEA (see Section 13.9) with a 64-bit block and a 128-bit key.

These two schemes produce a 128-bit hash value and have a hash rate of %[930,925].

â€˜Gi

Figure 18.2 1 Tandem Davies-Meyer.

Page 451

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One-Way Hash Functions

In this first scheme, two modified Davies-Meyer functions work in tandem (see

Figure 18.11).

Go = Ic, where IG is some random initial value

Ho = IH, where IH is some other random initial Value

Wi = EGO ,,tv+(Hi - 1)

_

Gi=G,-l @E,,,(Gi-,)

Hi=WiOHl-1

The following scheme uses two modified Davies-Meyer functions side-by-side

(see Figure 18.12).

Go = 16, where IG is some random initial value

Ho = IH, where IH is some other random initial Value

Gi = Gi - 10 EMi,Hi_ l(TGi - 1)

Hi = Hi - 10 EGO ,,Mi(Hi - I)

_

In both schemes, the two 64-bit hash values Gi and Hi are concatenated to produce

a single 128-bit hash.

As far as anyone knows, these algorithms have ideal security for a 128-bit hash

function: Finding a message that hashes to a given hash value requires 2â€ť* attempts,

and finding two random messages that hash to the same value requires 264attempts-

assuming that there is no better way to attack the block algorithm than by using

brute force.

MDC-2 and MDC-4

MDC-2 and MDC-4 were first developed at IBM [ 1081,1079]. MDC-2, sometimes

called Meyer-Schilling, is under consideration as an ANSI and IS0 standard [61,765];

a variant was proposed in [762]. MDC-4 is specified for the RIPE project [1305] (see

Section 25.7). The specifications use DES as the block function, although in theory

any encryption algorithm could be used.

Encrypt

Hi-l Hi

Kev ,

I

A f

I

J +

Key

â€˜i-1 â€˜i

Encrypt

I I

Figure 28.22 Abreast Davies-Meyer.

Page 452

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

1 Key 1

4

Encrypt

Figure 18.13 MDC-2.

MDC-2 has a hash rate of %, and produces a hash value twice the length of the

block size. It is shown in Figure 18.13. MDC-4 also produces a hash value twice the

length of the block size, and has a hash rate of %(see Figure 18.14).

These schemes have been analyzed in [925,1262]. They are secure against current

computing power, but they are not nearly as secure as the designers have estimated.

If the block algorithm is DES, they have been looked at with respect to differential

cryptanalysis [ 12621.

Both MDC-2 and MDC-4 are patented [223].

AR Hash Function

The AR hash function was developed by Algorithmic Research, Ltd. and has been

distributed by the IS0 for information purposes only [767]. Its basic structure is a

variant of the underlying block cipher (DES in the reference) in CBC mode. The last

two ciphertext blocks and a constant are XORed to the current message block and

encrypted by the algorithm. The hash is the last two ciphertext blocks computed.

The message is processed twice, with two different keys, so the hash function has a

hash rate of %. The first key is 0x0000000000000000, the second key is Ox2a4152

2f4446502a, and c is Ox0123456789abcdef. The result is compressed to a single 128-

bit hash value. See 1750) for the details.

H,=E,(MiOHi-,˜Hi-z8c)$Mi

This sounds interesting, but it is insecure. After considerable preprocessing, it is

possible to find collisions for this hash function easily [416].

Page 453

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One-Way Hash Functions

Encrypt

Key 1

Hi-

Figure 18.14 MDC-4.

GOST Hash Function

This hash function comes from Russia, and is specified in the standard GOST R

34.1 l-94 [657]. It uses the GOST block algorithm (see Section 14.1) although in the-

ory it could use any block algorithm with a 64-bit block size and a 256-bit key. The

function produces a 256-bit hash value.

The compression function, Hi = f(Mi,Hi - r) (both operands are 256-bit quantities) is

defined as follows:

(1) Generate four GOST encryption keys by some linear mixing of Mi, H, - 1,

and some constants.

(2) Use each key to encrypt a different 64 bits of Hi - 1in ECB mode. Store the

resulting 256 bits into a temporary variable, S.

(3) Hi is a complex, although linear, function of S, Mi, and Hi - 1.

The final hash of M is not the hash of the last block. There are actually three

chaining variables: H, is the hash of the last message block, Z is the sum mod 2256 of

all the message blocks, and L is the length of the message. Given those variables and

the padded last block, Mâ€™, the final hash value is:

H = f(Z 0 Mâ€™,f(L,f(Mâ€™,H,)))

The documentation is a bit confusing (and in Russian), but I think all that is cor-

rect. In any case, this hash function is specified for use with the Russian Digital Sig-

nature Standard (see Section 20.3).

Page 454

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.14 Message Authentication Codes

Schemes

Other

Ralph Merkle proposed a scheme using DES, but itâ€™s slow; it only processes seven

message bits per iteration and each iteration involves two DES encryptions [ 1065,

1069). Another scheme [1642,1645] is insecure [1267]; it was once proposed as an

IS0 standard.

18.12 USING PUBLIC-KEY ALGORITHMS

It is possible to use a public-key encryption algorithm in a block chaining mode as

a one-way hash function. If you then throw away the private key, breaking the hash

would be as difficult as reading the message without the private key.

Hereâ€™s an example using RSA. If M is the message to be hashed, n is the product of

two primes p and q, and e is another large number relatively prime to (p - l)(q - l),

then the hash function, H(M), would be

H(M) = Me mod n

An even easier solution would be to use a single strong prime as the modulus

p. Then:

H(M) = Me mod p

Breaking this problem is probably as difficult as finding the discrete logarithm of

e. The problem with this algorithm is that itâ€™s far slower than any others discussed

here. I donâ€™t recommend it for that reason.

18.13 CHOOSING A ONE-WAY HASH FUNCTION

The contenders seem to be SHA, MD5, and constructions based on block ciphers;

the others really havenâ€™t been studied enough to be in the running. I vote for SHA.

It has a longer hash value than MD5, is faster than the various block-cipher con-

structions, and was developed by the NSA. I trust the NSAâ€™s abilities at cryptanaly-

sis, even if they donâ€™t make their results public.

Table 18.2 gives timing measurements for some hash functions. They are meant

for comparison purposes only.

18.14 MESSAGE AUTHENTICATION CODES

A message authentication code, or MAC, is a key-dependent one-way hash function.

MACs have the same properties as the one-way hash functions discussed previously,

but they also include a key. Only someone with the identical key can verify the hash.

They are very useful to provide authenticity without secrecy.

MACs can be used to authenticate files between users. They can also be used by

a single user to determine if his files have been altered, perhaps by a virus. A user

could compute the MAC of his files and store that value in a table. If the user used

Page 455

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 18 One-Way Hash Functions

Table 18.2

Speeds of Some Hash Functions on a 33 MHz 486SX

Encryption Speed

(kilobytes/second)

Hash Length

Algorithm

Abreast Davies-Meyer (with IDEA) 128 22

Davies-Meyer (with DES) 64 9

GOST Hash 256 11

168

variable

HAVAL (3 passes]

variable 118

HAVAL (4 passes)

variable

HAVAL (5 passes) 95

MD2 128 23

MD4 128 236

MD5 128 174

N-HASH (12 rounds) 128 29

N-HASH ( 15 rounds) 128 24

RIPE-MD 128 182

SHA 160 75

SNEFRU (4 passes) 128 48

SNEFRU (8 uassesl 128 23

instead a one-way hash function, then the virus could compute the new hash value

after infection and replace the table entry. A virus could not do that with a MAC,

because the virus does not know the key.

An easy way to turn a one-way hash function into a MAC is to encrypt the hash

value with a symmetric algorithm. Any MAC can be turned into a one-way hash

function by making the key public.

CBC-MAC

The simplest way to make a key-dependent one-way hash function is to encrypt a

message with a block algorithm in CBC or CFB modes. The hash is the last encrypted

block, encrypted once more in CBC or CFB modes. The CBC method is specified in

ANSI X9.9 [54], ANSI X9.19 [56], IS0 8731-1 [759], IS0 9797 [763], and an Australian

standard [ 14961.Differential cryptanalysis can break this scheme with reduced-round

DES or FEAL as the underlying block algorithms [ 11971.

The potential security problem with this method is that the receiver must have

the key, and that key allows him to generate messages with the same hash value as

a given message by decrypting in the reverse direction.

Message Authenticator Algorithm (MAA)

This algorithm is an IS0 standard (7601. It produces a 32-bit hash, and was

designed for mainframe computers with a fast multiply instruction [428].

Page 456

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

18.14 Message Authentication Codes

v=v<<< 1

e=vOw

x = ((((e + y) mod 232)v A A C) 8 Mi)) mod 232- 1

l (X

y = ((((e +x) mod 232)v B A D) * (y 0 Mi)) mod 232- 2

Iterate these for each message block, n/l,, and the resultant hash is the XOR of x and

y. The variables v and e are determined from the key. A, B, C, and D are constants.

This algorithm is probably in wide use, but I canâ€™t believe it is all that secure. It

was designed a long time ago, and isnâ€™t very complicated.

Bidirectional MAC

This MAC produces a hash value twice the length of the block algorithm [978].

First, compute the CBC-MAC of the message. Then, compute the CBC-MAC of the

message with the blocks in reverse order. The bidirectional MAC value is simply

the concatenation of the two. Unfortunately, this construction is insecure [ 10971.

Juenemanâ€™s Methods

This MAC is also called a quadratic congruential manipulation detection code

(QCMDC) [792,789). First, divide the message into m-bit blocks. Then:

Ho = IHr where IH is the secret key

H, = (H, - r + Mi)â€™ mod p, where p is a prime less than 2â€ť - 1

and + denotes integer addition

Jueneman suggests n = 16 and p = 231- 1. In [792] he also suggests that an addi-

tional key be used as H1, with the actual message starting at Hz.

Because of a variety of birthday-type attacks discovered in conjunction with Don

Coppersmith, Jueneman suggested computing the QCMDC four times, using the

result of one iteration as the Iv for the next iteration, and then concatenating the

results to obtain a 128-bit hash value [793]. Thâ€™IS was further strengthened by doing

the four iterations in parallel and cross-linking them [790,791]. This scheme was

broken by Coppersmith [376].

Another variant [432,434] replaced the addition operation with an XOR and used

message blocks significantly smaller than p. H,, was also set, making it a keyless

one-way hash function. After this scheme was attacked [612], it was strengthened as

ńňđ. 1 |