Der Artikel zeigt, wie Sie eine nicht rekursive Zip-Bombe erstellen, die ein hohes Maß an Komprimierung bietet, indem Sie Dateien in einem Zip-Container überlappen. "Nicht rekursiv" bedeutet, dass es nicht von den Dekomprimierern abhängt, die in Zip-Archive eingebettete Dateien dekomprimieren: Es gibt nur eine Runde. Die Ausgabegröße erhöht sich quadratisch von der Eingabe und erreicht ein Komprimierungsverhältnis von mehr als 28 Millionen (10 MB → 281 TB) innerhalb des Zip-Formats. Eine weitere Erweiterung ist mit 64-Bit-Erweiterungen möglich. Das Design verwendet nur den gängigsten DEFLATE-Komprimierungsalgorithmus und ist mit den meisten Zip-Parsern kompatibel.

• zbsm.zip 42 kB → 5,5 GB
  
• zblg.zip 10 MB → 281 TB
  
• zbxl.zip 46 MB → 4,5 PB (Zip64, weniger kompatibel mit Parsern)

Quellcode:

  Git-Klon https://www.bamsoftware.com/git/zipbomb.git 

zipbomb-20190702.zip

Daten und Quelle der Abbildungen:

  Git-Klon https://www.bamsoftware.com/git/zipbomb-paper.git 

<sub>* Es gibt zwei Versionen von 42.zip: die alten 42 374 Bytes und die neueren 42 428 Bytes. Der Unterschied besteht darin, dass der neue vor dem Auspacken ein Passwort benötigt. Wir vergleichen nur mit der alten Version. Hier ist eine Kopie der Datei, falls Sie sie benötigen: 42.zip .

** Ich möchte den Autor von 42.zip kennen und angeben, konnte ihn aber nicht finden - lassen Sie mich wissen, wenn Sie Informationen haben.</sub>

Zip-Bomben müssen die Tatsache überwinden, dass der von Parsern am häufigsten unterstützte DEFLATE-Komprimierungsalgorithmus das Komprimierungsverhältnis von 1032 zu 1 nicht überschreiten kann . Aus diesem Grund basieren Zip-Bomben normalerweise auf rekursiver Dekomprimierung, indem Zip-Dateien in Zip-Dateien eingebettet werden, um ein zusätzliches Verhältnis zu erhalten 1032 mit jeder Schicht. Der Trick funktioniert jedoch nur in Implementierungen, die rekursiv dekomprimieren, und die meisten nicht. Die berühmteste 42.zip- Bombe dehnt sich auf beeindruckende 4,5 PB aus, wenn alle sechs Schichten rekursiv entpackt werden, auf der obersten Schicht jedoch nur 0,6 MB. Zip-Quines geben wie die von Cox und Ellingsen eine Kopie von sich selbst aus und dehnen sich daher beim rekursiven Auspacken unbegrenzt aus. Sie sind aber auch beim einmaligen Auspacken absolut sicher.

Dieser Artikel zeigt, wie eine nicht rekursive Zip-Bombe erstellt wird, deren Komprimierungsrate die DEFLATE-Grenze von 1032 überschreitet. Dabei werden Dateien in einem Zip-Container überlappt, um auf den „Kern“ stark komprimierter Daten in mehreren Dateien zu verweisen, ohne mehrere Kopien zu erstellen. Die Ausgabegröße der Reißverschlussbombe wächst quadratisch aus der Eingabegröße. d.h. das Kompressionsverhältnis verbessert sich mit zunehmender Bombengröße. Das Design hängt von den Funktionen von zip und DEFLATE ab: Es kann nicht direkt in andere Dateiformate oder Komprimierungsalgorithmen übertragen werden. Die Bombe ist mit den meisten Zip-Parsern kompatibel, mit Ausnahme von Streaming-Parsern, die Dateien in einem einzigen Durchgang analysieren, ohne das zentrale Verzeichnis der Zip-Datei zu überprüfen. Wir versuchen zwei widersprüchliche Ziele in Einklang zu bringen:

• Kompressionsverhältnis erhöhen. Wir definieren das Komprimierungsverhältnis als die Summe der Größen aller Dateien im Archiv geteilt durch die Größe der Zip-Datei selbst. Es werden keine Dateinamen oder andere Dateisystem-Metadaten berücksichtigt, sondern nur der Inhalt.
  
• Kompatibilität beibehalten. Zip ist ein komplexes Format, und Parser unterscheiden sich insbesondere in Grenzsituationen und in zusätzlichen Funktionen. Verwenden Sie keine Techniken, die nur mit bestimmten Parsern funktionieren. Wir werden einige Möglichkeiten zur Steigerung der Effizienz einer Zip-Bombe mit einem gewissen Kompatibilitätsverlust aufzeigen.

Zip-Dateistruktur

Die Zip-Datei besteht aus einem zentralen Verzeichnis von Dateilinks.



Das zentrale Verzeichnis befindet sich am Ende der Zip-Datei. Dies ist eine Liste der zentralen Verzeichnisheader . Jeder zentrale Verzeichnisheader enthält Metadaten für eine einzelne Datei, z. B. den Dateinamen und die CRC-32-Prüfsumme, sowie einen Zeiger zurück auf den lokalen Dateikopf. Der zentrale Verzeichnisheader hat eine Länge von 46 Bytes plus der Länge des Dateinamens.

Die Datei besteht aus dem Header der lokalen Datei, gefolgt von den komprimierten Dateidaten. Die Länge des lokalen Dateikopfs beträgt 30 Byte plus die Länge des Dateinamens. Es enthält eine redundante Kopie der Metadaten aus dem Header des zentralen Verzeichnisses sowie die Größe der komprimierten und nicht komprimierten Datendateien dahinter. Zip ist ein Containerformat, kein Komprimierungsalgorithmus. Die Daten jeder Datei werden mit dem in den Metadaten angegebenen Algorithmus komprimiert - normalerweise DEFLATE .

In dieser Beschreibung des Zip-Formats werden viele Details ausgelassen, die zum Verständnis der Zip-Bombe nicht erforderlich sind. Vollständige Informationen finden Sie in Abschnitt 4.3 APPNOTE.TXT oder „PKZip File Structure“ von Florian Buchholz oder im Quellcode .

Signifikante Redundanz und viele Unklarheiten im Zip-Format eröffnen Möglichkeiten für Unfug verschiedener Art. Eine Reißverschlussbombe ist nur die Spitze des Eisbergs. Links zur weiteren Lektüre:

• "Zehntausend Sicherheitsfallen: Ein ZIP-Format" von Ginwael Coldwind
  
• Durch mehrdeutiges Zip-Parsing können Sie Firefox-Add-On-Dateien vor dem Linter und anderen Personen verbergen : meine Sicherheitslücke bei addons.mozilla.org

Erste Entdeckung: Überlappende Dateien

Durch Komprimieren einer langen Folge von wiederholten Bytes können wir einen Kern hochkomprimierter Daten erstellen. Das Komprimierungsverhältnis des Kernels selbst darf das DEFLATE-Limit von 1032 nicht überschreiten. Daher benötigen wir eine Möglichkeit, den Kernel in vielen Dateien wiederzuverwenden, ohne in jeder Datei eine separate Kopie davon zu erstellen. Wir können dies tun, indem wir Dateien überlappen: Stellen Sie sicher, dass viele Header des zentralen Verzeichnisses auf eine einzelne Datei verweisen, deren Daten der Kern sind.



