International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Preimage Attacks On Provably Secure FFT Hashing proposed at Second Hash Workshop in 2006

Authors:
Donghoon Chang
Download:
URL: http://eprint.iacr.org/2006/460
Search ePrint
Search Google
Abstract: `Provably Secure FFT Hashing' (We call FFT-Hash in this paper) was suggested by Lyubashevsky et al.. in Second Hash Workshop in Aug. 2006. This paper shows preimage attacks on hash functions based on three modes of FFT-Hash. In case of `Nano' whose output size is 513 bits, we can find a preimage with complexity $2^{385}$. In case of `Mini' whose output size is 1025 bits, we can find a preimage with complexity $2^{769}$. In case of `Mini' whose output size is 28672 bits, we can find a preimage with complexity $2^{24576}$. This means that the structure of FFT-Hash is weak in the viewpoint of the preimage resistance. We recommend that FFT-Hash can not be used in case of the output size less than 256 bits because the full security against the preimage attack are crucial in such a short output size. And also we should not chop the hash output in order to get a short hash output like SHA-224 and SHA-384, because for example we can find a preimage with complexity $2^{128}$ (not $2^{256}$) in case of `Nano' with chopping 257 bits whose hash output is 256 bits.
BibTeX
@misc{eprint-2006-21951,
  title={Preimage Attacks On Provably Secure FFT Hashing proposed at Second Hash Workshop in 2006},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Hash Function, Preimage Attack},
  url={http://eprint.iacr.org/2006/460},
  note={ pointchang@gmail.com 13487 received 4 Dec 2006},
  author={Donghoon Chang},
  year=2006
}