In this paper, we develop new algorithms for cryptanalysis of hash combiners and use them to devise the first second preimage attack on the concatenation combiner. The attack finds second preimages faster than $2^n$ for messages longer than $2^{2n/7}$ and has optimal complexity of $2^{3n/4}$. This shows that the concatenation of two Merkle-Damgård hash functions is not as strong a single ideal hash function.
Our methods are also applicable to other well-studied combiners, and we use them to devise a new preimage attack with complexity of $2^{2n/3}$ on the XOR combiner $H_1(M) \oplus H_2(M)$ of two Merkle-Damgård hash functions. This improves upon the attack by Leurent and Wang (presented at Eurocrypt 2015) whose complexity is $2^{5n/6}$ (but unlike our attack is also applicable to HAIFA hash functions).
Our algorithms exploit properties of random mappings generated by fixing the message block input to the compression functions of $H_1$ and $H_2$. Such random mappings have been widely used in cryptanalysis, but we exploit them in new ways to attack hash function combiners.
Category / Keywords: secret-key cryptography / Hash function, cryptanalysis, concatenation combiner, XOR combiner Original Publication (in the same form): IACR-EUROCRYPT-2016 Date: received 13 Feb 2016 Contact author: dinuri at cs bgu ac il Available format(s): PDF | BibTeX Citation Version: 20160215:192855 (All versions of this report) Short URL: ia.cr/2016/131 Discussion forum: Show discussion | Start new discussion