L 'article montre comment créer une bombe zip non récursive qui fournit un degré élevé de compression en chevauchant des fichiers à l' intérieur d 'un conteneur zip. «Non récursif» signifie qu'il ne dépend pas des décompresseurs décompressant les fichiers intégrés dans les archives zip: il n'y a qu'un seul tour. La taille de sortie augmente de façon quadratique à partir de l'entrée, atteignant un taux de compression de plus de 28 millions (10 Mo → 281 To) dans le format zip. Une extension supplémentaire est possible avec des extensions 64 bits. La conception utilise uniquement l'algorithme de compression DEFLATE le plus courant et est compatible avec la plupart des analyseurs zip.

• zbsm.zip 42 ko → 5,5 Go
  
• zblg.zip 10 Mo → 281 To
  
• zbxl.zip 46 Mo → 4,5 PB (Zip64, moins compatible avec les analyseurs)

Code source:

  git clone https://www.bamsoftware.com/git/zipbomb.git 

zipbomb-20190702.zip

Données et source d'illustrations:

  git clone https://www.bamsoftware.com/git/zipbomb-paper.git 

<sub>* Il existe deux versions de 42.zip: les anciens 42 374 octets et les nouveaux 42 428 octets. La différence est que le nouveau nécessite un mot de passe avant de déballer. Nous ne comparons qu'avec l'ancienne version. Voici une copie du fichier si vous en avez besoin: 42.zip .

** Je voudrais connaître et indiquer l'auteur de 42.zip, mais je ne l'ai pas trouvé - faites-moi savoir si vous avez des informations.</sub>

Les bombes zip doivent surmonter le fait que l'algorithme de compression DEFLATE le plus souvent pris en charge par les analyseurs ne peut pas dépasser le taux de compression de 1032 à 1. Pour cette raison, les bombes zip reposent généralement sur la décompression récursive en insérant des fichiers zip dans des fichiers zip pour obtenir un rapport supplémentaire 1032 avec chaque couche. Mais l'astuce ne fonctionne que dans les implémentations qui décompressent récursivement, et la plupart ne le font pas. La bombe 42.zip la plus célèbre se développe à un formidable 4,5 PB si les six couches sont récursivement déballées, mais sur la couche supérieure, elle a 0,6 Mo. Les tyroliennes, comme celles de Cox et Ellingsen , donnent une copie d'eux-mêmes et, par conséquent, se développent indéfiniment lors du déballage récursif. Mais ils sont également complètement sûrs lors du déballage une fois.

Cet article montre comment créer une bombe zip non récursive, dont le taux de compression dépasse la limite DEFLATE de 1032. Il fonctionne en chevauchant les fichiers à l'intérieur d'un conteneur zip pour référencer le «noyau» de données hautement compressées dans plusieurs fichiers sans faire plusieurs copies. La taille de sortie de la bombe zip croît de façon quadratique par rapport à la taille d'entrée; c'est-à-dire que le taux de compression s'améliore avec l'augmentation de la taille de la bombe. La conception dépend des fonctionnalités de zip et DEFLATE: elle ne peut pas être transférée directement vers d'autres formats de fichiers ou algorithmes de compression. La bombe est compatible avec la plupart des analyseurs zip, à l'exception de ceux en "streaming", qui analysent les fichiers en une seule fois sans vérifier le répertoire central du fichier zip. Nous essayons d'équilibrer deux objectifs contradictoires:

• Augmentez le taux de compression. Nous définissons le taux de compression comme la somme des tailles de tous les fichiers de l'archive divisée par la taille du fichier zip lui-même. Il ne prend pas en compte les noms de fichiers ou autres métadonnées de système de fichiers, mais uniquement le contenu.
  
• Gardez la compatibilité. Zip est un format complexe et les analyseurs diffèrent, en particulier dans les situations limites, et les fonctions supplémentaires. N'utilisez pas de techniques qui fonctionnent uniquement avec certains analyseurs. Nous noterons quelques façons d'augmenter l'efficacité d'une bombe zip avec une certaine perte de compatibilité.

Structure du fichier Zip

Le fichier zip se compose d'un répertoire central de liens de fichiers.



Le répertoire central se trouve à la fin du fichier zip. Il s'agit d'une liste d'en- têtes de répertoire central . Chaque en-tête de répertoire central contient des métadonnées pour un seul fichier, comme le nom de fichier et la somme de contrôle CRC-32, ainsi qu'un pointeur vers l'en-tête de fichier local. L'en-tête du répertoire central a une longueur de 46 octets plus la longueur du nom de fichier.

Le fichier se compose de l'en-tête du fichier local, suivi des données du fichier compressé. La longueur de l'en-tête de fichier local est de 30 octets plus la longueur du nom de fichier. Il contient une copie redondante des métadonnées de l'en-tête du répertoire central, ainsi que les tailles des fichiers de données compressés et non compressés qui se trouvent derrière. Zip est un format de conteneur, pas un algorithme de compression. Les données de chaque fichier sont compressées à l'aide de l'algorithme spécifié dans les métadonnées - généralement DEFLATE .

Cette description du format zip omet de nombreux détails qui ne sont pas nécessaires pour comprendre la bombe zip. Pour des informations complètes, voir la section 4.3 APPNOTE.TXT ou «PKZip File Structure» par Florian Buchholz, ou voir le code source .

Une redondance importante et de nombreuses ambiguïtés au format zip ouvrent des possibilités de méfaits de différents types. Une bombe zip n'est que la pointe de l'iceberg. Liens pour plus de lecture:

• «Dix mille pièges de sécurité: un format ZIP», par Ginwael Coldwind
  
• L'analyse syntaxique ambiguë vous permet de masquer les fichiers complémentaires de Firefox du linter et des personnes : ma vulnérabilité sur addons.mozilla.org

Première découverte: chevauchement de fichiers

En compressant une longue chaîne d'octets répétés, nous pouvons créer un noyau de données hautement compressées. Le taux de compression du noyau lui-même ne peut pas dépasser la limite DEFLATE de 1032, nous avons donc besoin d'un moyen de réutiliser le noyau dans de nombreux fichiers, sans en créer une copie séparée dans chaque fichier. Nous pouvons le faire en chevauchant les fichiers: faites en sorte que de nombreux en-têtes du répertoire central pointent vers un seul fichier dont les données sont le cœur.



Prenons un exemple de la façon dont cette conception affecte le taux de compression. Supposons qu'un noyau de 1000 octets soit décompressé dans 1 Mo. Ensuite, le premier mégaoctet de sortie «coûte» 1078 octets de données d'entrée:

• 31 octets pour l'en-tête du fichier local (dont 1 nom de fichier octet)
  
• 47 octets pour l'en-tête du répertoire central (y compris un nom de fichier à 1 octet)
  
• 1000 octets par cœur

Mais chaque 1 Mo de sortie après le premier ne coûte que 47 octets - nous n'avons pas besoin d'un autre en-tête du fichier local ou d'une autre copie du noyau, seulement d'un en-tête supplémentaire du répertoire central. Ainsi, alors que le premier maillon du noyau a un taux de compression de 1 000 000/1 078 ≈ 928, chaque maillon supplémentaire rapproche le coefficient de 1 000 000/47 ≈ 21 277, et un gros noyau soulève le plafond.

Le problème avec cette idée est le manque de compatibilité. Étant donné que de nombreux en-têtes du répertoire central pointent vers un en-tête du fichier local, les métadonnées (en particulier, le nom du fichier) ne peuvent pas être les mêmes pour chaque fichier. Certains analyseurs ne jurent que par cela . Par exemple, Info-ZIP UnZip (le programme de unzip standard sur Unix) récupère les fichiers, mais avec des avertissements:

  $ décompressez overlap.zip
   gonflage: A
 B: incompatibilité du nom de fichier "local" (A),
          continuer avec la version "centrale" du nom de fichier
   gonflage: B
 ... 

Le fichier zip Python lève également une exception :

  $ python3 -m fichier zip -e overlap.zip.
 Traceback (dernier appel le plus récent):
 ...
 __main __. BadZipFile: Le nom de fichier dans le répertoire 'B' et l'en-tête b'A 'diffèrent. 

Ensuite, nous allons voir comment repenser la cohérence des noms de fichiers, tout en préservant la plupart des avantages des fichiers qui se chevauchent.

Deuxième découverte: citer les en-têtes des fichiers locaux

Nous devons séparer les en-têtes des fichiers locaux pour chaque fichier, tout en réutilisant un noyau. La simple combinaison de tous les en-têtes ne fonctionne pas, car l'analyseur zip trouvera l'en-tête du fichier local là où il attend le début du flux DEFLATE. Mais l'idée fonctionnera, avec des changements mineurs. Nous utiliserons la fonction DEFLATE des blocs non compressés pour «citer» les en-têtes des fichiers locaux afin qu'ils semblent faire partie du même flux DEFLATE qui se termine dans le noyau. Chaque en-tête du fichier local (sauf le premier) sera interprété de deux manières: en tant que code (partie de la structure du fichier zip) et en tant que données (partie du contenu du fichier).



Un flux DEFLATE est une séquence de blocs où chaque bloc peut être compressé ou non compressé. Nous ne pensons généralement qu'aux blocs compressés, par exemple, le noyau est un gros bloc compressé. Mais il existe également des fichiers non compressés qui commencent par un en -tête de 5 octets avec un champ de longueur, ce qui signifie simplement: "affiche les n octets suivants mot pour mot." Décompresser un bloc non compressé signifie uniquement supprimer l'en-tête de 5 octets. Les blocs compressés et non compressés peuvent se mélanger librement dans le flux DEFLATE. La sortie est une concaténation des résultats du déballage de tous les blocs dans l'ordre. Le concept de «non compressé» n'a d'importance qu'au niveau DEFLATE; les données des fichiers sont toujours considérées comme «compressées» au niveau zip, quels que soient les blocs utilisés.

La façon la plus simple d'imaginer cette conception est un chevauchement interne, du dernier fichier au premier. Nous commençons par insérer un noyau qui formera la fin du fichier de données pour chaque fichier. Ajoutez l'en-tête du fichier LFH _N local et l'en-tête du répertoire central CDH _N qui pointe vers celui-ci. Définissez le champ de métadonnées «taille compressée» dans LFH _N et CDH _N sur la taille de noyau compressé. Ajoutez maintenant l'en-tête de 5 octets du bloc non compressé (en vert sur le diagramme), dont le champ de longueur est égal à la taille LFH _N. Ajoutez le deuxième en-tête du fichier LFH local _{N -1} et le titre du répertoire central CDH _{N -1} , qui pointe vers lui. Définissez le champ de métadonnées «taille compressée» comme nouvel en-tête pour la taille du noyau compressé plus la taille de l'en-tête de bloc non compressé (5 octets) plus la taille de LFH _N.

Pour le moment, le fichier zip contient deux fichiers avec les noms Y et Z. Voyons ce que l'analyseur verra lors de l'analyse. Supposons que la taille du noyau compressé soit de 1000 octets et la taille LFH _{N de} 31 octets. Nous commençons par CDH _{N -1} et suivons le signe pour LFH _{N -1} . Le nom du premier fichier est Y et la taille compressée de son fichier de données est de 1036 octets. En interprétant les 1036 octets suivants comme un flux DEFLATE, nous rencontrons d'abord un en-tête de 5 octets d'un bloc non compressé qui dit de copier les 31 octets suivants. Nous écrivons les 31 octets suivants, qui sont LFH _N , que nous décompressons et ajoutons au fichier Y. En allant plus loin dans le flux DEFLATE, nous trouvons le bloc compressé (noyau), que nous décompressons dans le fichier Y. Nous avons maintenant atteint la fin des données compressées et terminé avec le fichier Y.

Passant au fichier suivant, nous suivons le pointeur de CDH _N à LFH _N et trouvons un fichier nommé Z avec une taille compressée de 1000 octets. Interprétant ces 1000 octets comme un flux DEFLATE, nous rencontrons immédiatement un bloc compressé (core encore) et le décompressons dans un fichier Z. Nous avons maintenant atteint la fin du fichier final et terminé. Le fichier de sortie Z contient le noyau décompressé; le fichier de sortie Y est le même, mais éventuellement avec un préfixe de 31 octets LFH _N.

Nous terminons la construction en répétant la procédure de citation jusqu'à ce que l'archive zip contienne le nombre de fichiers requis. Chaque nouveau fichier ajoute un en-tête de répertoire central, un en-tête de fichier local et un bloc non compressé pour citer directement à partir de l'en-tête de fichier local suivant. Les données de fichiers compressés sont généralement une chaîne de blocs DEFLATE non compressés (en-têtes de fichiers locaux entre guillemets) suivis d'un noyau compressé. Chaque octet du noyau contribue à environ 1032 N à la taille de sortie, car chaque octet fait partie de tous les N fichiers. Les fichiers de sortie sont également de tailles différentes: les premiers sont plus grands que les derniers car ils citent davantage les en-têtes des fichiers locaux. Le contenu des fichiers de sortie n'a pas beaucoup de sens, mais personne n'a dit que cela devrait avoir du sens.

Cette conception de citation de chevauchement a une meilleure compatibilité que la conception de chevauchement complet de la section précédente, mais la compatibilité est obtenue par compression. Là, chaque fichier ajouté ne coûte que le titre du répertoire central, ici il en coûte le titre du répertoire central, l'en-tête du fichier local et encore 5 octets pour l'en-tête de citation.

Optimisation

Après avoir reçu le design de base de la bombe zip, nous allons essayer de la rendre aussi efficace que possible. Nous voulons répondre à deux questions:

• Quel est le taux de compression maximal pour une taille de fichier zip donnée?
  
• Quel est le taux de compression maximal compte tenu des limites du format zip?

Compression du noyau

Il est avantageux pour nous de compresser le noyau autant que possible, car chaque octet décompressé est multiplié par N. Pour cela, nous utilisons un compresseur DEFLATE personnalisé appelé bulk_deflate, spécialisé dans la compression d'une chaîne d'octets répétés.

Tous les archiveurs DEFLATE décents se rapprochent du taux de compression de 1032 sur un flux sans fin d'octets répétés, mais nous sommes préoccupés par la taille spécifique. Dans notre taille d'archive, bulk_deflate contient plus de données que les archiveurs à usage général: environ 26 Ko de plus que zlib et Info-ZIP, et environ 15 Ko de plus que Zopfli , ce qui sacrifie la vitesse au profit de la qualité de la compression.



Le prix d'un taux de compression élevé bulk_deflate - le manque de polyvalence. Il ne peut compresser que des lignes d'octets répétitifs et seulement une certaine longueur, à savoir 517 + 258 k pour un entier k ≥ 0. En plus d'une bonne compression, bulk_deflate fonctionne rapidement, effectuant un travail presque en même temps quelle que soit la taille des données d'entrée, compter le travail d'écriture d'une chaîne compressée.

Noms de fichiers

Pour nos besoins, les noms de fichiers ont presque un poids mort. Bien qu'ils contribuent à la taille de la sortie en faisant partie des en-têtes des fichiers locaux entre guillemets, les octets du nom de fichier contribuent beaucoup moins que les octets du noyau. Nous voulons que les noms de fichiers soient aussi courts que possible, tout en étant différents, sans oublier la compatibilité.

Chaque octet dépensé sur un nom de fichier signifie deux octets non dépensés sur le noyau (deux car chaque nom de fichier apparaît deux fois: dans l'en-tête du répertoire central et dans l'en-tête du fichier local). Un octet de nom de fichier donne une moyenne de seulement ( N + 1) / 4 octets de sortie, tandis qu'un octet dans le noyau compte pour 1032 N. Exemples: 1 , 2 , 3 .

La première considération de compatibilité est le codage. La spécification du format zip indique que les noms de fichiers doivent être interprétés comme CP 437 ou UTF-8 si un bit indicateur spécifique est défini ( APPNOTE.TXT, annexe D ). C'est le principal point d'incompatibilité entre les analyseurs zip, qui peuvent interpréter les noms de fichiers dans certains encodages fixes ou spécifiques aux paramètres régionaux. Par conséquent, pour des raisons de compatibilité, il est préférable de vous limiter aux caractères ayant le même codage dans le CP 437 et l'UTF-8. À savoir, ce sont 95 caractères US-ASCII imprimables.

Nous sommes également liés par des restrictions de dénomination du système de fichiers. Certains systèmes de fichiers ne sont pas sensibles à la casse, donc «a» et «A» ne sont pas considérés comme des noms différents. Les systèmes de fichiers courants, tels que FAT32, interdisent certains caractères , tels que «*» et «?».

Comme compromis sûr, mais pas nécessairement optimal, notre bombe zip utilisera des noms de fichiers issus de l'alphabet à 36 caractères, qui n'inclut pas les caractères spéciaux et les caractères de casse différente:

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

Les noms de fichiers sont générés de manière évidente, toutes les positions à tour de rôle, avec l'ajout d'une position à la fin de la boucle:

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

Il existe 36 noms de fichier à un caractère, 36² noms à deux caractères, etc. Quatre octets suffisent pour 1 727 604 noms de fichiers différents.

Étant donné que les noms de fichiers dans l'archive auront généralement des longueurs différentes, comment puis-je mieux les trier: du plus court au plus long ou vice versa? Si vous réfléchissez un peu, il vaut mieux mettre les noms les plus longs en dernier. Ce tri ajoute plus de 900 Mo de sortie à zblg.zip , par rapport à la commande la plus longue à la plus courte. Cependant, il s'agit d'une optimisation mineure, car 900 Mo ne représentent que 0,0003% de la taille totale du problème.

Taille du noyau

La conception de devis qui se chevauchent vous permet de placer un noyau de données compressé, puis de le copier à plusieurs reprises à moindre coût. Pour une taille spécifique du fichier zip X , combien d'espace est optimal à allouer pour stocker le noyau, et combien pour créer des copies?

Pour trouver l'équilibre optimal, vous devez optimiser une seule variable N , le nombre de fichiers dans l'archive zip. Chaque valeur N nécessite une certaine quantité de surcharge pour les en-têtes du répertoire central, les en-têtes des fichiers locaux, les en-têtes des blocs de citation et les noms de fichiers. Le reste de l'espace sera occupé par le noyau. Étant donné que N doit être un entier et que vous ne pouvez mettre qu'un certain nombre de fichiers avant que la taille du noyau ne tombe à zéro, il suffit de vérifier toutes les valeurs possibles de N et de sélectionner celle qui donne la plus grande sortie.

L'application de la procédure d'optimisation à X = 42 374 pour 42.zip trouve un maximum à N = 250. Ces 250 fichiers nécessitent 21 195 octets de surcharge, ce qui laisse 21 179 octets pour le noyau. Un noyau de cette taille est décompressé en 21 841 249 octets (rapport 1031,3 pour 1). 250 copies du noyau décompressé et quelques en-têtes de fichiers locaux cités donnent une sortie totale décompressée de 5 461 307 620 octets et un taux de compression de 129 000.

• zbsm.zip 42 ko → 5,5 Go

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

L'optimisation a conduit à une répartition presque uniforme de l'espace entre le noyau et les en-têtes de fichiers. Ce n'est pas un hasard. Considérons un modèle simplifié d'une construction de citation avec chevauchement. Dans un modèle simplifié, nous ignorons les noms de fichiers, ainsi qu'une légère augmentation de la taille du fichier de sortie en raison de la citation des en-têtes des fichiers locaux. L'analyse du modèle simplifié montrera que la distribution optimale entre le noyau et les en-têtes de fichier est approximativement uniforme, et la taille de sortie avec la distribution optimale croît de façon quadratique en fonction de la taille de l'entrée.

Définition de certaines constantes et variables:


Soit H (N) le volume de la surcharge pour les en-têtes de N fichiers. Consultez le tableau pour comprendre l'essence de la formule.

$$

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

Pour le noyau, il reste des emplacements X - H (N) . La taille totale décompressée S _X (N) est égale à la taille de N copies du noyau décompressé avec le rapport C (dans ce modèle simplifié, nous ignorons la légère extension supplémentaire des en-têtes de fichiers locaux mentionnés).

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

S _X (N) est un polynôme dans la partie N, par conséquent, le maximum devrait être où la dérivée S ' _X (N) est égale à zéro. Prendre la dérivée et trouver zéro nous donne N _OPT , le nombre optimal de fichiers.

$$$$ afficher $$ 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 $$ affichage $$

H (N _OPT ) donne la quantité optimale d'espace pour placer les en-têtes de fichier. Il est indépendant de CDH, LFH et C et est proche de X / 2 .

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

S _X (N _OPT ) - taille totale non emballée à distribution optimale. De cela, nous voyons que la taille de la sortie augmente de façon quadratique avec l'augmentation des données d'entrée.

$$

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

En augmentant la taille du fichier zip, nous rencontrerons finalement les limites du format zip: l'archive ne peut pas avoir plus de 2 ¹⁶ −1 fichiers avec une taille ne dépassant pas 2 ³² −1 octets chacun. Pire, certaines implémentations prennent des valeurs maximales comme indicateur de la présence d' extensions 64 bits , donc nos limites sont en fait 2 ¹⁶ -2 et 2 ³² -2. Il arrive que la première fois nous rencontrons une limite sur la taille d'un fichier non compressé. Avec une taille de fichier zip de 8 319 377 octets, l'optimisation naïve nous donnera le nombre de fichiers 47 837 et un fichier maximum de 2 ³² +311 octets.

(En fait, tout est un peu plus compliqué, car les limites exactes dépendent de l'implémentation. Le fichier zip Python ignore le nombre de fichiers, archive / zip dans Go permet d' augmenter le nombre de fichiers jusqu'à ce qu'ils correspondent aux 16 bits inférieurs. Mais pour une compatibilité générale, nous devons respecter limites établies).

Si nous ne pouvons pas augmenter indéfiniment N ou la taille du noyau, nous aimerions trouver le taux de compression maximum dans le format zip. Vous devez rendre le noyau aussi grand que possible avec le nombre maximum de fichiers. Malgré le fait que nous ne pouvons plus maintenir une séparation approximativement uniforme entre le noyau et les en-têtes de fichiers, chaque fichier ajouté augmente toujours le taux de compression - mais pas aussi vite que si nous pouvions continuer à augmenter le noyau. En fait, à mesure que des fichiers sont ajoutés, nous devrons réduire la taille du noyau pour libérer de l'espace pour la taille de fichier maximale, qui augmente légèrement avec chaque fichier ajouté.

Le plan conduit à une archive zip avec 2 ¹⁶ −2 fichiers et un noyau, qui est décompressé en 2 ³² −2 178 825 octets. Les fichiers seront plus volumineux vers le début de l'archive zip - le premier et le plus gros fichier est décompressé en 2 ³² −56 octets. C'est aussi proche que possible de l'utilisation des paramètres de sortie approximatifs de bulk_deflate - l'encodage des 54 derniers octets coûtera plus cher que leur taille (le fichier zip dans son ensemble a un taux de compression de 28 millions, et les 54 derniers octets recevront un maximum de 54 ⋅ 10 ³² ⋅ ( 2 ¹⁶ - 2) ≈ 36 - 5 millions d'octets, donc cela n'aide que si 54 octets peuvent être encodés en un octet - et je n'ai pas pu coder en moins de deux. Par conséquent, si vous ne pouvez pas encoder 54 octets en 1 octet, cela ne fait que réduire le taux de compression). La taille de sortie de cette bombe zip est de 281 395 456 244 934 octets, 99,97% du maximum théorique (2 ³² - 1) × (2 ¹⁶ - 1). Toute amélioration significative du taux de compression ne peut être obtenue qu'en réduisant la taille du signal d'entrée et non en augmentant la sortie.

• zblg.zip 10 Mo → 281 To

  zipbomb --mode = quoted_overlap --num-files = 65534 --max-uncompressed-size = 4292788525> zblg.zip 

Calcul CRC-32 efficace

Parmi les métadonnées dans l'en-tête du répertoire central et l'en-tête du fichier local se trouve une somme de contrôle des données du fichier non compressé - CRC-32 . Cela pose un problème car la quantité de calculs CRC-32 pour chaque fichier est proportionnelle à sa taille, qui est très grande par défaut (après tout, c'est une bombe zip). Nous préférons effectuer un travail au moins proportionnel à la taille de l'archive. Deux facteurs jouent en notre faveur: tous les fichiers ont un noyau commun et un noyau non compressé est une chaîne d'octets répétés. Imaginez le CRC-32 comme un produit matriciel - cela nous permettra non seulement de calculer rapidement la somme de contrôle du noyau, mais également de réutiliser les calculs entre les fichiers. La méthode décrite dans cette section est une petite extension de la fonction crc32_combine dans zlib, que Mark Adler explique ici .

Le CRC-32 peut être modélisé comme une machine d'état, mettant à jour un registre d'état 32 bits pour chaque bit d'entrée. Les opérations de mise à jour de base pour les bits 0 et 1 sont les suivantes:

 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; } 

Si vous représentez le registre d'état comme un vecteur binaire à 32 éléments et utilisez XOR pour l'addition et la multiplication, alors crc32_update_0 est un mappage linéaire ; c'est-à-dire qu'il peut être représenté comme une multiplication par une matrice de transition binaire 32 × 32. Pour comprendre pourquoi, notez que multiplier une matrice par un vecteur revient simplement à additionner les colonnes de la matrice après avoir multiplié chaque colonne par l'élément correspondant du vecteur. L' state >> 1 opération de décalage state >> 1 prend simplement chaque bit i du vecteur d'état et le multiplie par un vecteur qui est nul partout sauf pour le bit i - 1 (numérotation des bits de droite à gauche). Relativement parlant, l' state ^ 0xedb88320 XOR final state ^ 0xedb88320 se produit uniquement lorsque le bit b est égal à un. Cela peut être représenté comme la première multiplication de b par 0xedb88320, puis XORing à cet état.

De plus, crc32_update_1 n'est qu'une crc32_update_0 plus (XOR).Cela fait crc32_update_1 une transformation affine : multiplication matricielle suivie d'une cartographie (c'est-à-dire, addition de vecteur). Nous pouvons imaginer la multiplication et la cartographie matricielles en une seule étape, si nous augmentons la taille de la matrice de transformation à 33 × 33 et ajoutons un élément supplémentaire au vecteur d'état, qui est toujours 1 (cette représentation est appelée coordonnées homogènes ).


Les matrices de transformation sont 33 × 33 M ₀ et M ₁ , qui calculent le changement d'état CRC-32 effectué respectivement par les bits 0 et 1. Les vecteurs de colonne sont stockés avec le bit le plus significatif ci-dessous: en lisant la première colonne de bas en haut, vous voyez la constante polynomiale CRC-32 edb8832016 = 111 0 11 0 110 111 000 1 00000 11 00 1 00000 ₂ . Ces deux matrices ne diffèrent que dans la dernière colonne, qui représente le vecteur de translation en coordonnées homogènes. Dans M _{0, la} translation est nulle et dans M _{1, c'est} edb88320 ₁₆ , la constante polynomiale est CRC-32. Les unités sont immédiatement au-dessus de l'état de l'opération en diagonalestate >> 1

deux opérationscrc32_update_0etcrc32_update_1peuvent être représentés par la matrice de transition de 33 x 33. Les matrices M ₀ et M ₁ sont représentées.. L'avantage de la représentation matricielle est que les matrices peuvent être multipliées. Supposons que nous voulons voir un changement d'état effectué en traitant un caractère ASCII «a», dont la représentation binaire est 01100001 ₂ . On peut imaginer le changement cumulé de l'état du CRC-32 de ces huit bits dans une matrice de transformation:

$$

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

Et nous pouvons imaginer un changement dans l'état d'une rangée répétant «a» en multipliant plusieurs copies de M _a - élevant la matrice à une puissance. Nous pouvons le faire rapidement en utilisant l' algorithme d'exponentiation rapide , ce qui permet de calculer le M ⁿ connectez ₂ ⁿ étapes. Par exemple, voici une matrice pour changer l'état d'une chaîne de 9 caractères '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$$

L'algorithme de multiplication rapide de matrice est utile pour calculer le _noyau M , une matrice pour un noyau non compressé, car le noyau est une chaîne d'octets répétés. Pour obtenir la somme de contrôle CRC-32 de la matrice, multipliez la matrice par le vecteur zéro (le vecteur zéro est en coordonnées uniformes, soit 32 zéros, puis l'unité; ici, nous omettons la légère complication du pré et post-traitement de la somme de contrôle pour vérifier la conformité). Pour calculer la somme de contrôle de chaque fichier, nous travaillons dans la direction opposée. Nous commençons par un initialisées M: M = _{le noyau} . La somme de contrôle du noyau est également la somme de contrôle du fichier final N , donc nous multiplions Mun vecteur zéro et stocke la somme de contrôle reçue dans la CDH _N et LFH _N . Les données du fichier N - 1 sont les mêmes que les données du fichier N , mais avec le préfixe LFH _N ajouté . Par conséquent, nous calculons$$M L F H N , matrice de changement d'état pour LFH_Net mise à jour$M_{L{FH_N}}$$$$M := M M_{L{FH_N}}$ .Maintenant, M représente le changement d'état cumulatif du traitement de LFH _N derrière le noyau. Nous calculons la somme de contrôle pour le fichier N - 1 , multipliant à nouveau M par le vecteur zéro. Nous continuons la procédure en accumulant des matrices de changement d'état dans M jusqu'à ce que tous les fichiers soient traités.

Extension: Zip64

Plus tôt, nous avons été confrontés au problème de l'expansion en raison des limitations du format zip - il était impossible d'émettre plus de 281 To, quelle que soit la façon dont le fichier zip était emballé. Vous pouvez transcender ces limites en utilisant Zip64, une extension au format zip qui augmente la taille de certains champs d'en-tête à 64 bits. La prise en charge de Zip64 n'est en aucun cas universelle, mais c'est l'une des extensions les plus couramment implémentées. Quant au taux de compression, l'effet de Zip64 est d'augmenter la taille de l'en-tête du répertoire central de 46 à 58 octets, et la taille de l'en-tête du répertoire local de 30 à 50 octets. En regardant la formule du coefficient d'expansion optimal dans un modèle simplifié, nous voyons que la bombe zip au format Zip64 croît toujours de manière quadratique, mais plus lentement en raison du plus grand dénominateur - cela peut être vu dans le diagramme ci-dessous. En raison de la perte de compatibilité et du retard de croissance, nous supprimons presque toutes les restrictions sur la taille des fichiers.

Supposons que nous ayons besoin d'une bombe zip qui se développe à 4,5 PB, comme 42.zip. Quelle doit être la taille des archives? En utilisant la recherche binaire, nous constatons que la taille minimale d'un tel fichier est de 46 Mo.

• zbxl.zip 46 Mo → 4,5 PB (Zip64, moins compatible)

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

4,5 pétaoctets - à peu près la même quantité de données a été enregistrée par le télescope Event Horizon pour la première image d'un trou noir : des racks et des racks avec des disques durs dans le centre de données.

Avec Zip64, il n'est presque pas intéressant de considérer le taux de compression maximal, car nous pouvons simplement continuer à augmenter la taille du fichier zip et le taux de compression avec lui, jusqu'à ce que même le fichier zip compressé devienne prohibitif. Un seuil intéressant, cependant, est de 2 ⁶⁴ octets (18 EB ou 16 EiB) - tant de données ne rentreront pas sur la plupart des systèmes de fichiers. La recherche binaire trouve la plus petite bombe zip qui produit au moins autant de sortie: elle contient 12 millions de fichiers et un noyau compressé de 1,5 Go. La taille totale du fichier zip est de 2,9 Go et il est déballé en 2 ⁶⁴+11 727 895 877 octets avec un taux de compression de plus de 6,2 milliards à un. Je n'ai pas téléchargé ce fichier pour le télécharger, mais vous pouvez le générer vous-même en utilisant le code source . Il a des fichiers d'une taille telle que même un bug a été révélé dans Info-ZIP UnZip 6.0.

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

Extension: bzip2

DEFLATE est l'algorithme de compression le plus courant pour le format zip, mais ce n'est qu'une des nombreuses options. Le deuxième algorithme le plus courant est probablement bzip2 . Bien qu'il ne soit pas aussi compatible que DEFLATE. Théoriquement, dans bzip2, le taux de compression maximal est d'environ 1,4 million pour un, ce qui permet un compactage plus dense du noyau.

bzip2 code d'abord le «codage de longueur d'exécution», réduisant de 51 fois la longueur de chaîne des octets répétés. Ensuite, les données sont divisées en blocs de 900 Ko et chaque bloc est compressé séparément. Théoriquement, un bloc peut compresser jusqu'à 32 octets. 900 000 × 51/32 = 1 434 375.

Ignorant la perte de compatibilité, bzip2 fait-il une bombe plus efficace?

Oui - mais uniquement pour les petits fichiers. Le problème est que dans bzip2 il n'y a rien de tel que les blocs DEFLATE non compressés que nous avons utilisés pour citer les en-têtes des fichiers locaux. Ainsi, il est impossible de chevaucher des fichiers et de réutiliser le noyau - pour chaque fichier, vous devez écrire votre propre copie, donc le taux de compression global ne sera pas meilleur que le taux pour un seul fichier. Dans le graphique ci-dessous, nous voyons que sans chevauchement, bzip2 est supérieur à DEFLATE uniquement pour les fichiers d'environ mégaoctets.

Il n'y a qu'un espoir pour un autre moyen de citer les en-têtes dans bzip2, qui est discuté dans la section suivante. De plus, si vous savez qu'un analyseur zip particulier prend en charge bzip2 etpermet des noms de fichiers incompatibles, vous pouvez utiliser la construction de chevauchement complète, qui n'a pas besoin d'être citée.


Comparaison du taux de compression de différentes bombes zip. Faites attention à l'axe logarithmique. Chaque design est illustré avec et sans Zip64. Les structures sans chevauchement ont un taux de croissance linéaire, qui peut être vu à partir du rapport constant des axes. Le décalage vertical du graphique bzip2 signifie que le taux de compression de bzip2 est environ mille fois supérieur à celui de DEFLATE. Les constructions DEFLATE citées ont un taux de croissance quadratique, comme en témoigne une inclinaison vers les axes 2: 1. La variante Zip64 est légèrement moins efficace, mais permet plus de 281 To. Les graphiques pour bzip2 avec des citations à travers un champ supplémentaire passent de quadratique à linéaire lorsque la taille maximale du fichier est atteinte (2 ³² −2 octets), ou le nombre maximal autorisé de fichiers

Extension: cotation via un champ supplémentaire

Jusqu'à présent, nous avons utilisé la fonction DEFLATE pour citer les en-têtes des fichiers locaux, et nous venons de voir que cette astuce ne fonctionne pas dans bzip2. Cependant, il existe une autre méthode de citation, un peu plus limitée, qui n'utilise que des fonctions de format zip et est indépendante de l'algorithme de compression.

À la fin de la structure d'en-tête du fichier local, il y a un champ supplémentaire de longueur variable pour stocker des informations qui ne correspondent pas aux champs d'en-tête habituels ( APPNOTE.TXT, section 4.3.7) Des informations supplémentaires peuvent inclure, par exemple, un horodatage ou un uid / gid d'Unix. Les informations Zip64 sont également stockées dans un champ supplémentaire. Un champ supplémentaire est représenté comme une structure de valeur de longueur; si vous augmentez la longueur sans ajouter de valeur, le champ supplémentaire inclura ce qu'il y a derrière dans le fichier zip, à savoir l'en-tête suivant du fichier local. En utilisant cette méthode, chaque en-tête du fichier local peut «citer» les en-têtes suivants, en les enfermant dans son propre champ supplémentaire. Comparé à DEFLATE, il y a trois avantages:

1. Citer via un champ supplémentaire ne nécessite que 4 octets, pas 5, ce qui laisse plus d'espace pour le noyau.
   
2. Il n'augmente pas la taille du fichier, ce qui signifie un noyau plus grand, compte tenu des limites du format zip.
   
3. Il fournit des citations dans bzip2.

Malgré ces avantages, la cotation dans des champs supplémentaires est moins flexible. Ce n'est pas une chaîne, comme dans DEFLATE: chaque en-tête d'un fichier local doit contenir non seulement l'en-tête immédiatement suivant, mais aussi tous les en-têtes suivants. Les champs supplémentaires augmentent à mesure que vous approchez du début du fichier zip. Étant donné que la longueur maximale du champ est de 2 ¹⁶ −1 octets, seuls 1808 en-têtes de fichiers locaux (ou 1170 en Zip64) peuvent être cités, en supposant que les noms sont attribués comme prévu.(dans le cas de DEFLATE, vous pouvez utiliser un champ supplémentaire pour citer les premiers en-têtes (les plus courts) des fichiers locaux, puis passer à la citation DEFLATE pour le reste). Autre problème: pour correspondre à la structure interne des données du champ supplémentaire, il est nécessaire de sélectionner une balise 16 bits pour le type ( APPNOTE.TXT, section 4.5.2 ) précédant les données de citation. Nous voulons sélectionner une balise de type qui obligera les analyseurs à ignorer les données entre guillemets, plutôt que d'essayer de les interpréter comme des métadonnées significatives. Les analyseurs Zip devraient ignorer les balises de type inconnu, afin que nous puissions sélectionner des balises au hasard, mais il y a un risque qu'à l'avenir certaines balises violent la compatibilité du design.

Le schéma précédent illustre la possibilité d'utiliser des champs supplémentaires dans bzip2, c et sans Zip64. Sur les deux graphiques, il y a un tournant, lorsque la croissance passe du quadratique au linéaire. Sans Zip64, cela se produit lorsque la taille maximale du fichier non compressé est atteinte (2 ³²−2 octets); alors vous pouvez seulement augmenter le nombre de fichiers, mais pas leur taille. Le graphique se termine complètement lorsque le nombre de fichiers atteint 1809, puis nous manquons d'espace dans un champ supplémentaire pour citer des en-têtes supplémentaires. Avec Zip64, une fracture se produit sur 1171 fichiers, après quoi seule la taille du fichier peut être augmentée, mais pas leur nombre. Un champ supplémentaire aide dans le cas de DEFLATE, mais la différence est si petite qu'elle n'est pas visuellement perceptible. Il augmente le taux de compression de zbsm.zip de 1,2%; zblg.zip de 0,019%; et zbxl.zip de 0,0025%.

La discussion

Dans leur travail sur ce sujet, Pletz et ses collègues utilisent le chevauchement de fichiers pour créer une archive zip presque auto-réplicable. Le chevauchement du fichier lui-même a été suggéré plus tôt (diapositive 47) par Ginvael Coldwind.

Nous avons développé une conception d'une bombe zip avec un chevauchement de devis prenant en compte la compatibilité - un certain nombre de différences dans les implémentations, dont certaines sont présentées dans le tableau ci-dessous. La conception résultante est compatible avec les analyseurs zip qui fonctionnent de la manière habituelle, c'est-à-dire en vérifiant d'abord le répertoire central et en l'utilisant comme index de fichiers. Parmi eux, un analyseur zip unique de Nailqui est généré automatiquement à partir de la grammaire formelle. Cependant, la conception est incompatible avec les analyseurs "en streaming", qui analysent le fichier zip du début à la fin en une seule passe sans avoir d'abord lu le répertoire central. De par leur nature, les analyseurs en streaming ne permettent en aucun cas aux fichiers de se chevaucher. Très probablement, ils extrairont uniquement le premier fichier. De plus, ils peuvent même lancer une erreur, comme c'est le cas avec sunzip , qui analyse le répertoire central à la fin et vérifie la cohérence avec les en-têtes des fichiers locaux qu'il a déjà vus.

Si vous souhaitez que les fichiers extraits commencent par un préfixe spécifique différent des octets d'en-tête du fichier local, vous pouvez insérer un bloc DEFLATE avant le bloc non compressé cité par l'en-tête suivant. Tous les fichiers de l'archive zip ne doivent pas participer à la création de la bombe: vous pouvez inclure des fichiers ordinaires dans l'archive, si nécessaire, afin de correspondre à un format spécial (il y a un paramètre dans le code source --templatepour ce cas d'utilisation). De nombreux formats utilisent zip comme conteneur, tels que les documents Java JAR, Android APK et LibreOffice.

Pdfà bien des égards similaire à zip. Il a une table de références croisées à la fin du fichier qui pointe vers les objets précédents, et il prend en charge la compression des objets via le filtre FlateDecode. Je n'ai pas essayé, mais vous pouvez utiliser l'idée de citer avec chevauchement pour fabriquer une bombe PDF. Peut-être que vous n'avez même pas à travailler dur ici: binaryhax0r écrit dans un article de blog que vous pouvez simplement spécifier plusieurs couches FlateDecode sur un objet, après quoi la création d'une bombe PDF devient triviale.

Définir une classe particulière de bombes zip décrit dans cet article est simple: il suffit de trouver les fichiers qui se chevauchent. Mark Adler a écrit un patchpour Unzip Info-ZIP, qui fait exactement cela. Cependant, en général, le blocage des fichiers qui se chevauchent ne protège pas contre toutes les classes de bombes zip. Il est difficile de prédire à l'avance si le fichier est une bombe zip ou non si vous n'avez pas une connaissance précise des composants internes des analyseurs qui seront utilisés pour l'analyser. La consultation des en-têtes et la somme des champs «taille non compressée» de tous les fichiers ne fonctionnent pas , car la valeur dans les en-têtes peut ne pas correspondre à la taille réelle non compressée (dans le tableau de compatibilité, voir la ligne «permet que le fichier soit trop petit»). Une protection fiable contre les bombes zip comprend des limites de temps, de mémoire et d'espace disque dans l'analyseur zip pendant son fonctionnement. Prenez l'analyse des fichiers zip, comme toutes les opérations complexes avec des données non fiables, avec prudence.


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

Remerciements

Merci à Mark Adler , Russ Cox , Brandon Enright , Marek Maykovsky , Josh Wolfe et aux critiques de USENIX WOOT 2019 pour leurs commentaires sur le projet de cet article. Kaolan McNamara a évalué l'impact des bombes zip sur la sécurité de LibreOffice.

Une version de cet article a été préparée pour l'atelier USENIX WOOT 2019 . Le code source est disponible. Les artefacts à présenter lors de l'atelier se trouvent dans le fichier zipbomb-woot19.zip .

Avez-vous trouvé un système qui largue l'une des bombes? Les bombes vous ont-elles aidé à trouver un bug ou à gagner de l'argent dans un programme de recherche de bug? Faites le moi savoir, je vais essayer de le mentionner ici.

LibreOffice 6.1.5.2

Après avoir renommé zblg.zip en zblg.odt ou zblg.docx, LibreOffice crée et supprime une série de fichiers temporaires d'environ 4 Go, essayant de déterminer le format de fichier. En fin de compte, il termine cette opération et supprime les fichiers temporaires à mesure qu'ils arrivent, de sorte que la bombe zip ne provoque qu'un DoS temporaire sans remplir le disque. Kaolan McNamara a répondu à mon message d'erreur.

Mozilla addons-server 2019.06.06

J'ai essayé des bombes zip contre l'installation du serveur d'addons local, qui fait partie du logiciel addons.mozilla.org. Le système gère gracieusement la bombe, imposant un délai de 110 secondes sur l'extraction des fichiers. La bombe zip se développe rapidement, dans la mesure où le disque le permet jusqu'à cette limite de temps, mais le processus est alors tué et les fichiers décompressés sont finalement automatiquement effacés.

UnZip 6.0

Mark Adler a écrit un patch pour UnZip pour détecter cette classe de bombes zip.

5 juillet 2019: j'ai remarqué que CVE-2019-13232 a été attribué à UnZip. Personnellement, je dirais que la capacité / l'incapacité d'UnZip (ou de tout analyseur zip) de traiter ce type de bombe zip est nécessairement une vulnérabilité ou même un bug. Il s'agit d'une implémentation naturelle qui ne viole pas les spécifications, que puis-je dire. Le type de bombe dans cet article n'est qu'un type, et il existe de nombreuses autres façons de résoudre un analyseur zip. Comme mentionné ci-dessus, si vous souhaitez vous protéger contre les attaques d'épuisement des ressources, vous ne devez pas essayer de répertorier, détecter et bloquer chaque attaque connue; il est plutôt nécessaire d'établir des restrictions externes sur le temps et les autres ressources afin que l'analyseur n'entre pas dans une telle situation, quel que soit le type d'attaque qu'il a rencontré. Il n'y a rien de mal à essayer de détecter et de rejeter certains modèles comme une optimisation de la première passe,mais vous ne pouvez pas vous arrêter là. À moins que vous finissiez par isoler et restreindre les opérations avec des données non fiables, votre système est probablement toujours vulnérable. Considérez l'analogie avec les scripts intersites en HTML: la bonne protection n'est pas d'essayer de filtrer des octets spécifiques qui peuvent être interprétés comme du code, mais d'éviter tout correctement.

Moteurs antivirus

L'utilisateur de Twitter @TVqQAAMAAAAEAAA rapporte : "L'antivirus McAfee sur ma machine de test vient d'exploser." Je ne l'ai pas testé moi-même et je n'ai pas de détails tels que le numéro de version.

Tavis Ormandi indique que VirusTotal a un certain nombre de délais d'expiration pour zblg.zip ( capture d'écran du 6 juin 2019 ): AhnLab-V3, ClamAV, DrWeb, Endgame, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, McAfee-GW -Edition, Panda, Qihoo-360, Sophos ML, VBA32. Résultats pour zbsm.zip ( capture d'écran du 6 juin 2019) sont similaires, mais avec un ensemble différent de moteurs de temporisation: Baido, Bkav, ClamAV, CMC, DrWeb, Endgame, ESET-NOD32, F-Secure, GData, Kingsoft, McAfee-GW-Edition, NANO-Antivirus, Acronis. Fait intéressant, il n'y a pas de délais d'attente dans les résultats de zbxl.zip ( capture d'écran du 6 juin 2019 ). Peut-être que certains antivirus ne prennent pas en charge Zip64? Plusieurs moteurs détectent les fichiers comme une sorte de «bombe de compression». Il est intéressant de voir s'ils continueront à le faire avec des modifications mineures, telles que la modification des noms de fichiers ou l'ajout d'un préfixe ASCII à chaque fichier.

Déclaration finale

Il est temps de mettre fin à Facebook. Ce n'est pas un travail neutre pour vous: chaque jour, quand vous venez au travail, vous faites quelque chose de mal. Si vous avez un compte Facebook, supprimez-le. Si vous travaillez sur Facebook, licenciez-vous.

Et n'oubliez pas que l'Agence de sécurité nationale doit être détruite.