Difference between revisions of "MD5"

From The ECRYPT Hash Function Website
 
(→‎Collision Attacks)
 
(12 intermediate revisions by 5 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>
 +
@inproceedings{eurocryptStevensLW07,
 +
  author = {Marc Stevens and Arjen K. Lenstra and Benne de Weger},
 +
  title = {Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities},
 +
  booktitle = {EUROCRYPT},
 +
  year = {2007},
 +
  pages = {1-22},
 +
  abstract = {We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 250 calls to the MD5 compression function, for any two chosen message prefixes P and P′, suffixes S and S′ can be constructed such that the concatenated values P||S and P′||S′ collide under MD5. Although the practical attack potential of this construction of chosen-prefix collisions is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys and different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/.},
 +
  editor = {Moni Naor},
 +
  volume = {4515},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {978-3-540-72539-8},
 +
  url = {http://dx.doi.org/10.1007/978-3-540-72540-4_1},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{eurocryptWangY05,
 +
  author = {Xiaoyun Wang and Hongbo Yu},
 +
  title = {How to Break MD5 and Other Hash Functions},
 +
  booktitle = {EUROCRYPT},
 +
  year = {2005},
 +
  pages = {19-35},
 +
  abstract = {MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.},
 +
  editor = {Ronald Cramer},
 +
  volume = {3494},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {3-540-25910-4},
 +
  url = {http://dx.doi.org/10.1007/11426639_2},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{eurocryptBoerB93,
 +
  author = {Bert den Boer and Antoon Bosselaers},
 +
  title = {Collisions for the Compression Function of MD5},
 +
  booktitle = {EUROCRYPT},
 +
  year = {1993},
 +
  pages = {293-304},
 +
  abstract = {At Crypto’ 91 Ronald L. Rivest introduced the MD5 Message Digest Algorithm as a strengthened version of MD4, differing from it on six points. Four changes are due to the two existing attacks on the two round versions of MD4. The other two changes should additionally strengthen MD5. However both these changes cannot be described as well-considered. One of them results in an approximate relation between any four consecutive additive constants. The other allows to create collisions for the compression function of MD5. In this paper an algorithm is described that finds such collisions. A C program implementing the algorithm establishes a work load of finding about 216 collisions for the first two rounds of the MD5 compression function to find a collision for the entire four round function. On a 33MHz 80386 based PC the mean run time of this program is about 4 minutes.},
 +
  url = {http://link.springer.de/link/service/series/0558/bibs/0765/07650293.htm},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{eurocryptBerson92,
 +
  author = {Thomas A. Berson},
 +
  title = {Differential Cryptanalysis Mod 2^32 with Applications to MD5},
 +
  booktitle = {EUROCRYPT},
 +
  year = {1992},
 +
  pages = {71-80},
 +
  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},
 +
  editor    = {Rainer A. Rueppel},
 +
  series    = {LNCS},
 +
  volume    = {658},
 +
  year      = {1993},
 +
}
 +
</bibtex>
  
 
----
 
----
Line 30: 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>
  
 
----
 
----
  
 
=== Others ===
 
=== Others ===
 +
<bibtex>
 +
@inproceedings{fseBlackCH06,
 +
  author    = {John Black and Martin Cochran and Trevor Highland},
 +
  title    = {A Study of the MD5 Attacks: Insights and Improvements},
 +
  pages    = {262-277},
 +
  url        = {http://dx.doi.org/10.1007/11799313_17},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4047},
 +
  year      = {2006},
 +
  isbn      = {3-540-36597-4},
 +
  abstract  = {MD5 is a well-known and widely-used cryptographic
 +
hash function. It has received renewed attention from researchers
 +
subsequent to the recent announcement of collisions found by Wang et al. [16].
 +
To date, however, the method used by researchers in this work has been fairly
 +
difficult to grasp. In this paper we conduct a study of all attacks on MD5 starting
 +
from Wang. We explain the techniques used by her team, give insights on how to improve
 +
these techniques, and use these insights to produce an even faster attack on MD5.
 +
Additionally, we provide an “MD5 Toolkit” implementing these improvements that we
 +
hope will serve as an open-source platform for further research. Our hope is that
 +
a better understanding of these attacks will lead to a better understanding of our
 +
current collection of hash functions, what their strengths and weaknesses are, and
 +
where we should direct future efforts in order to produce even stronger primitives.}
 +
}
 +
</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"