Introduction The SHA competition New attacks on SHA candidates
110 Pages
English
Gain access to the library to view online
Learn more

Introduction The SHA competition New attacks on SHA candidates

-

Gain access to the library to view online
Learn more
110 Pages
English

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


Subjects

Informations

Published by
Reads 9
Language English
Document size 1 MB

Exrait

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. ICryptographic 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. ICryptographic 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: 2n.
Second-preimage attack
GivenFandM1, findM2 Ideal security: 2n.
=M1s.t.F(M1
) =F(M2
Collision attack GivenF, findM16=M2s.t.F(M1) =F(M2). Ideal security: 2n/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: 2n.
Second-preimage attack
GivenFandM1, findM2 Ideal security: 2n .
=M1s.t.F(M1
) =F(M2
Collision attack GivenF, findM16=M2s.t.F(M1) =F(M2). 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: 2n.
Second-preimage attack
GivenFandM1, findM2 Ideal security: 2n.
=M1s.t.F(M1
) =F(M2
Collision attack GivenF, findM16=M2s.t.F(M1) =F(M2). Ideal security: 2n/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. IPrecomputation is allowed in standard security definition IDefine a family of function
Obvious relations between the security definitions do not hold. IEven 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 IStoreH(pw) IAllow verification of the password without storing the password
New attacks on SHA-3 candidates
One-time password IUser picksxand server storesy=H(H(H(x))) ITo authenticate, user sends a preimage ofy IFirst authentication withH(H(x)), server now storesH(H(x)) ISecond 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 ISignature algorithm are costly ISignH(m)instead ofm
Commitment IAlice commits toH(m ILater, she revealsm.
)without revealingm.
New attacks on SHA-3 candidates
Time-stamping IAuthority certifies thatH(m)was known at timet1 Imis revealed at timet2 INeed 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