Paper 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.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Hash FunctionPolynomialPreimage Attack
- Contact author(s)
- pointchang @ gmail com
- History
- 2006-11-22: last of 5 revisions
- 2006-11-14: received
- See all versions
- Short URL
- https://ia.cr/2006/411
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/411,
author = {Donghoon Chang},
title = {Preimage Attack on Hashing with Polynomials proposed at ICISC'06},
howpublished = {Cryptology ePrint Archive, Paper 2006/411},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/411}},
url = {https://eprint.iacr.org/2006/411}
}
