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

Maria Eichlseder; Florian Mendel; Martin Schläffer

Paper 2014/302

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

Maria Eichlseder

Florian Mendel

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 .

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in TOSC 2014
DOI: 10.1007/978-3-662-46706-0_24
Keywords: cryptanalysis hash functions differential cryptanalysis SHA-2 SHA-512 collision attack guess-and-determine
Contact author(s): maria eichlseder @ iaik tugraz at
History: 2024-06-07: revised; 2014-04-30: received; See all versions
Short URL: https://ia.cr/2014/302
License: CC BY

BibTeX

@misc{cryptoeprint:2014/302,
      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},
      doi = {10.1007/978-3-662-46706-0_24},
      url = {https://eprint.iacr.org/2014/302}
}