MULTI-COLLISIONS ATTACK IN RING HASH STRUCTURE

Nasour Bagheri, Babak Sadeghiyan, Majid Naderi

2008

Abstract

Ring hash structure is a new hash structure which has been introduced by Joux to strengthen the current hash structures against multi-collision attacks. In this paper, we present a cryptanalysis on Ring hash structure. We show that finding multi-collisions, i.e. 2k-way collision, for a Ring hash structure is not much harder than finding such multi-collisions for ordinary MD hash structure. The complexity of our attack is approximately log (n) times harder than the complexity of attacks against MD structures. We employ these multi-collisions to find a D-way pre-image for this structure. We show the complexity of finding 2K-way multi-collision and 2k-way preimage are O((k+1)x(n / 2)x2n/2 ) and O(kx n / 2x2n/2+2x2n ) respectively. We also show that Ring structure should not be used to create a hash function of 2n-bit length, by concatenatingmthis structure to any other hash structure of n-bit output length. We show that the time complexity of finding a collision for this concatenated structure is O((k+1)x(n / 2)x 2n /2 )that is much smaller than Ω(2n ), which is expected for a generic-birthday attack.

Paper Citation

in Harvard Style

Bagheri N., Sadeghiyan B. and Naderi M. (2008). MULTI-COLLISIONS ATTACK IN RING HASH STRUCTURE . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008) ISBN 978-989-8111-59-3, pages 278-284. DOI: 10.5220/0001917102780284

in Bibtex Style

@conference{secrypt08,
author={Nasour Bagheri and Babak Sadeghiyan and Majid Naderi},
title={MULTI-COLLISIONS ATTACK IN RING HASH STRUCTURE},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008)},
year={2008},
pages={278-284},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001917102780284},
isbn={978-989-8111-59-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2008)
TI - MULTI-COLLISIONS ATTACK IN RING HASH STRUCTURE
SN - 978-989-8111-59-3
AU - Bagheri N.
AU - Sadeghiyan B.
AU - Naderi M.
PY - 2008
SP - 278
EP - 284
DO - 10.5220/0001917102780284