Improved Collision Attacks on MD4 and MD5

Yu SASAKI; Yusuke NAITO; Noboru KUNIHIRO; Kazuo OHTA

doi:10.1093/ietfec/e90-a.1.36

Improved Collision Attacks on MD4 and MD5

Yu SASAKI, Yusuke NAITO, Noboru KUNIHIRO, Kazuo OHTA

Full Text Views

0

Share
Cite this

Summary :

At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2³⁷ MD5 hash operations, and a collision of MD4 with complexity less than 2⁸ MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2²⁹ MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.1 pp.36-47

Publication Date: 2007/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.1.36

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Hash Functions

Cite this

Copy

Yu SASAKI, Yusuke NAITO, Noboru KUNIHIRO, Kazuo OHTA, "Improved Collision Attacks on MD4 and MD5" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 1, pp. 36-47, January 2007, doi: 10.1093/ietfec/e90-a.1.36.
Abstract: At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2³⁷ MD5 hash operations, and a collision of MD4 with complexity less than 2⁸ MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2²⁹ MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.1.36/_p

Copy

@ARTICLE{e90-a_1_36,
author={Yu SASAKI, Yusuke NAITO, Noboru KUNIHIRO, Kazuo OHTA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Collision Attacks on MD4 and MD5},
year={2007},
volume={E90-A},
number={1},
pages={36-47},
abstract={At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2³⁷ MD5 hash operations, and a collision of MD4 with complexity less than 2⁸ MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2²⁹ MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.},
keywords={},
doi={10.1093/ietfec/e90-a.1.36},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Improved Collision Attacks on MD4 and MD5
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 36
EP - 47
AU - Yu SASAKI
AU - Yusuke NAITO
AU - Noboru KUNIHIRO
AU - Kazuo OHTA
PY - 2007
DO - 10.1093/ietfec/e90-a.1.36
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2007
AB - At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2³⁷ MD5 hash operations, and a collision of MD4 with complexity less than 2⁸ MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2²⁹ MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.
ER -