Wie würde Git mit einer SHA-1-Kollision auf einem Blob umgehen?

543

Dies ist wahrscheinlich noch nie in der realen Welt passiert und wird vielleicht auch nie passieren, aber lassen Sie uns Folgendes bedenken: Angenommen, Sie haben ein Git-Repository, machen ein Commit und haben sehr, sehr viel Pech: Einer der Blobs hat am Ende den gleichen SHA-1 als eine andere, die bereits in Ihrem Repository ist. Die Frage ist, wie würde Git damit umgehen? Einfach scheitern? Finden Sie einen Weg, um die beiden Blobs zu verknüpfen und zu überprüfen, welcher für den jeweiligen Kontext benötigt wird?

Eher ein Rätsel als ein eigentliches Problem, aber ich fand das Problem interessant.

Gnurou
quelle
76
Einst ein Rätsel, jetzt möglicherweise ein tatsächliches Problem .
Toby
11
@Toby Bei dieser Frage ging es um einen Pre-Image-Angriff . Was Google demonstrierte, ist ein Kollisionsangriff - ähnlich, aber leicht unterschiedlich. Sie können mehr über den Unterschied lesen hier .
Saheed
@Saheed Ich verstehe nicht, in welchem ​​Teil dieser Frage es sich speziell um einen Pre-Image-Angriff handelt, da es sich bei der gestellten Frage nur um eine Kollision in einem Git-Repository handelt, nicht um die Ausnutzung.
Toby
3
@Toby Bei dem ursprünglichen Brain Teaser ging es nicht um einen Angriff (weder Vorbild noch Kollision), sondern um eine versehentliche Kollision, die so unwahrscheinlich ist, dass es sich nicht lohnt, darüber nachzudenken. Ich denke, was Saheed richtig versucht hat zu sagen, dass dies immer noch kein wirkliches Problem ist. Sie haben jedoch Recht, dass der Google-Kollisionsangriff je nach Verwendung von Git möglicherweise ein Sicherheitsproblem verursacht hat.
Andrew W. Phillips
Hier ist eine zweite Kollision, die nur 320 Bytes umfasst privacylog.blogspot.com/2019/12/the-second-sha-collision.html
William Entriken

Antworten:

736

Ich habe ein Experiment durchgeführt, um herauszufinden, wie sich Git in diesem Fall genau 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 das folgende 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 Commits gemacht und Folgendes bemerkt.

  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).
  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 durchfü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.

Für # 2 wird normalerweise ein Fehler wie der folgende angezeigt, 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.

Bei # 4 und # 6 wird normalerweise ein Fehler wie der folgende angezeigt:

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

beim Ausführen von "git commit". In diesem Fall können Sie normalerweise einfach "git commit" erneut eingeben, da dadurch ein neuer Hash erstellt wird (aufgrund des geänderten Zeitstempels).

Bei # 5 und # 9 wird normalerweise ein Fehler wie der folgende angezeigt:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

beim Ausführen von "git commit"

Wenn jemand versucht, Ihr beschädigtes Repository zu klonen, sieht er normalerweise Folgendes:

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 Repository-Inhalt unterscheidet sich von dem, was Sie erwarten sein. Menschen, die klonen oder ziehen, haben einen anderen Inhalt als Sie. Die Fälle 4,5,6 und 9 sind in Ordnung, da sie mit einem Fehler beendet werden. Ich nehme an, es wäre besser, wenn es zumindest in allen Fällen mit einem Fehler fehlschlagen würde.

Ruben
quelle
157
Tolle Antwort - es ist eine großartige Idee, die Hash-Größe zu reduzieren, um zu sehen, wie sie sich tatsächlich verhält.
Gnurou
4
@Gnurou Ich stimme zu und habe diese Antwort zu der Zeit positiv bewertet. Wurden diese Fälle in der Git-Mailingliste erwähnt?
VonC
1
Wie wahrscheinlich ist es, dass dies tatsächlich ohne reduzierte Hash-Größe geschieht?
Mathias Bader
4
Was sind die Pläne, um zu einem anderen Hashing-Algorithmus zu wechseln?
Pete
9
Muss gelesen werden - Linus Torvals Erklärungen: plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL
phil_lgr
238

Ursprüngliche Antwort (2012) (siehe shattered.ioSHA1-Kollision 2017 unten)

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

Nee. Wenn es das gleiche SHA1 hat, bedeutet dies, dass wir das bereits vorhandene Objekt nicht überschreiben , wenn wir das Objekt vom anderen Ende empfangen .

Wenn also jemals eine Kollision auftritt, wird das "frühere" Objekt in einem bestimmten Repository immer überschrieben. Beachten Sie jedoch, dass "früher" offensichtlich pro Repository ist, in dem Sinne, dass das Git-Objektnetzwerk eine DAG generiert, die nicht vollständig geordnet ist. Während sich also verschiedene Repositorys darüber einig sind, was bei direkter Abstammung "früher" ist, wenn die Objekt kam durch separate und nicht direkt verwandte Zweige, zwei verschiedene Repos können offensichtlich die beiden Objekte in unterschiedlicher Reihenfolge erhalten haben.

Unter Sicherheitsgesichtspunkten ist das "frühere Überschreiben" jedoch genau das, was Sie wollen: Denken Sie daran, dass das Git-Modell darin besteht, dass Sie in erster Linie nur Ihrem eigenen Repository vertrauen sollten .
Wenn Sie also ein " git pull" ausführen, sind die neuen eingehenden Objekte per Definition weniger vertrauenswürdig als die Objekte, die Sie bereits haben, und als solche wäre es falsch, einem neuen Objekt zu erlauben, ein altes zu ersetzen.

Sie haben also zwei Kollisionsfälle:

  • die versehentliche Art , bei der Sie irgendwie sehr, sehr unglücklich sind und zwei Dateien am Ende den gleichen SHA1 haben.
    Zu diesem Zeitpunkt wird beim Festschreiben dieser Datei (oder wenn Sie ein " git-update-index" ausführen, um sie in den Index zu verschieben, aber noch nicht festgeschrieben) der SHA1 des neuen Inhalts berechnet. Da er jedoch mit einem alten Objekt übereinstimmt, Es wird kein neues Objekt erstellt, und der Commit-or-Index zeigt auf das alte Objekt .
    Sie werden es nicht sofort bemerken (da der Index mit dem alten Objekt SHA1 übereinstimmt und das bedeutet, dass so etwas wie " git diff" die ausgecheckte Kopie verwendet), aber wenn Sie jemals einen Diff auf Baumebene machen (oder einen Klon machen) oder ziehen oder erzwingen Sie eine Kaufabwicklung) Sie werden plötzlich bemerken, dass sich diese Datei in etwas geändert hatganz anders als erwartet. In verwandten Nachrichten stellt sich die Frage, was gegen die unbeabsichtigte Kollision zu tun ist. Lassen Sie mich zunächst die Leute daran erinnern, dass die unbeabsichtigte Art der Kollision wirklich sehr, sehr, sehr unwahrscheinlich ist, sodass wir sie höchstwahrscheinlich nie in der gesamten Geschichte sehen werden des Universums. Aber wenn es passiert, ist es nicht das Ende der Welt: Am wahrscheinlichsten müssten Sie nur die Datei ändern, die leicht kollidiert ist, und einfach ein neues Commit mit den geänderten Inhalten erzwingen (fügen Sie einen Kommentar mit den Worten " ") und hinzu dann unterrichte git über die Magie SHA1, die sich als gefährlich erwiesen hat.
    Sie würden diese Art von Kollision also im Allgemeinen ziemlich schnell bemerken.


    /* This line added to avoid collision */
    In ein paar Millionen Jahren müssen wir vielleicht ein oder zwei "vergiftete" SHA1-Werte zu git hinzufügen. Es ist sehr unwahrscheinlich, dass es sich um ein Wartungsproblem handelt;)

  • Die Art von Kollision des Angreifers, weil jemand SHA1 gebrochen (oder brutal erzwungen) hat.
    Dieser ist eindeutig viel wahrscheinlicher als der unbeabsichtigte, aber per Definition ist er immer ein "entferntes" Repository. Wenn der Angreifer Zugriff auf das lokale Repository hätte, hätte er viel einfachere Möglichkeiten, Sie zu vermasseln.
    In diesem Fall ist die Kollision also kein Problem : Sie erhalten ein "schlechtes" Repository, das sich von dem unterscheidet, was der Angreifer beabsichtigt hat. Da Sie sein kollidierendes Objekt jedoch nie verwenden, unterscheidet es sich buchstäblich nicht von dem Angreifer, der überhaupt keine Kollision gefunden hat, aber nur das Objekt verwenden, das Sie bereits hatten (dh es entspricht zu 100% der "trivialen" Kollision der identischen Datei, die denselben SHA1 erzeugt).

Die Frage der Verwendung von SHA-256 wird regelmäßig erwähnt, aber vorerst nicht behandelt (2012).
Hinweis: Ab 2018 und Git 2.19 wird der Code für die Verwendung von SHA-256 überarbeitet.


Hinweis (Humor): Mit dem Projekt gitbrute von Brad Fitzpatrick ( ) können Sie ein Commit für ein bestimmtes SHA1- Präfix erzwingen .bradfitz

gitbrute brute erzwingt ein Paar von Zeitstempeln für Autor + Committer, sodass das resultierende Git-Commit Ihr gewünschtes Präfix hat.

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


Daniel Dinnyes weist in den Kommentaren zu 7.1 Git Tools - Revisionsauswahl darauf hin , dass:

Es besteht eine höhere Wahrscheinlichkeit, dass jedes Mitglied Ihres Programmierteams in derselben Nacht von Wölfen in nicht verwandten Vorfällen angegriffen und getötet wird.


Noch in jüngerer Zeit (Februar 2017) wurde shattered.iodie Möglichkeit einer SHA1-Kollision aufgezeigt:
(Weitere Informationen finden Sie in meiner separaten Antwort , einschließlich des Google+ Posts von Linus Torvalds.)

  • a / erfordert immer noch über 9.223.372.036.854.775.808 SHA1-Berechnungen. Dies erforderte eine Prozessorleistung von 6.500 Jahren Einzel-CPU-Berechnungen und 110 Jahren Einzel-GPU-Berechnungen.
  • b / würde eine Datei fälschen (mit demselben SHA1), aber mit der zusätzlichen Einschränkung würden Inhalt und Größe den identischen SHA1 erzeugen (eine Kollision mit dem Inhalt allein reicht nicht aus): siehe " Wie wird der Git-Hash berechnet? ") : Ein Blob SHA1 wird basierend auf Inhalt und Größe berechnet .

Weitere Informationen finden Sie unter " Lebensdauern kryptografischer Hash-Funktionen " von Valerie Anita Aurora .
Auf dieser Seite stellt sie fest:

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

Weitere Informationen finden Sie in meiner separaten Antwort unten .

VonC
quelle
25
Twist: Hashes nach dem Hinzufügen immer noch gleich /* This line added to avoid collision */: D Sie können die Lotterie zweimal gewinnen: P
Janus Troelsen
4
@ JanusTroelsen sicher, aber es ist immer noch eine Lotterie, nicht wahr ? ;) (wie in dieser kurzen Notiz über SHA1 erwähnt )
VonC
6
@VonC in Bezug auf diese Referenz : Wird ein Ausbruch einer globalen Werwolf-Epidemie - die die gesamte Menschheit auslöscht und in derselben Nacht zum grausamen Tod aller meiner Entwickler führt, obwohl sie geografisch verteilt waren - als nicht verwandter Vorfall angesehen? Natürlich unter der Annahme, dass es bei Vollmond passiert ist. Nun würde ein solches Szenario die Dinge ändern. Sogar darüber nachzudenken ist Wahnsinn! Das ist auf einer ganz anderen Wahrscheinlichkeitsskala! Das würde bedeuten, dass wir ... aufhören müssen, GIT zu benutzen! JETZT!!! JEDER RUUUUUN !!!!!!!
Daniel Dinnyes
2
Beachten Sie, dass der Gitbrute kein bestimmtes SHA1 erzwingt, sondern nur ein Präfix (dh einen Teil des gesamten SHA1). Das Erzwingen eines gesamten SHA1 (dh mit einem Präfix der gesamten Länge des Schlüssels) wird wahrscheinlich "zu lange" dauern.
mb14
2
@ JanusTroelsen Dann würden Sie hinzufügen:/* This line added to avoid collision of the avoid collision line */
smg
42

Laut Pro Git :

Wenn Sie zufällig ein Objekt festschreiben, das denselben SHA-1-Wert wie ein vorheriges Objekt in Ihrem Repository hat, sieht Git das vorherige Objekt bereits in Ihrer Git-Datenbank und geht davon aus, 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 auch Ihr neues Objekt nicht speichern.
Ich weiß nicht, wie das in der Kommandozeile aussehen würde, aber das wäre sicherlich verwirrend.

Etwas weiter unten versucht dieselbe Referenz, die Wahrscheinlichkeit einer solchen Kollision zu veranschaulichen:

Hier ist ein Beispiel, um Ihnen eine Vorstellung davon zu geben, was für eine SHA-1-Kollision erforderlich ist. Wenn alle 6,5 Milliarden Menschen auf der Erde programmieren würden und jede Sekunde Code produzieren würde, der der gesamten Linux-Kernel-Geschichte (1 Million Git-Objekte) entspricht, und ihn in ein riesiges Git-Repository verschieben würde, würde es 5 Jahre dauern, bis Dieses Repository enthielt genügend Objekte, um eine 50% ige Wahrscheinlichkeit einer einzelnen SHA-1-Objektkollision zu haben. Es besteht eine höhere Wahrscheinlichkeit, dass jedes Mitglied Ihres Programmierteams in derselben Nacht von Wölfen in nicht verwandten Vorfällen angegriffen und getötet wird.

Matte
quelle
44
Ich würde gerne die Quelle für die Zahlen im letzten Satz sehen ;-)
Joachim Sauer
17
@Jasper: Dieser Link ist eine gute Dokumentation, enthält jedoch keine Statistiken über die Wahrscheinlichkeit, dass jedes Mitglied eines Teams in derselben Nacht von Wölfen in nicht verwandten Vorfällen angegriffen und getötet wird.
Joachim Sauer
5
@Jasper: Nun, so wie ich es gelesen habe, behauptet der Text buchstäblich, dass die Wahrscheinlichkeit, dass 6,5 Milliarden Teammitglieder in derselben Nacht von Wölfen getötet werden, höher als 50% ist. Aber mein Haupteinwand gegen seine Aussage ist , dass ein solches Ereignis würde haben zu einem weltweiten Phänomen sein; Es ist unvorstellbar, dass dies aufgrund nicht zusammenhängender Vorfälle auftreten kann. ;)
Keith Robertson
5
@KeithRobertson Ich bin mir ziemlich sicher, dass es in dem Beitrag um die Wahrscheinlichkeit geht, dass alle Ihre tatsächlichen Teammitglieder gefressen werden, verglichen mit der Wahrscheinlichkeit einer Hash-Kollision, wenn alle auf der Welt wahnsinnige Mengen an Code produzieren, neben der Zeit, die unter diesen Umständen benötigt wird Erreichen Sie eine 50% ige Chance auf eine Kollision (dh der Vorfall mit den Wölfen betraf nicht die ganze Welt und die 50% waren von den Wölfen getrennt). Sie haben jedoch verstanden, wenn ein solches Ereignis unvorstellbar ist, sollte es auch eine Git-Hash-Kollision geben. (Natürlich ist einer (fast) rein zufällig und der andere nicht, aber immer noch.)
Jasper
23

Um meine vorherige Antwort aus dem Jahr 2012 zu ergänzen , gibt es jetzt (Februar 2017, fünf Jahre später) ein Beispiel für eine tatsächliche SHA-1-Kollision mit shattered.io , bei der Sie zwei kollidierende PDF-Dateien erstellen können: das heißt, Sie erhalten eine SHA- 1 digitale Signatur in der ersten PDF-Datei, die auch als gültige Signatur in der zweiten PDF-Datei missbraucht werden kann.
Siehe auch " Seit Jahren vor der Tür des Todes ist die weit verbreitete SHA1-Funktion jetzt tot " und diese Abbildung .

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

(1) Zunächst einmal - der Himmel fällt nicht. Es gibt einen großen Unterschied zwischen der Verwendung eines kryptografischen Hashs für Dinge wie Sicherheitssignaturen und der Verwendung eines solchen zum Generieren einer "Inhaltskennung" für ein inhaltsadressierbares System wie git.

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

(3) Und schließlich gibt es tatsächlich einen recht einfachen Übergang zu einem anderen Hash, der die Welt nicht zerstören wird - oder sogar zu alten Git-Repositories.

Bezüglich dieses Übergangs siehe die Q1 2018 Git 2.16 , in dem eine Struktur hinzugefügt wird, die den Hash-Algorithmus darstellt. Die Umsetzung dieses Übergangs hat begonnen.

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


Ursprüngliche Antwort (25. Februar) Aber:

Joey Hess probiert diese PDFs in einem Git-Repo aus und fand :

