**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.

**Category / Keywords: **Hash Function, Polynomial, Preimage Attack

**Date: **received 7 Nov 2006, last revised 22 Nov 2006

**Contact author: **pointchang at gmail com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20061122:180157 (All versions of this report)

**Short URL: **ia.cr/2006/411

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]