Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/142884
Title: Generic attacks on hash combiners
Authors: Bao, Zhenzhen
Dinur, Itai
Guo, Jian
Leurent, Gaëtan
Wang, Lei
Keywords: Science::Mathematics
Issue Date: 2019
Source: Bao, Z., Dinur, I., Guo, J., Leurent, G., & Wang, L. (2020). Generic attacks on hash combiners. Journal of Cryptology, 33(3), 742-823. doi:10.1007/s00145-019-09328-w
Journal: Journal of Cryptology
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) com-biner H1(M)⊕H2(M) and the concatenation combiner H1(M) H2(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 H2(H1(IV, M), M) and the Zipper hash H2(H1(IV, M), ← − M), where ← − 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 § This paper is a combination and extension of three conference papers [LW15,Din16,BWGG17]. 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 preim-ages 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.
URI: https://hdl.handle.net/10356/142884
ISSN: 0933-2790
DOI: 10.1007/s00145-019-09328-w
Rights: © 2019 International Association for Cryptologic Research. All rights reserved. This paper was published by Springer in Journal of Cryptology and is made available with permission of International Association for Cryptologic Research.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Generic attacks on hash combiners_manuscript.pdf3.13 MBAdobe PDFView/Open

Page view(s) 50

23
checked on Oct 28, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.