Cryptology ePrint Archive: Report 2006/411

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 formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Discussion forum: Show discussion | Start new discussion