Security Analysis of Zipper Hash Against Multicollisions Attacks
Abstract
In this paper, the existence of multicollisions in Zipper Hash structure, a new Hash structure which was introduced to strengthen the iterated Hash structures, is presented. This study shows that finding multicollisions, i.e. 2k-way collision, in this Hash structure is not much harder than finding such multicollisions in ordinary Merkle - Damgard (MD) structure. In fact, the complexity of the attacks is approximately n/2 times harder than what has been found for MD structures. Then, these large multicollisions are used as a tool to find D-way preimage for this structure. The complexity of finding 2K-way multicollisions and 2k-way preimages are (eq) and (eq) respectively. Similar to what has been proved by Joux for MD, it is shown in this paper that this structure could not be used to create a Hash function with 2n-bit length by concatenating this structure with any other Hash structure by Hash’s output length of n-bite. It is also shown that time complexity of finding a collision for this concatenated structure is (eq) which is much smaller than what was expected from generic-birthday attack which would be (eq) . In addition, it is shown that increasing the number of rounds of this Hash function can not improve its security against this attack significantly and the attacker can find multicollisions on this Hash function which means that this Hash function has a structural flaw.
Keywords:
Zipper Hash Structure, Hash function, multicollision attack, Joux attack, preimage attack, r-way collisionDownloads
References
A. Joux, “Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions”, Advances in Cryptology-CRYPTO ’04, Springer-Verlag, pp. 306–316, 2004 DOI: https://doi.org/10.1007/978-3-540-28628-8_19
M. Nandi, D. R. Stinson, “Multicollision Attacks on Some Generalized Sequential Hash Functions”, IEEE Transactions on Information Theory, Vol. 53, No. 2, pp. 759-767, 2007 DOI: https://doi.org/10.1109/TIT.2006.889721
M. Liskov, “Constructing an Ideal Hash Function from Weak Ideal Compression Functions”, 13th International Conference on Selected Areas in Cryptography, pp. 358-375, 2007 DOI: https://doi.org/10.1007/978-3-540-74462-7_25
P. Gauravaram, W. Millan, E. Dawson, K. Viswanathan, ”Constructing Secure Hash Functions by Enhancing Merkle-Damgard Construction”, Lecture Notes in Computer Science, Vol. 4058, pp. 407–420, 2006
P. Gauravaram, W. Millan, E. Dawson, K. Viswanathan, ”Constructing Secure Hash Functions by Enhancing Merkle-Damgard Construction (Extended Version)”, Information Security Institute (ISI), Queensland University of Technology (QUT), number QUT-ISI-TR-2006-013, http://www.isi.qut.edu.au/ research/ publications/technical/qut-isi-tr-2006-013.pdf, July 2006 DOI: https://doi.org/10.1007/11780656_34
S. Su, Y. Yang, B. Yang, S. Zhang ,”The Design and Analysis of a Hash Ring-iterative Structure”, available: http://eprint.iacr.org/2006/384.pdf
S. Lucks, “A failure-friendly design principle for Hash functions”, Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, 2005 DOI: https://doi.org/10.1007/11593447_26
W. R. Speirs, J. Molly, ”Making large Hash Functions from small compression function”, available:http://eprint.iacr.org/2007/239.ps
P. Lin, W. Wu, C. Wu1, T. Qiu, "Analysis of Zipper as a Hash Function”, Lecture Notes in Computer Science, Vol. 4991, pp. 392-403, 2008 DOI: https://doi.org/10.1007/978-3-540-79104-1_28
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
