Paper 2006/413

Preimage Attack on Parallel FFT-Hashing

Donghoon Chang

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cryptographic Hash FunctionPreimage AttackParallel FFT-Hashing.
Contact author(s)
pointchang @ gmail com
History
2007-01-30: last of 4 revisions
2006-11-14: received
See all versions
Short URL
https://ia.cr/2006/413
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/413,
      author = {Donghoon Chang},
      title = {Preimage Attack on Parallel FFT-Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2006/413},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/413}},
      url = {https://eprint.iacr.org/2006/413}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.