Dazu gehören zwei Dateien mit demselben SHA und derselben Größe, die aufgrund der Art und Weise, wie git den Header dem Inhalt voranstellt, unterschiedliche Blobs erhalten.

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

Das Anhängen identischer Daten an diese kollidierenden Dateien führt zwar zu anderen Kollisionen, das Voranstellen von Daten jedoch nicht.

Der Hauptangriffsvektor (Schmieden eines Commits) wäre also :

  • Generieren Sie ein reguläres Festschreibungsobjekt.
  • Verwenden Sie das gesamte Festschreibungsobjekt + NUL als ausgewähltes Präfix und
  • Verwenden Sie den Kollisionsangriff mit identischem Präfix, um die kollidierenden guten / schlechten Objekte zu generieren.
  • ... 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 erkennen, die in jeder Datei mit vorhanden sind cr-marcstevens/sha1collisiondetection

Das Hinzufügen einer ähnlichen Prüfung in Git selbst würde einige Berechnungskosten verursachen .

Beim Ändern des Hashs kommentiert Linux :

Die Größe des Hashs und die Wahl des Hash-Algorithmus sind unabhängige Aspekte.
Was würden Sie vermutlich tun , ist Umstellung auf einen 256-Bit - Hash, die Verwendung , die intern und in der nativen git Datenbank, und dann standardmäßig nur zeigen , als die Hash - 40-Zeichen Hex - String ( eine Art, wie , wie wir abkürzen schon Dinge in viele Situationen).
Auf diese Weise sehen Tools um git die Änderung nicht einmal, es sei denn, sie werden in einem speziellen " --full-hash" Argument (oder " --abbrev=64" oder was auch immer übergeben - die Standardeinstellung ist, dass wir mit 40 abkürzen).

Ein Übergangsplan (von SHA1 zu einer anderen Hash-Funktion) wäre immer noch komplex , würde aber aktiv untersucht.
Eine convert-to-object_idKampagne ist im Gange :


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

SHA-1-Namen können über verschiedene Mechanismen als vertrauenswürdig eingestuft werden. Mit Git können Sie beispielsweise ein Commit oder Tag kryptografisch signieren. Dadurch wird nur das Commit- oder Tag-Objekt selbst signiert, das wiederum unter Verwendung ihrer SHA-1-Namen auf andere Objekte verweist, die die tatsächlichen Dateidaten enthalten. Eine Kollision in diesen Objekten könnte eine Signatur erzeugen, die gültig erscheint, aber auf andere Daten verweist als der beabsichtigte Unterzeichner. Bei einem solchen Angriff sieht der Unterzeichner nur die eine Hälfte der Kollision und das Opfer die andere Hälfte.

Schutz:

Der jüngste Angriff verwendet 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 erkannt werden kann, wenn der SHA-1 einer der Hälften eines kollidierenden Paares berechnet wird.

GitHub.com führt diese Erkennung jetzt für jeden berechneten SHA-1 durch und bricht die Operation ab, wenn Anzeichen dafür vorliegen, dass das Objekt die Hälfte eines kollidierenden Paares ist. Dies verhindert, dass Angreifer GitHub verwenden, um ein Projekt davon zu überzeugen, die "unschuldige" Hälfte ihrer Kollision zu akzeptieren, und verhindert, dass sie die böswillige Hälfte hosten.

Siehe " sha1collisiondetection" von Marc Stevens


Mit dem Hinzufügen einer Struktur, die den Hash-Algorithmus darstellt, im ersten Quartal 2018, Git 2.16 , wurde erneut die Implementierung eines Übergangs zu einem neuen Hash gestartet.
Wie oben erwähnt, wird der neue unterstützte Hash SHA-256 sein .

VonC
quelle
Die Kollision: 1. Der Versuch bestand darin, eine Kollision zu erzeugen, die nicht zufällig auftrat. 2. Aus dem PDF-Bericht: Insgesamt entspricht der Rechenaufwand 2 ^ 63.1 SHA-1-Komprimierungen und dauerte ungefähr 6.500 CPU-Jahre und 100 GPU-Jahre . 3. Obwohl wir von MD5 und SHA-1 fortfahren sollten, sind diese im Allgemeinen für die Verwendung von Dateien eindeutig.
Zaph
Es ist erwähnenswert, dass WebKit die kollidierenden PDFs für einen Test eingecheckt hat. Es brach ihre git-svn-Spiegelinfrastruktur: bugs.webkit.org/show_bug.cgi?id=168774#c24
dahlbyk
1
@dahlbyk Es ist in der Tat erwähnenswert ... dass ich es in der Antwort vermerkt habe (der Link hinter "Es hat ein Problem für git-svnobwohl" bezieht sich darauf, wenn auch indirekt)
VonC
1
@Mr_and_Mrs_D nein, es schlägt noch nicht mit einem Fehler fehl. Ein großer Patch ist in Arbeit, der dann die Kollisionserkennung erleichtert: marc.info/?l=git&m=148987267504882&w=2
VonC
1
@Mr_and_Mrs_D SIEHE 4 in stackoverflow.com/posts/42450327/revisions : Es schlägt jetzt fehl, zumindest wenn es auf GitHub aktualisiert wird.
VonC
6

Ich denke, Kryptographen würden feiern.

Zitat aus dem Wikipedia-Artikel zu SHA-1 :

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

Willem Hengeveld
quelle
7
Der Punkt ist, dass ein Fehler in SHA1 gefunden wurde und dass dies ungefähr zu der Zeit war, als Git eingeführt wurde. Die Wahrscheinlichkeit ist auch nicht linear. Nur weil Sie fünfzig Jahre lang Lotto spielen, bedeutet dies nicht, dass Sie eine höhere Gewinnchance haben. Sie haben jedes Mal die gleiche Chance. Die Person, die zum ersten Mal spielt, kann immer noch gewinnen.
0xC0000022L
Dies wird angreifen nur feststellen , dass Kollision, was bedeutet , dass Sie finden können , yso dass h(x) == h (y) ` , die für beliebige Daten wie SSL - Zertifikate ernsthafte Bedrohung ist dies jedoch nicht Git beeinflussen , welche auf dem zweiten Urbild Angriff anfällig sein würde , was bedeutet , dass mit Meldung xkönnen Sie es auf die Nachricht ändern , x'dass h(x) == h(x'). Dieser Angriff schwächt Git also nicht. Außerdem hat Git aus Sicherheitsgründen SHA-1 nicht ausgewählt.
Hauleth
Jetzt wurde eine Kollision gefunden - nur noch keine, die Git direkt stört. stackoverflow.com/questions/42433126/…
Willem Hengeveld
2 ^ 69 ist ungefähr 600 Exa-Operationen. Acht Jahre später kann der SaturnV-Supercomputer von Nvidia, der mit dem A100 aufgerüstet wurde, 4,6 ExaOPS ausführen, sodass dies möglicherweise in etwas mehr als 2 Minuten behoben oder in wenigen Tagen ein Brute-Force-Angriff ausgeführt werden kann.
Qdin
6

Es gibt verschiedene Angriffsmodelle für Hashes wie SHA-1, aber das normalerweise diskutierte ist die Kollisionssuche, einschließlich des HashClash- Tools von Marc Stevens .

"Ab 2012 wird der effizienteste Angriff gegen SHA-1 von Marc Stevens [34] mit geschätzten Kosten von 2,77 Mio. USD als Bruch eines einzelnen Hashwerts durch Anmietung von CPU-Leistung von Cloud-Servern angesehen."

Wie die Leute betonten, könnten Sie eine Hash-Kollision mit git erzwingen, aber dadurch werden die vorhandenen Objekte in einem anderen Repository nicht überschrieben. Ich würde mir sogar vorstellengit push -f --no-thin dass die vorhandenen Objekte nicht überschrieben werden, aber nicht 100% sicher sind.

Das heißt, wenn Sie sich in ein Remote-Repository hacken, können Sie Ihr falsches Objekt dort zum älteren machen und möglicherweise gehackten Code in ein Open-Source-Projekt auf Github oder ähnlichem einbetten. Wenn Sie vorsichtig waren, könnten Sie vielleicht eine gehackte Version einführen, die neue Benutzer heruntergeladen haben.

Ich vermute jedoch, dass viele Dinge, die die Entwickler des Projekts tun könnten, Ihren millionenschweren Hack entweder aufdecken oder versehentlich zerstören könnten. Insbesondere ist das eine Menge Geld, wenn ein Entwickler, den Sie nicht gehackt haben, jemals das oben Genannte ausführt, git push --no-thinnachdem er die betroffenen Dateien geändert hat, manchmal sogar ohne die --no-thinAbhängigkeit.

Jeff Burdges
quelle