El artículo muestra cómo crear una bomba zip no recursiva que proporciona un alto grado de compresión mediante la superposición de archivos dentro de un contenedor zip. "No recursivo" significa que no depende de que los descompresores descompriman archivos incrustados en archivos zip: solo hay una ronda. El tamaño de salida aumenta cuadráticamente desde la entrada, alcanzando una relación de compresión de más de 28 millones (10 MB → 281 TB) dentro del formato zip. Es posible una mayor expansión con extensiones de 64 bits. El diseño utiliza solo el algoritmo de compresión DEFLATE más común y es compatible con la mayoría de los analizadores zip.

• zbsm.zip 42 kB → 5.5 GB
  
• zblg.zip 10 MB → 281 TB
  
• zbxl.zip 46 MB → 4.5 PB (Zip64, menos compatible con analizadores)

Código fuente:

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

zipbomb-20190702.zip

Datos y fuente de ilustraciones:

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

<sub>* Hay dos versiones de 42.zip: el antiguo 42 374 bytes y el nuevo 42 428 bytes. La diferencia es que la nueva requiere una contraseña antes de desempacar. Solo comparamos con la versión anterior. Aquí hay una copia del archivo si lo necesita: 42.zip .

** Me gustaría saber e indicar el autor de 42.zip, pero no pude encontrarlo; avíseme si tiene alguna información.</sub>

Las bombas Zip deben superar el hecho de que el algoritmo de compresión DEFLATE más comúnmente soportado por los analizadores no puede exceder la relación de compresión de 1032 a 1. Por esta razón, las bombas Zip generalmente dependen de la descompresión recursiva al insertar archivos zip en archivos zip para obtener una relación adicional 1032 con cada capa. Pero el truco solo funciona en implementaciones que se descomprimen de forma recursiva, y la mayoría no. La bomba 42.zip más famosa se expande a un formidable 4.5 PB, si las seis capas se desempaquetan recursivamente, pero en la capa superior tiene 0.6 MB insignificantes. Las quines zip, como las de Cox y Ellingsen , emiten una copia de sí mismas y, por lo tanto, se expanden indefinidamente cuando se desempaquetan recursivamente. Pero también son completamente seguros al desempacar una vez.

Este artículo muestra cómo crear una bomba zip no recursiva, cuya relación de compresión excede el límite DEFLATE de 1032. Funciona superponiendo archivos dentro de un contenedor zip para hacer referencia al "núcleo" de datos altamente comprimidos en múltiples archivos sin hacer múltiples copias. El tamaño de salida de la bomba zip crece cuadráticamente desde el tamaño de entrada; es decir, la relación de compresión mejora al aumentar el tamaño de la bomba. El diseño depende de las características de zip y DEFLATE: no se puede transferir directamente a otros formatos de archivo o algoritmos de compresión. La bomba es compatible con la mayoría de los analizadores zip, excepto los de "transmisión", que analizan archivos en una sola pasada sin verificar el directorio central del archivo zip. Intentamos equilibrar dos objetivos en conflicto:

• Aumentar la relación de compresión. Definimos la relación de compresión como la suma de los tamaños de todos los archivos en el archivo dividido por el tamaño del archivo zip en sí. No tiene en cuenta los nombres de archivo u otros metadatos del sistema de archivos, sino solo el contenido.
  
• Mantener compatibilidad. Zip es un formato complejo, y los analizadores difieren, especialmente en situaciones límite y funciones adicionales. No utilice técnicas que funcionen solo con ciertos analizadores sintácticos. Observaremos algunas formas de aumentar la eficiencia de una bomba zip con una cierta pérdida de compatibilidad.

Estructura del archivo zip

El archivo zip consta de un directorio central de enlaces de archivos.



El directorio central está al final del archivo zip. Esta es una lista de encabezados del directorio central . Cada encabezado del directorio central contiene metadatos para un solo archivo, como el nombre del archivo y la suma de verificación CRC-32, así como un puntero al encabezado del archivo local. El encabezado del directorio central tiene una longitud de 46 bytes más la longitud del nombre del archivo.

El archivo consta del encabezado del archivo local, seguido de los datos del archivo comprimido. La longitud del encabezado del archivo local es de 30 bytes más la longitud del nombre del archivo. Contiene una copia redundante de los metadatos del encabezado del directorio central, así como los tamaños de los archivos de datos comprimidos y no comprimidos detrás de él. Zip es un formato contenedor, no un algoritmo de compresión. Los datos de cada archivo se comprimen utilizando el algoritmo especificado en los metadatos, generalmente DEFLATE .

Esta descripción del formato zip omite muchos detalles que no son necesarios para comprender la bomba zip. Para obtener información completa, consulte la sección 4.3 APPNOTE.TXT o "Estructura de archivo PKZip" de Florian Buchholz, o consulte el código fuente .

La redundancia significativa y muchas ambigüedades en el formato zip abren oportunidades para travesuras de diferentes tipos. Una bomba zip es solo la punta del iceberg. Enlaces para lecturas adicionales:

• "Diez mil trampas de seguridad: un formato ZIP", por Ginwael Coldwind
  
• El análisis zip ambiguo le permite ocultar los archivos de complemento de Firefox de la interfaz y las personas : mi vulnerabilidad en addons.mozilla.org

Primer descubrimiento: archivos superpuestos

Al comprimir una larga cadena de bytes repetidos, podemos crear un núcleo de datos altamente comprimidos. La relación de compresión del núcleo en sí no puede exceder el límite DEFLATE de 1032, por lo que necesitamos una forma de reutilizar el núcleo en muchos archivos, sin crear una copia separada en cada archivo. Podemos hacer esto superponiendo archivos: haga que muchos encabezados del directorio central apunten a un solo archivo cuyos datos son el núcleo.



Considere un ejemplo de cómo este diseño afecta la relación de compresión. Supongamos que un núcleo de 1000 bytes se desempaqueta en 1 MB. Luego, el primer megabyte de salida "cuesta" 1078 bytes de datos de entrada:

• 31 bytes para el encabezado del archivo local (incluido el nombre de archivo de 1 byte)
  
• 47 bytes para el encabezado del directorio central (incluido un nombre de archivo de 1 byte)
  
• 1000 bytes por núcleo

Pero cada 1 MB de salida después de la primera cuesta solo 47 bytes: no necesitamos otro encabezado del archivo local u otra copia del núcleo, solo un encabezado adicional del directorio central. Por lo tanto, mientras que el primer enlace desde el núcleo tiene una relación de compresión de 1,000,000 / 1,078 ≈ 928, cada enlace adicional mueve el coeficiente más cerca de 1,000,000 / 47 ≈ 21,277, y un núcleo grande eleva el techo.

El problema con esta idea es la falta de compatibilidad. Dado que muchos encabezados del directorio central apuntan a un encabezado del archivo local, los metadatos (en particular, el nombre del archivo) no pueden ser los mismos para cada archivo. Algunos analizadores juran por esto . Por ejemplo, Info-ZIP UnZip (el programa de unzip estándar en Unix) recupera archivos, pero con advertencias:

  $ descomprimir overlap.zip
   inflado: A
 B: nombre de archivo "local" no coincidente (A),
          continuando con la versión del archivo "central"
   inflado: B
 ... 

Python zipfile también arroja una excepción :

  $ python3 -m archivo zip -e overlap.zip.
 Rastreo (última llamada más reciente):
 ...
 __main __. BadZipFile: El nombre del archivo en el directorio 'B' y el encabezado b'A 'difieren. 

A continuación, veremos cómo rediseñar la coherencia del nombre del archivo, al tiempo que conservamos la mayoría de los beneficios de la superposición de archivos.

Segundo descubrimiento: citando los encabezados de los archivos locales

Necesitamos separar los encabezados de los archivos locales para cada archivo, mientras reutilizamos un núcleo. Simplemente combinar todos los encabezados no funciona, porque el analizador zip encontrará el encabezado del archivo local donde espera el inicio de la secuencia DEFLATE. Pero la idea funcionará, con cambios menores. Utilizaremos la función DEFLATE de bloques sin comprimir para "citar" los encabezados de los archivos locales para que parezcan ser parte de la misma secuencia DEFLATE que termina en el núcleo. Cada encabezado del archivo local (excepto el primero) se interpretará de dos maneras: como código (parte de la estructura del archivo zip) y como datos (parte del contenido del archivo).



Una secuencia DEFLATE es una secuencia de bloques donde cada bloque se puede comprimir o descomprimir. Por lo general, solo pensamos en bloques comprimidos, por ejemplo, el núcleo es un gran bloque comprimido. Pero también hay otros sin comprimir que comienzan con un encabezado de 5 bytes con un campo de longitud, lo que simplemente significa: "imprime los siguientes n bytes al pie de la letra". Desempaquetar un bloque sin comprimir significa solo eliminar el encabezado de 5 bytes. Los bloques comprimidos y sin comprimir pueden mezclarse libremente en la secuencia DEFLATE. La salida es una concatenación de los resultados de desempaquetar todos los bloques en orden. El concepto de "sin comprimir" solo importa en el nivel DEFLATE; los datos del archivo aún se consideran "comprimidos" en el nivel zip, independientemente de qué bloques se utilicen.

La forma más fácil de imaginar este diseño es como una superposición interna, desde el último archivo hasta el primero. Comenzamos insertando un núcleo que formará el final del archivo de datos para cada archivo. Agregue el encabezado del archivo LFH _N local y el encabezado del directorio central de CDH _N que apunta a él. Establezca el campo de metadatos "tamaño comprimido" en LFH _N y CDH _N en el tamaño del núcleo comprimido. Ahora agregue el encabezado de 5 bytes del bloque sin comprimir (en verde en el diagrama), cuyo campo de longitud es igual al tamaño LFH _N. Agregue el segundo encabezado del archivo LFH local _{N −1} y el título del directorio central CDH _{N −1} , que apunta a él. Establezca el campo de metadatos "tamaño comprimido" como el nuevo encabezado para el tamaño del núcleo comprimido más el tamaño del encabezado del bloque sin comprimir (5 bytes) más el tamaño de LFH _N.

Por el momento, el archivo zip contiene dos archivos con los nombres Y y Z. Veamos qué verá el analizador al analizar. Supongamos que el tamaño del núcleo comprimido es de 1000 bytes y el tamaño LFH _N es de 31 bytes. Comenzamos con CDH _{N −1} y seguimos el signo de LFH _{N −1} . El nombre del primer archivo es Y, y el tamaño comprimido de su archivo de datos es 1036 bytes. Al interpretar los siguientes 1036 bytes como una secuencia DEFLATE, primero encontramos un encabezado de 5 bytes de un bloque sin comprimir que dice copiar los siguientes 31 bytes. Anotamos los siguientes 31 bytes, que son LFH _N , que desempaquetamos y agregamos al archivo Y. Avanzando en la secuencia DEFLATE, encontramos el bloque comprimido (kernel) que desempaquetamos en el archivo Y. Ahora hemos llegado al final de los datos comprimidos y hemos terminado con el archivo Y.

Pasando al siguiente archivo, seguimos el puntero desde CDH _N a LFH _N y encontramos un archivo llamado Z con un tamaño comprimido de 1000 bytes. Al interpretar estos 1000 bytes como una secuencia DEFLATE, inmediatamente encontramos un bloque comprimido (núcleo nuevamente) y lo descomprimimos en un archivo Z. Ahora hemos llegado al final del archivo final y hemos terminado. El archivo de salida Z contiene el kernel desempaquetado; el archivo de salida Y es el mismo, pero opcionalmente con un prefijo de 31 bytes LFH _N.

Completamos la construcción repitiendo el procedimiento de citas hasta que el archivo zip incluya el número requerido de archivos. Cada archivo nuevo agrega un encabezado de directorio central, un encabezado de archivo local y un bloque sin comprimir para citar directamente desde el siguiente encabezado de archivo local. Los datos de archivos comprimidos suelen ser una cadena de bloques DEFLATE sin comprimir (encabezados de archivos locales citados) seguidos de un núcleo comprimido. Cada byte en el núcleo aporta aproximadamente 1032 N al tamaño de salida, porque cada byte es parte de todos los N archivos. Los archivos de salida también son de diferentes tamaños: los anteriores son más grandes que los posteriores porque citan más los encabezados de los archivos locales. El contenido de los archivos de salida no tiene mucho sentido, pero nadie dijo que debería tener sentido.

Este diseño de citas superpuestas tiene una mejor compatibilidad que el diseño de superposición completa de la sección anterior, pero la compatibilidad se logra mediante la compresión. Allí, cada archivo agregado cuesta solo el título del directorio central, aquí cuesta el título del directorio central, el encabezado del archivo local y otros 5 bytes para el encabezado de cita.

Optimización

Habiendo recibido el diseño básico de la bomba Zip, intentaremos que sea lo más eficiente posible. Queremos responder dos preguntas:

• ¿Cuál es la relación de compresión máxima para un tamaño de archivo zip dado?
  
• ¿Cuál es la relación de compresión máxima dadas las limitaciones del formato zip?

Compresión del núcleo

Es beneficioso para nosotros comprimir el núcleo tanto como sea posible, porque cada byte desempaquetado se multiplica por N. Para este propósito, utilizamos un compresor DEFLATE personalizado llamado bulk_deflate, especializado en comprimir una cadena de bytes repetidos.

Todos los archivadores DEFLATE decentes se acercan a la relación de compresión de 1032 en una secuencia interminable de bytes repetidos, pero nos preocupa el tamaño específico. En nuestro tamaño de archivo, bulk_deflate contiene más datos que los archivadores de uso general: aproximadamente 26 KB más que zlib e Info-ZIP, y aproximadamente 15 KB más que Zopfli , lo que sacrifica la velocidad en aras de la calidad de compresión.



El precio de una alta relación de compresión bulk_deflate: la falta de versatilidad. Puede comprimir solo líneas de bytes repetidos y solo una cierta longitud, es decir, 517 + 258 k para un entero k ≥ 0. Además de una buena compresión, bulk_deflate funciona rápidamente, realizando el trabajo casi al mismo tiempo, independientemente del tamaño de los datos de entrada, contando el trabajo de escribir realmente una cadena comprimida.

Nombres de archivo

Para nuestros propósitos, los nombres de los archivos son casi de peso muerto. Aunque contribuyen al tamaño de salida al ser parte de los encabezados de los archivos locales entre comillas, los bytes en el nombre del archivo contribuyen mucho menos que los bytes en el núcleo. Queremos que los nombres de los archivos sean lo más cortos posible, a la vez que diferentes, sin olvidar la compatibilidad.

Cada byte gastado en un nombre de archivo significa dos bytes no gastados en el núcleo (dos porque cada nombre de archivo aparece dos veces: en el encabezado del directorio central y en el encabezado del archivo local). Un byte de nombre de archivo da como resultado un promedio de solo ( N + 1) / 4 bytes de salida, mientras que un byte en el núcleo cuenta como 1032 N. Ejemplos: 1 , 2 , 3 .

La primera consideración de compatibilidad es la codificación. La especificación del formato zip establece que los nombres de archivo deben interpretarse como CP 437 o UTF-8 si se establece un bit de bandera específico ( APPNOTE.TXT, apéndice D ). Este es el principal punto de incompatibilidad entre los analizadores zip, que pueden interpretar nombres de archivo en alguna codificación fija o específica de la localidad. Por lo tanto, por compatibilidad, es mejor limitarse a caracteres con la misma codificación tanto en CP 437 como en UTF-8. A saber, estos son 95 caracteres imprimibles US-ASCII.

También estamos sujetos a restricciones de nomenclatura del sistema de archivos. Algunos sistemas de archivos no distinguen entre mayúsculas y minúsculas, por lo que 'a' y 'A' no se consideran nombres diferentes. Los sistemas de archivos comunes, como FAT32, prohíben ciertos caracteres , como '*' y '?'.

Como un compromiso seguro, pero no necesariamente óptimo, nuestra bomba zip utilizará nombres de archivo del alfabeto de 36 caracteres, que no incluye caracteres especiales y caracteres de mayúsculas y minúsculas diferentes:

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

Los nombres de archivo se generan de manera obvia, todas las posiciones a su vez, con la adición de una posición al final del ciclo:

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

Hay 36 nombres de archivo de un carácter, 36² nombres de dos caracteres, etc. Cuatro bytes son suficientes para 1,727,604 nombres de archivo diferentes.

Dado que los nombres de archivo en el archivo generalmente tendrán diferentes longitudes, ¿cómo puedo ordenarlos mejor: del más corto al más largo o viceversa? Si piensa un poco, es mejor poner los nombres más largos al final. Esta clasificación agrega más de 900 MB de salida a zblg.zip , en comparación con el pedido más largo al más corto. Sin embargo, esta es una optimización menor, porque 900 MB es solo el 0,0003% del tamaño total del problema.

Tamaño del núcleo

El diseño de citas superpuestas le permite colocar un núcleo de datos comprimido y luego copiarlo de forma económica muchas veces. Para un tamaño específico del archivo zip X , ¿cuánto espacio es óptimo para asignar para almacenar el núcleo y cuánto para crear copias?

Para encontrar el equilibrio óptimo, necesita optimizar solo una variable N , el número de archivos en el archivo zip. Cada valor de N requiere una cierta cantidad de sobrecarga para los encabezados del directorio central, encabezados de archivos locales, encabezados de bloques de citas y nombres de archivos. El resto del espacio estará ocupado por el núcleo. Dado que N debe ser un número entero y solo puede colocar una cierta cantidad de archivos antes de que el tamaño del kernel caiga a cero, es suficiente verificar todos los valores posibles de N y seleccionar el que proporcione el mayor rendimiento.

La aplicación del procedimiento de optimización a X = 42,374 para 42.zip encuentra un máximo en N = 250. Estos 250 archivos requieren 21,195 bytes de sobrecarga, dejando 21,179 bytes para el núcleo. Un núcleo de este tamaño se descomprime en 21,841,249 bytes (relación 1031.3 a 1). 250 copias del kernel desempaquetado más algunos encabezados citados de archivos locales dan una salida total desempaquetada de 5,461,307,620 bytes y una relación de compresión de 129,000.

• zbsm.zip 42 kB → 5.5 GB

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

La optimización ha llevado a una distribución casi uniforme del espacio entre el núcleo y los encabezados de los archivos. Esto no es una coincidencia. Considere un modelo simplificado de una construcción de citas con superposición. En un modelo simplificado, ignoramos los nombres de los archivos, así como un ligero aumento en el tamaño del archivo de salida debido a la cita de los encabezados de los archivos locales. El análisis del modelo simplificado mostrará que la distribución óptima entre el núcleo y los encabezados de los archivos es aproximadamente uniforme, y el tamaño de salida con la distribución óptima crece de forma cuadrática dependiendo del tamaño de la entrada.

Definición de algunas constantes y variables:


Deje H (N) ser el volumen de la sobrecarga de encabezados para N archivos. Vea la tabla para comprender la esencia de la fórmula.

$$

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

Para el núcleo, quedan lugares X - H (N) . El tamaño total desempaquetado S _X (N) es igual al tamaño de N copias del kernel desempaquetado con la proporción C (en este modelo simplificado, ignoramos la leve extensión adicional de los encabezados de archivo locales mencionados).

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

S _X (N) es un polinomio en la parte N, por lo tanto, el máximo debe ser donde la derivada S ' _X (N) es igual a cero. Tomar la derivada y encontrar cero nos da N _OPT , el número óptimo de archivos.

$$$$ display $$ 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 $$ display $$

H (N _OPT ) proporciona la cantidad óptima de espacio para colocar encabezados de archivo. Es independiente de CDH, LFH y C y está cerca de X / 2 .

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

S _X (N _OPT ): tamaño total desempaquetado con distribución óptima. A partir de esto, vemos que el tamaño de la salida aumenta cuadráticamente al aumentar los datos de entrada.

$$

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

Al aumentar el tamaño del archivo zip, al final encontraremos los límites del formato zip: el archivo no puede tener más de 2 ¹⁶ −1 archivos con un tamaño de no más de 2 ³² −1 bytes cada uno. Peor aún, algunas implementaciones toman valores máximos como un indicador de la presencia de extensiones de 64 bits , por lo que nuestros límites son en realidad 2 ¹⁶ −2 y 2 ³² −2. Sucede que la primera vez que encontramos un límite en el tamaño de un archivo sin comprimir. Con un tamaño de archivo zip de 8 319 377 bytes, la optimización ingenua nos dará la cantidad de archivos 47 837 y un archivo máximo de 2 ³² +311 bytes.

(En realidad, todo es un poco más complicado, porque los límites exactos dependen de la implementación. El archivo zip de Python ignora la cantidad de archivos, archive / zip en Go permite aumentar la cantidad de archivos hasta que coincidan con los 16 bits inferiores. Pero para compatibilidad general, debemos adherirnos a límites establecidos).

Si no podemos aumentar infinitamente N o el tamaño del núcleo, nos gustaría encontrar la relación de compresión máxima dentro del formato zip. Debe hacer que el núcleo sea lo más grande posible con el número máximo de archivos. A pesar del hecho de que ya no podemos mantener una separación aproximadamente uniforme entre el núcleo y los encabezados de los archivos, cada archivo agregado todavía aumenta la relación de compresión, pero no tan rápido como si pudiéramos continuar aumentando el núcleo. De hecho, a medida que se agregan archivos, necesitaremos reducir el tamaño del kernel para liberar espacio para el tamaño máximo de archivo, que crece ligeramente con cada archivo agregado.

El plan lleva a un archivo zip con 2 ¹⁶ −2 archivos y un núcleo, que se descomprime en 2 ³² −2 178 825 bytes. Los archivos serán más grandes hacia el comienzo del archivo zip: el primer y más grande archivo se descomprime en 2 ³² −56 bytes. Esto es lo más cercano posible usando los parámetros de salida aproximada de bulk_deflate: codificar los 54 bytes finales costará más que su tamaño (el archivo zip en su conjunto tiene una relación de compresión de 28 millones, y los 54 bytes finales recibirán un máximo de 54 ⋅ 10 ³² ⋅ ( 2 ¹⁶ - 2) ≈ 36? 5 millones de bytes, por lo que esto solo ayuda si 54 bytes pueden codificarse en un byte, y no podría codificar menos de dos. Por lo tanto, si no puede codificar 54 bytes en 1 byte, solo reduce la relación de compresión). El tamaño de salida de esta bomba Zip es 281,395,456,244,934 bytes, 99.97% del máximo teórico (2 ³² - 1) × (2 ¹⁶ - 1). Cualquier mejora significativa en la relación de compresión se puede lograr solo reduciendo el tamaño de la señal de entrada y no aumentando la salida.

• zblg.zip 10 MB → 281 TB

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

Computación eficiente CRC-32

Entre los metadatos en el encabezado del directorio central y el encabezado del archivo local se encuentra una suma de verificación de los datos del archivo sin comprimir: CRC-32 . Esto plantea un problema porque la cantidad de cálculos de CRC-32 para cada archivo es proporcional a su tamaño, que es muy grande por defecto (después de todo, es una bomba zip). Preferiríamos hacer un trabajo que sea al menos proporcional al tamaño del archivo. Dos factores funcionan a nuestro favor: todos los archivos tienen un núcleo común y un núcleo sin comprimir es una cadena de bytes repetidos. Imagine CRC-32 como un producto matricial: esto nos permitirá no solo calcular rápidamente la suma de comprobación del núcleo, sino también reutilizar los cálculos entre archivos. El método descrito en esta sección es una pequeña extensión de la función crc32_combine en zlib, que Mark Adler explica aquí .

CRC-32 puede modelarse como una máquina de estado, actualizando un registro de estado de 32 bits para cada bit de entrada. Las operaciones básicas de actualización para los bits 0 y 1 son:

 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 representa el registro de estado como un vector binario de 32 elementos y usa XOR para crc32_update_0 y multiplicar, entonces crc32_update_0 es un mapeo lineal ; es decir, se puede representar como una multiplicación por una matriz binaria de transición 32 × 32. Para entender por qué, tenga en cuenta que multiplicar una matriz por un vector es simplemente sumar las columnas de la matriz después de multiplicar cada columna por el elemento correspondiente del vector. El state >> 1 operación de cambio state >> 1 simplemente toma cada bit i del vector de estado y lo multiplica por un vector que es cero en todas partes excepto el bit i - 1 (numerando los bits de derecha a izquierda). Relativamente hablando, el state ^ 0xedb88320 XOR final state ^ 0xedb88320 ocurre solo cuando el bit b es igual a uno. Esto se puede representar como la primera multiplicación de b por 0xedb88320, y luego XORing a este estado.

Además, crc32_update_1 es solo una crc32_update_0 plus (XOR).Esto hace crc32_update_1 una transformación afín : multiplicación de matrices seguida de mapeo (es decir, suma de vectores). Podemos imaginar la multiplicación y el mapeo de matrices en un solo paso, si aumentamos el tamaño de la matriz de transformación a 33 × 33 y agregamos un elemento adicional al vector de estado, que siempre es 1 (esta representación se denomina coordenadas homogéneas ).


Las matrices de transformación son 33 × 33 M ₀ y M ₁ , que calculan el cambio de estado CRC-32 realizado por los bits 0 y 1, respectivamente. Los vectores de columna se almacenan con el bit más significativo a continuación: leyendo la primera columna de abajo hacia arriba, verá la constante polinómica CRC-32 edb8832016 = 111 0 11 0 110 111 000 1 00000 11 00 1 00000 ₂ . Estas dos matrices difieren solo en la columna final, que representa el vector de traducción en coordenadas homogéneas. En M _{0, la} traducción es cero, y en M ₁ es edb88320 ₁₆ , la constante polinómica es CRC-32. Las unidades son inmediatamente por encima del estado diagonal de la operaciónstate >> 1

Ambas operacionescrc32_update_0ycrc32_update_1pueden ser representados por la matriz de transición de 33 × 33. Se muestran las matrices M ₀ y M ₁ .. La ventaja de la representación matricial es que las matrices se pueden multiplicar. Supongamos que queremos ver un cambio de estado realizado al procesar un carácter ASCII 'a', cuya representación binaria es 01100001 ₂ . Podemos imaginar el cambio acumulativo en el estado del CRC-32 de estos ocho bits en una matriz de transformación:

$$

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

Y podemos imaginar un cambio en el estado de una fila repitiendo 'a' multiplicando muchas copias de M _a , elevando la matriz a una potencia. Podemos hacer esto de forma rápida utilizando el algoritmo de exponenciación rápida , lo que permite calcular el M ⁿ sólo tiene que entrar ₂ ⁿ pasos. Por ejemplo, aquí hay una matriz para cambiar el estado de una cadena de 9 caracteres '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$$

El algoritmo de multiplicación rápida de matriz es útil para calcular el _núcleo M , una matriz para un núcleo sin comprimir, ya que el núcleo es una cadena de bytes repetidos. Para obtener la suma de verificación CRC-32 de la matriz, multiplique la matriz por el vector cero (el vector cero está en coordenadas uniformes, es decir 32 ceros, y luego la unidad; aquí omitimos la ligera complicación del procesamiento previo y posterior de la suma de verificación para verificar el cumplimiento). Para calcular la suma de verificación para cada archivo, trabajamos en la dirección opuesta. Comenzamos inicializando M: = M _kernel . La suma de comprobación del núcleo también es la suma de comprobación del archivo final N , por lo que multiplicamos Mun vector y almacena cero la suma de comprobación recibida en el CDH _N y LFH _N . Los datos del archivo N - 1 son los mismos que los del archivo N , pero con el prefijo LFH _N agregado . Por lo tanto, calculamos$$M L F H N , matriz de cambio de estado para LFH_Ny actualización$M_{L{FH_N}}$$$$M := M M_{L{FH_N}}$ .Ahora M representa el cambio acumulativo en el estado del procesamiento de LFH _N detrás del núcleo. Calculamos la suma de comprobación para el archivo N - 1 , multiplicando nuevamente M por el vector cero. Continuamos el procedimiento acumulando matrices de cambio de estado en M hasta que se procesen todos los archivos.

Extensión: Zip64

Anteriormente, nos enfrentamos al problema de la expansión debido a las limitaciones del formato zip: era imposible emitir más de 281 TB, independientemente de cuán inteligente fuera el paquete zip. Puedes trascender estos límites usando Zip64, una extensión de formato zip que aumenta el tamaño de algunos campos de encabezado a 64 bits. La compatibilidad con Zip64 no es universal, pero es una de las extensiones implementadas más comúnmente. En cuanto a la relación de compresión, el efecto de Zip64 es aumentar el tamaño del encabezado del directorio central de 46 a 58 bytes, y el tamaño del encabezado del directorio local de 30 a 50 bytes. Al observar la fórmula del coeficiente de expansión óptimo en un modelo simplificado, vemos que la bomba zip en el formato Zip64 todavía crece de forma cuadrática, pero más lenta debido al denominador más grande; esto se puede ver en el siguiente diagrama. Debido a la pérdida de compatibilidad y el retraso del crecimiento, eliminamos casi cualquier restricción en el tamaño del archivo.

Supongamos que necesitamos una bomba zip que se expande a 4.5 PB, como 42.zip. ¿Qué tan grande debe ser el archivo? Usando la búsqueda binaria, encontramos que el tamaño mínimo de dicho archivo es de 46 MB.

• zbxl.zip 46 MB → 4.5 PB (Zip64, menos compatible)

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

4.5 petabytes: el telescopio Event Horizon registró aproximadamente la misma cantidad de datos para la primera imagen de un agujero negro : bastidores y bastidores con discos duros en el centro de datos.

Con Zip64, casi no es interesante considerar la relación de compresión máxima, porque simplemente podemos continuar aumentando el tamaño del archivo zip y la relación de compresión con él, hasta que incluso el archivo zip comprimido se vuelva prohibitivo. Sin embargo, un umbral interesante es de 2 ⁶⁴ bytes (18 EB o 16 EiB), por lo que muchos datos no caben en la mayoría de los sistemas de archivos. La búsqueda binaria encuentra la bomba zip más pequeña que produce al menos la misma cantidad de salida: contiene 12 millones de archivos y un núcleo comprimido de 1,5 GB. El tamaño total del archivo zip es de 2.9 GB y se descomprime en 2 ⁶⁴+11 727 895 877 bytes con una relación de compresión de más de 6.2 mil millones a uno. No cargué este archivo para descargarlo, pero puede generarlo usted mismo utilizando el código fuente . Tiene archivos de tal tamaño que incluso un error fue revelado en Info-ZIP UnZip 6.0.

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

Extensión: bzip2

DEFLATE es el algoritmo de compresión más común para el formato zip, pero esta es solo una de las muchas opciones. Probablemente el segundo algoritmo más común es bzip2 . Aunque no es tan compatible como DEFLATE. Teóricamente, en bzip2, la relación de compresión máxima es de aproximadamente 1,4 millones a uno, lo que permite un relleno más denso del núcleo.

bzip2 primero codifica la "codificación de longitud de ejecución", reduciendo la longitud de la cadena de bytes repetidos en 51 veces. Luego, los datos se dividen en bloques de 900 KB y cada bloque se comprime por separado. Teóricamente, un bloque puede comprimir hasta 32 bytes. 900 000 × 51/32 = 1 434 375.

Ignorando la pérdida de compatibilidad, ¿bzip2 hace una bomba más efectiva?

Sí, pero solo para archivos pequeños. El problema es que en bzip2 no hay nada como los bloques DEFLATE sin comprimir que utilizamos para citar los encabezados de los archivos locales. Por lo tanto, es imposible superponer archivos y reutilizar el kernel; para cada archivo debe escribir su propia copia, por lo que la relación de compresión general no será mejor que la relación para un solo archivo. En el gráfico a continuación, vemos que sin superposición, bzip2 es superior a DEFLATE solo para archivos de un tamaño aproximado de megabytes.

Solo hay esperanza de un medio alternativo para citar encabezados en bzip2, que se discute en la siguiente sección. Además, si sabe que un analizador zip particular es compatible con bzip2 ypermite nombres de archivo no coincidentes, puede usar la construcción de superposición completa, que no necesita ser citada.


Comparación de la relación de compresión de diferentes bombas zip. Presta atención al eje logarítmico. Cada diseño se muestra con y sin Zip64. Las estructuras sin superposición tienen una tasa de crecimiento lineal, que se puede ver a partir de la relación constante de los ejes. El desplazamiento vertical del gráfico bzip2 significa que la relación de compresión de bzip2 es aproximadamente mil veces mayor que la de DEFLATE. Las construcciones DEFLATE citadas tienen una tasa de crecimiento cuadrática, como lo demuestra una inclinación a los ejes 2: 1. La variante Zip64 es ligeramente menos efectiva, pero permite más de 281 TB. Los gráficos para bzip2 con comillas a través de un campo adicional van de cuadrático a lineal cuando se alcanza el tamaño máximo de archivo (2 ³² −2 bytes), o el número máximo permitido de archivos

Extensión: citando a través de un campo adicional

