| Presentation | 2005-11-15 Improved Collision Attack on MD5 Yu SASAKI, Yusuke NAITO, Noboru KUNIHIRO, Kazuo OHTA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al. In this attack, conditions which are sufficient to generate collisions (called "sufficient condition") are introduced. This attack raises the success probability by modifing messages to satisfy these conditions. In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is 2^<37>. After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the complexity is 2^<33>. In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far. In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that this method work correctly is roughly 1/2. Therefore, the complexity of this attack is 2^<30>. Furthermore, we propose a more efficient collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | MD5 / collision attack / message modification / sufficient condition |
| Paper # | ISEC2005-104,OIS2005-67 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2005/11/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improved Collision Attack on MD5 |
| Sub Title (in English) | |
| Keyword(1) | MD5 |
| Keyword(2) | collision attack |
| Keyword(3) | message modification |
| Keyword(4) | sufficient condition |
| 1st Author's Name | Yu SASAKI |
| 1st Author's Affiliation | The University of Electro-Communications() |
| 2nd Author's Name | Yusuke NAITO |
| 2nd Author's Affiliation | The University of Electro-Communications |
| 3rd Author's Name | Noboru KUNIHIRO |
| 3rd Author's Affiliation | The University of Electro-Communications |
| 4th Author's Name | Kazuo OHTA |
| 4th Author's Affiliation | The University of Electro-Communications |
| Date | 2005-11-15 |
| Paper # | ISEC2005-104,OIS2005-67 |
| Volume (vol) | vol.105 |
| Number (no) | 396 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |