wake-up-neo.com

Hash-Kollision in Git

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

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

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

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

161
Sec

Auf 10 Monden Atome sammeln

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

Was ist das Äquivalent von? Nun, der Mond besteht aus ungefähr 1047 Atome. Also, wenn wir 10 Monde haben ... und Sie zufällig einen atom auf einem dieser Monde auswählen ... und dann fortfahren und einen zufälligen atom auswählen auf sie wieder ... dann ist die Wahrscheinlichkeit, dass Sie das gleiche atom zweimal auswählen, die Wahrscheinlichkeit, dass zwei gegebene git-Commits den gleichen SHA-1-Hash haben.

Darauf aufbauend können wir die Frage stellen ...

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

Dies bezieht sich auf sogenannte "Geburtstagsattacken", die sich wiederum auf das "Geburtstagsparadoxon" oder "Geburtstagsproblem" beziehen, das besagt, dass Sie, wenn Sie nach dem Zufallsprinzip aus einem gegebenen Satz auswählen, überraschend wenige Tipps benötigen, bevor Sie wahrscheinlich sind zweimal was gepflückt haben. Aber "überraschend wenig" ist hier ein sehr relativer Begriff.

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

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

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

"Aber wenn eine Kollision auftritt , was passiert dann tatsächlich?"

Angenommen, das Unwahrscheinliche passiert, oder jemand hat es geschafft, das Ergebnis anzupassen eine absichtliche SHA-1-Hash-Kollision . Was passiert dann?

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

  1. Wenn bereits ein Blob mit demselben Hash existiert, 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 obigen Erläuterungen).
  2. Wenn bereits ein Baumobjekt vorhanden ist und Sie einen Blob mit demselben Hash erstellen: Alles scheint normal zu sein, bis Sie entweder versuchen, das Repository zu pushen oder jemand das Repository klont. Dann werden Sie sehen, dass das Repo beschädigt ist.
  3. Wenn bereits ein Festschreibungsobjekt vorhanden ist und Sie einen Blob mit demselben Hash erstellen: wie # 2 - beschädigt
  4. Wenn bereits ein Blob vorhanden ist und Sie ein Festschreibungsobjekt mit demselben Hash erstellen, schlägt die Aktualisierung von "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 die Aktualisierung 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 Festschreibungsobjekt vorhanden ist und Sie ein Festschreibungsobjekt mit demselben Hash erstellen, scheint alles in Ordnung zu sein. Wenn Sie jedoch ein Commit ausführen, wird das Commit niemals erstellt, und der Zeiger HEAD wird auf ein altes Commit verschoben.
  9. Wenn bereits ein Festschreibungsobjekt vorhanden ist und Sie ein Baumobjekt mit demselben Hash erstellen, schlägt dies beim Erstellen der Festschreibung fehl.

Wie Sie scheinen können, sind einige Fälle nicht gut. Besonders 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 Reposistorien ausbreitet.

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

83
MichaelK

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 jederzeit einen Commit wiederholen und etwas in der Datei ändern, damit sie nicht mehr kollidieren ...

Siehe Linus Torvalds 'Beitrag im Thread "Beginn des Denkens über Sha-256?" In der Git-Mailingliste .

63
klaustopher

