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 exclusive-or (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 Hash-Twice $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 best-known 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 best-case 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 Merkle-Damgård construction or the HAIFA framework. -- A second attack with a best-case 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 Merkle-Damgård construction. -- An improvement upon the second attack with a best-case 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 narrow-pipe hash functions following the considered constructions can never provide $ n $-bit security. 2. A generic second-preimage 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 best-case 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 second-preimage attack on the Zipper hash with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{3n/5}$, obtained for challenge messages of length $2^{2n/5}$. 4. An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{13n/22}$, obtained for challenge messages of length $2^{13n/22}$. The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two $n$-bit narrow-pipe Merkle-Damgå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 multi-collision 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)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in JOC 2019
DOI
10.1007/s00145-019-09328-w
Keywords
Hash functionGeneric attackHash combinerXOR combinerConcatenation combinerZipper hashHash-Twice(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
2019-06-26: revised
2019-06-26: received
See all versions
Short URL
https://ia.cr/2019/755
License
Creative Commons Attribution
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/s00145-019-09328-w},
      note = {\url{https://eprint.iacr.org/2019/755}},
      url = {https://eprint.iacr.org/2019/755}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.