Welcome to the resource topic for
**2006/411**

**Title:**

Preimage Attack on Hashing with Polynomials proposed at ICISC’06

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

**ePrint:**
https://eprint.iacr.org/2006/411

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .