//img.uscri.be/pth/7473ed110ec49468d12946b0d60a6681cdeb0b9e
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Introduction The SHA competition New attacks on SHA candidates

De
110 pages
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


Voir plus Voir moins
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