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 Analysis of the MD4 family The Design of SIMD Attacks on New Hash Functions

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


Voir plus Voir moins
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. ICryptographic 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. ICryptographic 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: 2n.
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
=
?
GivenFandM1, findM2 Ideal security: 2n.
G. Leurent (ENS)
The Design ofSIMD
Security goals
F
F
0xf46cc414
=M1s.t.F(M1) =F(M2).
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, findM16=M2s.t.F(M1) =F(M2). 2 Ideal security: 2n/.
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 IHash-and-sign signatures ICommitment schemes
As aone-wayfunction IOne-Time-Passwords IForward security
Tobreak the structureof the input IEntropy extractors IKey derivation IPseudo-random number generator
To buildMACs IHMAC IChallenge/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 chunksM0, ...Mk Hi=f(Mi,H1) F(M) =Hk
M0
IV
G. Leurent (ENS)
f
M1
H0
f
M2
H1
f
Design and Analysis of Hash Functions
M3
H2
f
Attacks on New Hash Functions
H3
September 30, 2010
6 / 59
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin