Welcome to the resource topic for 2006/411
Title:
Preimage Attack on Hashing with Polynomials proposed at ICISC’06
Authors: 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.
ePrint: https://eprint.iacr.org/2006/411
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .