Difference between revisions of "MD5"

@@ Line 1: / Line 1: @@
 == Specification ==
-<!--
+* digest size: 128 bits
-* digest size: 160 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 ==
@@ Line 12: / Line 10: @@
 === 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 ===
+<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 ===
+<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>
 ----

Difference between revisions of "MD5"

Latest revision as of 15:20, 10 November 2008

Contents

1 Specification

2 Cryptanalysis

2.1 Best Known Results

2.2 Generic Attacks

2.3 Collision Attacks

2.4 Second Preimage Attacks

2.5 Preimage Attacks

2.6 Others

Navigation menu

Views

Personal tools

Navigation

Search

Tools