Hasta ahora, hemos utilizado la función DEFLATE para citar los encabezados de los archivos locales, y acabamos de ver que este truco no funciona en bzip2. Sin embargo, existe un método alternativo de citas, algo más limitado, que usa solo funciones de formato zip y es independiente del algoritmo de compresión.

Al final de la estructura de encabezado del archivo local, hay un campo adicional de longitud variable para almacenar información que no cabe en los campos de encabezado habituales ( APPNOTE.TXT, sección 4.3.7) La información adicional puede incluir, por ejemplo, una marca de tiempo o uid / gid de Unix. La información de Zip64 también se almacena en un campo adicional. Un campo adicional se representa como una estructura de valor de longitud; Si aumenta la longitud sin agregar un valor, el campo adicional incluirá lo que está detrás de él en el archivo zip, es decir, el siguiente encabezado del archivo local. Con este método, cada encabezado del archivo local puede "citar" los siguientes encabezados, encerrándolos en su propio campo adicional. En comparación con DEFLATE, hay tres ventajas:

1. Citar a través de un campo adicional requiere solo 4 bytes, no 5, dejando más espacio para el núcleo.
   
2. No aumenta el tamaño del archivo, lo que significa un núcleo más grande, dadas las limitaciones del formato zip.
   
3. Proporciona citas en bzip2.

A pesar de estas ventajas, las citas a través de campos adicionales son menos flexibles. Esto no es una cadena, como en DEFLATE: cada encabezado de un archivo local debe contener no solo el encabezado inmediatamente siguiente, sino también todos los encabezados posteriores. Los campos adicionales aumentan a medida que se acerca al comienzo del archivo zip. Como la longitud máxima del campo es de 2 ¹⁶ −1 bytes, solo se pueden citar hasta 1808 encabezados de archivos locales (o 1170 en Zip64), suponiendo que los nombres se asignen como se esperaba(en el caso de DEFLATE, puede usar un campo adicional para citar los primeros encabezados (más cortos) de los archivos locales y luego cambiar a citar DEFLATE para el resto). Otro problema: para corresponder con la estructura de datos interna del campo adicional, es necesario seleccionar una etiqueta de 16 bits para el tipo ( APPNOTE.TXT, sección 4.5.2 ) que precede a los datos de citas. Queremos seleccionar una etiqueta de tipo que haga que los analizadores ignoren los datos entre comillas, en lugar de intentar interpretarlos como metadatos significativos. Los analizadores zip deben ignorar las etiquetas de un tipo desconocido, por lo que podemos seleccionar etiquetas al azar, pero existe el riesgo de que en el futuro alguna etiqueta viole la compatibilidad del diseño.

El diagrama anterior ilustra la posibilidad de usar campos adicionales en bzip2, c y sin Zip64. En ambos gráficos hay un punto de inflexión, cuando el crecimiento pasa de cuadrático a lineal. Sin Zip64, esto sucede cuando se alcanza el tamaño máximo del archivo sin comprimir (2 ³²−2 bytes); entonces solo puede aumentar la cantidad de archivos, pero no su tamaño. El gráfico termina completamente cuando el número de archivos llega a 1809, luego nos quedamos sin espacio en un campo adicional para citar encabezados adicionales. Con Zip64, se produce una fractura en 1171 archivos, después de lo cual solo se puede aumentar el tamaño del archivo, pero no su número. Un campo adicional ayuda en el caso de DEFLATE, pero la diferencia es tan pequeña que no se nota visualmente. Aumenta la relación de compresión de zbsm.zip en un 1,2%; zblg.zip en 0.019%; y zbxl.zip en 0.0025%.

La discusión

En su trabajo sobre este tema, Pletz y sus colegas utilizan la superposición de archivos para crear un archivo zip casi autorreplicante. La superposición de archivos en sí fue sugerida anteriormente (diapositiva 47) por Ginvael Coldwind.

Desarrollamos un diseño de una bomba zip con una superposición de citas teniendo en cuenta la compatibilidad, una serie de diferencias en las implementaciones, algunas de las cuales se muestran en la tabla a continuación. El diseño resultante es compatible con los analizadores zip que funcionan de la manera habitual, es decir, primero verificando el directorio central y usándolo como índice de archivos. Entre ellos, un exclusivo analizador zip de Nailque se genera automáticamente a partir de la gramática formal. Sin embargo, el diseño es incompatible con los analizadores de "transmisión", que analizan el archivo zip de principio a fin en una sola pasada sin leer primero el directorio central. Por su naturaleza, los analizadores de transmisión no permiten que los archivos se superpongan de ninguna manera. Lo más probable es que solo extraigan el primer archivo. Además, incluso pueden arrojar un error, como es el caso de sunzip , que analiza el directorio central al final y comprueba la coherencia con los encabezados de los archivos locales que ya ha visto.

Si desea que los archivos extraídos comiencen con un prefijo específico que sea diferente de los bytes del encabezado del archivo local, puede insertar un bloque DEFLATE antes del bloque sin comprimir que cita el siguiente encabezado. No todos los archivos en el archivo zip deben participar en la creación de la bomba: puede incluir archivos ordinarios en el archivo, si es necesario, para corresponder a algún formato especial (hay un parámetro en el código fuente --templatepara este caso de uso). Muchos formatos usan zip como contenedor, como documentos Java JAR, Android APK y LibreOffice.

Pdfen muchos sentidos similar a zip. Tiene una tabla de referencia cruzada al final del archivo que apunta a objetos anteriores, y admite la compresión de objetos a través del filtro FlateDecode. No lo he intentado, pero puedes usar la idea de citar con superposición para hacer una bomba PDF. Quizás ni siquiera tenga que trabajar mucho: binaryhax0r escribe en un blog que simplemente puede especificar varias capas de FlateDecode en un objeto, después de lo cual crear una bomba PDF se vuelve trivial.