Es ist nicht wirklich möglich, diese Frage mit dem richtigen "aber" zu beantworten, ohne auch zu erklären, warum es kein Problem ist. Das ist nicht möglich, ohne wirklich 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 besteht ein grundlegendes Missverständnis der Informationstheorie. Wenn Sie eine große Menge an Informationen in eine kleinere Menge umwandeln, indem Sie eine bestimmte Menge (z. B. einen Hash) verwerfen, besteht die Möglichkeit einer Kollision, die in direktem Zusammenhang mit der Länge der Daten steht. 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 nie einchecken ... selbst ein Binärbild ist etwas strukturiert). Am Ende sind die Chancen gering. Um Ihre Frage zu beantworten, werden sie von git als gleich behandelt, und das Ändern des Hash-Algorithmus hilft nicht weiter. Es wird eine Art "zweite Prüfung" erfordern, aber letztendlich würden Sie so viele "zusätzliche Prüfdaten" benötigen als die Länge der Daten zu 100% sicher sein ... denken Sie daran, dass Sie 99,99999 sein würden ... zu einer wirklich großen Anzahl von Ziffern ... sicher mit einer einfachen Überprüfung, wie Sie 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 aufweisen. Eine Änderung in den Daten sollte mehr als ein (vorzugsweise so viele wie möglich) Änderungsbit in der Hash-Ausgabe erzeugen, was auch bedeutet, dass es sehr schwierig (aber nicht ganz unmöglich) ist, vom Hash auf den vollständigen Satz von zurückzugreifen Kollisionen und damit das Herausziehen der Originalnachricht aus dieser Gruppe von Kollisionen - alle bis auf ein paar werden Kauderwelsch sein, und diejenigen, bei denen es nicht immer noch eine große Zahl gibt, die durchgesiebt werden muss, wenn die Nachrichtenlänge eine signifikante Länge hat. Der Nachteil eines Krypto-Hashs ist, dass er nur langsam berechnet wird ... im Allgemeinen.

Also, was bedeutet das alles für Git? Nicht viel. Die Hashes werden (im Verhältnis zu allem anderen) so selten ausgeführt, dass der Rechenaufwand für Operationen insgesamt gering ist. Die Wahrscheinlichkeit, dass ein Kollisionspaar getroffen wird, ist so gering, dass es nicht realistisch ist und nicht sofort erkannt wird (dh, Ihr Code würde höchstwahrscheinlich plötzlich aufhören zu bauen), dass der Benutzer das Problem beheben kann (eine Revision sichern, und nehmen Sie die Änderung erneut vor, und Sie erhalten mit ziemlicher Sicherheit einen anderen Hash aufgrund der Zeitverschiebung, die 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 das ist, was das primäre Verwendungsmodell ist. Wenn Sie das 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" bezeichnen -, aber es ist wirklich etwas komplizierter. Wenn dies der Fall ist, sollte es sehr leicht erkennbar sein, und es handelt sich nicht um eine stille Beschädigung in einem normalen Workflow.

25
Steve

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

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 dir dann eine wirklich gute Hash-Funktion aussuchen (SHA-1 gibt es schon, aber du hast darum gebeten, nicht informiert zu werden :)

8

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

Da nun eine SHA1-Kollision möglich ist (wie ich in beziehe), lautet diese Antwort mit shattered.io ) , wissen, dass Git 2.13 (Q2 2017) die aktuelle Situation mit einer Variante der SHA-1-Implementierung von Marc Stevens (CWI) und Dan Shumow (Microsoft) verbessern/mildern wird. .

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: Legt DC_SHA1 als Standard fest

Wir haben standardmäßig die SHA1-Implementierung aus der OpenSSL-Bibliothek verwendet.
Da wir versuchen, Kollisionsangriffe nach der kürzlichen "zerbrochenen" Ankündigung zu vermeiden, sollten Sie die Standardeinstellung so ändern, dass die Benutzer ermutigt werden, stattdessen die Implementierung von DC_SHA1 zu verwenden.
Wer die Implementierung von OpenSSL nutzen möchte, kann dies explizit mit OPENSSL_SHA1=YesPlease Anfordern, wenn er "make" ausführt.

Wir haben eigentlich keine Git-Objekt-Kollision. Das Beste, was wir tun können, ist, eine der zerbrochenen PDF-Dateien ü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 zu einem neuen Hash-Algorithmus wechseln?

pdate Dez. 2017 mit Git 2.16 (Q1 2018): Diese Bemühungen, eine Alternative zu unterstützen SHA) sind im Gange: siehe " Why doesn ' Verwenden Sie modernere 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: Verdeutlichen Sie, was SHAttered bedeutet

Versuchen Sie zu klären, was der SHAttered-Angriff in der Praxis für Git bedeutet.
Die vorherige Version des Textes erwähnte in keiner Weise, dass Git bereits eine Abschwächung für diesen spezifischen Angriff aufweist, von dem die SHAttered-Forscher behaupten, dass sie kryptoanalytische Kollisionsangriffe erkennen werden.

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

Der vorige Text war daher falsch, als er behauptete:

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

Das ist nicht der Fall. Wir haben eine Abschwächung gegen SHAttered, jedoch wir halten es für ratsam, auf ein NewHash hinzuarbeiten, falls zukünftige Sicherheitslücken in SHA-1 oder Hardened-SHA-1 auftauchen.

Die neue Dokumentation lautet nun:

Git v2.13.0 und höher wechselte anschließend standardmäßig zu einer gehärteten SHA-1-Implementierung, die für den SHAttered-Angriff nicht anfällig ist.

Daher ist Git bereits auf einen neuen Hash migriert, der nicht SHA-1 ist und dessen Schwachstellen nicht freigegeben sind. Die neue Hash-Funktion erzeugt einfach 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 vernünftig erachtet, an einer SHA-1-Variante 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.

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 bekannte gute Version des Inhalts darstellt, den der Sprecher beabsichtigt hat.

Hinweis: Dasselbe Dokument (Q3 2018, Git 2.19) verweist jetzt explizit auf "new hash" als SHA-256: see " Warum verwendet Git kein moderneres SHA? ".

7
VonC

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 zur Überprüfung der Dateiintegrität verwendet, bedeutet dies, dass die Dateiintegrität in git gefährdet ist.

IMO, Git sollte definitiv einen besseren Hashalgorithmus verwenden, da absichtliche Kollisionen jetzt möglich sind.

5

Eine Hash-Kollision ist so unwahrscheinlich, dass sie umwerfend ist! Wissenschaftler auf der ganzen Welt sind bemüht, eine zu erreichen, haben es aber noch nicht geschafft. Bei bestimmten 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 grafischer 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 Gewinnchance im Lotto liegt bei 1: 14 Mio . Die Chance einer Kollision mit SHA-256 ist wie ein Lottogewinn an 11 aufeinanderfolgenden Tagen !

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

Außerdem hat das niversum ungefähr 10 ^ 80 Atome. Das ist nur 100-mal mehr als bei SHA-256-Kombinationen.

Erfolgreiche MD5-Kollision

Selbst für MD5 sind die Chancen gering. Mathematiker haben es jedoch geschafft, eine Kollision zu erzeugen:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89 
 55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b 
 D8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0 
 E99f33420f577ee8 ce54b67080ein80d1e c69821bcb6a88393 96f9652b6ff72a70

hat das gleiche MD5 wie

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5712467eab 4004583eb8fb7f89 
 55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b 
 D8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0 
 E99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965einb6ff72a70

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 viel ist.

Fazit

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

2
bytecode77

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 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 Chance für eine SHA-1-Hash-Kollision aufgrund des Geburtstagsangriffs 1 in pow (2, 80).

Dies hört sich sehr viel an und ist sicherlich weit mehr als die Gesamtzahl der Versionen einzelner Dateien, die in allen Git-Repositories der Welt vorhanden sind.

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

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

Tritt die Kollision jedoch während des Rebase- oder Filter-Zweigs auf, kann dies 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 vom Pow entfernt sind (2, 80).

Nehmen wir an, wir haben ungefähr 8 Milliarden Menschen, und alle von ihnen würden git ausführen und ihre Sachen 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 Tree-Objekt und das Commit-Objekt selbst. Zusammen mit der geänderten Datei haben wir 3 Hashes pro Revision und somit 300 Hashes pro Repository.

Für 100 Endlager von 8 Milliarden Menschen ergibt dies POW (2, 47), das noch weit von POW (2, 80) entfernt ist.

Dies schließt jedoch den oben erwähnten angenommenen Multiplikationseffekt nicht ein, da ich nicht sicher bin, wie er in diese Schätzung einbezogen werden soll. Vielleicht könnte es die Kollisionschancen erheblich erhöhen. Vor allem, wenn sehr große Repositorys mit einer langen Commit-Historie (wie der Linux-Kernel) von vielen Leuten für kleine Änderungen umbasiert werden, die dennoch unterschiedliche Hashes für alle betroffenen Commits erstellen.

1

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

1
Conor Bradley