Paper 2014/302

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

Maria Eichlseder, Florian Mendel, and Martin Schläffer


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}$.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in FSE 2014
cryptanalysishash functionsdifferential cryptanalysisSHA-2SHA-512collision attackguess-and-determine
Contact author(s)
maria eichlseder @ iaik tugraz at
2014-04-30: received
Short URL
Creative Commons Attribution


      author = {Maria Eichlseder and Florian Mendel and Martin Schläffer},
      title = {Branching Heuristics in Differential Collision Search with Applications to SHA-512},
      howpublished = {Cryptology ePrint Archive, Paper 2014/302},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.