Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

The First Collision for Full SHA-1

verfasst von : Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks.
Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes.
A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack.
In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two distinct PDF documents with the same SHA-1 hash that display different arbitrarily-chosen visual contents.
We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to \(2^{63.1}\) calls to SHA-1’s compression function, and took approximately 6 500 CPU years and 100 GPU years. While the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100 000 times faster than a brute force search.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Identity-Based Encryption from the Diffie-Hellman Assumption
Nächstes Kapitel Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
For instance, SHA-1 certificates are still being sold by CloudFlare at the time of writing: https://​www.​cloudflare.​com/​ssl/​dedicated-certificates/​.
 
2
We eventually produced two message block pair solutions for the first near-collision attack. This provided a small additional amount of freedom in the search for the non-linear path of the second block.
 
5
We were quite lucky in that respect. The expected number required is about 2.5 times more than that.
 
6
Note that the comparison between factorization and discrete logarithm computation mentioned in [23] gives for the former a slightly lower figure of about 1700 core years.
 
7
But now is also a good time to recall that directly comparing CPU and GPU cost is tricky.
 
8
This is assuming that the total energy requirements scale linearly with the consumption of the processing units.
 
Literatur
1.
Albertini, A., Aumasson, J.-P., Eichlseder, M., Mendel, F., Schläffer, M.: Malicious hashing: Eve’s variant of SHA-1. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 1–19. Springer, Cham (2014). doi:10.​1007/​978-3-319-13051-4_​1 CrossRef
2.
Albertini, A., et al.: Exploiting identical-prefix hash function collisions. Draft (2017)
3.
4.
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and reduced SHA-1. In: Cramer [6], pp. 36–57 (2005)
5.
Chabaud, F., Joux, A.: Differential collisions in SHA-0. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 56–71. Springer, Heidelberg (1998). doi:10.​1007/​BFb0055720
6.
Cramer, R. (ed.): EUROCRYPT. LNCS, vol. 3494. Springer, Cham (2005)MATH
7.
Cannière, C., Mendel, F., Rechberger, C.: Collisions for 70-step SHA-1: on the full cost of collision search. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 56–73. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-77360-3_​4 CrossRef
8.
De Cannière, C., Rechberger, C.: Finding SHA-1 characteristics: general results and applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1–20. Springer, Heidelberg (2006). doi:10.​1007/​11935230_​1 CrossRef
9.
Boer, B., Bosselaers, A.: An attack on the last two rounds of MD4. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 194–203. Springer, Heidelberg (1992). doi:10.​1007/​3-540-46766-1_​14
10.
Boer, B., Bosselaers, A.: Collisions for the compression function of MD5. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 293–304. Springer, Heidelberg (1994). doi:10.​1007/​3-540-48285-7_​26
11.
12.
Fillinger, M., Stevens, M.: Reverse-engineering of the cryptanalytic attack used in the flame super-malware. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 586–611. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48800-3_​24 CrossRef
13.
14.
Gebhardt, M., Illies, G., Schindler, W.: A note on practical value of single hash collisions for special file formats. In: NIST First Cryptographic Hash Workshop, October 2005
15.
Grechnikov, E.: Collisions for 72-step and 73-step SHA-1: improvements in the method of characteristics. Cryptology ePrint Archive, Report 2010/413 (2010)
16.
Grechnikov, E., Adinetz, A.: Collision for 75-step SHA-1: intensive parallelization with GPU. Cryptology ePrint Archive, Report 2011/641 (2011)
17.
18.
InfoWorld: Oracle to Java devs: stop signing jar files with MD5, January 2017
19.
20.
Jutla, C.S., Patthak, A.C.: A matching lower bound on the minimum weight of SHA-1 expansion code. IACR Cryptology ePrint Archive 2005, 266 (2005)
21.
Karpman, P., Peyrin, T., Stevens, M.: Practical free-start collision attacks on 76-step SHA-1. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 623–642. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​30 CrossRef
22.
23.
Kleinjung, T., Diem, C., Lenstra, A.K., Priplata, C., Stahlke, C.: Computation of a 768-bit prime field discrete logarithm. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 185–201. Springer, Cham (2017). doi:10.​1007/​978-3-319-56620-7_​7 CrossRef
24.
CrySyS Lab: sKyWiper (a.k.a. flame a.k.a. flamer): a complex malware for targeted attacks. Laboratory of Cryptography and System Security, Budapest University of Technology and Economics, 31 May 2012
25.
Kaspersky Lab: The flame: questions and answers. Securelist blog, 28 May 2012
26.
Manuel, S.: Classification and generation of disturbance vectors for collision attacks against SHA-1. Des. Codes Cryptogr. 59(1–3), 247–263 (2011)MathSciNetCrossRefMATH
27.
28.
Mendel, F., Pramstaller, N., Rechberger, C., Rijmen, V.: The impact of carries on the complexity of collision attacks on SHA-1. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 278–292. Springer, Heidelberg (2006). doi:10.​1007/​11799313_​18 CrossRef
29.
Third author’s mum, T.: SHA-1 is still being used. Personnal communication
30.
National Institute of Standards and Technology: FIPS 180: Secure Hash Standard, May 1993
31.
National Institute of Standards and Technology: FIPS 180-1: Secure Hash Standard, April 1995
32.
Nossum, V.: SAT-based preimage attacks on SHA-1. Master’s thesis, University of Oslo (2012)
33.
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)MathSciNetCrossRefMATH
34.
Post, T.W.: US, Israel developed flame computer virus to slow Iranian nuclear efforts, officials say, June 2012
35.
Pramstaller, N., Rechberger, C., Rijmen, V.: Exploiting coding theory for collision attacks on SHA-1. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 78–95. Springer, Heidelberg (2005). doi:10.​1007/​11586821_​7 CrossRef
36.
Rivest, R.L.: The MD4 message digest algorithm. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303–311. Springer, Heidelberg (1991). doi:10.​1007/​3-540-38424-3_​22
37.
Rivest, R.L.: RFC 1321: The MD5 Message-Digest Algorithm, April 1992
38.
Schneier, B.: When will we see collisions for SHA-1? Blog (2012)
39.
40.
Shoup, V. (ed.): CRYPTO. LNCS, vol. 3621. Springer, Heidelberg (2005)MATH
41.
Stevens, M.: Attacks on hash functions and applications. Ph.D. thesis, Leiden University, June 2012
42.
43.
Stevens, M.: New collision attacks on SHA-1 based on optimal joint local-collision analysis. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 245–261. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38348-9_​15 CrossRef
44.
45.
Stevens, M., Lenstra, A., Weger, B.: Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 1–22. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72540-4_​1 CrossRef
46.
Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A., Molnar, D., Osvik, D.A., Weger, B.: Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 55–69. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-03356-8_​4 CrossRef
47.
ThreadPost: SHA-1 end times have arrived, January 2017
48.
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup [40], pp. 17–36 (2005)
49.
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [6], pp. 19–35 (2005)
50.
Wang, X., Yu, H., Yin, Y.L.: Efficient collision search attacks on SHA-0. In: Shoup [40], pp. 1–16 (2005)
51.
52.
Yajima, J., Sasaki, Y., Naito, Y., Iwasaki, T., Shimoyama, T., Kunihiro, N., Ohta, K.: A new strategy for finding a differential path of SHA-1. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 45–58. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-73458-1_​4 CrossRef
Metadaten
Titel
The First Collision for Full SHA-1
verfasst von
Marc Stevens
Elie Bursztein
Pierre Karpman
Ange Albertini
Yarik Markov
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_19