New Message Differences for Collision Attacks on MD4 and MD5

Yu SASAKI; Lei WANG; Noboru KUNIHIRO; Kazuo OHTA

doi:10.1093/ietfec/e91-a.1.55

New Message Differences for Collision Attacks on MD4 and MD5

Yu SASAKI, Lei WANG, Noboru KUNIHIRO, Kazuo OHTA

Full Text Views

0

Share
Cite this

Summary :

In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 2⁴² MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.1 pp.55-63

Publication Date: 2008/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.1.55

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

Category: Hash Functions

Cite this

Copy

Yu SASAKI, Lei WANG, Noboru KUNIHIRO, Kazuo OHTA, "New Message Differences for Collision Attacks on MD4 and MD5" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 1, pp. 55-63, January 2008, doi: 10.1093/ietfec/e91-a.1.55.
Abstract: In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 2⁴² MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.1.55/_p

Copy

@ARTICLE{e91-a_1_55,
author={Yu SASAKI, Lei WANG, Noboru KUNIHIRO, Kazuo OHTA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={New Message Differences for Collision Attacks on MD4 and MD5},
year={2008},
volume={E91-A},
number={1},
pages={55-63},
abstract={In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 2⁴² MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.},
keywords={},
doi={10.1093/ietfec/e91-a.1.55},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - New Message Differences for Collision Attacks on MD4 and MD5
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 55
EP - 63
AU - Yu SASAKI
AU - Lei WANG
AU - Noboru KUNIHIRO
AU - Kazuo OHTA
PY - 2008
DO - 10.1093/ietfec/e91-a.1.55
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2008
AB - In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 2⁴² MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.
ER -