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

Donghoon Chang

Paper 2006/460

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

Donghoon Chang

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.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Hash Function Preimage Attack
Contact author(s): pointchang @ gmail com
History: 2006-12-05: received
Short URL: https://ia.cr/2006/460
License: CC BY

BibTeX

@misc{cryptoeprint:2006/460,
      author = {Donghoon Chang},
      title = {Preimage Attacks On Provably Secure {FFT} Hashing proposed at Second Hash Workshop in 2006},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/460},
      year = {2006},
      url = {https://eprint.iacr.org/2006/460}
}