Introduction Analysis of the MD4 family The Design of SIMD Attacks on New Hash Functions

Gaëtan Leurent

Description

Introduction Analysis of the MD4 family The Design of SIMD Attacks on New Hash Functions Design and Analysis of Hash Functions Gaëtan Leurent École normale supérieure Paris, France Ph.D. Defense September 30, 2010 G. Leurent (ENS) Design and Analysis of Hash Functions September 30, 2010 1 / 59

• md4 family


• supérieure de paris


• no structural


• hash functions


• ecole normale


• output can


• any key


• introduction analysis

Sujets

• Oracle
• Hash function
• École normale
• Any key

Informations

• Publié par: pefav
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Introduction

Analysis of the MD4 family

The Design ofSIMD

Attacks on New Hash Functions

Design and Analysis of Hash Functions

G. Leurent (ENS)

Gaëtan Leurent

École normale supérieure Paris, France

Ph.D. Defense September 30, 2010

Design and Analysis of Hash Functions

September 30, 2010

1 / 59

Introduction

I

I

Analysis of the MD4 family

The Design ofSIMD

An Ideal Hash Function: the

Attacks on New Hash Functions

Random Oracle

Public Random Oracle The output can be used as a fingerprint of the document

G. Leurent (ENS)

Design and Analysis of Hash Functions

September 30, 2010

2 / 59

Introduction

I

I

Analysis of the MD4 family

The Design ofSIMD

Attacks on New Hash Functions

An Ideal Hash Function: the Random Oracle

0x1d66ca77ab361c6f

Public Random Oracle The output can be used as a fingerprint of the document

G. Leurent (ENS)

Design and Analysis of Hash Functions

September 30, 2010

2 / 59

Introduction

I

I

Analysis of the MD4 family

The Design ofSIMD

A Concrete Hash Function

A public function with no structural property. I Cryptographic strength without any key!

F:{0,1}

∗ → {0,1} n

G. Leurent (ENS)

F

Design and Analysis of Hash Functions

Attacks on New Hash Functions

0x1d66ca77ab361c6f

September 30, 2010

3 / 59

Introduction

I

I

Analysis of the MD4 family

The Design ofSIMD

A Concrete Hash Function

Apublicfunction withno structural property. I Cryptographic strength without any key!

F:{0,1}

∗ → {0,1} n

G. Leurent (ENS)

F

Design and Analysis of Hash Functions

Attacks on New Hash Functions

0x1d66ca77ab361c6f

September 30, 2010

3 / 59

Introduction

Analysis of the MD4 family

Preimage attack

GivenFandH, findM Ideal security: 2 n .

G. Leurent (ENS)

?

The Design ofSIMD

Security goals

F

s.t.F(M) =H.

0xb58bff99

Design and Analysis of Hash Functions

Attacks on New Hash Functions

September 30, 2010

4 / 59

Introduction

Analysis of the MD4 family

Second-preimage attack

=

?

GivenFandM 1 , findM 2 Ideal security: 2 n .

G. Leurent (ENS)

The Design ofSIMD

Security goals

F

F

0xf46cc414

=M 1 s.t.F(M 1 ) =F(M 2 ).

Design and Analysis of Hash Functions

Attacks on New Hash Functions

September 30, 2010

4 / 59

Introduction

Analysis of the MD4 family

Collision attack

?

=

?

The Design ofSIMD

Security goals

F

F

GivenF, findM 1 6=M 2 s.t.F(M 1 ) =F(M 2 ). 2 Ideal security: 2 n/ .

G. Leurent (ENS)

Design and Analysis of Hash Functions

?

Attacks on New Hash Functions

September 30, 2010

4 / 59

Introduction

Analysis of the MD4 family

The Design ofSIMD

Using Hash Functions

Hash functions are used in many different contexts:

I

I

I

I

To generateunique identifiers I Hash-and-sign signatures I Commitment schemes

As aone-wayfunction I One-Time-Passwords I Forward security

Tobreak the structureof the input I Entropy extractors I Key derivation I Pseudo-random number generator

To buildMACs I HMAC I Challenge/response authentication

G. Leurent (ENS)

Design and Analysis of Hash Functions

Attacks on New Hash Functions

September 30, 2010

5 / 59

Introduction

I

Analysis of the MD4 family

The Design ofSIMD

Hash function design

Build a smallcompression function, anditerate.

I

I I

Cut the message in chunksM 0 , ...M k H i =f(M i ,H −1 ) F(M) =H k

M 0

IV

G. Leurent (ENS)

f

M 1

H 0

f

M 2

H 1

f

Design and Analysis of Hash Functions

M 3

H 2

f

Attacks on New Hash Functions

H 3

September 30, 2010

6 / 59