Abstract: This work exposes a practical attack against the new hash function design FORK-256 proposed by Hong et al. at FSE 2006. Our attack allows to find a collision against a 160-bit truncated version of FORK-256's compression function with a complexity of 249 hash computations and with negligible memory. This has to be compared with the theoretical complexity of 280 hash computations given by the birthday paradox. Additionally, we expose a 1-bit (resp. 2-bit) near-collision attack against the full version of FORK-256 running with a complexity of 2125 (resp. 2120) and with negligible memory, and exhibit a 22-bit near collision. Finally, we discuss very recent independent results about FORK-256, and show how our attack strategy can be used to improve upon these results to yield a collision against the complete version of FORK-256 with a complexity of 2109 hash computations and about 264 memory.
Available material:
- get the paper submited to FSE 2007
- our 22-bit near collision is the best near collision
against FORK-256 up to now:
CVan: 0x8406e290 0x5988c6af 0x76a1d478 0x0eb60cea 0xf5c5d865 0x458b2dd1 0x528590bf 0xc3bf98a1 CVbn: 0x8406e290 0x5988cab3 0x76a1d478 0x0eb60cea 0xf5c5d865 0x458b2dd1 0x528590bf 0xc3bf98a1 M: 0x396eedd8 0x0e8c2a93 0xb961f8a4 0xf0a06fc6 0x9935952b 0xe01d16c9 0xddc60aa4 0x0ac1d8df 0xc6fef1d8 0x4c472ca6 0x58d9322d 0x2d087b65 0x7c8e1a26 0x71ba5da1 0xba5d2bfc 0x1988f929 CVan+1: 0x9897c70a 0x4e18862d 0xb4725ac1 0xcfc9f92c 0x9aa0637d 0xae772570 0x74dd4af1 0xcd444dd7 CVbn+1: 0x9897c70a 0x4e1880f9 0x1e677302 0x4c650966 0xf4792bf4 0xae772570 0x74dd4af1 0xcd444dd7
See also:
- Cryptanalysis of Reduced Variants of the FORK-256 Hash Function by Florian Mendel, Joseph Lano, and Bart Preneel. (CT-RSA 2007)
- Weaknesses of the FORK-256 Compression Function by Krystian Matusiewicz, Scott Contini, and Josef Pieprzyk with which our work was merged at FSE 2007.
- New FORK-256, a new version of the hash function.
- A Meet-in-the-Middle Collision Attack Against the New FORK-256 by Markku-Juhani O. Saarinen.