Introduction The SHA competition New attacks on SHA candidates

Gaëtan Leurent

Description

Introduction The SHA-3 competition New attacks on SHA-3 candidates A Look at the SHA-3 Competition: Design and Analysis of Hash Functions Gaëtan Leurent École Normale Supérieure Paris, France Universtity of Luxembourg January 19, 2010 G. Leurent (ENS) A Look at the SHA-3 Competition: Design and Analysis of Hash Functions 1 / 68

• hash functions


• attacks


• ideal security


• collision attack


• security goals


• candidates self-similarity attacks


• candidat

Sujets

• Hash function
• Collision attack
• Candidat

Informations

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

Extrait

Introduction

The SHA-3 competition

New attacks on SHA-3 candidates

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

G. Leurent (ENS)

Gaëtan Leurent

École Normale Supérieure Paris, France

Universtity of Luxembourg January 19, 2010

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

1 / 68

Introduction

Introduction Hash functions The MD4 family

The SHA-3 competition New designs SIMD

The SHA-3 competition

Outline

New attacks on SHA-3 candidates Self-similarity attacks Cancellation cryptanalysis on generalized Feistels

G. Leurent (ENS)

New attacks on SHA-3 candidates

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

2 / 68

Introduction

I

I

The SHA-3 competition

What is a hash function?

A public function with no structural properties. I Cryptographic strength without keys!

F:{0,1}

∗ → {0,1} n

G. Leurent (ENS)

F

New attacks on SHA-3 candidates

0x1d66ca77ab361c6f

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

3 / 68

Introduction

I

I

The SHA-3 competition

What is a hash function?

Apublicfunction withno structural properties. I Cryptographic strength without keys!

F:{0,1}

∗ → {0,1} n

G. Leurent (ENS)

F

New attacks on SHA-3 candidates

0x1d66ca77ab361c6f

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

3 / 68

Introduction

Preimage attack

The SHA-3 competition

Security goals

GivenFandH, findMs.t.F(M) =H. Ideal security: 2 n .

Second-preimage attack

GivenFandM 1 , findM 2 Ideal security: 2 n .

=M 1 s.t.F(M 1

) =F(M 2

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

I

Ideal behaviour: random oracle.

G. Leurent (ENS)

).

New attacks on SHA-3 candidates

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

4 / 68

Introduction

Preimage attack

The SHA-3 competition

Security goals

GivenFandH, findMs.t.F(M) =H. Ideal security: 2 n .

Second-preimage attack

GivenFandM 1 , findM 2 Ideal security: 2 n .

=M 1 s.t.F(M 1

) =F(M 2

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

I

Ideal behaviour: random oracle.

G. Leurent (ENS)

).

New attacks on SHA-3 candidates

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

4 / 68

Introduction

Preimage attack

The SHA-3 competition

Security goals

GivenFandH, findMs.t.F(M) =H. Ideal security: 2 n .

Second-preimage attack

GivenFandM 1 , findM 2 Ideal security: 2 n .

=M 1 s.t.F(M 1

) =F(M 2

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

I

Ideal behaviour: random oracle.

G. Leurent (ENS)

).

New attacks on SHA-3 candidates

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

4 / 68

Introduction

I

I

The SHA-3 competition

New attacks on SHA-3 candidates

Security definitions: difficulties

A single function can not be collision resistant. I Precomputation is allowed in standard security definition I Define a family of function

Obvious relations between the security definitions do not hold. I Even more mess with families of functions!

G. Leurent (ENS)

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

5 / 68

Introduction

I

I

The SHA-3 competition

Use as a one-way function

Unix password file I StoreH(pw) I Allow verification of the password without storing the password

New attacks on SHA-3 candidates

One-time password I User picksxand server storesy=H(H(H(x))) I To authenticate, user sends a preimage ofy I First authentication withH(H(x)), server now storesH(H(x)) I Second authentication withH(x) ... I

G. Leurent (ENS)

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

6 / 68

Introduction

I

I

I

The SHA-3 competition

Use as unique identifiers

Hash-and-sign I Signature algorithm are costly I SignH(m)instead ofm

Commitment I Alice commits toH(m I Later, she revealsm.

)without revealingm.

New attacks on SHA-3 candidates

Time-stamping I Authority certifies thatH(m)was known at timet 1 I mis revealed at timet 2 I Need a stronger notion that second-preimage resistance: herding attack

G. Leurent (ENS)

A Look at the SHA-3 Competition: Design and Analysis of Hash Functions

7 / 68