### Preimage Attack on Hashing with Polynomials proposed at ICISC'06

Donghoon Chang

##### Abstract

In this paper, we suggest a preimage attack on Hashing with Polynomials \cite{Shpilrain06b}. The algorithm has $n$-bit hash output and $n$-bit intermediate state. (for example, $n=163$). The algorithm is very simple and light so that it can be implement in low memory environment. Our attack is based on the meet-in-the-middle attack. We show that we can find a preimage with the time complexity $2^{n-t}+2^{t}*(n+1/33)$ and the memory $2^{t}$ even though the recursive formula $H$ uses any \textsf{f} whose each term's degree in terms of \textsf{x} is $2^a$ for a non-negative integer $a$. We recommend that hash functions such as Hashing with Polynomials should have the intermediate state size at least two times bigger than the output size.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash FunctionPolynomialPreimage Attack
Contact author(s)
pointchang @ gmail com
History
2006-11-22: last of 5 revisions
See all versions
Short URL
https://ia.cr/2006/411

CC BY

BibTeX

@misc{cryptoeprint:2006/411,
author = {Donghoon Chang},
title = {Preimage Attack on Hashing with Polynomials proposed at ICISC'06},
howpublished = {Cryptology ePrint Archive, Paper 2006/411},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/411}},
url = {https://eprint.iacr.org/2006/411}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.