Wie wirkt sich die neu gefundene SHA-1-Kollision auf Git aus?

Kürzlich hat ein Forscherteam zwei Dateien mit demselben SHA-1-Hash (https://shattered.it/).

Da Git diesen Hash für seinen internen Speicher verwendet, wie weit beeinflusst diese Art von Angriff Git?

Edit, Ende Dezember 2017: Git Version 2.16 erhält nach und nach interne Schnittstellen, um unterschiedliche Hashes zu ermöglichen. Es ist noch ein langer Weg.

Die kurze (aber unbefriedigende) Antwort lautet, dass die Beispieldateien kein Problem für Git sind – sondern zwei andere (sorgfältig berechnete) Dateien könnten sein.

Ich habe diese beiden Dateien heruntergeladen, shattered-1.pdf und shattered-2.pdfund legen Sie sie in ein neues leeres Repository:

macbook$ shasum shattered-*
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
macbook$ cmp shattered-*
shattered-1.pdf shattered-2.pdf differ: char 193, line 8
macbook$ git init
Initialized empty Git repository in .../tmp/.git/
macbook$ git add shattered-1.pdf 
macbook$ git add shattered-2.pdf 
macbook$ git status
On branch master

Initial commit

Changes to be committed:
  (use "git rm --cached <file>..." to unstage)

    new file:   shattered-1.pdf
    new file:   shattered-2.pdf

Obwohl die beiden Dateien die gleiche SHA-1-Prüfsumme haben (und größtenteils gleich angezeigt werden, obwohl die eine einen roten und die andere einen blauen Hintergrund hat), sind sie erhalten Sie verschiedene Git-Hashes:

macbook$ git ls-files --stage
100644 ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 0   shattered-1.pdf
100644 b621eeccd5c7edac9b7dcba35a8d5afd075e24f2 0   shattered-2.pdf

Das sind die beiden SHA-1-Prüfsummen für die Dateien wie in Git gespeichert: man ist ba9aa... und der andere ist b621e.... Beides nicht 38762c.... Aber-warum?

Die Antwort ist, dass Git Dateien nicht als sich selbst speichert, sondern als String-Literal blobein Leerzeichen, die dezimalisierte Größe der Datei und ein ASCII-NULL-Byte und dann die Dateidaten. Beide Dateien sind genau gleich groß:

macbook$ ls -l shattered-?.pdf
...  422435 Feb 24 00:55 shattered-1.pdf
...  422435 Feb 24 00:55 shattered-2.pdf

beiden wird also der wörtliche Text vorangestellt blob 422435\0 (wo \0 repräsentiert ein einzelnes Byte, a la C oder Python-Oktal-Escapes in Strings).

Vielleicht überraschend – oder auch nicht, wenn Sie wissen, wie SHA-1 berechnet wird – das Hinzufügen von gleiche Präfix zu zwei verschiedenen Dateien, die dennoch die erzeugten gleiche Prüfsumme vorherbewirkt, dass sie jetzt produzieren unterschiedlich Prüfsummen.

Der Grund, warum dies nicht überraschend sein sollte, ist, dass wenn das endgültige Prüfsummenergebnis wäre nicht exquisit empfindlich auf die Positionsowie den Wert jedes Eingabebits, wäre es einfach, bei Bedarf Kollisionen zu erzeugen, indem man eine bekannte Eingabedatei nimmt und lediglich einige ihrer Bits neu anordnet. Diese beiden Eingabedateien erzeugen die gleiche Summe, obwohl sie ein unterschiedliches Byte an haben char 193, line 8aber dieses Ergebnis wurde den Forschern zufolge durch den Versuch von über 9 Trillionen (kurze Skala) Eingänge. Zu bekommen Als Ergebnis fügten sie sorgfältig ausgewählte Rohdatenblöcke an einer von ihnen kontrollierten Position ein, die sich auf die Summen auswirkte, bis sie Paare von Eingaben fanden, die zu einer Kollision führten.

Durch Hinzufügen der blob Kopfzeile, Git die Stelle verschobenwodurch die 110-GPU-Jahre der Berechnung in einem einzigen mehr oder weniger zufälligen Rülpsen zerstört werden.

Jetzt, da sie wissen, dass Git dies tun wird, könnten sie es tun wiederholen ihre 110-GPU-Jahre der Berechnung mit Eingaben, die mit beginnen blob 422435\0 (vorausgesetzt, ihre Opferblöcke werden nicht zu viel herumgeschoben; und die tatsächliche Anzahl der benötigten GPU-Jahre der Berechnung würde wahrscheinlich variieren, da der Prozess ein bisschen ist stochastisch). Sie würden dann mit zwei kommen unterschiedlich Dateien, die die haben könnten blob Kopf abgezogen. Diese beiden Dateien hätten nun unterschiedliche SHA-1-Prüfsummen voneinander, aber wann git add-ed, beide würden die erzeugen gleich SHA-1-Prüfsumme.

In diesem speziellen Fall würde die erste hinzugefügte Datei den Slot “gewinnen”. (Nehmen wir an, es heißt shattered-3.pdf.) Ein ausreichend gutes Git – ich bin mir überhaupt nicht sicher, ob das aktuelle Git so gut ist; siehe Rubens experimentelle Antwort auf Wie würde Git mit einer SHA-1-Kollision auf einem Blob umgehen? – würde das bemerken git add shattered-4.pdfbeim Versuch, die zweite Datei hinzuzufügen, kollidierte mit der ersten, aber anderen shattered-3.pdf und würde dich warnen und das versäumen git add Schritt. In jedem Fall könnten Sie diese beiden Dateien nicht zu einem einzigen Repository hinzufügen.

Aber zuerst muss jemand viel mehr Zeit und Geld aufwenden, um die neue Hash-Kollision zu berechnen.

Vielleicht könnte die Antwort von Linus etwas Licht ins Dunkel bringen:

IIRC Jemand hat daran gearbeitet, die SHA1-Annahmen von git zu parametrisieren, damit ein Repository schließlich einen sichereren Hash verwenden könnte. Wie weit ist das gekommen? Es gibt immer noch viele “40”-Konstanten in git.git HEAD.

Ich glaube nicht, dass Sie unbedingt die Größe des Hashs ändern möchten. Sie können einen anderen Hash verwenden und nur die gleichen 160 Bit davon verwenden.

Da wir jetzt Kollisionen in gültigen PDF-Dateien haben, können wahrscheinlich Kollisionen in gültigen Git-Commit- und Baumobjekten konstruiert werden.

Ich habe den Angriff noch nicht gesehen, aber Git hasht die Daten nicht nur, es stellt ihnen ein Typ-/Längenfeld voran. Das macht normalerweise Kollisionsangriffe viel schwieriger, weil Sie entweder auch die resultierende Größe gleich machen müssen, oder Sie müssen auch in der Lage sein, das Größenfeld in der Kopfzeile zu bearbeiten.

PDFs haben dieses Problem nicht, sie haben einen festen Header und Sie können der Mitte ziemlich willkürlich stille Daten hinzufügen, die einfach nicht angezeigt werden.

PDFs sind also ein viel besserer Angriffsvektor, gerade weil sie ein ziemlich undurchsichtiges Datenformat sind. Git hat an manchen Stellen undurchsichtige Daten (wir verstecken Dinge zum Beispiel absichtlich in Commit-Objekten, aber per Definition sind diese undurchsichtigen Daten ziemlich zweitrangig.

Anders ausgedrückt: Ich bezweifle, dass der Himmel auf Git als Quellcodeverwaltungstool hereinfällt. Wollen wir zu einem anderen Hash migrieren? Jawohl. Ist es “Game Over” für SHA1, wie die Leute sagen wollen? Wahrscheinlich nicht.

Ich habe die Angriffsdetails nicht gesehen, aber ich wette

(a) Die Tatsache, dass wir eine separate Größencodierung haben, macht es viel schwieriger, überhaupt mit Git-Objekten umzugehen

(b) Wir können den undurchsichtigen Daten, die wir haben, wahrscheinlich leicht einige zusätzliche Plausibilitätsprüfungen hinzufügen, um das Verbergen zufälliger Daten, auf die diese Angriffe so ziemlich immer angewiesen sind, viel schwieriger zu machen.

Linus

Quelle: https://marc.info/?l=git&m=148787047422954