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
}