CryptoDB
Preimage Attack on Hashing with Polynomials proposed at ICISC'06
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2006-21902, title={Preimage Attack on Hashing with Polynomials proposed at ICISC'06}, booktitle={IACR Eprint archive}, keywords={Hash Function, Polynomial, Preimage Attack}, url={http://eprint.iacr.org/2006/411}, note={ pointchang@gmail.com 13474 received 7 Nov 2006, last revised 22 Nov 2006}, author={Donghoon Chang}, year=2006 }