[Resource Topic] 2006/413: Preimage Attack on Parallel FFT-Hashing

Welcome to the resource topic for 2006/413

Preimage Attack on Parallel FFT-Hashing

Authors: Donghoon Chang


Parallel FFT-Hashing was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. % In this work we show a preimage attack on Parallel FFT-Hashing with complexity 2^{t+64}+2^{128-t} and memory 2^{t} which is less than the generic complexity 2^{128}. When t=32, we can find a preimage with complexity 2^{97} and memory 2^{32}. Our method can be described as ``disseminative-meet-in-the-middle-attack’’ we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of Parallel FFT-Hashing has some weaknesses when preimage attack is considered. To the best of our knowledge, this is the first attack on Parallel FFT-Hashing.

ePrint: https://eprint.iacr.org/2006/413

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .