| Presentation | 2005-07-22 Improved Collision Attack on MD4 with Probability Almost 1 Yusuke NAITO, Yu SASAKI, 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 MD4 was proposed by Wang et. al.. Wang et. al. claimed that collision messeages are found with probability 2^<-6> to 2^<-2>, and the complexity is less than 2^8 MD4 hash operations. However, there were tyops and oversights in the method of Wang et. al.. In this paper, (1) We will evaluate the exact success probability again, (2) We will point out the typos and oversights in Wang's method, and (3) We will a new messege modification in third round of MD4. From (1), we proved that the method of Wang et. al. can find collision messages with success probability 2^<5.61>. From (2), we are able to find collision messages with the probability 2^<-2>. Also by combining the results of (2) and (3), our improved method is able to find collision messages with the probability almost 1. This complexity is less than 3 repetitions of MD4 hash operations. We confirmed that the improved method is about 85 times as fast as the method of Wang et. al. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | MD4 / collision attack / message modification / sufficient condition |
| Paper # | ISEC2005-58 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2005/7/15(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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improved Collision Attack on MD4 with Probability Almost 1 |
| Sub Title (in English) | |
| Keyword(1) | MD4 |
| Keyword(2) | collision attack |
| Keyword(3) | message modification |
| Keyword(4) | sufficient condition |
| 1st Author's Name | Yusuke NAITO |
| 1st Author's Affiliation | The University of Electro-Communications() |
| 2nd Author's Name | Yu SASAKI |
| 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-07-22 |
| Paper # | ISEC2005-58 |
| Volume (vol) | vol.105 |
| Number (no) | 194 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |