Chapter 13

Hash Functions

13.1 Introduction

The problem with digital signatures is that long messages require very long signatures. We

would like for performance as well as for security reasons to have one signature for a message

of arbitrary length. The solution to this problem are Hash functions.

kpr

y =

sig (z)

kpr

x ||zi-1 ) i z h (

sig (z)

i

y is of fixed length

=

x

z z is of fixed length

x is of arbitrary length

x

Figure 13.1: Hash functions and digital signatures

115

Remarks:

z, x don't have the same length.

h(x) has no key.

h(x) is public.

Basic Protocol:

Alice Bob

1) z = h(x)

2) y = sigkpr(z)

3) (x;y)

 􀀀

4) z = h(x)

5) verkpub(z; y)

Potential hash function properties

a) One-way: for (almost) all given output z, it is impossible to nd any input x such that

h(x) = z.

b) Weak collision resistant: given x, and thus h(x), it is impossible to nd any x0 such

that h(x) = h(x0).

c) Strong collision resistant: it is impossible to nd any two pairs x; x0 such that

h(x) = h(x0).

116

Requirements for a hash function (Adopted from [Sta95])

1. h(x) can be applied to x of any size.

2. h(x) produces a xed length output.

3. h(x) is relatively easy to compute in software and hardware.

4. h(x) is one-way.

5. h(x) is weak collision resistant.

6. h(x) is strong collision resistant.

Discussion:

(1) | (3) are practical requirements

(4) if h(x) is not one-way, Oscar can compute x from h(x) in cases where x is encrypted.

(5) if h(x) is not weak collission free, Oscar can replace x with x0.

Alice Oscar Bob

z = h(x)

(x;y)

 􀀀 y = sigKpr(z)

(y;x0)

 􀀀

z = h(x0) = h(x)

verKpub(z; y) = true

(6) if h(x) is not strong collission free, Oscar runs the following attack:

a) Choose legitimate message x1 and fraudulent message x2

117

b) Alter x1 and x2 at

on-visible" location, i.e. replace tabs through spaces, append

returns, etc., until h(x0

1) = h(x0

2) (Note: e.g. 64 alteration locations allow 264

versions of a message with 264 dierent hash values).

c) Let Bob sign x0

1 ! (x0

1; sigKpr(h(x0

1))

d) Replace x0

1 ! x0

2 and (x0

2; sigKpr(h(x0

2))

13.2 Security Considerations

Question: How many people are needed at a party so that there is a 50% chance that at

least two people have the same birthday?

In general, given a large set with n dierent values:

P(no collission among k random elements) = 1 􀀀

1

n

k| ={2z elt}.

1 􀀀

2

n

| k ={3z elt. }

1 􀀀

k 􀀀 1

n !

| k {ezlt. }

=

k􀀀1

Yi=1 1 􀀀

i

n

Often n is large (n = 365 in birthday paradox, n = 2160 in hash functions).

Recall:

e􀀀x = 1􀀀 x +

x2

2! 􀀀

x3

3!

+

if x << 1

e􀀀x 1 􀀀 x

Thus,

P(no collision)

k􀀀1

Yi=1

e􀀀 i

n = e􀀀 1

n e􀀀 2

n e􀀀 3

n e􀀀k􀀀1

n

k􀀀1

Yi=1

e􀀀 i

n = e􀀀1+2+3++k􀀀1

n

118

Rewriting the exponent with the help of the following identity:

1 + 2 + 3 + + k 􀀀1 = k(k 􀀀 1)=2

We obtain,

P(no collission) e􀀀

k(k􀀀1)

2n

Dene as

P(at least one collission) DEF = 1 􀀀 e􀀀

k(k􀀀1)

2n

1 􀀀 e􀀀

k(k􀀀1)

2n

ln (1 􀀀 ) 􀀀

k(k 􀀀 1)

2n

k(k + 1) 􀀀2n ln (1 􀀀 ) = 2n ln 1

1 􀀀

If k >> 1, then

k2 k(k 􀀀 1) 2n ln 1

1 􀀀

k s2n ln 1

1 􀀀

Example:

k( = 0:5) s2n ln 1

1 􀀀 0:5 = p2 ln2pn = 1:18pn

) A collission in a set of n values is found after about pn trials with a probability of 0.5.

In other words, hash funtion with 40 bit output ) collission after

p240 = 220 trials.

) In order to provide collision resistance in practice, the output space of the hash function

should contain at least 2160 elements, that is, the hash function should have at least 160

output bits. Finding a collision takes then roughly p2160 = 280 steps.

119

13.3 Hash Algorithms

Overview:

customized

e.g. MD4 family

modular arithmetic based

Hash Algorithms

block cipher based

(rare, often unsecure)

Figure 13.2: Family of Hash Algorithms

a) MD4{family

1. SHA-1

Output: 160 bits ) input size for DSS.

Input: 512 bit chunks of message x.

Operations: bitwise AND, OR, XOR, complement and cyclic shift.

2. RIPE-MD 160

Output: 160 bits.

Input: 512 bit chunks of message x.

Operations: same as SHA but runs two algorithms in parallel whose

outputs are combined after each round.

120

b) Hash functions from block ciphers

i-1

xi

Hi g(Hi-1 ) e xi ( ) xi =

H

n

Hi

n

m

K

e

y

g

Figure 13.3: Hash Functions from Block Ciphers