Wie würde Git eine SHA-1-Kollision bei einem Blob behandeln?

Question

Das ist in der Praxis wahrscheinlich noch nie passiert und wird vielleicht auch nie passieren, aber nehmen wir an, Sie haben ein Git-Repository, machen einen Commit und haben Pech: Einer der Blobs hat am Ende den gleichen SHA-1-Wert wie ein anderer, der bereits in Ihrem Repository ist. Die Frage ist, wie würde Git damit umgehen? Einfach fehlschlagen? Einen Weg finden, die beiden Blobs miteinander zu verknüpfen und zu prüfen, welcher davon je nach Kontext benötigt wird?

Das ist eher ein Denkanstoß als ein wirkliches Problem, aber ich fand das Thema interessant.

Answer 1

Ich habe ein Experiment durchgeführt, um genau herauszufinden, wie sich Git in diesem Fall verhalten würde. Dies ist mit Version 2.7.9~rc0+next.20151210 (Debian-Version). Ich habe im Grunde nur die Hash-Größe von 160-Bit auf 4-Bit reduziert, indem ich den folgenden Diff angewendet und Git neu erstellt habe:

--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
    blk_SHA1_Update(ctx, padlen, 8);

    /* Output hash */
-   for (i = 0; i < 5; i++)
-       put_be32(hashout + i * 4, ctx->H[i]);
+   for (i = 0; i < 1; i++)
+       put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+   for (i = 1; i < 5; i++)
+       put_be32(hashout + i * 4, 0);
 }

Dann habe ich ein paar Übertragungen vorgenommen und folgendes festgestellt.

1. Wenn ein Blob mit demselben Hash bereits existiert, erhalten Sie keine Warnungen. Alles scheint in Ordnung zu sein, aber wenn Sie pushen, jemand klont oder Sie zurückkehren, verlieren Sie die neueste Version (im Einklang mit dem, was oben erklärt wird).
2. Wenn ein Baumobjekt bereits existiert und Sie einen Blob mit demselben Hash erstellen: Alles wird normal erscheinen, bis Sie entweder versuchen zu pushen oder jemand Ihr Repository klont. Dann werden Sie sehen, dass das Repository beschädigt ist.
3. Wenn ein Commit-Objekt bereits existiert und Sie einen Blob mit demselben Hash erstellen: wie bei #2 - beschädigt
4. Wenn ein Blob bereits existiert und Sie ein Commit-Objekt mit demselben Hash erstellen, schlägt die Aktualisierung des "ref" fehl.
5. Wenn ein Blob bereits existiert und Sie ein Baumobjekt mit demselben Hash erstellen. Die Erstellung der Übergabe wird fehlschlagen.
6. Wenn ein Baumobjekt bereits existiert und Sie ein Commit-Objekt mit demselben Hash erstellen, schlägt die Aktualisierung des "ref" fehl.
7. Wenn ein Baumobjekt bereits existiert und Sie ein Baumobjekt mit demselben Hash erstellen, scheint alles in Ordnung zu sein. Aber wenn Sie übertragen, wird das gesamte Repository auf den falschen Baum verweisen.
8. Wenn ein Commit-Objekt bereits existiert und Sie ein Commit-Objekt mit demselben Hash erstellen, scheint alles in Ordnung zu sein. Aber wenn Sie eine Übergabe machen, wird die Übergabe nie erstellt und der HEAD-Zeiger wird auf eine alte Übergabe verschoben.
9. Wenn ein Commit-Objekt bereits existiert und Sie ein Tree-Objekt mit demselben Hash erstellen, schlägt die Erstellung des Commits fehl.

Für #2 erhalten Sie normalerweise eine Fehlermeldung wie diese, wenn Sie "git push" ausführen:

error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin

oder:

error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)

wenn Sie die Datei löschen und dann "git checkout file.txt" ausführen.

Für die Nummern 4 und 6 erhalten Sie normalerweise eine Fehlermeldung wie diese:

error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref

wenn Sie "git commit" ausführen. In diesem Fall können Sie in der Regel einfach erneut "git commit" eingeben, da dies einen neuen Hash erzeugt (aufgrund des geänderten Zeitstempels)

Für die Nummern 5 und 9 erhalten Sie normalerweise eine Fehlermeldung wie diese:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

beim Ausführen von "git commit"

Wenn jemand versucht, Ihr beschädigtes Repository zu klonen, wird er in der Regel etwas wie folgt sehen:

git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)

Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'

Was mich "beunruhigt" ist, dass in zwei Fällen (2,3) das Repository ohne Warnungen beschädigt wird, und in drei Fällen (1,7,8) scheint alles in Ordnung zu sein, aber der Inhalt des Repositorys unterscheidet sich von dem, was man erwartet. Leute, die klonen oder ziehen, werden einen anderen Inhalt haben, als Sie ihn haben. Die Fälle 4, 5, 6 und 9 sind in Ordnung, da sie mit einem Fehler abbrechen. Ich denke, es wäre besser, wenn es zumindest in allen Fällen mit einem Fehler abbrechen würde.

Answer 2

Originalantwort (2012) (siehe shattered.io 2017 SHA1-Kollision unten)

Das alte (2006) Antwort von Linus noch relevant sein könnte:

Nö. Wenn es denselben SHA1-Wert hat, bedeutet das, dass wir, wenn wir das Objekt von der anderen Seite erhalten, no das bereits vorhandene Objekt überschreiben.

Wenn es also zu einer Kollision kommt, wird das "frühere" Objekt in einem bestimmten Repository immer Vorrang haben. Beachten Sie aber, dass "früher" offensichtlich pro Repository ist, in dem Sinne, dass das Git-Objektnetzwerk eine DAG erzeugt, die nicht vollständig geordnet ist. Während sich also verschiedene Repositories darüber einig sind, was "früher" ist, wenn es sich um direkte Vorfahren handelt, können zwei verschiedene Repositories die beiden Objekte in unterschiedlicher Reihenfolge erhalten haben, wenn das Objekt durch separate und nicht direkt verwandte Zweige kam.

Allerdings ist das "earlier will override" genau das, was Sie vom Standpunkt der Sicherheit aus wollen: Denken Sie daran, dass das Git-Modell vorsieht, dass Sie in erster Linie nur Ihren eigene Repository.
Wenn Sie also eine " git pull "sind die neu ankommenden Objekte per Definition weniger vertrauenswürdig als die Objekte, die Sie bereits haben, und daher wäre es falsch, einem neuen Objekt zu erlauben ein altes Objekt zu ersetzen.

Es handelt sich also um zwei Fälle von Kollisionen:

• die ungewollte Art Wenn man Pech hat, haben zwei Dateien den gleichen SHA1-Wert.
  An diesem Punkt passiert Folgendes: Wenn Sie die Datei übertragen (oder ein " git-update-index ", um ihn in den Index zu verschieben, aber noch nicht übertragen), wird der SHA1 des neuen Inhalts berechnet, aber da es mit einem alten Objekt übereinstimmt, wird kein neues Objekt erstellt, und der Commit-or-Index zeigt am Ende auf den alt Objekt .
  Sie werden es nicht sofort bemerken (da der Index mit dem alten Objekt SHA1 übereinstimmt, und das bedeutet, dass etwas wie " git diff " die ausgecheckte Kopie verwenden), aber wenn Sie jemals einen Tree-Level-Diff durchführen (oder einen Clone oder Pull durchführen oder einen Checkout erzwingen), werden Sie plötzlich feststellen, dass sich diese Datei in etwas vollständig anders, als Sie erwartet haben.
  Diese Art von Zusammenstoß wird also in der Regel recht schnell bemerkt.
  In diesem Zusammenhang stellt sich auch die Frage, was mit der versehentlichen Kollision zu tun ist.
  Zunächst einmal möchte ich daran erinnern, dass die unbeabsichtigte Art der Kollision wirklich sehr wichtig ist. realmente verdammt unwahrscheinlich, so dass wir es in der gesamten Geschichte des Universums höchstwahrscheinlich nie zu Gesicht bekommen werden.
  Aber wenn Wenn es passiert, ist das nicht das Ende der Welt: Höchstwahrscheinlich müssen Sie nur die Datei ändern, die leicht kollidiert ist, und eine neue Übertragung mit dem geänderten Inhalt erzwingen (einen Kommentar hinzufügen: " /* This line added to avoid collision */ ") und dann Git das magische SHA1 beibringen, das sich als gefährlich erwiesen hat.
  Im Laufe von ein paar Millionen Jahren werden wir also vielleicht ein oder zwei "vergiftete" SHA1-Werte zu Git hinzufügen müssen. Es ist sehr unwahrscheinlich, dass es ein Wartungsproblem sein wird ;)

• Le site Angreifer Art der Kollision weil jemand SHA1 geknackt (oder gebrute-forced) hat.
  Dieser ist eindeutig ein Los wahrscheinlicher als die versehentliche Art, aber per Definition handelt es sich immer um ein "entferntes" Repository. Hätte der Angreifer Zugriff auf das lokale Repository, hätte er viel einfachere Möglichkeiten, Sie zu schädigen.
  In diesem Fall also, der Zusammenstoß ist völlig unbedeutend : Sie erhalten ein "schlechtes" Repository, das sich von dem unterscheidet, was der Angreifer beabsichtigte, aber da Sie sein kollidierendes Objekt nie wirklich benutzen werden, ist es buchstäblich nicht anders, als wenn der Angreifer überhaupt keine Kollision gefunden hätte sondern nur unter Verwendung des Objekts, das Sie bereits hatten (d. h. es ist zu 100 % gleichwertig mit der "trivialen" Kollision der identischen Datei, die denselben SHA1 erzeugt).

Le site Frage der Verwendung von SHA-256 wird regelmäßig erwähnt, aber vorerst nicht umgesetzt (2012).
Anmerkung: ab 2018 und Git 2.19 wird der Code überarbeitet, um SHA-256 zu verwenden.

---

Hinweis (Humor): Sie können eine Übergabe an einen bestimmten SHA1 erzwingen Präfix mit dem Projekt gitbrute de Brad Fitzpatrick ( bradfitz ) .

gitbrute erzwingt ein Paar von Zeitstempeln von Autor und Übermittler, so dass der resultierende Git-Commit das gewünschte Präfix hat.

例 https://github.com/bradfitz/deadbeef

---

Daniel Dinnyes weist darauf hin in den Kommentaren a 7.1 Git-Werkzeuge - Auswahl der Revision die Folgendes umfasst:

Es besteht eine höhere Wahrscheinlichkeit, dass alle Mitglieder Ihres Programmierteams in derselben Nacht von Wölfen angegriffen und getötet werden, ohne dass ein Zusammenhang besteht.

---

