Introduction Pseudo preimages Preimages Conclusion

Gaëtan Leurent

Description

Introduction Pseudo-preimages Preimages Conclusion MD4 is Not One-Way Gaëtan Leurent École Normale Supérieure Paris, France FSE 2008 G. Leurent (ENS) MD4 is Not One-Way FSE 2008 1 / 36

• hash functions


• preimages preimages


• round


• collision attack


• collisions complexity


• collision resistance


• full collision


• ecole normale

Sujets

• Hash function
• Collision attack
• Collision resistance
• École normale

Informations

• Publié par: pefav
• Nombre de lectures: 56
• Poids de l'ouvrage: 1 Mo

Extrait

Introduction Pseudo-preimages Preimages Conclusion
MD4 is Not One-Way
Gaëtan Leurent
École Normale Supérieure
Paris, France
FSE 2008
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 1 / 36Introduction Pseudo-preimages Preimages Conclusion
Hash Functions
nF :f0, 1g !f0, 1g
Should behave “like a random oracle”.
Collision attack
GivenF, findM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimage attack
GivenF andM , findM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage attack
GivenF andH, findM s.t. F(M)= H.
nIdeal security: 2 .
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 2 / 36766Introduction Pseudo-preimages Preimages Conclusion
Hash Functions
nF :f0, 1g !f0, 1g
Should behave “like a random oracle”.
Collision attack
GivenF, findM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimage attack
GivenF andM , findM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage attack
GivenF andH, findM s.t. F(M)= H.
nIdeal security: 2 .
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 2 / 36766Introduction Pseudo-preimages Preimages Conclusion
Hash Function Cryptanalysis
I Many papers study collision resistance...
... but collision attacks have limited impact.
I Preimage attacks are rather rare...
... but could have a devastating impact.
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 3 / 36Introduction Pseudo-preimages Preimages Conclusion
Previous work
1990 MD4 design (Rivest)
1991 2-round collisions (den Boer & Bosselaers – Merkle – Vaudenay)
1996 Full collision (Dobbertin)
1998 2-round preimages (Dobbertin)
2005 Very efficient collisions (Wangetal. – Sasakietal.)
Best attacks
1Collisions Complexity 2 (Sasakietal.)
32IPreimages 2 rounds: 2 (Dobbertin)
I 2 rounds & 7 steps (Deetal.)
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 4 / 36Introduction Pseudo-preimages Preimages Conclusion
Previous work
1990 MD4 design (Rivest)
1991 2-round collisions (den Boer & Bosselaers – Merkle – Vaudenay)
1996 Full collision (Dobbertin)
1998 2-round preimages (Dobbertin)
2005 Very efficient collisions (Wangetal. – Sasakietal.)
Best attacks
1Collisions Complexity 2 (Sasakietal.)
32IPreimages 2 rounds: 2 (Dobbertin)
I 2 rounds & 7 steps (Deetal.)
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 4 / 36Introduction Pseudo-preimages Preimages Conclusion
Why bother?
MD4 is clearly not a collision-resistant hash function, but:
I Many hash functions use a similar design:
MD5, SHA-1, SHA-2, ...
I MD4 is believed to be one-way.
I MD4 is still in use:
I To “encrypt” passwords in Windows NT
I In the S/KEY one-time-password system
I For integrity checks (rsync – eDonkey)
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 5 / 36Introduction Pseudo-preimages Preimages Conclusion
The Merkle-Damgård construction
Build a hash function from a compression function.
n+k ncF :f0, 1g !f0, 1g
h = IV, h = cF(h ,M)0 i+1 i i
F(M ,M , ...M )= h0 1 p 1 p
M
M M M M0 1 2 3
cF cF cF cF
h h h F(M)IV 1 2 3
Cryptanalysis targets the compression function.
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 6 / 367Introduction Pseudo-preimages Preimages Conclusion
Pseudo-preimage attack
Pseudo-preimage attack
GivencF andH, find IV,M s.t. cF(IV,M)= H.
nIdeal security: 2 .
kIf we have a pseudo-preimage attack with complexity 2 ,
n+k+1
2we can build a preimage attack with complexity 2 :
..IV H.
n+k n k
2 22 2
n k1 122
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 7 / 36Introduction Pseudo-preimages Preimages Conclusion
Pseudo-preimage attack
Pseudo-preimage attack
GivencF andH, find IV,M s.t. cF(IV,M)= H.
nIdeal security: 2 .
kIf we have a pseudo-preimage attack with complexity 2 ,
n+k+1
2we can build a preimage attack with complexity 2 :
..IV H.
n+k n k
2 22 2
n k1 122
G. Leurent (ENS) MD4 is Not One-Way FSE 2008 7 / 36