Hash-Kollision in Git

175

Was würde eigentlich passieren, wenn ich bei der Verwendung von git eine Hash-Kollision hätte?

ZB schaffe ich es, zwei Dateien mit derselben sha1-Prüfsumme festzuschreiben. Würde git es bemerken oder eine der Dateien beschädigen?

Könnte git verbessert werden, um damit zu leben, oder müsste ich auf einen neuen Hash-Algorithmus umsteigen?

(Bitte lenken Sie diese Frage nicht ab, indem Sie diskutieren, wie unwahrscheinlich das ist - Danke)

git hash sha1 hash-collision Sec
quelle
26
I've been informed by the git Gods that the chances of a SHA1 collision is the same as the Earth being sucked up into the black hole created by the CERN accelerator. If this is indeed true, then there's no need for that extra memcmp. , Quelle: lwn.net/Articles/307281
KurzedMetal
16
ABSOLUT NICHT SO. Um Dan Bernstein zu zitieren: "Die Tatsache, dass Akademiker den SHA-1-Kollisionsangriff noch nicht durchgeführt haben, ist ein kleiner historischer Unfall" - jetzt, da der SHA-3-Wettbewerb beendet ist, besteht eine gute Chance, dass die relevanten Personen ihre Aufmerksamkeit auf sich ziehen den bekannten Angriff zu verwenden, um eine Kollision zu erzeugen. Marc Stevens schätzt die Schwierigkeit auf nur 2 ^ 61 Operationen. Es wird sehr wahrscheinlich bald eine SHA-1-Kollision geben; Es ist seltsam, dass es noch nicht passiert ist.
Paul Crowley
27
@KurzedMetal: Es besteht die Möglichkeit, im CERN ein Schwarzes Loch zu erzeugen (zwei Protonen hätten genau kollidiert (10 ^ -15 m)), aber dieses Schwarze Loch würde die Erde nicht aufsaugen, es würde aufgrund der Hawking-Strahlung sofort verdunsten ... Also Die Wahrscheinlichkeit einer SHA1-Kollision ist viel größer als das Aufsaugen ... nur zu sagen ...
Jaa-c
9
Mögliches Duplikat von Wie würde Git mit einer SHA-1-Kollision auf einem Blob umgehen?
Meagar
17
Es ist erstaunlich, dass Sie die Leute ausdrücklich gebeten haben, die Unwahrscheinlichkeit einer Git-Kollision nicht zu diskutieren, und fast alle sprachen über die Unwahrscheinlichkeit einer Git-Kollision. Diese Personen sollten lebenslang vom Stackoverflow ausgeschlossen werden!
Yukio Fukuzawa

Antworten:

108

Atome auf 10 Monden auswählen

Ein SHA-1-Hash ist eine 40-Hex-Zeichenfolge ... das sind 4 Bit pro Zeichen mal 40 ... 160 Bit. Jetzt wissen wir, dass 10 Bits ungefähr 1000 sind (um genau zu sein 1024), was bedeutet, dass es 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 verschiedene SHA-1-Hashes gibt ... 10 48 .

Was ist das Äquivalent? Nun, der Mond besteht aus ungefähr 10 47 Atomen. Wenn wir also 10 Monde haben ... und Sie zufällig ein Atom auf einem dieser Monde auswählen ... und dann wieder ein zufälliges Atom auf ihnen auswählen ... dann die Wahrscheinlichkeit, dass Sie dasselbe Atom zweimal auswählen ist die Wahrscheinlichkeit, dass zwei gegebene Git-Commits denselben SHA-1-Hash haben.

Wenn wir dies erweitern, können wir die Frage stellen ...

Wie viele Commits benötigen Sie in einem Repository, bevor Sie sich über Kollisionen Gedanken machen sollten?

Dies bezieht sich auf sogenannte "Geburtstagsangriffe", die sich wiederum auf das "Geburtstagsparadoxon" oder "Geburtstagsproblem" beziehen, das besagt, dass Sie, wenn Sie zufällig aus einem bestimmten Satz auswählen, überraschend wenige Tipps benötigen, bevor Sie wahrscheinlich sind zweimal etwas gepflückt haben. Aber "überraschend wenige" ist hier ein sehr relativer Begriff.

Wikipedia hat eine Tabelle zur Wahrscheinlichkeit von Kollisionen mit dem Geburtstagsparadoxon . Es gibt keinen Eintrag für einen 40-Zeichen-Hash. Eine Interpolation der Einträge für 32 und 48 Zeichen bringt uns jedoch in den Bereich von 5 * 10 22 git Commits für eine Kollisionswahrscheinlichkeit von 0,1%. Das sind fünfzigtausend Milliarden Milliarden verschiedene Commits oder fünfzig Zettacommits , bevor Sie eine Wahrscheinlichkeit von 0,1% für eine Kollision erreicht haben.

Die Bytesumme der Hashes allein für diese Commits wären mehr Daten als alle Daten, die ein Jahr lang auf der Erde generiert wurden. Das heißt, Sie müssten Code schneller ausgeben, als YouTube Videos überträgt. Viel Glück damit. : D.

Der Punkt dabei ist, dass die Wahrscheinlichkeit, dass jemand zufällig eine Kollision verursacht, so erstaunlich gering ist, dass Sie dieses Problem ignorieren können, es sei denn, jemand verursacht absichtlich eine Kollision

"Aber wenn eine Kollision es tut auftreten, was passiert dann eigentlich?“

Angenommen, das Unwahrscheinliche passiert, oder es ist jemandem gelungen, eine absichtliche SHA-1-Hash-Kollision maßzuschneidern . Was passiert dann?

In diesem Fall gibt es eine ausgezeichnete Antwort, bei der jemand damit experimentiert hat . Ich werde aus dieser Antwort zitieren:

  1. Wenn bereits ein Blob mit demselben Hash vorhanden ist, erhalten Sie überhaupt keine Warnungen. Alles scheint in Ordnung zu sein, aber wenn Sie pushen, jemand klont oder zurückkehrt, verlieren Sie die neueste Version (in Übereinstimmung mit den oben erläuterten Angaben).
  2. Wenn bereits ein Baumobjekt vorhanden ist und Sie einen Blob mit demselben Hash erstellen: Alles scheint normal zu sein, bis Sie entweder versuchen zu pushen oder jemand Ihr Repository klont. Dann werden Sie sehen, dass das Repo beschädigt ist.
  3. Wenn bereits ein Commit-Objekt vorhanden ist und Sie einen Blob mit demselben Hash erstellen: wie # 2 - beschädigt
  4. Wenn bereits ein Blob vorhanden ist und Sie ein Commit-Objekt mit demselben Hash erstellen, schlägt dies beim Aktualisieren des "ref" fehl.
  5. Wenn bereits ein Blob vorhanden ist und Sie ein Baumobjekt mit demselben Hash erstellen. Beim Erstellen des Commits schlägt dies fehl.
  6. Wenn bereits ein Baumobjekt vorhanden ist und Sie ein Festschreibungsobjekt mit demselben Hash erstellen, schlägt dies beim Aktualisieren des "ref" fehl.
  7. Wenn bereits ein Baumobjekt vorhanden ist und Sie ein Baumobjekt mit demselben Hash erstellen, scheint alles in Ordnung zu sein. Wenn Sie jedoch ein Commit durchführen, verweist das gesamte Repository auf den falschen Baum.
  8. Wenn bereits ein Commit-Objekt vorhanden ist und Sie ein Commit-Objekt mit demselben Hash erstellen, scheint alles in Ordnung zu sein. Wenn Sie jedoch ein Commit ausführen, wird das Commit niemals erstellt und der HEAD-Zeiger wird auf ein altes Commit verschoben.
  9. Wenn bereits ein Commit-Objekt vorhanden ist und Sie ein Baumobjekt mit demselben Hash erstellen, schlägt dies beim Erstellen des Commits fehl.

Wie Sie scheinen können, sind einige Fälle nicht gut. Insbesondere die Fälle 2 und 3 bringen Ihr Repository durcheinander. Es scheint jedoch, dass der Fehler in diesem Repository verbleibt und sich die Angriffs- / bizarre Unwahrscheinlichkeit nicht auf andere Repositorys ausbreitet.

Es scheint auch, dass das Problem der absichtlichen Kollisionen als echte Bedrohung erkannt wird, und so ergreift GitHub beispielsweise Maßnahmen, um dies zu verhindern .

MichaelK
quelle
22
Ich weiß nicht, ob die Zahlen korrekt sind, aber meine Güte, dies ist eine großartige grafische Methode, um die Unwahrscheinlichkeit zu beschreiben, und lustig :)
Mimoralea
4
Ich bin jetzt mit der NASA in Kontakt, um 10 Monde zu finden und auszuprobieren. Wenn wir nicht 10 Monde haben, sagt niemand, ob es funktioniert;)
Utkarsh Kumar
2
Die Wahrscheinlichkeit, dass ein zufälliges Festschreiben einer tatsächlichen Textdatei kollidiert, ist so gut wie Null, sehr unwahrscheinlich. Diese Antwort überspringt jedoch völlig die Tatsache, dass jemand versuchen könnte, absichtlich eine Kollision zu erzeugen. Mit dem angegriffenen SHA-1-Hash wird dies zu einem ziemlich wichtigen Faktor.
Maarten Bodewes
7
Grund für die Ablehnung: Sehr schön gesagt, aber Wahrscheinlichkeit bedeutet hier absolut nichts. Sie können das gleiche über das Gewinnen des Lottos sagen, aber die Leute gewinnen hier und da täglich Lotto. Die Lottofirma kann also nicht einfach sagen: Die Chance ist gering, sodass wir uns keine Sorgen machen müssen, ob wir den Jackpot tatsächlich auszahlen. Die Frage des OP lautet hier: Was passiert, wenn diese kleine Chance eintritt, und Sie haben das nicht beantwortet?
Yukio Fukuzawa
3
@FukuzawaYukio Es werden jedoch nicht 2 ^ 48 Lottoscheine gedruckt - nur Millionen (vielleicht 200 Millionen insgesamt pro Jahr ... wer weiß?), Und es gibt eine Lottogewinnung. Die Wahrscheinlichkeit ist viel höher und bei einigen Lottoscheinen wird der Gewinnschein immer gedruckt. Der Gewinner ist also unvermeidlich (es sei denn, das Gewinnerticket wurde versehentlich verlegt). Außerdem habe ich vor vielen Jahren ein pseudorealistisches Lottoscheinspiel gemacht: lottery.py . Unnötig zu erwähnen, dass Sie 99% der Zeit verlieren.
dylnmc
67

Wenn zwei Dateien dieselbe Hash-Summe in git haben, werden diese Dateien als identisch behandelt. In dem absolut unwahrscheinlichen Fall, dass dies passiert, können Sie immer ein Commit zurückgehen und etwas in der Datei ändern, damit sie nicht mehr kollidieren ...

Siehe Linus Torvalds 'Beitrag im Thread "Fangen Sie an, über sha-256 nachzudenken?" in der Git-Mailingliste .

klaustopher
quelle
4
"Wenn zwei Dateien dieselbe Hash-Summe in Git haben, werden diese Dateien als identisch behandelt." Dies ist eigentlich eine richtige Antwort. Haben Sie jedoch eine Quelle für diese Aussage klaustopher? Ihr Link funktioniert bei mir nicht.
Tiago
3
Dies ist jedoch nicht unbedingt erforderlich, wenn Sie an einem Projekt mit einer Sammlung von Beispielen für Hash-Kollisionen arbeiten.
Doomjunky
6
@JBishop Nein, hat es nicht. Wenn Sie einen Beweis für eine Hash-Kollision haben, werden Sie sofort berühmt. Vergiss nicht es zu posten! Ich werde eine Kiste mit wirklich gutem Haarlem-Bier schicken, wenn Sie mir eine SHA-1-Hash-Kollision in voller Größe zeigen, die innerhalb einer Woche innerhalb von Git erstellt wurde. Beachten Sie, dass es sich um eine separate Hash-Kollision handeln muss, die nicht bereits an anderer Stelle zitiert wurde (noch hat niemand eine veröffentlicht, aber immer noch).
Maarten Bodewes
7
+1 Die einzige Antwort, die die Frage tatsächlich beantwortet. Der Rest plappert nur über die "kleine Chance", die auftreten könnte, die jeder Entwickler bereits kennt.
Yukio Fukuzawa
2
Seien Sie sehr vorsichtig, wenn Linus über IT-Sicherheit spricht. Er hat sich zuvor geirrt und liegt in dieser Sache falsch. Wenn man SHA-1-Kollisionen nach Belieben erstellen könnte, könnte man sie für alle Arten von Chaos verwenden, z. B. zum Erstellen von zirkulären Historien, die zum Absturz von Git-Servern und -Clients führen.
DomQ
26

Es ist nicht wirklich möglich, diese Frage mit dem richtigen "aber" zu beantworten, ohne auch zu erklären, warum es kein Problem ist. Es ist nicht möglich, dies zu tun, ohne wirklich gut im Griff zu haben, was ein Hash wirklich ist. Es ist komplizierter als die einfachen Fälle, denen Sie in einem CS-Programm ausgesetzt waren.

Hier liegt ein grundlegendes Missverständnis der Informationstheorie vor. Wenn Sie eine große Menge an Informationen auf eine kleinere Menge reduzieren, indem Sie eine bestimmte Menge (z. B. einen Hash) verwerfen, besteht die Möglichkeit einer Kollision, die direkt mit der Länge der Daten zusammenhängt. Je kürzer die Daten sind, desto WENIGER ist dies wahrscheinlich. Jetzt wird die überwiegende Mehrheit der Kollisionen Kauderwelsch sein, was die Wahrscheinlichkeit erhöht, dass sie tatsächlich auftreten (Sie würden Kauderwelsch niemals einchecken ... selbst ein Binärbild ist etwas strukturiert). Am Ende sind die Chancen gering. Um Ihre Frage zu beantworten, ja, git behandelt sie als gleich, das Ändern des Hash-Algorithmus hilft nicht, es wird eine Art "zweite Prüfung" erforderlich sein, aber letztendlich würden Sie ebenso viele "zusätzliche Überprüfungs" -Daten benötigen Da die Länge der Daten 100% sicher sein soll ... denken Sie daran, dass Sie 99,99999 wären .... auf eine wirklich lange Anzahl von Ziffern ... sicher mit einem einfachen Scheck, wie Sie ihn beschreiben. SHA-x sind kryptografisch starke Hashes, was bedeutet, dass es im Allgemeinen nicht schwierig ist, absichtlich zwei Quelldatensätze zu erstellen, die beide SEHR ÄHNLICH zueinander sind und denselben Hash haben. Ein Änderungsbit in den Daten sollte mehr als ein (vorzugsweise so viele) Änderungsbit in der Hash-Ausgabe erzeugen, was auch bedeutet, dass es sehr schwierig (aber nicht ganz unmöglich) ist, vom Hash zum vollständigen Satz von zurückzuarbeiten Kollisionen und damit die ursprüngliche Nachricht aus dieser Reihe von Kollisionen herausziehen - alle bis auf einige werden Kauderwelsch sein, und von denen, die es nicht sind, gibt es immer noch eine große Anzahl, die durchgesehen werden muss, wenn die Nachrichtenlänge eine signifikante Länge hat. Der Nachteil eines Krypto-Hash ist, dass er nur langsam berechnet werden kann ... im Allgemeinen.

Also, was bedeutet das alles für Git? Nicht viel. Die Hashes werden so selten ausgeführt (im Vergleich zu allem anderen), dass ihr Rechenaufwand für Operationen insgesamt gering ist. Die Wahrscheinlichkeit, auf ein Kollisionspaar zu stoßen, ist so gering, dass es nicht realistisch ist, dass sie auftreten und nicht sofort erkannt werden (dh Ihr Code würde höchstwahrscheinlich plötzlich aufhören zu bauen), sodass der Benutzer das Problem beheben kann (eine Revision sichern, und nehmen Sie die Änderung erneut vor, und Sie werden mit ziemlicher Sicherheit aufgrund der Zeitänderung einen anderen Hash erhalten, der auch den Hash in git füttert. Es ist wahrscheinlicher, dass es ein echtes Problem für Sie ist, wenn Sie beliebige Binärdateien in Git speichern, was nicht wirklich das primäre Verwendungsmodell ist. Wenn Sie das tun möchten, ist es wahrscheinlich besser, eine herkömmliche Datenbank zu verwenden.

Es ist nicht falsch, darüber nachzudenken - es ist eine gute Frage, die viele Leute einfach als "so unwahrscheinlich, dass es sich nicht lohnt, darüber nachzudenken" ausgeben -, aber es ist wirklich etwas komplizierter. Wenn es passiert, sollte es sehr leicht erkennbar sein, es wird keine stille Beschädigung in einem normalen Workflow sein.

Steve
quelle
4
you'll almost certainly get a different hash because of the time change, which also feeds the hash in gitBasiert der Hash nicht ausschließlich auf dem Inhalt einer Datei?
Fredoverflow
4
Der Hash eines Blobs basiert auf dem Inhalt einer Datei (mit einem winzigen Stück Metadaten). Der Hash eines Commits (der theoretisch auch kollidieren könnte) enthält jedoch die aktuelle Zeit sowie den Hash des Baums. Der Autor, die Hashes der übergeordneten Commits usw. Wie @Steve jedoch betont, ist es weniger wahrscheinlich, dass kleine Dinge kollidieren, und ein Commit ist eine kleine Sache.
cdyson37
1
Denken Sie nicht, dass ich mit dem "Je kürzer die Daten, desto WENIGER wahrscheinlich [Kollisionen] werden" einverstanden bin. Wenn Sie kürzere Hashes meinen, reduzieren Sie den Satz möglicher Hashes = mehr Eingaben auf jeden Hash = höhere Kollisionswahrscheinlichkeit. Wenn Sie kürzere Nachrichten meinen, die Sie hashen, dann ist dies nur in dem Sinne wahr, dass die Anzahl der möglichen Eingaben durch die Anzahl der verwendeten Zeichen begrenzt ist, was so offensichtlich erscheint, dass ich das Gefühl habe, dass ich Ihren Standpunkt verfehlen muss?
Basic
Ich habe nie an den "SEHR ÄHNLICHEN" Punkt gedacht, der ein wirklich guter Punkt ist. Dies bedeutet im Grunde, dass Sie einen signifikanten Teil der Zeichen in jeder einzelnen Datei ändern müssen, um zwei Commits mit demselben Hash zu erhalten (ganz zu schweigen von den Dateinamen, Pfaden und der Anzahl der Dateien).
PieterNuyts
1
@PieterNuyts Nein, um einen bestimmten Hash aus einer beliebigen Anfangsdatei zu erhalten, müssten Sie normalerweise die Informationen in der Datei um einen Betrag ändern, der der Anzahl der Informationsbits im Hash ähnlich ist, dh etwa 160 Bit für SHA-1. Hier zählen jedoch auch Informationen darüber, welche Bits geändert werden sollen. Je länger die Datei ist, desto weniger Bits müssen Sie ändern, wenn Sie die richtigen auswählen. Hypothetisch gesehen könnten Sie bei einer Datei mit einer Länge von weit über 2 ^ 160 Bytes fast jeden Hash erhalten, indem Sie ein einzelnes Bit ändern, da die Position dieses Bits mehr als 160 Informationsbits enthält!
M Kloster
10

Könnte git verbessert werden, um damit zu leben, oder müsste ich auf einen neuen Hash-Algorithmus umsteigen?

Kollisionen sind für jeden Hash-Algorithmus möglich, sodass das Ändern der Hash-Funktion das Problem nicht ausschließt, sondern nur die Wahrscheinlichkeit verringert, dass es auftritt. Also solltest du dann eine wirklich gute Hash-Funktion wählen (SHA-1 ist es schon, aber du hast darum gebeten, nicht informiert zu werden :)

Roberto Bonvallet
quelle
Ich denke du meinst "eher unwahrscheinlich" oder "weniger wahrscheinlich", oder? Sicher, Sie könnten zu einem Hash-Algorithmus mit weniger Bytes in der Ausgabe wechseln , aber das würden Sie nicht meinen, oder? :)
MichaelK
2
SHA-1 ist in dem Sinne kaputt, dass es möglich wird, absichtliche Hash-Kollisionen zu erzeugen. Ich denke, es war auch schon 2012. Ein Wechsel zu einem anderen Hash, der sicherer ist und einen größeren Status und eine größere Ausgabe hat, würde sicherlich einen Unterschied machen.
Maarten Bodewes
9

Sie können eine gute Studie in " Wie würde Git mit einer SHA-1-Kollision auf einem Blob umgehen? " Sehen .

Da eine SHA1-Kollision jetzt möglich ist (wie ich in dieser Antwort mit shattered.io verweise ), sollten Sie wissen, dass Git 2.13 (Q2 2017) die aktuelle Situation mit einer Variante der SHA-1-Implementierung "Versuch, Kollisionen zu erstellen" verbessern / mildern wird von Marc Stevens (CWI) und Dan Shumow (Microsoft) .

Siehe Commit f5f5e7f , Commit 8325e43 , Commit c0c2006 , Commit 45a574e , Commit 28dc98e (16. März 2017) von Jeff King ( peff) .
(Zusammengeführt von Junio ​​C Hamano - gitster- in Commit 48b3693 , 24. März 2017)

Makefile: DC_SHA1Standard festlegen

Wir haben standardmäßig die SHA1-Implementierung aus der OpenSSL-Bibliothek verwendet.
Wechseln Sie die Standardeinstellung, um die Benutzer zu ermutigen, stattdessen die DC_SHA1-Implementierung zu verwenden, da wir versuchen, nach der kürzlich angekündigten "zerbrochenen" Ankündigung vorsichtig gegen Kollisionsangriffe zu sein.
Diejenigen, die die Implementierung von OpenSSL verwenden möchten, können OPENSSL_SHA1=YesPleasebeim Ausführen von " make" explizit danach fragen .

Wir haben eigentlich keine Git-Objekt-Kollision. Das Beste, was wir tun können, ist, eine der zerbrochenen PDFs über test-sha1 auszuführen. Dies sollte die Kollisionsprüfung auslösen und sterben.

Könnte Git verbessert werden, um damit zu leben, oder müsste ich auf einen neuen Hash-Algorithmus umsteigen?

Update Dezember 2017 mit Git 2.16 (Q1 2018): Diese Bemühungen zur Unterstützung eines alternativen SHA sind im Gange: Siehe " Warum verwendet Git kein moderneres SHA? ".

Sie können einen anderen Hash-Algorithmus verwenden: SHA1 ist nicht mehr der einzige für Git.

Git 2.18 (Q2 2018) dokumentiert diesen Prozess.

Siehe Commit 5988eb6 , Commit 45fa195 (26. März 2018) von Ævar Arnfjörð Bjarmason ( avar) .
(Zusammengeführt von Junio ​​C Hamano - gitster- in Commit d877975 , 11. April 2018)

doc hash-function-transition: Klären Sie, was SHAttered bedeutet

Versuchen Sie zu klären, was der SHAttered-Angriff in der Praxis für Git bedeutet.
In der vorherigen Version des Textes wurde überhaupt nicht erwähnt, dass Git bereits eine Abschwächung für diesen spezifischen Angriff hat, von dem die SHAttered-Forscher behaupten, dass er kryptoanalytische Kollisionsangriffe erkennen wird.

Ich habe vielleicht einige Nuancen falsch verstanden, aber soweit ich weiß, fasst dieser neue Text die aktuelle Situation mit SHA-1 in Git genau zusammen. Dh Git verwendet SHA-1 nicht mehr wirklich, es verwendet Hardened-SHA-1 (sie produzieren zufällig 99,99999999999 ...% der Zeit die gleichen Ausgaben).

Daher war der vorherige Text falsch, als er behauptete:

[...] Aufgrund von [von SHAttered] kann SHA-1 nicht mehr als [...] kryptografisch sicher angesehen werden.

Das ist nicht der Fall. Wir haben eine Abschwächung gegen SHAttered, halten es jedoch für ratsam, auf eine mögliche NewHashkünftige Sicherheitsanfälligkeit in SHA-1 oder Hardened-SHA-1 hinzuarbeiten.

Die neue Dokumentation lautet nun:

Git v2.13.0 und höher wurde später standardmäßig auf eine gehärtete SHA-1-Implementierung umgestellt, die für den SHAttered-Angriff nicht anfällig ist.

Somit ist Git tatsächlich bereits auf einen neuen Hash migriert, der nicht SHA-1 ist und seine Schwachstellen nicht teilt. Die neue Hash-Funktion erzeugt zufällig genau die gleiche Ausgabe für alle bekannten Eingaben, mit Ausnahme von zwei von SHAttered veröffentlichten PDFs Forscher, und die neue Implementierung (von diesen Forschern geschrieben) behauptet, zukünftige kryptoanalytische Kollisionsangriffe zu erkennen.

Unabhängig davon wird es als ratsam angesehen, an jeder Variante von SHA-1 vorbei zu einem neuen Hash zu wechseln. Es gibt keine Garantie dafür, dass zukünftige Angriffe auf SHA-1 in Zukunft nicht veröffentlicht werden, und diese Angriffe haben möglicherweise keine tragfähigen Abhilfemaßnahmen.

Wenn SHA-1 und seine Varianten wirklich kaputt wären, könnte die Hash-Funktion von Git nicht mehr als kryptografisch sicher angesehen werden. Dies würde sich auf die Kommunikation von Hash-Werten auswirken, da wir nicht darauf vertrauen können, dass ein bestimmter Hash-Wert die bekannt gute Version des vom Sprecher beabsichtigten Inhalts darstellt.

Hinweis: Das gleiche Dokument (Q3 2018, Git 2.19) verweist explizit auf den "neuen Hash" als SHA-256 : siehe " Warum verwendet Git kein moderneres SHA? ".

VonC
quelle
4
Dies ist die einzige anständige Antwort oder ein Kommentar hier. Zusammenfassung ist - obwohl äußerst unwahrscheinlich, ist es möglich. Sie wären auch sofort nicht identifizierbar und würden durch Optimieren einer Datei (mit einem Kommentar) behoben, um die Kollision zu vermeiden. Absichtliche Exploits werden als irrelevant angesehen, da jemand genauso gut "schlechten Code" einchecken könnte - und es gibt Dinge wie Signaturen und absichtliche Pull-Anfragen, um zu verhindern, dass zufällige Personen zufällige Dinge einchecken.
Brad
5

Google behauptet nun, dass eine SHA-1-Kollision unter bestimmten Voraussetzungen möglich ist: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Da git SHA-1 verwendet, um die Dateiintegrität zu überprüfen, bedeutet dies, dass die Dateiintegrität in git gefährdet ist.

IMO, git sollte definitiv einen besseren Hashing-Algorithmus verwenden, da jetzt eine absichtliche Kollision möglich ist.

Petercommand Hsu
quelle
2
Es wäre auch ratsam, Linus 'Wort bezüglich der Computersicherheit nicht zu vertrauen. Er hat sich schon einmal geirrt, und er hat sich in dieser Sache geirrt. (Mit einem SHA-1-Kollisionsorakel können Sie beispielsweise zirkuläre Commit-Historien für Absturzserver und Clients erstellen.)
DomQ
2

Eine Hash-Kollision ist so unwahrscheinlich, dass sie einfach umwerfend ist! Wissenschaftler auf der ganzen Welt bemühen sich, eine zu erreichen, haben es aber noch nicht geschafft. Für bestimmte Algorithmen wie MD5 waren sie jedoch erfolgreich.

Was sind die Chancen?

SHA-256 hat 2 ^ 256 mögliche Hashes. Das ist ungefähr 10 ^ 78 . Oder um anschaulicher zu sein, die Wahrscheinlichkeit einer Kollision liegt bei ungefähr

1: 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

Die Chance, im Lotto zu gewinnen ist etwa 1: 14 Mio . Die Chance einer Kollision mit SHA-256 ist wie ein Lottogewinn an 11 aufeinander folgenden Tagen !

Mathematische Erklärung: 14 000 000 ^ 11 ~ 2 ^ 256

Darüber hinaus hat das Universum etwa 10 ^ 80 Atome. Das ist nur 100-mal mehr als bei SHA-256-Kombinationen.

Erfolgreiche MD5-Kollision

Auch für MD5 die Chancen gering. Den Mathematikern gelang es jedoch, eine Kollision zu erzeugen:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

hat das gleiche MD5 wie

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

Dies bedeutet nicht, dass MD5 jetzt, da sein Algorithmus geknackt ist, weniger sicher ist. Sie können absichtlich MD5-Kollisionen erstellen, aber die Wahrscheinlichkeit einer versehentlichen MD5-Kollision beträgt immer noch 2 ^ 128, was immer noch sehr hoch ist.

Fazit

Sie müssen sich keine Sorgen um Kollisionen machen. Hashing-Algorithmen sind der zweit sicherste Weg, um die Gleichheit von Dateien zu überprüfen. Der einzig sicherere Weg ist ein binärer Vergleich.

Bytecode77
quelle
4
Diese Antwort bezieht sich hauptsächlich auf SHA-256, was irrelevant ist, da es sich um SHA-1 handelt. Die Mathematik, die die Unwahrscheinlichkeit einer SHA-256-Kollision zeigt, ist viel optimistischer als eine SHA-1-Kollision. Es ist immer noch sehr unwahrscheinlich, aber eine SHA-1-Antwort wäre relevanter gewesen.
Andrew Arnott
@ AndrewArnott Es gibt keinen relevanten Unterschied zwischen SHA-256 und SHA-1. SHA-1 ist 2 ^ 128 mal schwächer, aber das spielt auch keine Rolle. Es ist immer noch nicht zerbrechlich, also ist meine Antwort nicht so falsch.
Bytecode77
4
SHA-1 ist in der Tat kaputt, daher ist es auch falsch zu sagen, dass es "immer noch nicht zerbrechlich" ist. Da SHA-1 tatsächlich defekt ist, könnte jemand möglicherweise absichtlich den sha-1-Algorithmus von git angreifen, um Inhalte zu ersetzen, ohne entdeckt zu werden. SHA-256 wurde noch nicht beschädigt, daher wäre es sicherer. Die Beantwortung einer Frage zu möglichen Git-Kollisionen sollte daher am besten an SHA-1 weitergeleitet werden.
Andrew Arnott
"Dies bedeutet nicht, dass MD5 jetzt, da sein Algorithmus geknackt ist, weniger sicher ist." Komm wieder? Könnten Sie diesen Satz erklären?
Maarten Bodewes
Grund für die Antwort: Weil es unter Menschen, die mit Computern nicht vertraut sind und immer noch von der Suche im Internet hierher kommen, viel Verwirrung gibt. Missverständnisse über "Verschlüsselung vs. Rechenleistung" sind meiner Erfahrung nach häufiger als Sie denken, daher habe ich dies als zusätzliche Information angesprochen.
Bytecode77
1

Nun, ich denke, wir wissen jetzt, was passieren würde - Sie sollten damit rechnen, dass Ihr Repository beschädigt wird ( Quelle ).

Conor Bradley
quelle
1

Ich habe kürzlich einen Beitrag vom 29.04.2013 in einer BSD-Diskussionsgruppe unter gefunden

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

wo das Plakat behauptet:

Ich bin einmal mit einer Git-Rebase auf eine Hash-Kollision gestoßen.

Leider liefert er keinen Beweis für seine Behauptung. Aber vielleicht möchten Sie versuchen, ihn zu kontaktieren und ihn nach diesem vermeintlichen Vorfall zu fragen.

Auf einer allgemeineren Ebene beträgt die Wahrscheinlichkeit für eine SHA-1-Hash-Kollision aufgrund des Geburtstagsangriffs 1 in pow (2, 80).

Das klingt sehr viel und ist sicherlich weit mehr als die Gesamtzahl der Versionen einzelner Dateien, die in allen Git-Repositories der Welt zusammen vorhanden sind.

Dies gilt jedoch nur für die Versionen, die tatsächlich im Versionsverlauf verbleiben.

Wenn sich ein Entwickler stark auf die Neubasierung verlässt, erhalten jedes Mal, wenn eine Neubasis für einen Zweig ausgeführt wird, alle Commits in allen Versionen dieses Zweigs (oder eines neu basierten Teils des Zweigs) neue Hashes. Das gleiche gilt für jede Datei, die mit "git filter-branch" geändert wird. Daher können "Rebase" und "Filter-Branch" große Multiplikatoren für die Anzahl der im Laufe der Zeit generierten Hashes sein, obwohl nicht alle tatsächlich beibehalten werden: Häufig nach dem Rebasing (insbesondere zum "Aufräumen" eines Zweigs ) wird der ursprüngliche Zweig weggeworfen.

Wenn die Kollision jedoch während der Rebase oder des Filterzweigs auftritt, kann sie dennoch nachteilige Auswirkungen haben.

Eine andere Sache wäre, die Gesamtzahl der gehashten Entitäten in Git-Repositories zu schätzen und zu sehen, wie weit sie von pow entfernt sind (2, 80).

Nehmen wir an, wir haben ungefähr 8 Milliarden Menschen, und alle würden Git ausführen und ihre Inhalte in 100 Git-Repositories pro Person versionieren. Nehmen wir weiter an, das durchschnittliche Repository hat 100 Commits und 10 Dateien, und nur eine dieser Dateien ändert sich pro Commit.

Für jede Revision haben wir mindestens einen Hash für das Baumobjekt und das Festschreibungsobjekt selbst. Zusammen mit der geänderten Datei haben wir 3 Hashes pro Revision und damit 300 Hashes pro Repository.

Für 100 Repositories von 8 Milliarden Menschen ergibt dies pow (2, 47), was noch weit von pow (2, 80) entfernt ist.

Dies schließt jedoch den oben erwähnten vermeintlichen Multiplikationseffekt nicht ein, da ich nicht sicher bin, wie ich ihn in diese Schätzung einbeziehen soll. Vielleicht könnte es die Wahrscheinlichkeit einer Kollision erheblich erhöhen. Besonders wenn sehr große Repositorys, die einen langen Commit-Verlauf haben (wie der Linux-Kernel), von vielen Leuten für kleine Änderungen neu basiert werden, die dennoch unterschiedliche Hashes für alle betroffenen Commits erzeugen.

Günther Brunthaler
quelle
Interessant. +1. Wie ich oben erwähnte, wird dieses Problem irgendwann verschwinden
VonC