Paper 2016/131

New Attacks on the Concatenation and XOR Hash Combiners

Itai Dinur

Abstract

We study the security of the concatenation combiner $H_1(M) \| H_2(M)$ for two independent iterated hash functions with $n$-bit outputs that are built using the Merkle-Damgård construction. In 2004 Joux showed that the concatenation combiner of hash functions with an $n$-bit internal state does not offer better collision and preimage resistance compared to a single strong $n$-bit hash function. On the other hand, the problem of devising second preimage attacks faster than $2^n$ against this combiner has remained open since 2005 when Kelsey and Schneier showed that a single Merkle-Damgård hash function does not offer optimal second preimage resistance for long messages. 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2016
Keywords
Hash functioncryptanalysisconcatenation combinerXOR combiner
Contact author(s)
dinuri @ cs bgu ac il
History
2016-02-15: received
Short URL
https://ia.cr/2016/131
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/131,
      author = {Itai Dinur},
      title = {New Attacks on the Concatenation and XOR Hash Combiners},
      howpublished = {Cryptology ePrint Archive, Paper 2016/131},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/131}},
      url = {https://eprint.iacr.org/2016/131}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.