Betrachten Sie ein Beispiel dafür, wie sich dieses Design auf das Komprimierungsverhältnis auswirkt. Angenommen, ein Kern von 1000 Bytes wird in 1 MB entpackt. Dann „kostet“ das erste Megabyte Ausgabe 1078 Byte Eingabedaten:

• 31 Bytes für den lokalen Dateikopf (einschließlich 1-Byte-Dateiname)
  
• 47 Bytes für den zentralen Verzeichnisheader (einschließlich eines 1-Byte-Dateinamens)
  
• 1000 Bytes pro Kern

Aber jede 1 MB Ausgabe nach der ersten kostet nur 47 Bytes - wir brauchen keinen weiteren Header der lokalen Datei oder eine andere Kopie des Kernels, nur einen zusätzlichen Header des zentralen Verzeichnisses. Während die erste Verbindung vom Kern ein Kompressionsverhältnis von 1.000.000 / 1.078 ≈ 928 aufweist, bewegt jede zusätzliche Verbindung den Koeffizienten näher an 1.000.000 / 47 ≈ 21.277, und ein großer Kern erhöht die Decke.

Das Problem bei dieser Idee ist die mangelnde Kompatibilität. Da viele Header des zentralen Verzeichnisses auf einen Header der lokalen Datei verweisen, können die Metadaten (insbesondere der Dateiname) nicht für jede Datei gleich sein. Einige Parser schwören darauf . Zum Beispiel ruft Info-ZIP UnZip (das Standard- unzip unter Unix) Dateien ab, jedoch mit Warnungen:

  $ unzip overrap.zip
   Aufblasen: A.
 B: Nicht übereinstimmender "lokaler" Dateiname (A),
          Fortsetzung mit "zentraler" Dateinamenversion
   Aufblasen: B.
 ... 

Python zipfile löst auch eine Ausnahme aus :

  $ python3 -m zipfile -e überlappende.zip.
 Traceback (letzter Anruf zuletzt):
 ...
 __main __. BadZipFile: Dateiname im Verzeichnis 'B' und Header b'A 'unterscheiden sich. 

Als Nächstes sehen wir uns an, wie Sie die Konsistenz von Dateinamen neu gestalten und dabei die meisten Vorteile überlappender Dateien beibehalten.

Zweite Entdeckung: Zitieren der Header lokaler Dateien

Wir müssen die Header der lokalen Dateien für jede Datei trennen, während wir einen Kern wiederverwenden. Das einfache Kombinieren aller Header funktioniert nicht, da der Zip-Parser den Header der lokalen Datei findet, in der er den Start des DEFLATE-Streams erwartet. Aber die Idee wird funktionieren, mit geringfügigen Änderungen. Wir werden die DEFLATE-Funktion von unkomprimierten Blöcken verwenden, um die Header lokaler Dateien so zu "zitieren", dass sie Teil desselben DEFLATE-Streams zu sein scheinen, der im Kernel endet. Jeder Header der lokalen Datei (mit Ausnahme der ersten) wird auf zwei Arten interpretiert: als Code (Teil der Struktur der Zip-Datei) und als Daten (Teil des Dateiinhalts).



Ein DEFLATE-Stream ist eine Folge von Blöcken, bei denen jeder Block komprimiert oder nicht komprimiert werden kann. Wir denken normalerweise nur an komprimierte Blöcke, zum Beispiel ist der Kernel ein großer komprimierter Block. Es gibt aber auch unkomprimierte, die mit einem 5-Byte-Header mit einem Längenfeld beginnen, was einfach bedeutet: "Drucke die nächsten n Bytes wörtlich." Das Entpacken eines unkomprimierten Blocks bedeutet nur das Löschen des 5-Byte-Headers. Komprimierte und unkomprimierte Blöcke können sich im DEFLATE-Stream frei mischen. Die Ausgabe ist eine Verkettung der Ergebnisse des Entpackens aller Blöcke in der angegebenen Reihenfolge. Das Konzept „unkomprimiert“ ist nur auf DEFLATE-Ebene von Bedeutung. Dateidaten werden auf Zip-Ebene weiterhin als "komprimiert" betrachtet, unabhängig davon, welche Blöcke verwendet werden.

Der einfachste Weg, sich dieses Design vorzustellen, ist eine interne Überlappung von der letzten zur ersten Datei. Wir beginnen mit dem Einfügen eines Kernels, der das Ende der Datendatei für jede Datei bildet. Fügen Sie den Header der lokalen LFH _N- Datei und den Header des zentralen CDH _N- Verzeichnisses hinzu, das darauf verweist. Stellen Sie das Metadatenfeld "Komprimierte Größe" in LFH _N und CDH _N auf die komprimierte Kerngröße ein. Fügen Sie nun den 5-Byte-Header des unkomprimierten Blocks hinzu (im Diagramm grün dargestellt), dessen Längenfeld der Größe LFH _{N entspricht.} Fügen Sie den zweiten Header der lokalen LFH-Datei _{N −1} und den Titel des zentralen Verzeichnisses CDH _{N −1 hinzu} , das darauf verweist. Legen Sie das Metadatenfeld "komprimierte Größe" als neuen Header für die komprimierte Kernelgröße plus die Größe des unkomprimierten Blockheaders (5 Byte) plus die Größe von LFH _{N fest.}

Im Moment enthält die Zip-Datei zwei Dateien mit den Namen Y und Z. Lassen Sie uns durchgehen, was der Parser beim Parsen sieht. Angenommen, die komprimierte Kernelgröße beträgt 1000 Byte und die LFH _N- Größe beträgt 31 Byte. Wir beginnen mit CDH _{N −1} und folgen dem Vorzeichen für LFH _{N −1} . Der Name der ersten Datei lautet Y, und die komprimierte Größe der Datendatei beträgt 1036 Byte. Wenn wir die nächsten 1036 Bytes als DEFLATE-Stream interpretieren, stoßen wir zuerst auf einen 5-Byte-Header eines unkomprimierten Blocks, der besagt, dass die nächsten 31 Bytes kopiert werden sollen. Wir schreiben die nächsten 31 Bytes auf, die LFH _{N sind} , die wir entpacken und zur Y-Datei hinzufügen. Wenn wir uns weiter im DEFLATE-Stream bewegen, finden wir den komprimierten Block (Kernel), den wir in die Y-Datei entpacken. Jetzt haben wir das Ende der komprimierten Daten erreicht und sind mit der Y-Datei fertig.

Wenn wir zur nächsten Datei übergehen, folgen wir dem Zeiger von CDH _N auf LFH _N und finden eine Datei mit dem Namen Z mit einer komprimierten Größe von 1000 Bytes. Wenn wir diese 1000 Bytes als DEFLATE-Stream interpretieren, stoßen wir sofort auf einen komprimierten Block (wieder Core) und entpacken ihn in eine Z-Datei. Jetzt haben wir das Ende der endgültigen Datei erreicht und sind fertig. Die Ausgabedatei Z enthält den entpackten Kernel; Die Ausgabedatei Y ist dieselbe, jedoch optional mit einem Präfix von 31 Byte LFH _N.

Wir schließen die Konstruktion ab, indem wir den Zitiervorgang wiederholen, bis das Zip-Archiv die erforderliche Anzahl von Dateien enthält. Jede neue Datei fügt einen zentralen Verzeichnisheader, einen lokalen Dateikopf und einen unkomprimierten Block hinzu, um direkt aus dem nächsten lokalen Dateikopf zu zitieren. Komprimierte Dateidaten sind normalerweise eine Kette von nicht komprimierten DEFLATE-Blöcken (zitierte lokale Dateikopfzeilen), gefolgt von einem komprimierten Kern. Jedes Byte im Kernel trägt ungefähr 1032 N zur Ausgabegröße bei, da jedes Byte Teil aller N Dateien ist. Die Ausgabedateien haben auch unterschiedliche Größen: Die früheren sind größer als die späteren, da sie die Überschriften der lokalen Dateien häufiger zitieren. Der Inhalt der Ausgabedateien macht nicht viel Sinn, aber niemand sagte, dass es Sinn machen sollte.

Dieses Überlappungszitierungsdesign ist besser kompatibel als das vollständige Überlappungsdesign aus dem vorherigen Abschnitt, aber die Kompatibilität wird durch Komprimierung erreicht. Dort kostet jede hinzugefügte Datei nur den Titel des zentralen Verzeichnisses, hier den Titel des zentralen Verzeichnisses, den Header der lokalen Datei und weitere 5 Bytes für den Citation-Header.

Optimierung

Nachdem wir das grundlegende Design der Reißverschlussbombe erhalten haben, werden wir versuchen, sie so effizient wie möglich zu gestalten. Wir wollen zwei Fragen beantworten:

• Was ist das maximale Komprimierungsverhältnis für eine bestimmte Zip-Dateigröße?
  
• Was ist das maximale Komprimierungsverhältnis angesichts der Einschränkungen des Zip-Formats?

Kernel-Komprimierung

Es ist für uns von Vorteil, den Kernel so weit wie möglich zu komprimieren, da jedes entpackte Byte mit N multipliziert wird . Zu diesem Zweck verwenden wir einen benutzerdefinierten DEFLATE-Kompressor namens massiven_deflate, der auf das Komprimieren einer Zeichenfolge wiederholter Bytes spezialisiert ist.

Alle anständigen DEFLATE-Archivierer kommen dem Komprimierungsverhältnis von 1032 in einem endlosen Strom wiederholter Bytes nahe, aber wir sind besorgt über die spezifische Größe. In unserer Archivgröße enthält Bulk_deflate mehr Daten als Allzweckarchivierer: etwa 26 KB mehr als zlib und Info-ZIP und etwa 15 KB mehr als Zopfli , wodurch die Geschwindigkeit aus Gründen der Komprimierungsqualität beeinträchtigt wird.



Der Preis eines hohen Kompressionsverhältnisses mass_deflate - der Mangel an Vielseitigkeit. Es können nur Zeilen mit sich wiederholenden Bytes und nur eine bestimmte Länge komprimiert werden, nämlich 517 + 258 k für eine Ganzzahl k ≥ 0. Zusätzlich zu einer guten Komprimierung arbeitetulk_deflate schnell und führt die Arbeit unabhängig von der Größe der Eingabedaten fast zur gleichen Zeit aus. Zählen der Arbeit des tatsächlichen Schreibens einer komprimierten Zeichenfolge.

Dateinamen

Für unsere Zwecke sind Dateinamen fast tot. Obwohl sie zur Ausgabegröße beitragen, indem sie Teil der zitierten Header lokaler Dateien sind, tragen die Bytes im Dateinamen viel weniger bei als die Bytes im Kernel. Wir möchten, dass die Dateinamen so kurz wie möglich und unterschiedlich sind, ohne die Kompatibilität zu vergessen.

Jedes für einen Dateinamen ausgegebene Byte bedeutet zwei nicht für den Kernel ausgegebene Bytes (zwei, da jeder Dateiname zweimal angezeigt wird: im Header des zentralen Verzeichnisses und im Header der lokalen Datei). Ein Dateinamenbyte ergibt einen Durchschnitt von nur ( N + 1) / 4 Bytes der Ausgabe, während ein Byte im Kernel als 1032 N zählt. Beispiele: 1 , 2 , 3 .

Die erste Überlegung zur Kompatibilität ist die Codierung. Die Zip-Format-Spezifikation besagt, dass Dateinamen als CP 437 oder UTF-8 interpretiert werden sollten, wenn ein bestimmtes Flag-Bit gesetzt ist ( APPNOTE.TXT, Anhang D ). Dies ist der Hauptgrund für die Inkompatibilität zwischen Zip-Parsern, die Dateinamen in einer festen oder länderspezifischen Codierung interpretieren können. Aus Kompatibilitätsgründen ist es daher besser, sich auf Zeichen mit derselben Codierung in CP 437 und UTF-8 zu beschränken. Dies sind nämlich 95 druckbare US-ASCII-Zeichen.

Wir sind auch an Namensbeschränkungen für Dateisysteme gebunden. Bei einigen Dateisystemen wird die Groß- und Kleinschreibung nicht berücksichtigt, daher werden 'a' und 'A' nicht als unterschiedliche Namen betrachtet. Gängige Dateisysteme wie FAT32 verbieten bestimmte Zeichen wie '*' und '?'.

Als sicheren, aber nicht unbedingt optimalen Kompromiss verwendet unsere Zip-Bombe Dateinamen aus dem 36-stelligen Alphabet, das keine Sonderzeichen und Zeichen in verschiedenen Groß- und Kleinschreibung enthält:

  0 1 2 3 4 5 6 7 8 9 ABCDEFGHIJKLMNOPQRSTU VWXYZ 

Dateinamen werden auf offensichtliche Weise generiert, alle Positionen der Reihe nach, wobei eine Position am Ende der Schleife hinzugefügt wird:

  "0", "1", "2", ..., "Z",
 "00", "01", "02", ..., "0Z",
 ...
 "Z0", "Z1", "Z2", ..., "ZZ",
 "000", "001", "002", ... 

Es gibt 36 einstellige Dateinamen, 36² zweistellige Dateinamen usw. Vier Bytes reichen für 1.727.604 verschiedene Dateinamen.

Wie kann ich sie besser sortieren, da die Dateinamen im Archiv normalerweise unterschiedlich lang sind: vom kürzesten zum längsten oder umgekehrt? Wenn Sie ein wenig nachdenken, ist es besser, die längsten Namen zuletzt zu setzen. Diese Sortierung fügt zblg.zip mehr als 900 MB Ausgabe hinzu , verglichen mit der längsten bis kürzesten Bestellung. Dies ist jedoch eine geringfügige Optimierung, da 900 MB nur 0,0003% der Gesamtgröße des Problems ausmachen.

Kerngröße

Überlappendes Angebotsdesign ermöglicht es Ihnen, einen komprimierten Datenkern zu platzieren und ihn dann viele Male kostengünstig zu kopieren. Wie viel Speicherplatz ist für eine bestimmte Größe der Zip-Datei X optimal zum Speichern des Kernels zuzuweisen und wie viel zum Erstellen von Kopien?

Um das optimale Gleichgewicht zu finden, müssen Sie nur eine Variable N optimieren, die Anzahl der Dateien im Zip-Archiv. Jeder N- Wert erfordert einen bestimmten Overhead für die Header des zentralen Verzeichnisses, die Header lokaler Dateien, die Header von Zitierblöcken und die Dateinamen. Der Rest des Raumes wird vom Kern eingenommen. Da N eine Ganzzahl sein muss und Sie nur eine bestimmte Anzahl von Dateien einfügen können, bevor die Kernelgröße auf Null fällt, reicht es aus, jeden möglichen Wert von N zu überprüfen und den Wert auszuwählen, der die größte Ausgabe liefert.

Durch Anwenden des Optimierungsverfahrens auf X = 42.374 für 42.zip wird ein Maximum bei N = 250 gefunden. Diese 250 Dateien erfordern 21.195 Byte Overhead, sodass 21.179 Byte für den Kernel übrig bleiben. Ein Kernel dieser Größe wird in 21.841.249 Bytes (1031,3 zu 1 Verhältnis) entpackt. 250 Kopien des entpackten Kernels sowie einige zitierte Header lokaler Dateien ergeben eine entpackte Gesamtausgabe von 5.461.307.620 Bytes und ein Komprimierungsverhältnis von 129.000.

• zbsm.zip 42 kB → 5,5 GB

  zipbomb --mode = quote_overlap --num-files = 250 --compressed-size = 21179> zbsm.zip 

Die Optimierung hat zu einer nahezu gleichmäßigen Verteilung des Speicherplatzes zwischen dem Kernel und den Dateiköpfen geführt. Dies ist kein Zufall. Betrachten Sie ein vereinfachtes Modell einer Zitierkonstruktion mit Überlappung. In einem vereinfachten Modell ignorieren wir Dateinamen sowie eine leichte Vergrößerung der Ausgabedatei aufgrund der Angabe der Header lokaler Dateien. Die Analyse des vereinfachten Modells zeigt, dass die optimale Verteilung zwischen dem Kernel und den Dateikopfzeilen ungefähr gleichmäßig ist und die Ausgabegröße mit der optimalen Verteilung in Abhängigkeit von der Größe der Eingabe quadratisch wächst.

Definition einiger Konstanten und Variablen:


Sei H (N) das Volumen des Overheads für Header für N Dateien. Sehen Sie sich die Tabelle an, um die Essenz der Formel zu verstehen.

$$

$$H (N) = N ≤ (CDH + LFH) + (N - 1) ≤ Q$$

Für den Kernel bleiben X - H (N) Stellen übrig. Die gesamte entpackte Größe S _X (N) entspricht der Größe von N Kopien des entpackten Kernels mit dem Verhältnis C (in diesem vereinfachten Modell ignorieren wir die geringfügige zusätzliche Erweiterung der genannten lokalen Dateikopfzeilen).

$$$$ Anzeige $$ S_X (N) = (X - H (N)) CN \\ = (X - (N ⋅ (CDH + LFH) + (N - 1) ⋅ Q)) CN \\ = - (CDH + LFH + Q) CN ^ 2 + (X + Q) CN $$ Anzeige $$

S _X (N) ist in Teil N ein Polynom, daher sollte das Maximum dort sein, wo die Ableitung S ' _X (N) gleich Null ist. Wenn wir die Ableitung nehmen und Null finden, erhalten wir N _OPT , die optimale Anzahl von Dateien.

$$$$ Anzeige $$ S'X (N_ {OPT}) = –2 (CDH + LFH + Q) C N_ {OPT} + (X + Q) C \\ 0 = –2 (CDH + LFH + Q) C. N_ {OPT} + (X + Q) C \\ N_ {OPT} = (X + Q) / (CDH + LFH + Q) / 2 $$ Anzeige $$

H (N _OPT ) bietet den optimalen Platz zum Platzieren von Datei-Headern. Es ist unabhängig von CDH, LFH und C und liegt nahe bei X / 2 .

$$$$ Anzeige $$ H (N_ {OPT}) = N_ {OPT} ⋅ (CDH + LFH) + (N_ {OPT} - 1) ⋅ Q \\ = (X - Q) / 2 $$ Anzeige $$

S _X (N _OPT ) - Gesamtgröße beim Auspacken bei optimaler Verteilung. Daraus ergibt sich, dass die Größe der Ausgabe mit zunehmenden Eingabedaten quadratisch zunimmt.

$$

$$S_X (N_ {OPT}) = (X + Q) ^ 2C / (CDH + LFH + Q) / 4$$

Wenn Sie die Größe der Zip-Datei erhöhen, werden wir am Ende an die Grenzen des Zip-Formats stoßen: Das Archiv kann nicht mehr als 2 ¹⁶ -1-Dateien mit einer Größe von jeweils nicht mehr als 2 ³² -1 Bytes enthalten. Schlimmer noch, einige Implementierungen verwenden Maximalwerte als Indikator für das Vorhandensein von 64-Bit-Erweiterungen , sodass unsere Grenzwerte tatsächlich 2 ¹⁶ −2 und 2 ³² −2 sind. Es kommt vor, dass beim ersten Mal die Größe einer unkomprimierten Datei begrenzt wird. Bei einer Zip-Dateigröße von 8 319 377 Bytes ergibt die naive Optimierung die Anzahl der Dateien 47 837 und eine maximale Datei von 2 ³² +311 Bytes.

(Eigentlich ist alles etwas komplizierter, da die genauen Grenzen von der Implementierung abhängen. Die Python-Zip-Datei ignoriert die Anzahl der Dateien. Mit Archiv / Zip in Go können Sie die Anzahl der Dateien erhöhen, bis sie den unteren 16 Bit entsprechen. Aus Gründen der allgemeinen Kompatibilität müssen wir uns jedoch daran halten festgelegte Grenzen).

Wenn wir die N- oder Kernelgröße nicht unendlich erhöhen können, möchten wir das maximale Komprimierungsverhältnis innerhalb des Zip-Formats ermitteln. Sie müssen den Kernel mit der maximalen Anzahl von Dateien so groß wie möglich machen. Trotz der Tatsache, dass wir keine annähernd gleichmäßige Trennung zwischen dem Kernel und den Datei-Headern mehr aufrechterhalten können, erhöht jede hinzugefügte Datei das Komprimierungsverhältnis - nur nicht so schnell, als ob wir den Kernel weiter vergrößern könnten. Tatsächlich müssen wir beim Hinzufügen von Dateien die Größe des Kernels reduzieren , um Speicherplatz für die maximale Dateigröße freizugeben, die mit jeder hinzugefügten Datei leicht wächst.

Der Plan führt zu einem Zip-Archiv mit 2 ^{16 -} 2 Dateien und einem Kernel, der in 2 ^{32 -} 2 178 825 Bytes entpackt wird. Die Dateien werden zu Beginn des Zip-Archivs größer - die erste und größte Datei wird in 2 ^{32 -} 56 Byte entpackt. Dies ist so nah wie möglich an den groben Ausgabeparametern von mass_deflate - die Codierung der letzten 54 Bytes kostet mehr als ihre Größe (die gesamte Zip-Datei hat ein Komprimierungsverhältnis von 28 Millionen und die letzten 54 Bytes erhalten maximal 54 ⋅ 10 ³² ⋅ ( 2 ¹⁶ - 2) ≈ 36? 5 Millionen Bytes, dies hilft also nur, wenn 54 Bytes in ein Byte codiert werden können - und ich konnte nicht weniger als zwei codieren. Wenn Sie also 54 Bytes nicht in 1 Byte codieren können, es reduziert nur das Kompressionsverhältnis). Die Ausgabegröße dieser Zip-Bombe beträgt 281.395.456.244.934 Byte, 99,97% des theoretischen Maximums (2 ³² - 1) × (2 ¹⁶ - 1). Eine signifikante Verbesserung des Kompressionsverhältnisses kann nur durch Verringern der Größe des Eingangssignals und nicht durch Erhöhen des Ausgangs erreicht werden.

• zblg.zip 10 MB → 281 TB

  zipbomb --mode = quote_overlap --num-files = 65534 --max-uncpressed-size = 4292788525> zblg.zip 

Effizientes CRC-32-Computing

Unter den Metadaten im Header des zentralen Verzeichnisses und im Header der lokalen Datei befindet sich eine Prüfsumme der unkomprimierten Dateidaten - CRC-32 . Dies stellt ein Problem dar, da die Anzahl der CRC-32-Berechnungen für jede Datei proportional zu ihrer Größe ist, die standardmäßig sehr groß ist (schließlich handelt es sich um eine Zip-Bombe). Wir würden es vorziehen, Arbeiten auszuführen, die mindestens proportional zur Größe des Archivs sind. Zwei Faktoren sprechen für uns: Alle Dateien haben einen gemeinsamen Kern, und ein unkomprimierter Kernel ist eine Folge von wiederholten Bytes. Stellen Sie sich CRC-32 als Matrixprodukt vor - so können wir nicht nur die Prüfsumme des Kernels schnell berechnen, sondern auch die Berechnungen zwischen Dateien wiederverwenden. Die in diesem Abschnitt beschriebene Methode ist eine kleine Erweiterung der Funktion crc32_combine in zlib, die Mark Adler hier erläutert.

CRC-32 kann als Zustandsmaschine modelliert werden, wobei ein 32-Bit-Zustandsregister für jedes Eingangsbit aktualisiert wird. Die grundlegenden Aktualisierungsoperationen für die Bits 0 und 1 sind:

 uint32 crc32_update_0(uint32 state) { // Shift out the least significant bit. bit b = state & 1; state = state >> 1; // If the shifted-out bit was 1, XOR with the CRC-32 constant. if (b == 1) state = state ^ 0xedb88320; return state; } uint32 crc32_update_1(uint32 state) { // Do as for a 0 bit, then XOR with the CRC-32 constant. return crc32_update_0(state) ^ 0xedb88320; } 

Wenn Sie das Zustandsregister als binären Vektor mit 32 Elementen darstellen und XOR für Addition und Multiplikation verwenden, ist crc32_update_0 eine lineare Abbildung . es kann als Multiplikation mit einer binären 32 × 32- Übergangsmatrix dargestellt werden . Um zu verstehen, warum, beachten Sie, dass beim Multiplizieren einer Matrix mit einem Vektor einfach die Spalten der Matrix addiert werden, nachdem jede Spalte mit dem entsprechenden Element des Vektors multipliziert wurde. Der Verschiebungsoperationszustand state >> 1 nimmt einfach jedes Bit i des Zustandsvektors und multipliziert es mit einem Vektor, der überall Null ist, mit Ausnahme von Bit i - 1 (Nummerierung der Bits von rechts nach links). Relativ gesehen tritt der endgültige XOR- state ^ 0xedb88320 nur auf, wenn Bit b gleich eins ist. Dies kann als erste Multiplikation von b mit 0xedb88320 und dann als XORing in diesen Zustand dargestellt werden.

Außerdem ist crc32_update_1 nur eine crc32_update_0 plus (XOR) crc32_update_0 .Dies führt zu crc32_update_1 einer affinen Transformation : Matrixmultiplikation, gefolgt von Abbildung (d. H. Vektoraddition). Wir können uns eine Matrixmultiplikation und -abbildung in einem Schritt vorstellen, wenn wir die Größe der Transformationsmatrix auf 33 × 33 erhöhen und dem Zustandsvektor ein zusätzliches Element hinzufügen, das immer 1 ist (diese Darstellung wird als homogene Koordinaten bezeichnet ).


Die Transformationsmatrizen sind 33 × 33 M ₀ und M ₁ , die die durch die Bits 0 bzw. 1 vorgenommene CRC-32-Zustandsänderung berechnen. Spaltenvektoren werden mit dem höchstwertigen Bit unten gespeichert: Wenn Sie die erste Spalte von unten nach oben lesen, sehen Sie die Polynomkonstante CRC-32 edb8832016 = 111 0 11 0 110 111 000 1 00000 11 00 1 00000 ₂ . Diese beiden Matrizen unterscheiden sich nur in der letzten Spalte, die den Translationsvektor in homogenen Koordinaten darstellt. In M _{0 ist die} Translation Null und in M _{1 ist es} edb88320 ₁₆ , die Polynomkonstante ist CRC-32. Die Einheiten sind unmittelbar oberhalb der diagonalen Status der Operationstate >> 1

Beide Operationencrc32_update_0undcrc32_update_1kann durch die Übergangsmatrix von 33 × 33 dargestellt werden. Die Matrizen M ₀ und M ₁ sind gezeigt.. Der Vorteil der Matrixdarstellung besteht darin, dass Matrizen multipliziert werden können. Angenommen, wir möchten eine Statusänderung sehen, die durch Verarbeiten eines ASCII-Zeichens 'a' erfolgt, dessen binäre Darstellung 01100001 _{2 ist} . Wir können uns die kumulative Änderung des Zustands des CRC-32 dieser acht Bits in einer Transformationsmatrix vorstellen:

$$

$$M_a = M_0 M_1 M_1 M_0 M_0 M_0 M_0 M_1$$

Und wir können uns eine Änderung des Zustands einer Zeile vorstellen, die 'a' wiederholt, indem viele Kopien von M _a multipliziert werden, wodurch die Matrix zu einer Potenz erhöht wird. Wir können diese schnell mit tun schnell Potenzierung Algorithmus , der die M zu berechnen erlaubt ⁿ log nur ₂ ⁿ Schritte. Hier ist zum Beispiel eine Matrix zum Ändern des Status einer Zeichenfolge mit 9 Zeichen 'a':

$$

$$(M_a)^9 = M_a M_a M_a M_a M_a M_a M_a M_a M_a\\ = (M_a M_a M_a M_a)^2 M_a\\ = ((M_a M_a)^2)^2 M_a\\ = (((M_a)^2)^2)^2 M_a$$

Der Matrix-Schnellmultiplikationsalgorithmus ist nützlich für die Berechnung des M- _Kernels , einer Matrix für einen nicht komprimierten Kernel, da der Kernel eine Folge von wiederholten Bytes ist. Um die CRC-32-Prüfsumme aus der Matrix zu erhalten, multiplizieren Sie die Matrix mit dem Nullvektor (der Nullvektor hat einheitliche Koordinaten, dh 32 Nullen, und dann die Einheit; hier lassen wir die geringfügige Komplikation der Vor- und Nachbearbeitung der Prüfsumme weg, um die Übereinstimmung zu überprüfen). Um die Prüfsumme für jede Datei zu berechnen, arbeiten wir in die entgegengesetzte Richtung. Wir beginnen mit einem initialisierten M: M = _{der Kern} . Die Kernel-Prüfsumme ist auch die Prüfsumme der endgültigen Datei N , also multiplizieren wir M.ein Nullvektor und speichert die empfangene Prüfsumme in der CDH _N und LFH _N . Datendatei N-1 sind die gleichen wie Dateidatendatei N , aber mit einem hinzugefügten Präfix LFH _N . Deshalb berechnen wir$$M L F H N , Zustandsänderungsmatrix für LFH_Nund Aktualisierung$M_{L{FH_N}}$$$$M := M M_{L{FH_N}}$ .Nun repräsentiert M die kumulative Zustandsänderung durch Verarbeitung von LFH _N hinter dem Kern. Wir berechnen die Prüfsumme für die Datei N - 1 und multiplizieren M erneut mit dem Nullvektor. Wir setzen den Vorgang fort, indem wir Statusänderungsmatrizen in M akkumulieren, bis alle Dateien verarbeitet sind.

Erweiterung: Zip64

Früher hatten wir das Problem der Erweiterung aufgrund von Einschränkungen des Zip-Formats - es war unmöglich, mehr als 281 TB auszugeben, unabhängig davon, wie intelligent die Zip-Datei gepackt war. Sie können diese Grenzen mit Zip64 überschreiten, eine Erweiterung im Zip-Format, die die Größe einiger Header-Felder auf 64 Bit erhöht. Die Unterstützung für Zip64 ist keineswegs universell, aber eine der am häufigsten implementierten Erweiterungen. Das Komprimierungsverhältnis bewirkt, dass Zip64 die Größe des Headers des zentralen Verzeichnisses von 46 auf 58 Bytes und die Größe des Headers des lokalen Verzeichnisses von 30 auf 50 Bytes erhöht. Wenn wir uns die Formel für den optimalen Expansionskoeffizienten in einem vereinfachten Modell ansehen, sehen wir, dass die Zip-Bombe im Zip64-Format immer noch quadratisch wächst, aber aufgrund des größeren Nenners langsamer - dies ist in der folgenden Abbildung dargestellt. Aufgrund des Kompatibilitätsverlusts und der Wachstumsverzögerung entfernen wir fast alle Einschränkungen der Dateigröße.

Angenommen, wir brauchen eine Zip-Bombe, die sich auf 4.5 PB erweitert, wie 42.zip. Wie groß sollte das Archiv sein? Bei Verwendung der binären Suche stellen wir fest, dass die Mindestgröße einer solchen Datei 46 MB beträgt.

• zbxl.zip 46 MB → 4,5 PB (Zip64, weniger kompatibel)

 zipbomb --mode = quote_overlap --num-files = 190023 --compressed-size = 22982788 --zip64> zbxl.zip 

4,5 Petabyte - ungefähr die gleiche Datenmenge wurde vom Event Horizon Telescope für das erste Bild eines Schwarzen Lochs aufgezeichnet : Racks und Racks mit Festplatten im Rechenzentrum.

Bei Zip64 ist es fast nicht interessant, das maximale Komprimierungsverhältnis zu berücksichtigen, da wir einfach die Größe der Zip-Datei und das Komprimierungsverhältnis damit weiter erhöhen können, bis selbst die komprimierte Zip-Datei unzulässig wird. Ein interessanter Schwellenwert sind jedoch 2 ⁶⁴ Byte (18 EB oder 16 EiB) - so viele Daten passen nicht auf die meisten Dateisysteme. Bei der binären Suche wird die kleinste Zip-Bombe gefunden, die mindestens genauso viel Ausgabe erzeugt: Sie enthält 12 Millionen Dateien und einen komprimierten Kern von 1,5 GB. Die Gesamtgröße der Zip-Datei beträgt 2,9 GB und wird in 2 ⁶⁴ entpackt+11 727 895 877 Bytes mit einem Komprimierungsverhältnis von mehr als 6,2 Milliarden zu eins. Ich habe diese Datei nicht zum Download hochgeladen, aber Sie können sie mithilfe des Quellcodes selbst generieren . Er hat Dateien von einer solchen Größe, dass sogar ein Fehler in Info-ZIP UnZip 6.0 aufgedeckt wurde.

 zipbomb --mode = quote_overlap --num-files = 12056313 --compressed-size = 1482284040 --zip64> zbxxl.zip 

Erweiterung: bzip2

DEFLATE ist der häufigste Komprimierungsalgorithmus für das Zip-Format, dies ist jedoch nur eine von vielen Optionen. Der wahrscheinlich zweithäufigste Algorithmus ist bzip2 . Obwohl es nicht so kompatibel ist wie DEFLATE. Theoretisch beträgt in bzip2 das maximale Kompressionsverhältnis etwa 1,4 Millionen zu eins, was eine dichtere Packung des Kerns ermöglicht.

bzip2 codiert zuerst die "Lauflängencodierung", wodurch die Zeichenfolgenlänge für sich wiederholende Bytes um das 51-fache reduziert wird. Dann werden die Daten in 900-KB-Blöcke unterteilt und jeder Block wird separat komprimiert. Theoretisch kann ein Block bis zu 32 Bytes komprimieren. 900 000 × 51/32 = 1 434 375. Ist

bzip2 eine effektivere Bombe, wenn man den Kompatibilitätsverlust ignoriert?

Ja - aber nur für kleine Dateien. Das Problem ist, dass es in bzip2 nichts Vergleichbares zu den unkomprimierten DEFLATE-Blöcken gibt, mit denen wir die Header lokaler Dateien zitiert haben. Daher ist es unmöglich, Dateien zu überlappen und den Kernel wiederzuverwenden. Für jede Datei müssen Sie eine eigene Kopie schreiben, sodass das Gesamtkomprimierungsverhältnis nicht besser ist als das Verhältnis für eine einzelne Datei. In der folgenden Grafik sehen wir, dass bzip2 ohne Überlappung DEFLATE nur für Dateien mit einer Größe von etwa Megabyte überlegen ist.

Es gibt nur Hoffnung auf ein alternatives Mittel zum Zitieren von Headern in bzip2, das im nächsten Abschnitt behandelt wird. Wenn Sie wissen, dass ein bestimmter Zip-Parser bzip2 und unterstütztWenn nicht übereinstimmende Dateinamen berücksichtigt werden, können Sie das vollständige Überlappungskonstrukt verwenden, das nicht in Anführungszeichen gesetzt werden muss.


Vergleich des Kompressionsverhältnisses verschiedener Reißverschlussbomben. Achten Sie auf die logarithmische Achse. Jedes Design wird mit und ohne Zip64 gezeigt. Strukturen ohne Überlappung weisen eine lineare Wachstumsrate auf, die sich aus dem konstanten Verhältnis der Achsen ergibt. Der vertikale Versatz des bzip2-Diagramms bedeutet, dass das Komprimierungsverhältnis von bzip2 etwa tausendmal höher ist als das von DEFLATE. Die genannten DEFLATE-Konstrukte weisen eine quadratische Wachstumsrate auf, was durch eine Neigung zu den 2: 1-Achsen belegt wird. Die Zip64-Variante ist etwas weniger effektiv, erlaubt aber mehr als 281 TB. Diagramme für bzip2 mit Anführungszeichen durch ein zusätzliches Feld wechseln von quadratisch zu linear, wenn entweder die maximale Dateigröße erreicht ist (2 ³²⁾ −2 Bytes) oder die maximal zulässige Anzahl von Dateien

Erweiterung: Zitieren durch ein zusätzliches Feld

Bisher haben wir die DEFLATE-Funktion verwendet, um die Header lokaler Dateien in Anführungszeichen zu setzen, und wir haben gerade gesehen, dass dieser Trick in bzip2 nicht funktioniert. Es gibt jedoch eine alternative, etwas eingeschränktere Zitiermethode, die nur Funktionen im Zip-Format verwendet und vom Komprimierungsalgorithmus unabhängig ist.

Am Ende der Header-Struktur der lokalen Datei befindet sich ein zusätzliches Feld mit variabler Länge zum Speichern von Informationen, die nicht in die üblichen Header-Felder passen ( APPNOTE.TXT, Abschnitt 4.3.7)) Zusätzliche Informationen können beispielsweise einen Zeitstempel oder eine UID / GID von Unix enthalten. Zip64-Informationen werden auch in einem zusätzlichen Feld gespeichert. Ein zusätzliches Feld wird als Längenwertstruktur dargestellt. Wenn Sie die Länge erhöhen, ohne einen Wert hinzuzufügen, enthält das zusätzliche Feld das, was dahinter in der Zip-Datei steht, nämlich den nächsten Header der lokalen Datei. Mit dieser Methode kann jeder Header der lokalen Datei die folgenden Header in Anführungszeichen setzen und sie in ein eigenes zusätzliches Feld einschließen. Gegenüber DEFLATE gibt es drei Vorteile:

1. Das Zitieren durch ein zusätzliches Feld erfordert nur 4 Bytes, nicht 5, wodurch mehr Platz für den Kernel bleibt.
   
2. Aufgrund der Einschränkungen des Zip-Formats wird die Dateigröße nicht erhöht, was einen größeren Kernel bedeutet.
   
3. Es bietet Zitate in bzip2.

Trotz dieser Vorteile ist das Zitieren durch zusätzliche Felder weniger flexibel. Dies ist keine Kette wie in DEFLATE: Jede Überschrift einer lokalen Datei sollte nicht nur die unmittelbar folgende Überschrift enthalten, sondern auch alle nachfolgenden Überschriften. Zusätzliche Felder werden vergrößert, wenn Sie sich dem Anfang der Zip-Datei nähern. Da die maximale Feldlänge 2 ^{16 -} 1 Byte beträgt , können nur bis zu 1808 lokale Dateikopfzeilen (oder 1170 in Zip64) in Anführungszeichen gesetzt werden, vorausgesetzt, die Namen werden wie erwartet zugewiesen(Im Fall von DEFLATE können Sie ein zusätzliches Feld verwenden, um die ersten (kürzesten) Header lokaler Dateien in Anführungszeichen zu setzen und dann für den Rest zu DEFLATE zu wechseln.) Ein weiteres Problem: Um der internen Datenstruktur des zusätzlichen Feldes zu entsprechen, muss ein 16-Bit-Tag für den Typ ( APPNOTE.TXT, Abschnitt 4.5.2 ) vor den Zitierdaten ausgewählt werden. Wir möchten ein Typ-Tag auswählen, das dazu führt, dass Parser die Daten in Anführungszeichen ignorieren, anstatt zu versuchen, sie als aussagekräftige Metadaten zu interpretieren. Zip-Parser sollten Tags eines unbekannten Typs ignorieren, damit wir Tags nach dem Zufallsprinzip auswählen können. Es besteht jedoch das Risiko, dass in Zukunft einige Tags die Kompatibilität des Designs verletzen.

Das vorherige Diagramm zeigt die Möglichkeit, zusätzliche Felder in bzip2, c und ohne Zip64 zu verwenden. In beiden Diagrammen gibt es einen Wendepunkt, an dem das Wachstum von quadratisch nach linear verläuft. Ohne Zip64 geschieht dies, wenn die maximale Größe der unkomprimierten Datei erreicht ist (2 ³²−2 Bytes); Dann können Sie nur die Anzahl der Dateien erhöhen, nicht jedoch deren Größe. Das Diagramm endet vollständig, wenn die Anzahl der Dateien 1809 erreicht. In einem zusätzlichen Feld ist nicht mehr genügend Speicherplatz vorhanden, um zusätzliche Header anzugeben. Mit Zip64 tritt bei 1171 Dateien ein Bruch auf, wonach nur die Dateigröße erhöht werden kann, nicht jedoch deren Anzahl. Ein zusätzliches Feld hilft bei DEFLATE, aber der Unterschied ist so gering, dass er optisch nicht erkennbar ist. Es erhöht das Komprimierungsverhältnis von zbsm.zip um 1,2%; zblg.zip um 0,019%; und zbxl.zip um 0,0025%.

Die Diskussion

Bei ihrer Arbeit zu diesem Thema verwenden Pletz und Kollegen Dateiüberlappungen, um ein sich fast selbst replizierendes Zip-Archiv zu erstellen. Die Dateiüberlappung selbst wurde früher von Ginvael Coldwind vorgeschlagen (Folie 47).

Wir haben ein Design einer Reißverschlussbombe mit einer Angebotsüberlappung unter Berücksichtigung der Kompatibilität entwickelt - eine Reihe von Unterschieden bei den Implementierungen, von denen einige in der folgenden Tabelle aufgeführt sind. Das resultierende Design ist mit Zip-Parsern kompatibel, die auf die übliche Weise funktionieren, dh zuerst das zentrale Verzeichnis überprüfen und es als Index für Dateien verwenden. Darunter ein einzigartiger Zip-Parser von Naildie automatisch aus der formalen Grammatik generiert wird. Das Design ist jedoch nicht mit "Streaming" -Parsern kompatibel, die die Zip-Datei von Anfang bis Ende in einem Durchgang analysieren, ohne zuerst das zentrale Verzeichnis zu lesen. Streaming-Parser erlauben naturgemäß nicht, dass sich Dateien in irgendeiner Weise überlappen. Höchstwahrscheinlich wird nur die erste Datei extrahiert. Darüber hinaus können sie sogar einen Fehler auslösen , wie dies bei sunzip der Fall ist , bei dem das zentrale Verzeichnis am Ende analysiert und die Konsistenz mit den Headern der bereits gesehenen lokalen Dateien überprüft wird.

Wenn Sie möchten, dass die extrahierten Dateien mit einem bestimmten Präfix beginnen, das sich von den Header-Bytes der lokalen Datei unterscheidet, können Sie einen DEFLATE-Block vor dem unkomprimierten Block einfügen, den der folgende Header zitiert. Nicht jede Datei im Zip-Archiv sollte an der Erstellung der Bombe beteiligt sein: Sie können bei Bedarf normale Dateien in das Archiv aufnehmen, um einem bestimmten Format zu entsprechen ( --templatefür diesen Anwendungsfall enthält der Quellcode einen Parameter ). Viele Formate verwenden zip als Container, z. B. Java JAR-Dokumente, Android APK und LibreOffice.

Pdfin vielerlei Hinsicht ähnlich wie zip. Am Ende der Datei befindet sich eine Querverweistabelle, die auf vorherige Objekte verweist, und sie unterstützt die Komprimierung von Objekten über den FlateDecode-Filter. Ich habe es nicht versucht, aber Sie können die Idee des Zitierens mit Überlappung verwenden, um eine PDF-Bombe zu erstellen. Vielleicht müssen Sie hier nicht einmal hart arbeiten: binaryhax0r schreibt in einem Blog-Beitrag, dass Sie einfach mehrere FlateDecode-Ebenen für ein Objekt angeben können, wonach das Erstellen einer PDF-Bombe trivial wird.

Das Definieren einer bestimmten Klasse von Zip-Bomben, die in diesem Artikel beschrieben wird, ist einfach: Suchen Sie einfach die überlappenden Dateien. Mark Adler hat einen Patch geschriebenfür Unzip Info-ZIP, das genau das tut. Im Allgemeinen schützt das Blockieren überlappender Dateien jedoch nicht vor allen Klassen von Zip-Bomben. Es ist schwierig, im Voraus vorherzusagen, ob es sich bei der Datei um eine Zip-Bombe handelt oder nicht, wenn Sie keine genauen Kenntnisse über die internen Komponenten der Parser haben, die zur Analyse verwendet werden. Das Betrachten der Header und das Summieren der Felder "unkomprimierte Größe" aller Dateien funktioniert nicht , da der Wert in den Headern möglicherweise nicht mit der tatsächlichen unkomprimierten Größe übereinstimmt (siehe Kompatibilitätstabelle in der Zeile "Erlaubt, dass die Datei zu klein ist"). Zum zuverlässigen Schutz vor Zip-Bomben gehören Zeit-, Speicher- und Speicherplatzbeschränkungen im Zip-Parser während des Betriebs. Analysieren Sie Zip-Dateien wie komplexe Vorgänge mit nicht vertrauenswürdigen Daten mit Vorsicht.


zip-, , zip-. DEFLATE Zip64, , CRC 32- 16- .

Danksagung

Vielen Dank an Mark Adler , Russ Cox , Brandon Enright , Marek Maykovsky , Josh Wolfe und die Rezensenten von USENIX WOOT 2019 für die Kommentare zum Entwurf dieses Artikels. Kaolan McNamara untersuchte die Auswirkungen von Reißverschlussbomben auf die Sicherheit von LibreOffice.

Eine Version dieses Artikels wurde für den USENIX WOOT 2019 Workshop vorbereitet . Quellcode ist verfügbar. Artefakte für die Präsentation auf dem Workshop befinden sich in der Datei zipbomb-woot19.zip .

Haben Sie ein System gefunden, das eine der Bomben abwirft? Haben Bomben Ihnen geholfen, einen Fehler zu finden oder Geld in einem Fehlersuchprogramm zu verdienen? Lassen Sie es mich wissen, ich werde versuchen, es hier zu erwähnen.

LibreOffice 6.1.5.2

Nach dem Umbenennen von zblg.zip in zblg.odt oder zblg.docx erstellt und löscht LibreOffice eine Reihe temporärer Dateien mit ca. 4 GB und versucht, das Dateiformat zu ermitteln. Letztendlich beendet er dies und löscht die temporären Dateien, sobald sie eintreffen, sodass die Zip-Bombe nur ein temporäres DoS verursacht, ohne die Festplatte zu füllen. Kaolan McNamara hat meine Fehlermeldung beantwortet.

Mozilla Addons-Server 2019.06.06

Ich habe Zip-Bomben gegen die lokale Addons-Server-Installation ausprobiert, die Teil der Software addons.mozilla.org ist. Das System handhabt die Bombe elegant und legt ein Zeitlimit von 110 Sekunden für das Extrahieren von Dateien fest. Die Zip-Bombe dehnt sich schnell aus, soweit die Festplatte dies bis zu diesem Zeitlimit zulässt. Dann wird der Prozess abgebrochen und die entpackten Dateien werden schließlich automatisch bereinigt.

UnZip 6.0

Mark Adler hat einen Patch für UnZip geschrieben, um diese Klasse von Zip-Bomben zu erkennen.

5. Juli 2019: Ich habe festgestellt, dass CVE-2019-13232 UnZip zugewiesen wurde. Persönlich würde ich argumentieren, dass die Fähigkeit / Unfähigkeit von UnZip (oder einem beliebigen Zip-Parser), diese Art von Zip-Bombe zu verarbeiten, notwendigerweise eine Sicherheitslücke oder sogar ein Fehler ist. Dies ist eine natürliche Implementierung, die nicht gegen die Spezifikation verstößt, was soll ich sagen. Der Bombentyp in diesem Artikel ist nur ein Typ, und es gibt viele andere Möglichkeiten, wie Sie einen Zip-Parser rätseln können. Wie oben erwähnt, sollten Sie nicht versuchen, jeden einzelnen bekannten Angriff aufzulisten, zu erkennen und zu blockieren, wenn Sie sich vor Angriffen zur Erschöpfung der Ressourcen schützen möchten. Vielmehr müssen externe Zeit- und andere Ressourcenbeschränkungen festgelegt werden, damit der Parser nicht in eine solche Situation gerät, unabhängig davon, auf welche Art von Angriff er gestoßen ist. Es ist nichts Falsches daran, bestimmte Designs als Optimierung des ersten Durchgangs zu erkennen und abzulehnen.aber man kann dort nicht aufhören. Ihr System ist wahrscheinlich immer noch anfällig, es sei denn, Sie isolieren und beschränken Vorgänge mit nicht vertrauenswürdigen Daten. Betrachten Sie die Analogie zum Cross-Site-Scripting in HTML: Der richtige Schutz besteht nicht darin, bestimmte Bytes herauszufiltern, die als Code interpretiert werden können, sondern alles richtig zu vermeiden.

Antiviren-Engines

Der Twitter-Benutzer @TVqQAAMAAAAEAAA berichtet : "McAfee Antivirus auf meinem Testcomputer ist gerade explodiert." Ich habe es nicht selbst getestet und ich habe keine Details wie die Versionsnummer.

Tavis Ormandi gibt an, dass VirusTotal eine Reihe von Zeitüberschreitungen für zblg.zip aufweist ( Screenshot vom 6. Juni 2019 ): AhnLab-V3, ClamAV, DrWeb, Endspiel, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, McAfee-GW -Edition, Panda, Qihoo-360, Sophos ML, VBA32. Ergebnisse für zbsm.zip ( Screenshot vom 6. Juni 2019) sind ähnlich, aber mit einem anderen Satz von Timeout-Engines: Baido, Bkav, ClamAV, CMC, DrWeb, Endspiel, ESET-NOD32, F-Secure, GData, Kingsoft, McAfee-GW-Edition, NANO-Antivirus, Acronis. Interessanterweise gibt es in den Ergebnissen von zbxl.zip keine Zeitüberschreitungen ( Screenshot vom 6. Juni 2019 ). Vielleicht unterstützen einige Antivirenprogramme Zip64 nicht? Mehrere Engines erkennen Dateien als eine Art „Kompressionsbombe“. Es ist interessant zu sehen, ob sie dies auch weiterhin tun, wenn geringfügige Änderungen vorgenommen werden, z. B. das Ändern von Dateinamen oder das Hinzufügen eines ASCII-Präfixes zu jeder Datei.

Schlusserklärung

Es ist Zeit, Facebook ein Ende zu setzen. Dies ist kein neutraler Job für Sie: Jeden Tag, wenn Sie zur Arbeit kommen, machen Sie etwas falsch. Wenn Sie ein Facebook-Konto haben, löschen Sie es. Wenn Sie auf Facebook arbeiten, werden Sie entlassen.

Und vergessen Sie nicht, dass die Nationale Sicherheitsagentur zerstört werden muss.