Paper 2019/755
Generic Attacks on Hash Combiners
Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, and Lei Wang
Abstract
Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusiveor (XOR) combiner $H_1(M) \oplus H_2(M)$ and the concatenation combiner $H_1(M) \parallel H_2(M)$. Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as HashTwice $H_2(H_1(IV,M),M)$ and the Zipper hash $H_2(H_1(IV,M),\overleftarrow{M})$, where $\overleftarrow{M}$ is the reverse of the message $M$. In this work, we study the security of these hash combiners by devising the bestknown generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: 1. Several generic preimage attacks on the XOR combiner:  A first attack with a bestcase complexity of $2^{5n/6}$ obtained for messages of length $2^{n/3}$. It relies on a novel technical tool named Interchange Structure. It is applicable for combiners whose underlying hash functions follow the MerkleDamgård construction or the HAIFA framework.  A second attack with a bestcase complexity of $2^{2n/3}$ obtained for messages of length $ 2^{n/2} $. It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the MerkleDamgård construction.  An improvement upon the second attack with a bestcase complexity of $2^{5n/8}$ obtained for messages of length $2^{5n/8}$. It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two $n$bit narrowpipe hash functions following the considered constructions can never provide $ n $bit security. 2. A generic secondpreimage attack on the concatenation combiner of two Merkle Damgård hash functions. This attack finds second preimages faster than $2^n$ for challenges longer than $2^{2n/7}$ and has a bestcase complexity of $2^{3n/4}$ obtained for challenges of length $2^{3n/4}$. It also exploits properties of functional graphs of random mappings. 3. The first generic secondpreimage attack on the Zipper hash with underlying hash functions following the MerkleDamgård construction. The bestcase complexity is $2^{3n/5}$, obtained for challenge messages of length $2^{2n/5}$. 4. An improved generic secondpreimage attack on HashTwice with underlying hash functions following the MerkleDamgård construction. The bestcase complexity is $2^{13n/22}$, obtained for challenge messages of length $2^{13n/22}$. The last three attacks show that regarding secondpreimage resistance, the concatenation and cascade of two $n$bit narrowpipe MerkleDamgård hash functions do not provide much more security than that can be provided by a single $n$bit hash function. Our main technical contributions include the following: 1. The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. 2. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multicollision for both of the underlying hash functions. 3. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in JOC 2019
 DOI
 10.1007/s0014501909328w
 Keywords
 Hash functionGeneric attackHash combinerXOR combinerConcatenation combinerZipper hashHashTwice(Second) Preimage attack
 Contact author(s)

baozhenzhen10 @ gmail com
dinuri @ cs bgu ac il
guojian @ ntu edu sg
gaetan leurent @ inria fr
wanglei_hb @ sjtu edu cn  History
 20190626: revised
 20190626: received
 See all versions
 Short URL
 https://ia.cr/2019/755
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/755, author = {Zhenzhen Bao and Itai Dinur and Jian Guo and Gaëtan Leurent and Lei Wang}, title = {Generic Attacks on Hash Combiners}, howpublished = {Cryptology ePrint Archive, Paper 2019/755}, year = {2019}, doi = {10.1007/s0014501909328w}, note = {\url{https://eprint.iacr.org/2019/755}}, url = {https://eprint.iacr.org/2019/755} }