Difference between revisions of "MD5"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Collision Attacks)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Specification ==
 
== Specification ==
  
−
<!--
+
* digest size: 128 bits
−
* digest size: 160 bits
 
 
* max. message length: < 2<sup>64</sup> bits
 
* max. message length: < 2<sup>64</sup> bits
−
* compression function: 512-bit message block, 160-bit chaining variable
+
* compression function: 512-bit message block, 128-bit chaining variable
−
* Specification:  
+
* Specification: [http://www.ietf.org/rfc/rfc1321.txt RFC1321]
−
-->
 
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
Line 12: Line 10:
  
 
=== Best Known Results ===
 
=== Best Known Results ===
 +
 +
The best known collision attack is due to Klima with a complexity of 2<sup>29</sup> effort.
  
 
----
 
----
Line 21: Line 21:
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
−
 
+
<bibtex>
 +
@inproceedings{fseLeurent07,
 +
  author    = {Ga&euml;tan Leurent},
 +
  title    = {Message Freedom in MD4 and MD5 Collisions: Application to APOP},
 +
  pages    = {309-328},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-74619-5_20},
 +
  editor    = {Alex Biryukov},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4593},
 +
  year      = {2007},
 +
  isbn      = {978-3-540-74617-1},
 +
  abstract  = {In Wang’s attack, message modifications allow to
 +
deterministically satisfy certain sufficient conditions to find
 +
collisions efficiently. Unfortunately, message modifications
 +
significantly change the messages and one has little control
 +
over the colliding blocks. In this paper, we show how to choose
 +
small parts of the colliding messages. Consequently, we break a
 +
security countermeasure proposed by Szydlo and Yin at CT-RSA ’06,
 +
where a fixed padding is added at the end of each block. Furthermore,
 +
we also apply this technique to recover part of the passwords in the
 +
Authentication Protocol of the Post Office Protocol (POP). This shows
 +
that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.}
 +
}
 +
</bibtex>
 
<bibtex>
 
<bibtex>
 
@inproceedings{eurocryptStevensLW07,
 
@inproceedings{eurocryptStevensLW07,
Line 77: Line 102:
 
   abstract = {We introduce the idea of differential cryptanalysis mod 2^32 and apply it to the MD5 message digest algorithm. We derive a theory for differential cryptanalysis of the circular shift function. We demonstrate a high-probability differentials which leave the message digest register unchanged for each of MD5’s four rounds, and explain how more such differentials may be calculated.},
 
   abstract = {We introduce the idea of differential cryptanalysis mod 2^32 and apply it to the MD5 message digest algorithm. We derive a theory for differential cryptanalysis of the circular shift function. We demonstrate a high-probability differentials which leave the message digest register unchanged for each of MD5’s four rounds, and explain how more such differentials may be calculated.},
 
   url = {http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm},
 
   url = {http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm},
 +
  editor    = {Rainer A. Rueppel},
 +
  series    = {LNCS},
 +
  volume    = {658},
 +
  year      = {1993},
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 88: Line 117:
 
=== Preimage Attacks ===
 
=== Preimage Attacks ===
  
 +
<bibtex>
 +
@inproceedings{acispSasakiA08,
 +
  author    = {Yu Sasaki and Kazumaro Aoki},
 +
  title    = {Preimage Attacks on Step-Reduced MD5},
 +
  booktitle = {ACISP},
 +
  year      = {2008},
 +
  pages    = {282-296},
 +
  abstract  = {In this paper, we propose preimage attacks on step-reduced MD5. We show that a preimage of a 44-step MD5 can be computed to a complexity of 2^96. We also consider a preimage attack against variants of MD5 where the round order is modified from the real MD5. In such a case, a preimage of a 51-step round-reordered MD5 can be computed to a complexity of 2^96. Our attack uses local collisions of MD5 to create a degree of message freedom. This freedom enables us to match the two 128-bit intermediate values efficiently.},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-70500-0_21},
 +
  editor    = {Yi Mu and Willy Susilo and Jennifer Seberry},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5107},
 +
  isbn      = {978-3-540-69971-2},
 +
}
 +
</bibtex>
  
 
----
 
----

Latest revision as of 15:20, 10 November 2008

1 Specification

  • digest size: 128 bits
  • max. message length: < 264 bits
  • compression function: 512-bit message block, 128-bit chaining variable
  • Specification: RFC1321

2 Cryptanalysis

2.1 Best Known Results

The best known collision attack is due to Klima with a complexity of 229 effort.

2.2 Generic Attacks

2.3 Collision Attacks

Gaëtan Leurent - Message Freedom in MD4 and MD5 Collisions: Application to APOP

FSE 4593:309-328,2007
http://dx.doi.org/10.1007/978-3-540-74619-5_20
Bibtex
Author : Gaëtan Leurent
Title : Message Freedom in MD4 and MD5 Collisions: Application to APOP
In : FSE -
Address :
Date : 2007

Marc Stevens, Arjen K. Lenstra, Benne de Weger - Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities

EUROCRYPT 4515:1-22,2007
http://dx.doi.org/10.1007/978-3-540-72540-4_1
Bibtex
Author : Marc Stevens, Arjen K. Lenstra, Benne de Weger
Title : Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities
In : EUROCRYPT -
Address :
Date : 2007

Xiaoyun Wang, Hongbo Yu - How to Break MD5 and Other Hash Functions

EUROCRYPT 3494:19-35,2005
http://dx.doi.org/10.1007/11426639_2
Bibtex
Author : Xiaoyun Wang, Hongbo Yu
Title : How to Break MD5 and Other Hash Functions
In : EUROCRYPT -
Address :
Date : 2005

Bert den Boer, Antoon Bosselaers - Collisions for the Compression Function of MD5

EUROCRYPT pp. 293-304,1993
http://link.springer.de/link/service/series/0558/bibs/0765/07650293.htm
Bibtex
Author : Bert den Boer, Antoon Bosselaers
Title : Collisions for the Compression Function of MD5
In : EUROCRYPT -
Address :
Date : 1993

Thomas A. Berson - Differential Cryptanalysis Mod 2^32 with Applications to MD5

EUROCRYPT 658:71-80,1993
http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm
Bibtex
Author : Thomas A. Berson
Title : Differential Cryptanalysis Mod 2^32 with Applications to MD5
In : EUROCRYPT -
Address :
Date : 1993

2.4 Second Preimage Attacks

2.5 Preimage Attacks

Yu Sasaki, Kazumaro Aoki - Preimage Attacks on Step-Reduced MD5

ACISP 5107:282-296,2008
http://dx.doi.org/10.1007/978-3-540-70500-0_21
Bibtex
Author : Yu Sasaki, Kazumaro Aoki
Title : Preimage Attacks on Step-Reduced MD5
In : ACISP -
Address :
Date : 2008

2.6 Others

John Black, Martin Cochran, Trevor Highland - A Study of the MD5 Attacks: Insights and Improvements

FSE 4047:262-277,2006
http://dx.doi.org/10.1007/11799313_17
Bibtex
Author : John Black, Martin Cochran, Trevor Highland
Title : A Study of the MD5 Attacks: Insights and Improvements
In : FSE -
Address :
Date : 2006
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=MD5&oldid=2275"