Freestart Collision for Full SHA-1

Abstract : This article presents an explicit freestart colliding pair for SHA-1, i.e. a collision for its internal compression function. This is the first practical break of the full SHA-1, reaching all 80 out of 80 steps. Only 10 days of computation on a 64-GPU cluster were necessary to perform this attack, for a runtime cost equivalent to approximately 2^{57.5} calls to the compression function of SHA-1 on GPU. This work builds on a continuous series of cryptanalytic advancements on SHA-1 since the theoretical collision attack breakthrough of 2005. In particular, we reuse the recent work on 76-step SHA-1 of Karpman et al. from CRYPTO 2015 that introduced an efficient framework to implement (freestart) collisions on GPUs; we extend it by incorporating more sophisticated accelerating techniques such as boomerangs. We also rely on the results of Stevens from EUROCRYPT 2013 to obtain optimal attack conditions; using these techniques required further refinements for this work. Freestart collisions do not directly imply a collision for the full hash function. However, this work is an important milestone towards an actual SHA-1 collision and it further shows how GPUs can be used very efficiently for this kind of attack. Based on the state-of-the-art collision attack on SHA-1 by Stevens from EUROCRYPT 2013, we are able to present new projections on the computational and financial cost required for a SHA-1 collision computation. These projections are significantly lower than what was previously anticipated by the industry, due to the use of the more cost efficient GPUs compared to regular CPUs. We therefore recommend the industry, in particular Internet browser vendors and Certification Authorities, to retract SHA-1 quickly. We hope the industry has learned from the events surrounding the cryptanalytic breaks of MD5 and will retract SHA-1 before concrete attacks such as signature forgeries appear in the near future.
Type de document :
Communication dans un congrès
EUROCRYPT 2016, May 2016, Vienne, Austria. Advances in Cryptology – EUROCRYPT 2016, 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49890-3_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01251023
Contributeur : Pierre Karpman <>
Soumis le : mardi 5 janvier 2016 - 15:13:56
Dernière modification le : jeudi 12 avril 2018 - 01:49:41

Lien texte intégral

Identifiants

Collections

Citation

Marc Stevens, Pierre Karpman, Thomas Peyrin. Freestart Collision for Full SHA-1. EUROCRYPT 2016, May 2016, Vienne, Austria. Advances in Cryptology – EUROCRYPT 2016, 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49890-3_18〉. 〈hal-01251023〉

Partager

Métriques

Consultations de la notice

317