Auch die jüngste (Februar 2017) shattered.io demonstrierte die Möglichkeit, eine SHA1-Kollision zu fälschen:
(siehe viel mehr in meinem separate Antwort (einschließlich Linus Torvalds' Google+-Post)

• a/ erfordert immer noch über 9.223.372.036.854.775.808 SHA1-Berechnungen. Dies entspricht der Rechenleistung von 6.500 Jahren Einzel-CPU-Berechnungen und 110 Jahren Einzel-GPU-Berechnungen.
• b/ würde schmieden eine Datei (mit demselben SHA1), aber mit der zusätzlichen Einschränkung, dass ihr Inhalt y Größe den gleichen SHA1-Wert ergeben würde (eine Kollision des Inhalts allein reicht nicht aus): siehe " Wie wird der Git-Hash berechnet? "): a Blob SHA1 wird auf der Grundlage des Inhalts berechnet y Größe .

Siehe " Lebensdauer von kryptographischen Hash-Funktionen " aus Valerie Anita Aurora für mehr.
Auf dieser Seite vermerkt sie:

Google hat 6500 CPU-Jahre und 110 GPU-Jahre damit verbracht, alle davon zu überzeugen, dass wir SHA-1 nicht mehr für sicherheitskritische Anwendungen verwenden sollten.
Auch weil es cool war

Siehe mehr in meinem separate Antwort unten .

Answer 3

Selon Pro Git :

Wenn Sie ein Objekt übertragen, das denselben SHA-1-Wert hat wie ein vorheriges Objekt in Ihrem Repository, sieht Git das vorherige Objekt bereits in Ihrer Git-Datenbank und nimmt an, dass es bereits geschrieben wurde. Wenn Sie versuchen, dieses Objekt irgendwann erneut auszuchecken, erhalten Sie immer die Daten des ersten Objekts.

Es würde also nicht scheitern, aber es würde Ihr neues Objekt auch nicht speichern.
Ich weiß nicht, wie das in der Befehlszeile aussehen würde, aber das wäre sicherlich verwirrend.

Etwas weiter unten wird in demselben Verweis versucht, die Wahrscheinlichkeit eines solchen Zusammenstoßes zu veranschaulichen:

Hier ein Beispiel, um Ihnen eine Vorstellung davon zu geben, was nötig wäre, um eine SHA-1-Kollision zu verursachen. Wenn alle 6,5 Milliarden Menschen auf der Erde programmieren würden und jeder von ihnen jede Sekunde Code in der Größenordnung der gesamten Linux-Kernel-Geschichte (1 Million Git-Objekte) produzieren und in ein riesiges Git-Repository einspeisen würde, würde es 5 Jahre dauern, bis dieses Repository genug Objekte enthielte, um eine 50-prozentige Wahrscheinlichkeit für eine einzige SHA-1-Objektkollision zu haben. Eine höhere Wahrscheinlichkeit besteht darin, dass jedes Mitglied Ihres Programmierteams in derselben Nacht von Wölfen angegriffen und getötet wird, ohne dass ein Zusammenhang besteht.

Answer 4

Zur Ergänzung von meine frühere Antwort von 2012 gibt es jetzt (Feb. 2017, fünf Jahre später) ein Beispiel einer tatsächlichen SHA-1-Kollision mit zerschmettert.io , mit dem Sie zwei kollidierende PDF-Dateien erstellen können: Das heißt, Sie erhalten eine digitale SHA-1-Signatur für die erste PDF-Datei, die auch als gültige Signatur für die zweite PDF-Datei missbraucht werden kann.
Siehe auch " Die weit verbreitete SHA1-Funktion, die jahrelang auf der Kippe stand, ist nun tot ", und diese Illustration .

Aktualisierung vom 26. Februar: Linus hat die folgenden Punkte bestätigt in einem Google+ Beitrag :

(1) Erstens: Der Himmel stürzt nicht ein. Es besteht ein großer Unterschied zwischen der Verwendung eines kryptografischen Hashes für Dinge wie die Sicherheitssignierung und der Verwendung eines Hashes für die Generierung eines "Inhaltsbezeichners" für ein inhaltsadressierbares System wie Git.

(2) Zweitens bedeutet die Art dieses speziellen SHA1-Angriffs, dass es eigentlich ziemlich einfach ist, ihn zu entschärfen, und es wurden bereits zwei Sätze von Patches für diese Entschärfung veröffentlicht.

(3) Und schließlich gibt es einen relativ unkomplizierten Übergang zu einem anderen Hash, der nicht die Welt zerstört - oder sogar alte Git-Repositories.

Bezüglich dieses Übergangs siehe die Q1 2018 Git 2.16 Hinzufügen einer Struktur, die einen Hash-Algorithmus darstellt. Die Umsetzung dieses Übergangs hat begonnen.

Ab Git 2.19 (Q3 2018) hat Git ausgewählt SHA-256 als NewHash und ist dabei, es in den Code zu integrieren (d. h. SHA1 ist immer noch der Standard (Q2 2019, Git 2.21), aber SHA2 wird der Nachfolger sein)

---

Originalantwort (25. Februar) Aber:

• Dies erlaubt es, einen Blob zu fälschen, jedoch würde sich der SHA-1 des Baumes immer noch ändern, da die Größe des gefälschten Blob nicht mit der des Originals übereinstimmen könnte: siehe " Wie wird der Git-Hash berechnet? "; a blob SHA1 wird auf der Grundlage des Inhalts und der Größe berechnet .
  Sie hat ein Thema für git-svn obwohl . Oder vielmehr mit svn selbst als hier gesehen .
• Wie ich bereits erwähnt habe in meiner ursprünglichen Antwort Die Kosten eines solchen Versuchs sind derzeit noch unerschwinglich (6.500 CPU-Jahre und 100 GPU-Jahre) Siehe auch Valerie Anita Aurora in " Lebensdauer von kryptographischen Hash-Funktionen ".
• Wie bereits erwähnt, ist dies geht es nicht um Sicherheit oder Vertrauen, sondern die Integrität der Daten (Deduplizierung und Fehlererkennung), die leicht von einem git fsck als erwähnt von Linus Torvalds heute. git fsck würde vor einer Commit-Nachricht mit undurchsichtigen Daten warnen, die nach einer NUL (obwohl NUL ist nicht immer in einer betrügerischen Datei vorhanden ).
  Nicht jeder schaltet sich ein transfer.fsck Aber GitHub tut es: Jeder Push würde im Falle eines fehlerhaften Objekts oder eines defekten Links abgebrochen werden. Obwohl... es gibt eine warum dies nicht standardmäßig aktiviert ist .
• eine PDF-Datei kann beliebige Binärdaten enthalten, die Sie ändern können, um ein kollidierendes SHA-1 zu erzeugen, im Gegensatz zu gefälschtem Quellcode.
  Das eigentliche Problem bei der Erstellung von zwei Git-Repositories mit demselben Head-Commit-Hash und unterschiedlichen Inhalten. Und selbst dann ist die Angriff bleibt unübersichtlich .

• Linus fügt hinzu :

  Die gesamte Punkt eines SCM ist, dass es sich nicht um ein einmaliges Ereignis handelt, sondern um eine kontinuierliche Geschichte. Das bedeutet auch grundsätzlich, dass ein erfolgreicher Angriff über einen längeren Zeitraum hinweg funktionieren muss und nicht aufgedeckt werden darf.
  Wenn Sie einen SCM einmal überlisten können, Ihren Code einfügen und er nächste Woche entdeckt wird, haben Sie nicht wirklich etwas Sinnvolles getan. Sie haben nur sich selbst verbrannt.

Joey Hess versucht diese pdf in ein Git-Repositorium et er fand :

Dazu gehören zwei Dateien mit demselben SHA und derselben Größe, die d Inhalt.

joey@darkstar:~/tmp/supercollider>sha1sum  bad.pdf good.pdf 
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65    bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1    good.pdf

Während das Anhängen identischer Daten an diese kollidierenden Dateien weitere Kollisionen, während das Voranstellen von Daten dies nicht tut.

Also die Hauptangriffsvektor (Fälschung einer Übertragung) wäre :

• Erzeugen Sie ein reguläres Commit-Objekt;
• das gesamte Commit-Objekt + NUL als gewähltes Präfix verwenden, und
• den Kollisionsangriff mit identischen Präfixen verwenden, um die kollidierenden guten/schlechten Objekte zu erzeugen.
• ... und das ist nutzlos, weil die guten und schlechten Commit-Objekte immer noch auf denselben Baum zeigen!

Außerdem können Sie bereits kryptoanalytische Kollisionsangriffe gegen SHA-1, die in jeder Datei vorhanden sind, mit cr-marcstevens/sha1collisiondetection

Hinzufügen einer ähnlichen Prüfung in Git selbst würde einen gewissen Rechenaufwand erfordern .

Über die Änderung der Raute, Linux-Kommentare :

Die Größe des Hashes und die Wahl des Hash-Algorithmus sind voneinander unabhängig.
Wahrscheinlich würden Sie zu einem 256-Bit-Hash wechseln. intern und in der nativen Git-Datenbank verwenden, und dann durch anzeigen den Hash als 40-stellige Hex-Zeichenkette (ähnlich wie wir bereits in vielen Situationen abkürzen).
Auf diese Weise sehen die Werkzeuge rund um Git die Änderung nicht einmal ein spezielles " --full-hash " Argument (oder " --abbrev=64 " oder was auch immer - standardmäßig kürzen wir auf 40 ab).

Dennoch, ein der Übergangsplan (von SHA1 zu einer anderen Hash-Funktion) wäre immer noch komplex , sondern aktiv untersucht.
A convert-to-object_id Kampagne es in Arbeit :

---

Update vom 20. März: GitHub beschreibt einen möglichen Angriff und seinen Schutz :

SHA-1-Namen können durch verschiedene Mechanismen als vertrauenswürdig eingestuft werden. In Git können Sie zum Beispiel eine Übergabe oder ein Tag kryptografisch signieren. Dabei wird nur das Commit- oder Tag-Objekt selbst signiert, das wiederum mit Hilfe seiner SHA-1-Namen auf andere Objekte verweist, die die eigentlichen Dateidaten enthalten. Eine Kollision in diesen Objekten könnte zu einer Signatur führen, die zwar gültig erscheint, aber auf andere Daten verweist, als vom Unterzeichner beabsichtigt. Bei einem solchen Angriff sieht der Unterzeichner nur die eine Hälfte der Kollision, während das Opfer die andere Hälfte sieht.

Schutz:

Der jüngste Angriff nutzt spezielle Techniken, um Schwachstellen im SHA-1-Algorithmus auszunutzen, die eine Kollision in viel kürzerer Zeit finden. Diese Techniken hinterlassen ein Muster in den Bytes, das bei der Berechnung des SHA-1 der beiden Hälften eines kollidierenden Paares erkannt werden kann.

GitHub.com führt diese Erkennung jetzt für jede SHA-1-Berechnung durch und bricht den Vorgang ab, wenn es Hinweise darauf gibt, dass das Objekt die Hälfte eines kollidierenden Paares ist. Dadurch wird verhindert, dass Angreifer GitHub nutzen, um ein Projekt davon zu überzeugen, die "unschuldige" Hälfte ihrer Kollision zu akzeptieren, und sie daran zu hindern, die bösartige Hälfte zu hosten.

Siehe " sha1collisiondetection " von Marc Stevens

---

Wiederum mit Q1 2018 Git 2.16 durch Hinzufügen einer Struktur, die einen Hash-Algorithmus darstellt, hat die Implementierung eines Übergangs zu einem neuen Hash begonnen.
Wie bereits erwähnt, wird der neue unterstützte Hash sein SHA-256 .

Answer 5

Ich glaube, die Kryptographen würden feiern.

Zitat von Wikipedia-Artikel über SHA-1 :

Im Februar 2005 wurde ein Anschlag von Xiaoyun Wang, Yiqun Lisa Yin und Hongbo Yu angekündigt. Die Angriffe können Kollisionen in der Vollversion von SHA-1 finden und erfordern weniger als 2^69 Operationen. (Eine Brute-Force-Suche würde 2^80 Operationen erfordern.)