Introduction Pseudo preimages Preimages Conclusion

101

pages

Documents

Écrit par
Gaëtan Leurent

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

101

pages

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Poids de l'ouvrage

1 Mo

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

Voir

Publié par

pefav

Nombre de lectures

Poids de l'ouvrage

1 Mo

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, ﬁndM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimage attack
GivenF andM , ﬁndM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage attack
GivenF andH, ﬁndM 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, ﬁndM = M s.t. F(M )= F(M ).1 2 1 2
n/2Ideal security: 2 .
Second-preimage attack
GivenF andM , ﬁndM = M s.t. F(M )= F(M ).1 2 1 1 2
nIdeal security: 2 .
Preimage attack
GivenF andH, ﬁndM 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 efﬁcient 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 efﬁcient 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, ﬁnd 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, ﬁnd 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