Zlib DEFLATE bomba de descompresión

9

¿Me puede dar un ejemplo de una cadena de datos corta que, cuando se descomprime utilizando el método DEFLATE de Zlib, se expande a algo mucho más largo?

Más precisamente: ¿cuál es la bomba de descompresión más desagradable que uno puede construir para DEFLATE de Zlib? La figura del mérito aquí es la relación de compresión. Si el archivo comprimido tiene una longitud de n bytes, y después de la descompresión produce algo de m bytes, la relación de compresión es m / n . Estoy buscando algo que maximice la relación de compresión, donde espero que los datos comprimidos sean muy cortos. ¿Alguien puede darme un ejemplo de una bomba de descompresión?

Relacionado: Esta publicación afirma que DEFLATE puede aproximarse asintóticamente a una relación de compresión de 1032; ¿Es lo mejor que se puede hacer, o se puede lograr una mayor relación de compresión si seleccionamos una secuencia de bytes comprimidos cuidadosamente elegidos? Libpng defiende contra bombas de descompresión imponiendo límites de recursos, pero no dan un ejemplo concreto de una bomba de descompresión específica. Vea también zip bombas , el ataque correspondiente pero para el formato de archivo ZIP.

    
pregunta D.W. 06.02.2014 - 23:55
fuente

2 respuestas

6

La fuente de la cifra "1032: 1" se encuentra en el sitio zlib donde se indica que:

  

El límite viene del hecho de que un par de longitud / distancia puede representar como máximo 258 bytes de salida. Una longitud requiere al menos un bit y una distancia requiere al menos un bit, por lo que dos bits pueden dar 258 bytes de salida, u ocho bits dar 1032 bytes de salida. Un bloque dinámico no tiene restricción de longitud, por lo que podría acercarse arbitrariamente al límite de 1032: 1.

Esta es una cita de Mark Adler, uno de los dos diseñadores de zlib. Habiendo implementado una biblioteca para Deflate, puedo confirmar que, dado el funcionamiento del el algoritmo , este límite asintótico es ciertamente verdadero ( no puedes ir más allá, pero puedes acercarte lo más que quieras). Desinfle las obras codificando "copias": cada elemento es un nuevo byte o una copia de una secuencia pasada; las copias pueden superponerse (es decir, puede copiar una secuencia de longitud 30 en la distancia 4, lo que produce 15 veces la secuencia pasada de 4 bytes); Los códigos de Huffman se aplican en la secuencia de elementos. Para obtener una "copia" de longitud mínima, necesita superponerse mucho, y cada copia vale como máximo 258 bytes. Por lo tanto, los datos que deben comprimirse tendrán que ser una larga cadena de bytes idénticos.

Como dice @Steffen, al comprimir con gzip una larga secuencia de ceros producirá una relación de compresión de más de 1000: 1. No tiene que ser ceros; cualquier secuencia que consista en el mismo valor de byte una y otra vez hará el truco; pero una máquina Linux tiene un /dev/zero , no un /dev/fortytwo .

Las "bombas de compresión" ya estaban activas hace bastante tiempo; Lo vi empleado para matar a Netscape en 1996 (en ese momento, Netscape manejaba imágenes de fondo, pero Mosaic no lo hizo; un archivo GIF muy pequeño podía codificar un fondo enorme, que Netscape asignó como un solo gran mapa de píxeles en el servidor X11).

    
respondido por el Thomas Pornin 07.02.2014 - 13:32
fuente
4

gzip utiliza zlib deflate. Para crear una bomba ab 10k a partir de 10M de entrada, puede utilizar

dd if=/dev/zero  bs=1024 count=$((10*1024)) | gzip -9 > bomb.gz

Y creo que la publicación tiene razón al afirmar que tiene una proporción máxima de aproximadamente 1000. Más información en enlace (antiguo) pero enlace muestra que la mayoría de los navegadores modernos todavía no tienen protección contra it.

    
respondido por el Steffen Ullrich 07.02.2014 - 00:32
fuente

Lea otras preguntas en las etiquetas