Definir una clase particular de bombas zip descritas en este artículo es fácil: solo encuentre los archivos superpuestos. Mark Adler escribió un parchepara descomprimir Info-ZIP, que hace exactamente eso. Sin embargo, en general, el bloqueo de archivos superpuestos no protege contra todas las clases de bombas zip. Es difícil predecir de antemano si el archivo es una bomba zip o no si no tiene un conocimiento preciso sobre los componentes internos de los analizadores que se utilizarán para analizarlo. Mirar los encabezados y sumar los campos de "tamaño sin comprimir" de todos los archivos no funciona , porque el valor en los encabezados puede no coincidir con el tamaño real sin comprimir (en la tabla de compatibilidad, vea la línea "permite que el archivo sea demasiado pequeño"). La protección confiable contra las bombas zip incluye límites de tiempo, memoria y espacio en disco en el analizador zip durante su funcionamiento. Tome el análisis de archivos zip, como cualquier operación compleja con datos no confiables, con precaución.


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

Agradecimientos

Gracias a Mark Adler , Russ Cox , Brandon Enright , Marek Maykovsky , Josh Wolfe y los revisores de USENIX WOOT 2019 por sus comentarios sobre el borrador de este artículo. Kaolan McNamara evaluó el impacto de las bombas zip en la seguridad de LibreOffice.

Se ha preparado una versión de este artículo para el Taller USENIX WOOT 2019 . El código fuente está disponible. Los artefactos para la presentación en el taller se encuentran en el archivo zipbomb-woot19.zip .

¿Encontraste un sistema que arroja una de las bombas? ¿Las bombas lo ayudaron a encontrar un error o ganar dinero en un programa de búsqueda de errores? Avísame, intentaré mencionarlo aquí.

LibreOffice 6.1.5.2

Después de cambiar el nombre de zblg.zip a zblg.odt o zblg.docx, LibreOffice crea y elimina una serie de archivos temporales de aproximadamente 4 GB, tratando de determinar el formato del archivo. Finalmente, termina de hacer esto y elimina los archivos temporales a medida que llegan, por lo que la bomba zip solo causa un DoS temporal sin llenar el disco. Kaolan McNamara respondió mi mensaje de error.

Servidor de complementos de Mozilla 2019.06.06

Intenté bombas zip contra la instalación local de addons-server, que es parte del software addons.mozilla.org. El sistema maneja con gracia la bomba, imponiendo un límite de tiempo de 110 segundos para la extracción de archivos. La bomba zip se expande rápidamente, siempre que el disco permita este límite de tiempo, pero luego el proceso se anula y los archivos desempaquetados se borran automáticamente.

Descomprimir 6.0

Mark Adler escribió un parche para UnZip para detectar esta clase de bombas zip.

5 de julio de 2019: noté que CVE-2019-13232 fue asignado a UnZip. Personalmente, diría que la capacidad / incapacidad de UnZip (o cualquier analizador zip) para procesar este tipo de bomba zip es necesariamente una vulnerabilidad o incluso un error. Esta es una implementación natural que no viola la especificación, ¿qué puedo decir? El tipo de bomba en este artículo es solo un tipo, y hay muchas otras formas en que puedes descifrar un analizador zip. Como se mencionó anteriormente, si desea protegerse de los ataques de agotamiento de recursos, no debe intentar enumerar, detectar y bloquear cada ataque conocido; más bien, es necesario establecer restricciones externas sobre el tiempo y otros recursos para que el analizador no entre en tal situación, independientemente del tipo de ataque que haya encontrado. No hay nada de malo en tratar de detectar y rechazar ciertos diseños como una optimización del primer paso,pero no puedes parar ahí. A menos que termine aislando y restringiendo las operaciones con datos no confiables, su sistema probablemente aún sea vulnerable. Considere la analogía con las secuencias de comandos entre sitios en HTML: la protección correcta no es tratar de filtrar bytes específicos que se pueden interpretar como código, sino evitar todo correctamente.

Motores antivirus

El usuario de Twitter @TVqQAAMAAAAEAAA informa : "El antivirus de McAfee en mi máquina de prueba acaba de explotar". No lo he probado yo mismo y no tengo detalles como el número de versión.

Tavis Ormandi indica que VirusTotal tiene varios tiempos de espera para zblg.zip ( captura de pantalla del 6 de junio de 2019 ): AhnLab-V3, ClamAV, DrWeb, Endgame, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, McAfee-GW -Edition, Panda, Qihoo-360, Sophos ML, VBA32. Resultados para zbsm.zip ( captura de pantalla del 6 de junio de 2019) son similares, pero con un conjunto diferente de motores de tiempo de espera: Baido, Bkav, ClamAV, CMC, DrWeb, Endgame, ESET-NOD32, F-Secure, GData, Kingsoft, McAfee-GW-Edition, NANO-Antivirus, Acronis. Curiosamente, no hay tiempos de espera en los resultados de zbxl.zip ( captura de pantalla del 6 de junio de 2019 ). ¿Quizás algunos antivirus no son compatibles con Zip64? Varios motores detectan archivos como una especie de "bomba de compresión". Es interesante ver si continuarán haciéndolo con cambios menores, como cambiar los nombres de los archivos o agregar un prefijo ASCII a cada archivo.

Declaración final

Es hora de poner fin a Facebook. Este no es un trabajo neutral para ti: todos los días, cuando vienes a trabajar, estás haciendo algo mal. Si tiene una cuenta de Facebook, elimínela. Si trabajas en Facebook, despídete.

Y no olvide que la Agencia de Seguridad Nacional debe ser destruida.