Paper 2014/302
Branching Heuristics in Differential Collision Search with Applications to SHA-512
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}$.
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
- cryptanalysishash functionsdifferential cryptanalysisSHA-2SHA-512collision attackguess-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}
}
