Friday, October 1, 2010

Near-Collisions for the Reduced Round Versions of Some Second Round SHA-3 Compression Functions using Hill Climbing

Our latest paper on near-collision resistance on some of the SHA-3 candidates; Blake, Fugue, JH and Hamsi is accepted for Indocrypt 2010.

Abstract :
A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the second round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. Among the 130 possible reduced variants of Fugue-256, we practically observed collisions for 7 variants (e.g. (k; r; t) = (1; 2; 5)) and near-collisions for 26 variants (e.g. 234/256 bit near-collision for (k; r; t) = (2; 1; 8)).

We would like to thank Charanjit S. Jutla for pointing out an error in Fugue's results, in the previous version of this paper which is presented at the SHA-3 Workshop.

No comments: