Improved Collision Search for Hash Functions: New Advanced Message Modification

Yusuke NAITO; Kazuo OHTA; Noboru KUNIHIRO

doi:10.1093/ietfec/e91-a.1.46

Improved Collision Search for Hash Functions: New Advanced Message Modification

Yusuke NAITO, Kazuo OHTA, Noboru KUNIHIRO

Full Text Views

0

Share
Cite this

Summary :

In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 2³⁹ to 2³⁶ SHA-0 compression operations.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.1 pp.46-54

Publication Date: 2008/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.1.46

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

Category: Hash Functions

Cite this

Copy

Yusuke NAITO, Kazuo OHTA, Noboru KUNIHIRO, "Improved Collision Search for Hash Functions: New Advanced Message Modification" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 1, pp. 46-54, January 2008, doi: 10.1093/ietfec/e91-a.1.46.
Abstract: In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 2³⁹ to 2³⁶ SHA-0 compression operations.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.1.46/_p

Copy

@ARTICLE{e91-a_1_46,
author={Yusuke NAITO, Kazuo OHTA, Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Collision Search for Hash Functions: New Advanced Message Modification},
year={2008},
volume={E91-A},
number={1},
pages={46-54},
abstract={In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 2³⁹ to 2³⁶ SHA-0 compression operations.},
keywords={},
doi={10.1093/ietfec/e91-a.1.46},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Improved Collision Search for Hash Functions: New Advanced Message Modification
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 46
EP - 54
AU - Yusuke NAITO
AU - Kazuo OHTA
AU - Noboru KUNIHIRO
PY - 2008
DO - 10.1093/ietfec/e91-a.1.46
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2008
AB - In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 2³⁹ to 2³⁶ SHA-0 compression operations.
ER -