Online Cryptography Course

Dan Boneh

Collision
resistance
Introduction

Dan Boneh

Recap: message integrity

So far, four MAC constructions:
ECBC-MAC, CMAC

: commonly used with AES

(e.g. 802.11i)

PRFs
NMAC

: basis of HMAC (this segment)

PMAC: a parallel MAC

randomized
MAC

Carter-Wegman MAC: built from a fast one-time

MAC
This module: MACs from collision resistance.

Dan Boneh

Collision Resistance
Let H: M T be a hash function

( |M| >> |T| )

A collision for H is a pair m0 , m1 M such that:

H(m0) = H(m1) and m0 m1
A function H is collision resistant if for all (explicit)
ef algs. A:
AdvCR[A,H] = Pr[ A outputs collision for H]
is neg.
Example: SHA-256 (outputs 256 bits)

Dan Boneh

MACs from Collision

Resistance

Let I = (S,V) be a MAC for short messages over (K,M,T)

(e.g. AES)
Let H: Mbig M
Def:

Ibig = (Sbig , Vbig )

over (K, Mbig, T) as:

Sbig(k,m) = S(k,H(m))

Vbig(k,m,t) = V(k,H(m),t)

Thm: If I is a secure MAC and H is collision resistant

then

Ibig is a secure MAC.

Example:
S(k,m) = AES2-block-cbc(k, SHA-256(m)) is a
secure MAC.

Dan Boneh

MACs from Collision

Resistance
Sbig(k, m) = S(k, H(m))
V(k, H(m), t)

Vbig(k, m, t) =

Collision resistance is necessary for security:

Suppose adversary can find m0 m1 s.t. H(m0)
= H(m1).
Then: Sbig is insecure under a 1-chosen msg
attack
step 1: adversary asks for t S(k, m )

Dan Boneh

Protecting file integrity using C.R. hash

Software packages:
package name package name

F1

F2

package name

Fn

read-only
public
space
H(F2)
H(F1)

H(Fn)
When user downloads package, can verify that contents are valid
H collision resistant
attacker cannot modify package without detection
no key needed (public verifiability), but requires read-only
space

Dan Boneh

End of Segment

Dan Boneh

Online Cryptography Course

Dan Boneh

Collision
resistance
Generic birthday
attack

Dan Boneh

Generic attack on C.R.

functions

Let H: M {0,1}n be a hash function

Generic alg. to find a collision in time

Algorithm:
1. Choose 2n/2 random messages in M:

( |M| >> 2n )
O(2n/2)

hashes

m1, , m2n/2

(distinct w.h.p )

2. For i = 1, , 2n/2 compute ti = H(mi) {0,1}n

3. Look for a collision (ti = tj). If not found, got back to
step 1.

How well will this work?

Dan Boneh

The birthday paradox

Let r1, , rn {1,,B} be indep. identically
distributed integers.
Thm: when n= 1.2 B1/2 then Pr[ ij: ri = rj

Proof: (for uniform indep. r1, , rn )

Dan Boneh

B=106

# samples n

Dan Boneh

Generic attack
H: M {0,1}n .
Collision finding algorithm:
1. Choose 2n/2 random elements in M:
m1, ,
m2n/2
2. For i = 1, , 2n/2 compute
3. Look for a collision (ti = tj).
back to step 1.

ti = H(mi)

{0,1}n

If not found, got

Expected number of iteration 2

Dan Boneh

Sample C.R. hash functions:

AMD Opteron, 2.2 GHz

SHA-1
SHA-256
SHA-512

153 280
111 2128
99 2256

NIST standards

Speed

Whirlpool

512

[ Wei Dai ]

( Linux)

digest
function size (bits)
160
256
512

Crypto++ 5.6.0

generic
(MB/sec) attack time

57 2256

best known collision finder for SHA-1 requires 251 hash evaluations

Dan Boneh

Quantum Collision Finder

Block cipher
E: K X X
exhaustive
search
Hash function
H: M T
collision finder

Classical
algorithms

Quantum
algorithms

O( |K| )

O( |K|1/2 )

O( |T|1/2 )

O( |T|1/3 )

Dan Boneh

End of Segment

Dan Boneh

Online Cryptography Course

Dan Boneh

Collision
resistance
The MerkleDamgard
Paradigm

Dan Boneh

Collision resistance: review

Let H: M T be a hash function

( |M| >> |T| )

A collision for H is a pair m0 , m1 M such that:

H(m0) = H(m1) and m0 m1
Goal: collision resistant (C.R.) hash functions
Step 1: given C.R. function for short messages,
construct C.R. function for long messages

Dan Boneh

The Merkle-Damgard iterated construction

m[0]
IV
(fixed)

H0

m[1]

H1

m[2]

Given h: T X T
we obtain
variables
PB:

H2

m[3] ll PB

H4

(compression function)

H: XL T .

padding block

H3

H(m)

Hi - chaining

10000 ll msg
len
64 bits

If no space for PB
add another block

Dan Boneh

MD collision resistance
Thm: if h is collision resistant then so is H.
Proof: collision on H collision on h
Suppose H(M) = H(M).
= H0
= H0 ,

H1

, , Ht ,

H1 , , Hr,

We build collision for h.

Ht+1 = H(M)
Hr+1 = H(M)

Ht, Mt ll PB) = Ht+1 = Hr+1 = h(Hr, Mr ll PB)

Dan Boneh

ppose

Ht = Hr

and

Mt = Mr and PB = PB

hen: h( Ht-1, Mt-1) = Ht = Ht = h(Ht-1, Mt-1 )

Dan Boneh

 To construct C.R. function,

suffices to construct compression function

End of Segment

Dan Boneh

Online Cryptography Course

Dan Boneh

Collision
resistance
Constructing
Compression
Functions

Dan Boneh

The Merkle-Damgard iterated construction

m[0]
IV
(fixed)

Thm:

m[1]

m[2]

h collision resistant

m[3] ll PB

H(m)

H collision resistant

Goal: construct compression function h: T X T

Dan Boneh

Compr. func. from a block

cipher

E: K {0,1}n {0,1}n

a block cipher.

The Davies-Meyer compression function:

H)H

h(H, m) = E(m,

mi

>

Hi

Thm: Suppose E is an ideal cipher (collection of |K| random perms.).

Finding a collision h(H,m)=h(H,m) takes O(2n/2) evaluations of
(E,D).

Best possible !!

Dan Boneh

Suppose we define

h(H, m) = E(m, H)

Then the resulting h(.,.) is not collision resistant:

to build a collision (H,m) and (H,m)
choose random (H,m,m) and construct H as follows:
H=D(m, E(m,H))
H=E(m, D(m,H))
H=E(m, E(m,H))
H=D(m, D(m,H))

Other block cipher

constructions

E: {0,1}n {0,1}n {0,1}n for simplicity

Miyaguchi-Preneel:
(Whirlpool)

h(H, m) = E(m, H)Hm

h(H, m) = E(Hm, m)m

total of 12 variants like this
Other natural variants are insecure:
h(H, m) = E(m, H)m

(HW)

Dan Boneh

Case study: SHA-256

Merkle-Damgard function
Davies-Meyer compression function
Block cipher: SHACAL-2
512-bit key
>
256-bit block

SHACAL2

256-bit block

Dan Boneh

Provable compression
functions
Choose a random 2000-bit prime p and random 1
u, v p .
For m,h {0,,p-1}
vm (mod p)

define

h(H,m) = uH

Fact: finding collision for h(.,.) is as hard as

solving discrete-log modulo p.

Dan Boneh

End of Segment

Dan Boneh

Online Cryptography Course

Dan Boneh

Collision
resistance
HMAC:
a MAC from SHA256

Dan Boneh

The Merkle-Damgard iterated construction

m[0]
IV
(fixed)

Thm:

m[1]

m[2]

h collision resistant

m[3] ll PB

H(m)

H collision resistant

Can we use H(.) to directly build a MAC?

Dan Boneh

MAC from a Merkle-Damgard Hash Function

H: XL T a C.R. Merkle-Damgard Hash Function
Attempt #1:

S(k, m) = H( k ll m)

This MAC is insecure because:

Given H( k ll m) can compute H( w ll k ll m ll PB) for an

Given H( k ll m) can compute H( k ll m ll w ) for any w
Given H( k ll m) can compute H( k ll m ll PB ll w ) for an
Anyone can compute H( k ll m ) for any m.

Standardized method: HMAC

(Hash-MAC)
Most widely used MAC on the Internet.
H: hash function.
example: SHA-256

output is 256 bits

Building a MAC out of a hash function:

HMAC:
m)

S( k, m ) = H( kopad ll H( kipad ll

Dan Boneh

HMAC in pictures
kipad
IV
(fixed)

>

m[0]

>

m[1]

>

m[2] ll PB

>

kopad
>
IV
(fixed)

>

tag

Similar to the NMAC PRF.

main diference: the two keys k1, k2 are dependent

Dan Boneh

HMAC properties
Built from a black-box implementation of SHA-256.
HMAC is assumed to be a secure PRF
Can be proven under certain PRF assumptions
about h(.,.)
Security bounds similar to NMAC
Need q2/|T| to be negligible ( q << |T| )
In TLS:

must support HMAC-SHA1-96

Dan Boneh

End of Segment

Dan Boneh

Online Cryptography Course

Dan Boneh

Collision
resistance
Timing attacks on
MAC
verification

Dan Boneh

Warning: verification timing attacks

[L09]

Example: Keyczar crypto library (Python)

[simplified]

def Verify(key, msg, sig_bytes):

return HMAC(key, msg) == sig_bytes
The problem: == implemented as a byte-by-byte
comparison
Comparator returns false when first inequality
found

Dan Boneh

Warning: verification timing attacks

[L09]

target
msg

m , tag

accept or reject

Timing attack: to compute tag for target message m do:

Step 1: Query server with random tag
Step 2: Loop over all possible first bytes and query server.
stop when verification takes a little longer than in step 1
Step 3: repeat for all tag bytes until valid tag found

Dan Boneh

Defense #1
Make string comparator always take same time
(Python) :
return false if sig_bytes has wrong length
result = 0
for x, y in zip( HMAC(key,msg) , sig_bytes):
result |= ord(x) ^ ord(y)
return result == 0
Can be difficult to ensure due to optimizing compiler.

Dan Boneh

Defense #2
Make string comparator always take same time
(Python) :
def Verify(key, msg, sig_bytes):
mac = HMAC(key, msg)
return HMAC(key, mac) == HMAC(key,
sig_bytes)
Attacker doesnt know values being compared

Dan Boneh

Lesson

Dont implement crypto yourself !

Dan Boneh

End of Segment

Dan Boneh