Cryptology ePrint Archive: Report 2017/534

Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners

Zhenzhen Bao and Lei Wang and Jian Guo and Dawu Gu

Abstract: In this paper, we study functional-graph-based (second) preimage attacks against hash combiners. Our contributions are threefold:

\begin​{itemize}

\item in EUROCRYPT~2016, Dinur proposes generic (second) preimage attacks on the concatenation combiner and the XOR combiner using a new and essential observation on functional graph, which is experimentally verified but the proof is incomplete. Our first contribution is to provide a proof for Dinur's observation;

\item we find improved preimage attack against the XOR combiner with a complexity of $2^{5n/8}$, while the previous best-known complexity is $2^{2n/3}$;

\item we find the first generic second-preimage attack on Zipper hash with an optimal complexity of $2^{3n/5}$.

\end{itemize}

Category / Keywords: Hash Combiner, Functional Graph, XOR Combiner, Zipper Hash, (Second) Preimage Attack

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 5 Jun 2017, last revised 5 Jun 2017

Contact author: wanglei_hb at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Note: Minor revisited

Version: 20170607:035711 (All versions of this report)

Short URL: ia.cr/2017/534

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]