Paper 2006/411 Original: eprint.iacr.org/2006/411 ↗

Preimage Attack on Hashing with Polynomials proposed at ICISC'06

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.