Bomba di decompressione Zlib DEFLATE

9

Puoi darmi un esempio di una breve stringa di dati che, quando decompressa usando il metodo DEFLATE di Zlib, si espande a qualcosa di molto più lungo?

Più precisamente: qual è la bomba da decompressione peggiore che si possa costruire per DEFLATE di Zlib? La figura di merito qui è il rapporto di compressione. Se il file compresso è lungo n byte e dopo la decompressione restituisce qualcosa m byte, il rapporto di compressione è m / n . Sto cercando qualcosa che massimizzi il rapporto di compressione, dove si spera che i dati compressi siano molto brevi. Qualcuno può darmi un esempio di una tale bomba da decompressione?

Correlati: Questo post afferma che DEFLATE può avvicinarsi asintoticamente ad un rapporto di compressione di 1032; è che il migliore può fare o si può ottenere un rapporto di compressione più alto se selezioniamo una sequenza accuratamente scelta di byte compressi? Libpng difende contro le bombe di decompressione imponendo limiti di risorse, ma non fornisce un esempio concreto di una bomba di decompressione specifica. Vedi anche zip bomb , l'attacco corrispondente ma per il formato di file ZIP.

    
posta D.W. 06.02.2014 - 23:55
fonte

2 risposte

6

La fonte della figura "1032: 1" è data nel sito zlib dove viene detto che:

The limit comes from the fact that one length/distance pair can represent at most 258 output bytes. A length requires at least one bit and a distance requires at least one bit, so two bits in can give 258 bytes out, or eight bits in give 1032 bytes out. A dynamic block has no length restriction, so you could get arbitrarily close to the limit of 1032:1.

Questa è una citazione di Mark Adler, uno dei due designer di zlib. Avendo implementato una libreria per Deflate, posso confermare che, dato come funziona l'algoritmo , questo limite asintotico è vero ( non puoi andare oltre, ma puoi avvicinarti quanto vuoi). Deflate funziona codificando "copie": ogni elemento è un nuovo byte o una copia di una sequenza passata; le copie possono sovrapporsi (ad esempio è possibile copiare una sequenza di lunghezza 30 alla distanza 4, ottenendo 15 volte la sequenza passata di 4 byte); I codici di Huffman sono applicati sulla sequenza di elementi. Per ottenere una "copia" di lunghezza minima, è necessario che si sovrapponga molto, e ogni copia vale al massimo 258 byte. Quindi i dati che devono essere compressi dovranno essere una lunga stringa di byte identici.

Come dice @Steffen, comprimendo con gzip una lunga sequenza di zeri si otterrà un rapporto di compressione più di 1000: 1. Non deve essere zero; qualsiasi sequenza costituita dallo stesso valore byte più e più farà il trucco; ma una macchina Linux ha un /dev/zero , non un /dev/fortytwo .

"Bombe a compressione" erano già attive da molto tempo; L'ho visto impiegare per uccidere Netscape nel 1996 (a quel tempo Netscape gestiva le immagini di sfondo, ma Mosaic no: un file GIF molto piccolo poteva codificare uno sfondo enorme, che Netscape assegnava come una singola grande pixmap nel server X11).

    
risposta data 07.02.2014 - 13:32
fonte
4

zlib deflate è usato da gzip. Per creare una bomba ab 10k con un input da 10 M, puoi usare

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

E penso che il post abbia ragione nel sostenere che hai un rapporto massimo di circa 1000. Altre informazioni sono disponibili su link (vecchio) ma link mostra che la maggior parte dei browser moderni non ha ancora protezione contro esso.

    
risposta data 07.02.2014 - 00:32
fonte

Leggi altre domande sui tag