Cryptology ePrint Archive: Report 2014/302

Branching Heuristics in Differential Collision Search with Applications to SHA-512

Maria Eichlseder and Florian Mendel and Martin Schläffer

Abstract: In this work, we present practical semi-free-start collisions for SHA-512 on up to 38 (out of 80) steps with complexity $2^{40.5}$. The best previously published result was on 24 steps. The attack is based on extending local collisions as proposed by Mendel et al. in their Eurocrypt 2013 attack on SHA-256. However, for SHA-512, the search space is too large for direct application of these techniques. We achieve our result by improving the branching heuristic of the guess-and-determine approach to find differential characteristics and conforming message pairs. Experiments show that for smaller problems like 27 steps of SHA-512, the heuristic can also speed up the collision search by a factor of $2^{20}$.

Category / Keywords: secret-key cryptography / cryptanalysis, hash functions, differential cryptanalysis, SHA-2, SHA-512, collision attack, guess-and-determine

Original Publication (in the same form): IACR-FSE-2014

Date: received 29 Apr 2014

Contact author: maria eichlseder at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20140430:205734 (All versions of this report)

Short URL: ia.cr/2014/302

Discussion forum: Show discussion | Start new discussion