O artigo mostra como criar uma bomba zip não recursiva que fornece um alto grau de compactação ao sobrepor arquivos dentro de um contêiner zip. “Não recursivo” significa que ele não depende da descompactação dos arquivos descompactados anexados aos arquivos zip: existe apenas uma rodada. O tamanho da saída aumenta quadraticamente a partir da entrada, atingindo uma taxa de compressão superior a 28 milhões (10 MB → 281 TB) no formato zip. É possível expandir ainda mais com extensões de 64 bits. O design usa apenas o algoritmo de compactação DEFLATE mais comum e é compatível com a maioria dos analisadores de zip.

• zbsm.zip 42 kB → 5,5 GB
  
• zblg.zip 10 MB → 281 TB
  
• zbxl.zip 46 MB → 4.5 PB (Zip64, menos compatível com analisadores)

Código fonte:

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

zipbomb-20190702.zip

Dados e fonte de ilustrações:

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

<sub>* Existem duas versões do 42.zip: os antigos 42 374 bytes e os 42 428 bytes mais recentes . A diferença é que o novo requer uma senha antes de desembalar. Nós comparamos apenas com a versão antiga. Aqui está uma cópia do arquivo, se necessário: 42.zip .

** Gostaria de saber e indicar o autor do 42.zip, mas não o encontrei - informe-me se você tiver alguma informação.</sub>

As bombas zip devem superar o fato de que o algoritmo de compactação DEFLATE mais frequentemente suportado pelos analisadores não pode exceder a taxa de compactação de 1032 a 1. Por esse motivo, as bombas zip geralmente confiam na descompressão recursiva, inserindo arquivos zip em arquivos zip para obter uma taxa adicional 1032 com cada camada. Mas o truque só funciona em implementações que se descomprimem recursivamente, e a maioria não. A bomba 42.zip mais famosa se expande para um formidável 4.5 PB, se todas as seis camadas forem descompactadas recursivamente, mas na camada superior ela tem 0,6 MB em tamanho insignificante. Os tirolesas, como os de Cox e Ellingsen , emitem uma cópia de si mesmos e, assim, se expandem indefinidamente quando descompactados recursivamente. Mas eles também são completamente seguros ao desembalar uma vez.

Este artigo mostra como criar uma bomba zip não recursiva, cuja taxa de compactação excede o limite DEFLATE de 1032. Ele funciona sobrepondo arquivos dentro de um contêiner zip para referenciar o "núcleo" de dados altamente compactados em vários arquivos sem fazer várias cópias. O tamanho da saída da bomba zip cresce quadraticamente a partir do tamanho da entrada; isto é, a taxa de compressão melhora com o aumento do tamanho da bomba. O design depende dos recursos de zip e DEFLATE: não pode ser transferido diretamente para outros formatos de arquivo ou algoritmos de compactação. A bomba é compatível com a maioria dos analisadores de zip, exceto os de "streaming", que analisam arquivos de uma só vez sem verificar o diretório central do arquivo zip. Tentamos equilibrar dois objetivos conflitantes:

• Aumente a taxa de compactação. Definimos a taxa de compactação como a soma dos tamanhos de todos os arquivos no arquivo dividido pelo tamanho do próprio arquivo zip. Ele não leva em consideração nomes de arquivos ou outros metadados do sistema de arquivos, mas apenas o conteúdo.
  
• Mantenha a compatibilidade. Zip é um formato complexo e os analisadores diferem, especialmente em situações limítrofes e funções adicionais. Não use técnicas que funcionem apenas com determinados analisadores. Vamos observar algumas maneiras de aumentar a eficiência de uma bomba zip com uma certa perda de compatibilidade.

Estrutura do arquivo zip

O arquivo zip consiste em um diretório central de links de arquivos.



O diretório central está no final do arquivo zip. Esta é uma lista dos cabeçalhos de diretório central . Cada cabeçalho do diretório central contém metadados para um único arquivo, como o nome do arquivo e a soma de verificação CRC-32, além de um ponteiro para o cabeçalho do arquivo local. O cabeçalho do diretório central tem um comprimento de 46 bytes mais o comprimento do nome do arquivo.

O arquivo consiste no cabeçalho do arquivo local, seguido pelos dados do arquivo compactado. O comprimento do cabeçalho do arquivo local é de 30 bytes, mais o comprimento do nome do arquivo. Ele contém uma cópia redundante dos metadados do cabeçalho do diretório central, bem como os tamanhos dos arquivos de dados compactados e descompactados por trás dele. Zip é um formato de contêiner, não um algoritmo de compactação. Os dados de cada arquivo são compactados usando o algoritmo especificado nos metadados - geralmente DEFLATE .

Esta descrição do formato zip omite muitos detalhes que não são necessários para entender a bomba zip. Para obter informações completas, consulte a seção 4.3 APPNOTE.TXT ou a Estrutura do arquivo PKZip de Florian Buchholz, ou consulte o código-fonte .

Redundância significativa e muitas ambiguidades no formato zip abrem oportunidades para travessuras de diferentes tipos. Uma bomba zip é apenas a ponta do iceberg. Links para leitura adicional:

• “Dez mil armadilhas de segurança: um formato ZIP”, de Ginwael Coldwind
  
• A análise de zip ambígua permite ocultar os arquivos complementares do Firefox do linter e das pessoas : minha vulnerabilidade em addons.mozilla.org

Primeira descoberta: sobreposição de arquivos

Ao compactar uma longa sequência de bytes repetidos, podemos criar um núcleo de dados altamente compactados. A taxa de compactação do próprio kernel não pode exceder o limite DEFLATE de 1032, portanto, precisamos de uma maneira de reutilizar o kernel em muitos arquivos, sem criar uma cópia separada em cada arquivo. Podemos fazer isso sobrepondo arquivos: faça com que muitos cabeçalhos do diretório central aponte para um único arquivo cujos dados sejam o núcleo.



Considere um exemplo de como esse design afeta a taxa de compactação. Suponha que um núcleo de 1000 bytes seja descompactado em 1 MB. Em seguida, o primeiro megabyte de saída "custa" 1078 bytes de dados de entrada:

• 31 bytes para o cabeçalho do arquivo local (incluindo o nome do arquivo de 1 byte)
  
• 47 bytes para o cabeçalho do diretório central (incluindo um nome de arquivo de 1 byte)
  
• 1000 bytes por núcleo

Mas cada 1 MB de saída após o primeiro custa apenas 47 bytes - não precisamos de outro cabeçalho do arquivo local ou de outra cópia do kernel, apenas de um cabeçalho adicional do diretório central. Assim, enquanto o primeiro link do núcleo tem uma taxa de compressão de 1.000.000 / 1.078 ± 928, cada link adicional move o coeficiente para mais perto de 1.000.000 / 47 × 21.277, e um núcleo grande eleva o teto.

O problema com essa idéia é a falta de compatibilidade. Como muitos cabeçalhos do diretório central apontam para um cabeçalho do arquivo local, os metadados (em particular, o nome do arquivo) não podem ser os mesmos para cada arquivo. Alguns analisadores juram isso . Por exemplo, o Info-ZIP UnZip (o programa padrão de unzip no Unix) recupera arquivos, mas com avisos:

  $ unzip overlap.zip
   inflar: A
 B: nome de arquivo "local" incompatível (A),
          continuando com a versão do arquivo "central"
   inflar: B
 ... 

O zipfile do Python também gera uma exceção :

  $ python3 -m zipfile -e overlap.zip.
 Traceback (última chamada mais recente):
 ...
 __main __. BadZipFile: O nome do arquivo no diretório 'B' e o cabeçalho b'A 'diferem. 

A seguir, veremos como redesenhar a consistência do nome do arquivo, preservando a maioria dos benefícios da sobreposição de arquivos.

Segunda descoberta: citando os cabeçalhos dos arquivos locais

Precisamos separar os cabeçalhos dos arquivos locais para cada arquivo, enquanto reutilizamos um núcleo. Simplesmente combinar todos os cabeçalhos não funciona, porque o analisador zip encontrará o cabeçalho do arquivo local onde espera o início do fluxo DEFLATE. Mas a idéia funcionará, com pequenas mudanças. Usaremos a função DEFLATE de blocos não compactados para "citar" os cabeçalhos dos arquivos locais, para que pareçam fazer parte do mesmo fluxo DEFLATE que termina no kernel. Cada cabeçalho do arquivo local (exceto o primeiro) será interpretado de duas maneiras: como código (parte da estrutura do arquivo zip) e como dados (parte do conteúdo do arquivo).



Um fluxo DEFLATE é uma sequência de blocos em que cada bloco pode ser compactado ou descompactado. Normalmente pensamos apenas em blocos compactados, por exemplo, o kernel é um grande bloco compactado. Mas também existem os descompactados que começam com um cabeçalho de 5 bytes com um campo de comprimento, o que significa simplesmente: "imprima os próximos n bytes literalmente". Descompactar um bloco não compactado significa excluir apenas o cabeçalho de 5 bytes. Blocos compactados e não compactados podem se misturar livremente no fluxo DEFLATE. A saída é uma concatenação dos resultados da descompactação de todos os blocos em ordem. O conceito de "não compactado" importa apenas no nível DEFLATE; os dados do arquivo ainda são considerados "compactados" no nível do zip, independentemente de quais blocos são usados.

A maneira mais fácil de imaginar esse design é como uma sobreposição interna, do último arquivo ao primeiro. Começamos inserindo um kernel que formará o final do arquivo de dados para cada arquivo. Adicione o cabeçalho do arquivo LFH _N local e o cabeçalho do diretório CDH _N central que aponta para ele. Defina o campo de metadados "tamanho compactado" em LFH _N e CDH _N para o tamanho do núcleo compactado. Agora adicione o cabeçalho de 5 bytes do bloco não compactado (em verde no diagrama), cujo campo de comprimento é igual ao tamanho LFH _N. Adicione o segundo cabeçalho do arquivo LFH local _{N- 1} e o título do diretório central CDH _{N- 1} , que aponta para ele. Defina o campo de metadados "tamanho compactado" como o novo cabeçalho para o tamanho do kernel compactado mais o tamanho do cabeçalho de bloco não compactado (5 bytes) mais o tamanho de LFH _N.

No momento, o arquivo zip contém dois arquivos com os nomes Y e Z. Vamos ver o que o analisador verá ao analisar. Suponha que o tamanho do kernel compactado seja 1000 bytes e o tamanho LFH _N seja 31 bytes. Começamos com CDH _{N- 1} e seguimos o sinal para LFH _{N- 1} . O nome do primeiro arquivo é Y e o tamanho compactado do arquivo de dados é 1036 bytes. Interpretando os próximos 1036 bytes como um fluxo DEFLATE, primeiro encontramos um cabeçalho de 5 bytes de um bloco não compactado que diz copiar os próximos 31 bytes. Anotamos os próximos 31 bytes, que são LFH _N , que descompactamos e adicionamos ao arquivo Y. Seguindo adiante no fluxo DEFLATE, encontramos o bloco compactado (kernel) que descompactamos no arquivo Y. Agora chegamos ao final dos dados compactados e finalizamos o arquivo Y.

Passando para o próximo arquivo, seguimos o ponteiro de CDH _N para LFH _N e encontramos um arquivo chamado Z com um tamanho compactado de 1000 bytes. Interpretando esses 1000 bytes como um fluxo DEFLATE, encontramos imediatamente um bloco compactado (núcleo novamente) e o descompactamos em um arquivo Z. Agora chegamos ao final do arquivo final e finalizamos. O arquivo de saída Z contém o kernel descompactado; o arquivo de saída Y é o mesmo, mas opcionalmente com um prefixo de 31 bytes LFH _N.

Concluímos a construção repetindo o procedimento de citação até que o arquivo zip inclua o número necessário de arquivos. Cada novo arquivo adiciona um cabeçalho de diretório central, um cabeçalho de arquivo local e um bloco não compactado para citar diretamente do próximo cabeçalho de arquivo local. Os dados do arquivo compactado geralmente são uma cadeia de blocos DEFLATE não compactados (cabeçalhos de arquivo locais citados) seguidos por um núcleo compactado. Cada byte no kernel contribui com cerca de 1032 N para o tamanho da saída, porque cada byte faz parte de todos os N arquivos. Os arquivos de saída também são de tamanhos diferentes: os anteriores são maiores que os posteriores porque citam mais os cabeçalhos dos arquivos locais. O conteúdo dos arquivos de saída não faz muito sentido, mas ninguém disse que isso deveria fazer sentido.

Esse design de citação de sobreposição possui uma compatibilidade melhor do que o design de sobreposição total da seção anterior, mas a compatibilidade é obtida através da compactação. Lá, cada arquivo adicionado custa apenas o título do diretório central, aqui custa o título do diretório central, o cabeçalho do arquivo local e outros 5 bytes para o cabeçalho da citação.

Otimização

Tendo recebido o design básico da bomba zip, tentaremos torná-la o mais eficiente possível. Queremos responder duas perguntas:

• Qual é a taxa máxima de compactação para um determinado tamanho de arquivo zip?
  
• Qual é a taxa máxima de compactação, dadas as limitações do formato zip?

Compactação do Kernel

É benéfico para nós compactar o kernel o máximo possível, porque cada byte descompactado é multiplicado por N. Para esse fim, usamos um compressor DEFLATE personalizado chamado bulk_deflate, especializado em compactar uma sequência de bytes repetidos.

Todos os arquivadores DEFLATE decentes se aproximam da taxa de compressão de 1032 em um fluxo interminável de bytes repetidos, mas estamos preocupados com o tamanho específico. Em nosso tamanho de arquivo, bulk_deflate contém mais dados que arquivadores de uso geral: cerca de 26 KB a mais que zlib e Info-ZIP e 15 KB a mais que Zopfli , o que sacrifica a velocidade em prol da qualidade da compactação.



O preço de uma alta taxa de compressão bulk_deflate - a falta de versatilidade. Ele pode compactar apenas linhas de bytes repetidos e apenas um determinado comprimento, ou seja, 517 + 258 k para um número inteiro k ≥ 0. Além da boa compactação, o bulk_deflate funciona rapidamente, realizando trabalhos quase ao mesmo tempo, independentemente do tamanho dos dados de entrada, contando o trabalho de escrever uma string compactada.

Nomes de arquivos

Para nossos propósitos, os nomes de arquivos têm quase peso morto. Embora eles contribuam para o tamanho da saída fazendo parte dos cabeçalhos citados dos arquivos locais, os bytes no nome do arquivo contribuem muito menos que os bytes no kernel. Queremos que os nomes dos arquivos sejam o mais curtos possível, embora diferentes, sem esquecer a compatibilidade.

Cada byte gasto em um nome de arquivo significa dois bytes não gastos no kernel (dois porque cada nome de arquivo aparece duas vezes: no cabeçalho do diretório central e no cabeçalho do arquivo local). Um byte de nome de arquivo resulta em uma média de apenas ( N + 1) / 4 bytes de saída, enquanto um byte no kernel conta como 1032 N. Exemplos: 1 , 2 , 3 .

A primeira consideração de compatibilidade é a codificação. A especificação do formato zip indica que os nomes de arquivos devem ser interpretados como CP 437 ou UTF-8 se um bit de flag específico estiver definido ( APPNOTE.TXT, apêndice D ). Esse é o principal ponto de incompatibilidade entre os analisadores zip, que podem interpretar nomes de arquivos em alguma codificação fixa ou específica do código do idioma. Portanto, para compatibilidade, é melhor limitar-se a caracteres com a mesma codificação no CP 437 e UTF-8. Nomeadamente, esses são 95 caracteres imprimíveis em US-ASCII.

Também estamos sujeitos a restrições de nomeação de sistemas de arquivos. Alguns sistemas de arquivos não diferenciam maiúsculas de minúsculas, portanto 'a' e 'A' não são considerados nomes diferentes. Sistemas de arquivos comuns, como o FAT32, proíbem certos caracteres , como '*' e '?'.

Como um compromisso seguro, mas não necessariamente ideal, nossa bomba zip usará nomes de arquivos do alfabeto de 36 caracteres, que não inclui caracteres especiais e caracteres de maiúsculas e minúsculas:

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

Os nomes dos arquivos são gerados de maneira óbvia, todas as posições, por sua vez, com a adição de uma posição no final do loop:

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

Existem 36 nomes de arquivo de um caractere, 36² nomes de dois caracteres e assim por diante. Quatro bytes são suficientes para 1.727.604 nomes de arquivos diferentes.

Como os nomes dos arquivos no arquivo geralmente têm comprimentos diferentes, como posso classificá-los melhor: do mais curto ao mais longo ou vice-versa? Se você pensa um pouco, é melhor colocar os nomes mais longos por último. Essa classificação adiciona mais de 900 MB de saída ao zblg.zip , em comparação com a ordem mais longa e mais curta. No entanto, essa é uma otimização menor, porque 900 MB representa apenas 0,0003% do tamanho total do problema.

Tamanho do núcleo

O design de cotação sobreposto permite que você coloque um núcleo de dados compactados e depois copie-o de forma barata várias vezes. Para um tamanho específico do arquivo zip X , quanto espaço é ideal para alocar para armazenar o kernel e quanto criar cópias?

Para encontrar o equilíbrio ideal, você precisa otimizar apenas uma variável N , o número de arquivos no arquivo zip. Cada valor N requer uma certa quantidade de sobrecarga para os cabeçalhos do diretório central, cabeçalhos de arquivos locais, cabeçalhos de blocos de citações e nomes de arquivos. O restante do espaço será ocupado pelo núcleo. Como N deve ser um número inteiro e você só pode colocar um certo número de arquivos antes que o tamanho do kernel caia para zero, basta verificar todos os valores possíveis de N e selecionar o que fornece a melhor saída.

A aplicação do procedimento de otimização a X = 42.374 para 42.zip encontra um máximo em N = 250. Esses 250 arquivos requerem 21.195 bytes de sobrecarga, deixando 21.179 bytes para o kernel. Um kernel desse tamanho é descompactado em 21.841.249 bytes (proporção de 1031,3 para 1). 250 cópias do kernel descompactado mais alguns cabeçalhos de arquivos locais citados fornecem uma saída total descompactada de 5.461.307.620 bytes e uma taxa de compactação de 129.000.

• zbsm.zip 42 kB → 5,5 GB

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

A otimização levou a uma distribuição quase uniforme de espaço entre o kernel e os cabeçalhos de arquivo. Isto não é uma coincidência. Considere um modelo simplificado de uma construção de citação com sobreposição. Em um modelo simplificado, ignoramos os nomes dos arquivos, bem como um ligeiro aumento no tamanho do arquivo de saída devido à citação dos cabeçalhos dos arquivos locais. A análise do modelo simplificado mostrará que a distribuição ideal entre o kernel e os cabeçalhos de arquivo é aproximadamente uniforme, e o tamanho da saída com a distribuição ideal cresce quadraticamente, dependendo do tamanho da entrada.

Definição de algumas constantes e variáveis:


Seja H (N) o volume da sobrecarga dos cabeçalhos dos N arquivos. Veja o quadro para entender a essência da fórmula.

$$

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

Para o kernel, os locais X - H (N) permanecem. O tamanho total descompactado S _X (N) é igual ao tamanho de N cópias do kernel descompactado com a proporção C (neste modelo simplificado, ignoramos a pequena extensão adicional dos cabeçalhos de arquivos locais mencionados).

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

S _X (N) é um polinômio na parte N; portanto, o máximo deve estar onde a derivada S ' _X (N) é igual a zero. Tomar a derivada e encontrar zero nos dá N _OPT , o número ideal de arquivos.

$$$$ 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 $$ exibição $$

H (N _OPT ) oferece a quantidade ideal de espaço para colocar os cabeçalhos dos arquivos. É independente de CDH, LFH e C e está próximo de X / 2 .

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

S _X (N _OPT ) - tamanho total não embalado na distribuição ideal. A partir disso, vemos que o tamanho da saída aumenta quadraticamente com o aumento dos dados de entrada.

$$

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

Aumentando o tamanho do arquivo zip, no final, encontraremos os limites do formato zip: o archive não pode ter mais que 2 16-1 arquivos com um tamanho não superior a 2 32-1 bytes cada. Pior, algumas implementações usam valores máximos como um indicador da presença de extensões de 64 bits , portanto, nossos limites são realmente 2 ¹⁶ −2 e 2 ³² −2. Acontece que na primeira vez que encontramos um limite no tamanho de um arquivo não compactado. Com um tamanho de arquivo zip de 8 319 377 bytes, a otimização ingênua fornecerá o número de arquivos 47 837 e o arquivo máximo é 2 ³² +311 11 bytes.

(Na verdade, tudo é um pouco mais complicado, porque os limites exatos dependem da implementação. O arquivo zip do Python ignora o número de arquivos, o archive / zip no Go permite aumentar o número de arquivos até que correspondam aos 16 bits inferiores. Mas, para compatibilidade geral, devemos seguir limites estabelecidos).

Se não pudermos aumentar infinitamente o tamanho do N ou do kernel, gostaríamos de encontrar a taxa máxima de compactação no formato zip. Você precisa tornar o kernel o maior possível com o número máximo de arquivos. Apesar de não podermos mais manter uma separação aproximadamente uniforme entre o kernel e os cabeçalhos de arquivo, cada arquivo adicionado ainda aumenta a taxa de compactação - apenas não tão rápido como se pudéssemos continuar aumentando o kernel. De fato, à medida que os arquivos são adicionados, precisaremos reduzir o tamanho do kernel para liberar espaço para o tamanho máximo do arquivo, que cresce um pouco com cada arquivo adicionado.

O plano leva a um arquivo zip com 2 16-2 arquivos e um kernel, que é descompactado em 2 32-2 178 825 bytes. Os arquivos serão maiores no início do arquivo zip - o primeiro e maior arquivo é descompactado em 2 ^{32 a} 56 bytes. Isso é o mais próximo possível do uso dos parâmetros de saída aproximados de bulk_deflate - codificar os 54 bytes finais custará mais do que seu tamanho (o arquivo zip como um todo tem uma taxa de compactação de 28 milhões e os 54 bytes finais receberão no máximo 54 ⋅ 10 ³² ⋅ ( 2 ¹⁶ - 2)? 36? 5 milhões de bytes, portanto, isso só ajuda se 54 bytes puderem ser codificados em um byte - e eu não puder codificar menos de dois.Portanto, se você não puder codificar 54 bytes em 1 byte, apenas reduz a taxa de compressão). O tamanho da saída desta bomba zip é de 281.395.456.244.934 bytes, 99,97% do máximo teórico (2 ³² - 1) × (2 ¹⁶ - 1). Qualquer melhoria significativa na taxa de compressão pode ser alcançada apenas reduzindo o tamanho do sinal de entrada e não aumentando a saída.

• zblg.zip 10 MB → 281 TB

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

Computação CRC-32 eficiente

Entre os metadados no cabeçalho do diretório central e no cabeçalho do arquivo local, está uma soma de verificação dos dados do arquivo não compactado - CRC-32 . Isso representa um problema porque a quantidade de cálculos de CRC-32 para cada arquivo é proporcional ao seu tamanho, que é muito grande por padrão (afinal, é uma bomba compactada). Preferimos fazer um trabalho que seja pelo menos proporcional ao tamanho do arquivo morto. Dois fatores funcionam a nosso favor: todos os arquivos têm um núcleo comum e um kernel não compactado é uma sequência de bytes repetidos. Vamos imaginar o CRC-32 como um produto matricial - isso permitirá não apenas calcular rapidamente a soma de verificação do kernel, mas também reutilizar os cálculos entre os arquivos. O método descrito nesta seção é uma pequena extensão da função crc32_combine no zlib, que Mark Adler explica aqui .

O CRC-32 pode ser modelado como uma máquina de estado, atualizando um registro de estado de 32 bits para cada bit de entrada. As operações básicas de atualização para os bits 0 e 1 são:

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

Se você representa o registro de estado como um vetor binário de 32 elementos e usa o XOR para adição e multiplicação, crc32_update_0 é um mapeamento linear ; isto é, pode ser representado como uma multiplicação por uma matriz de transição binária 32 × 32. Para entender o porquê, observe que multiplicar uma matriz por um vetor é simplesmente adicionar as colunas da matriz depois de multiplicar cada coluna pelo elemento correspondente do vetor. O state >> 1 operação shift state >> 1 simplesmente pega cada bit i do vetor de estado e o multiplica por um vetor que é zero em qualquer lugar, exceto pelo bit i -1 (numerando os bits da direita para a esquerda). Relativamente falando, o state ^ 0xedb88320 XOR final state ^ 0xedb88320 ocorre apenas quando o bit b é igual a um. Isso pode ser representado como a primeira multiplicação de b por 0xedb88320 e, em seguida, XOR para esse estado.

Além disso, crc32_update_1 é apenas uma crc32_update_0 mais (XOR).Isso faz crc32_update_1 uma transformação afim : multiplicação da matriz seguida de mapeamento (isto é, adição de vetor). Podemos imaginar a multiplicação e o mapeamento da matriz em uma única etapa, se aumentarmos o tamanho da matriz de transformação para 33 × 33 e adicionarmos um elemento adicional ao vetor de estado, que é sempre 1 (essa representação é chamada de coordenadas homogêneas ).


As matrizes de transformação são 33 × 33 M ₀ e M ₁ , que calculam a mudança de estado CRC-32 feita pelos bits 0 e 1, respectivamente. Os vetores da coluna são armazenados com o bit mais significativo abaixo: lendo a primeira coluna de baixo para cima, você vê a constante polinomial CRC-32 edb8832016 = 111 0 11 0 110 111 000 1 00000 11 00 1 00000 ₂ . Essas duas matrizes diferem apenas na coluna final, que representa o vetor de conversão em coordenadas homogêneas. Em M _{0, a} translação é zero e em M ₁ é edb88320 ₁₆ , a constante polinomial é CRC-32. As unidades são imediatamente acima do estado da diagonal da operaçãostate >> 1

Ambas as operaçõescrc32_update_0ecrc32_update_1pode ser representado pela matriz de transição de 33 × 33. As matrizes M ₀ e M ₁ são mostradas.. A vantagem da representação da matriz é que as matrizes podem ser multiplicadas. Suponha que desejamos ver uma mudança de estado feita processando um caractere ASCII 'a', cuja representação binária é 01100001 ₂ . Podemos imaginar a mudança cumulativa no estado do CRC-32 desses oito bits em uma matriz de transformação:

$$

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

E podemos imaginar uma mudança no estado de uma linha repetindo 'a' multiplicando muitas cópias de M _a - elevando a matriz a uma potência. Podemos fazer isso rapidamente usando algoritmo rápido exponenciação , que permite calcular a M ⁿ basta ligar ₂ ⁿ passos. Por exemplo, aqui está uma matriz para alterar o estado de uma sequência 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$$

O algoritmo de multiplicação rápida da matriz é útil para calcular o _kernel M , uma matriz para um kernel não compactado, já que o kernel é uma sequência de bytes repetidos. Para obter a soma de verificação CRC-32 da matriz, multiplique a matriz pelo vetor zero (o vetor zero está em coordenadas uniformes, que são 32 zeros e depois na unidade; aqui omitimos a ligeira complicação do pré e pós-processamento da soma de verificação para verificar a conformidade). Para calcular a soma de verificação para cada arquivo, trabalhamos na direção oposta. Começamos inicializando M: = M _kernel . A soma de verificação do kernel também é a soma de verificação do arquivo final N , portanto multiplicamos Mum vector zero e a soma de verificação armazena recebido no CDH _N e LFH _N . Os dados do arquivo N-1 são iguais aos dados do arquivo N , mas com o prefixo LFH _N adicionado . Portanto, calculamos$$M L F H N , matriz de mudança de estado para LFH_Ne atualização$M_{L{FH_N}}$$$$M := M M_{L{FH_N}}$ .Agora M representa a mudança cumulativa de estado do tratamento com LFH _N atrás do núcleo. Calculamos a soma de verificação para o arquivo N - 1 , multiplicando novamente M pelo vetor zero. Continuamos o procedimento acumulando matrizes de mudança de estado em M até que todos os arquivos sejam processados.

Extensão: Zip64

Anteriormente, enfrentamos o problema de expansão devido a limitações do formato zip - era impossível emitir mais de 281 TB, independentemente da qualidade da compactação do arquivo zip. Você pode transcender esses limites usando o Zip64, uma extensão de formato zip que aumenta o tamanho de alguns campos de cabeçalho para 64 bits. O suporte ao Zip64 não é universal, mas é uma das extensões mais comumente implementadas. Quanto à taxa de compactação, o efeito do Zip64 é aumentar o tamanho do cabeçalho do diretório central de 46 para 58 bytes e o tamanho do cabeçalho do diretório local de 30 para 50 bytes. Observando a fórmula ideal do coeficiente de expansão em um modelo simplificado, vemos que a bomba zip no formato Zip64 ainda cresce quadraticamente, mas mais lentamente devido ao denominador maior - isso pode ser visto no diagrama abaixo. Devido à perda de compatibilidade e retardo de crescimento, removemos quase todas as restrições no tamanho do arquivo.

Suponha que precisamos de uma bomba zip que se expanda para 4,5 PB, como 42.zip. Qual o tamanho do arquivo? Usando a pesquisa binária, descobrimos que o tamanho mínimo de um arquivo é 46 MB.

• zbxl.zip 46 MB → 4.5 PB (Zip64, menos compatível)

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

4,5 petabytes - aproximadamente a mesma quantidade de dados foi registrada pelo Event Horizon Telescope para a primeira imagem de um buraco negro : racks e racks com discos rígidos no data center.

Com o Zip64, quase não é interessante considerar a taxa máxima de compactação, porque podemos simplesmente continuar aumentando o tamanho do arquivo zip e a taxa de compactação, até que até o arquivo zip compactado se torne proibitivo. Um limite interessante, no entanto, é de 2 ⁶⁴ bytes (18 EB ou 16 EiB) - muitos dados não cabem na maioria dos sistemas de arquivos. A pesquisa binária encontra a menor bomba zip que produz pelo menos a mesma quantidade: contém 12 milhões de arquivos e um núcleo compactado de 1,5 GB. O tamanho total do arquivo zip é 2,9 GB e é descompactado em 2 ⁶⁴+11 727 895 877 bytes com uma taxa de compressão superior a 6,2 bilhões para um. Não enviei este arquivo para download, mas você pode gerá-lo usando o código-fonte . Ele possui arquivos de tamanho que até um bug foi revelado no Info-ZIP UnZip 6.0.

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

Extensão: bzip2

DEFLATE é o algoritmo de compactação mais comum para o formato zip, mas essa é apenas uma das muitas opções. Provavelmente o segundo algoritmo mais comum é o bzip2 . Embora não seja tão compatível quanto DEFLATE. Teoricamente, no bzip2, a taxa de compressão máxima é de cerca de 1,4 milhão para um, o que permite um empacotamento mais denso do núcleo.

O bzip2 codifica primeiro a "codificação de comprimento de execução", reduzindo o comprimento da string de bytes repetidos em 51 vezes. Em seguida, os dados são divididos em blocos de 900 KB e cada bloco é compactado separadamente. Teoricamente, um bloco pode compactar até 32 bytes. 900 000 × 51/32 = 1 434 375.

Ignorando a perda de compatibilidade, o bzip2 produz uma bomba mais eficaz?

Sim - mas apenas para arquivos pequenos. O problema é que no bzip2 não há nada como os blocos DEFLATE descompactados que usamos para citar os cabeçalhos dos arquivos locais. Portanto, é impossível sobrepor arquivos e reutilizar o kernel - para cada arquivo você precisa escrever sua própria cópia, para que a taxa de compactação geral não seja melhor que a taxa de um único arquivo. No gráfico abaixo, vemos que, sem sobreposição, o bzip2 é superior a DEFLATE apenas para arquivos com tamanho de megabytes.

Há apenas uma esperança de um meio alternativo de citar cabeçalhos no bzip2, que será discutido na próxima seção. Além disso, se você souber que um analisador zip específico suporta bzip2 epermite nomes de arquivos incompatíveis, você pode usar a construção de sobreposição completa, que não precisa ser citada.


Comparação da taxa de compressão de diferentes bombas zip. Preste atenção ao eixo logarítmico. Cada design é mostrado com e sem Zip64. Estruturas sem sobreposição têm uma taxa de crescimento linear, que pode ser vista a partir da razão constante dos eixos. O deslocamento vertical do gráfico bzip2 significa que a taxa de compressão do bzip2 é cerca de mil vezes maior que a do DEFLATE. As construções DEFLATE citadas têm uma taxa de crescimento quadrática, como evidenciado por uma inclinação nos eixos 2: 1. A variante Zip64 é um pouco menos eficaz, mas permite mais de 281 TB. Os gráficos para bzip2 com aspas através de um campo adicional passam de quadrático para linear quando o tamanho máximo do arquivo é atingido (2 ³² -2 bytes) ou o número máximo permitido de arquivos

Extensão: citando através de um campo adicional

Até o momento, usamos a função DEFLATE para citar os cabeçalhos dos arquivos locais e vimos que esse truque não funciona no bzip2. No entanto, existe um método de citação alternativo, um pouco mais limitado, que usa apenas funções no formato zip e é independente do algoritmo de compactação.

No final da estrutura do cabeçalho do arquivo local, há um campo adicional de tamanho variável para armazenar informações que não se encaixam nos campos comuns do cabeçalho ( APPNOTE.TXT, seção 4.3.7) Informações adicionais podem incluir, por exemplo, um carimbo de data / hora ou uid / gid do Unix. As informações do Zip64 também são armazenadas em um campo adicional. Um campo adicional é representado como uma estrutura de valor-comprimento; se você aumentar o tamanho sem adicionar um valor, o campo adicional incluirá o que está por trás dele no arquivo zip, ou seja, o próximo cabeçalho do arquivo local. Usando esse método, cada cabeçalho do arquivo local pode "citar" os seguintes cabeçalhos, colocando-os em seu próprio campo adicional. Comparado ao DEFLATE, existem três vantagens:

1. A citação através de um campo extra requer apenas 4 bytes, não 5, deixando mais espaço para o kernel.
   
2. Não aumenta o tamanho do arquivo, o que significa um kernel maior, dadas as limitações do formato zip.
   
3. Ele fornece citações no bzip2.

Apesar dessas vantagens, a citação através de campos adicionais é menos flexível. Isso não é uma cadeia, como em DEFLATE: cada cabeçalho de um arquivo local deve conter não apenas o cabeçalho imediatamente a seguir, mas também todos os cabeçalhos subsequentes. Campos adicionais aumentam à medida que você se aproxima do início do arquivo zip. Uma vez que o comprimento do campo máxima é de 2 ¹⁶ -1 bytes podem citar apenas até 1808 cabeçalho do ficheiro local (ou 1170 em Zip64), sugerindo que os nomes atribuídos, como esperado(no caso de DEFLATE, você pode usar um campo adicional para citar os primeiros (mais curtos) cabeçalhos dos arquivos locais e depois mudar para citar DEFLATE para os demais). Outro problema: para corresponder à estrutura de dados interna do campo adicional, é necessário selecionar um tag de 16 bits para o tipo ( APPNOTE.TXT, seção 4.5.2 ) que precede os dados de citação. Queremos selecionar uma tag de tipo que faça com que os analisadores ignorem os dados entre aspas, em vez de tentar interpretá-los como metadados significativos. Os analisadores de zip devem ignorar as tags de um tipo desconhecido, para que possamos selecioná-las aleatoriamente, mas existe o risco de que, no futuro, alguma tag viole a compatibilidade do design.

O diagrama anterior ilustra a possibilidade de usar campos adicionais no bzip2, ce sem o Zip64. Nos dois gráficos, há um ponto de virada, quando o crescimento passa de quadrático para linear. Sem o Zip64, isso acontece quando o tamanho máximo do arquivo descompactado é atingido (2 ³²-2 bytes); só é possível aumentar o número de arquivos, mas não o tamanho. O gráfico termina completamente quando o número de arquivos atinge 1809, então o espaço em um campo adicional é insuficiente para citar cabeçalhos adicionais. Com o Zip64, ocorre uma fratura nos arquivos 1171, após os quais apenas o tamanho do arquivo pode ser aumentado, mas não o número. Um campo adicional ajuda no caso de DEFLATE, mas a diferença é tão pequena que não é visualmente perceptível. Aumenta a taxa de compactação de zbsm.zip em 1,2%; zblg.zip em 0,019%; e zbxl.zip em 0,0025%.

A discussão

Em seu trabalho sobre esse assunto, Pletz e colegas usam a sobreposição de arquivos para criar um arquivo zip quase auto-replicante. A sobreposição do arquivo foi sugerida anteriormente (slide 47) por Ginvael Coldwind.

Desenvolvemos um design de uma bomba zip com uma sobreposição de cotação, levando em consideração a compatibilidade - várias diferenças nas implementações, algumas das quais são mostradas na tabela abaixo. O design resultante é compatível com analisadores zip que funcionam da maneira usual, ou seja, primeiro verificando o diretório central e usando-o como um índice de arquivos. Entre eles, um analisador de zip exclusivo da Nailque é gerado automaticamente a partir da gramática formal. No entanto, o design é incompatível com os analisadores de "streaming", que analisam o arquivo zip do início ao fim em uma passagem sem primeiro ler o diretório central. Por sua natureza, os analisadores de streaming não permitem a sobreposição de arquivos. Provavelmente, eles extrairão apenas o primeiro arquivo. Além disso, eles podem até gerar um erro, como é o caso do sunzip , que analisa o diretório central no final e verifica a consistência com os cabeçalhos dos arquivos locais que ele já viu.

Se você deseja que os arquivos extraídos iniciem com um prefixo específico diferente dos bytes do cabeçalho do arquivo local, é possível inserir um bloco DEFLATE antes do bloco descompactado que o cabeçalho a seguir cita. Nem todos os arquivos no arquivo zip devem participar da criação da bomba: você pode incluir arquivos comuns no arquivo, se necessário, para corresponder a algum formato especial (existe um parâmetro no código-fonte --templatepara este caso de uso). Muitos formatos usam o zip como um contêiner, como documentos Java JAR, Android APK e LibreOffice.

Pdfde muitas maneiras semelhantes ao zip. Ele possui uma tabela de referência cruzada no final do arquivo que aponta para objetos anteriores e suporta a compactação de objetos por meio do filtro FlateDecode. Eu não tentei, mas você pode usar a idéia de citar com sobreposição para fazer uma bomba em PDF. Talvez você nem precise trabalhar duro aqui: binaryhax0r escreve em um post no blog que você pode simplesmente especificar várias camadas FlateDecode em um objeto, após o qual a criação de uma bomba PDF se torna trivial.

É fácil definir uma classe específica de bombas zip descritas neste artigo: basta encontrar os arquivos sobrepostos. Mark Adler escreveu um patchpara descompactar Info-ZIP, o que faz exatamente isso. No entanto, em geral, o bloqueio de arquivos sobrepostos não protege contra todas as classes de bombas compactas. É difícil prever com antecedência se o arquivo é uma bomba zip ou não, se você não tiver um conhecimento preciso sobre os componentes internos dos analisadores que serão usados ​​para analisá-lo. Observar os cabeçalhos e somar os campos "tamanho não compactado" de todos os arquivos não funciona , porque o valor nos cabeçalhos pode não corresponder ao tamanho real não compactado (na tabela de compatibilidade, consulte a linha "permite que o arquivo seja muito pequeno"). A proteção confiável contra bombas zip inclui limites de tempo, memória e espaço em disco no analisador zip durante sua operação. Faça uma análise de arquivos zip, como qualquer operação complexa com dados não confiáveis, com cuidado.


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

Agradecimentos

Agradecemos a Mark Adler , Russ Cox , Brandon Enright , Marek Maykovsky , Josh Wolfe e os revisores do USENIX WOOT 2019 por comentários sobre o rascunho deste artigo. Kaolan McNamara avaliou o impacto das bombas zip na segurança do LibreOffice.

Uma versão deste artigo foi preparada para o Workshop USENIX WOOT 2019 . O código fonte está disponível. Os artefatos para apresentação no workshop estão no arquivo zipbomb-woot19.zip .

Você encontrou um sistema que lança uma das bombas? As bombas o ajudaram a encontrar um bug ou ganhar dinheiro em um programa de busca de bug? Deixe-me saber, vou tentar mencionar aqui.

LibreOffice 6.1.5.2

Após renomear zblg.zip para zblg.odt ou zblg.docx, o LibreOffice cria e exclui uma série de arquivos temporários de aproximadamente 4 GB, tentando determinar o formato do arquivo. Por fim, ele acaba fazendo isso e exclui os arquivos temporários à medida que eles chegam, portanto a bomba zip causa apenas um DoS temporário sem encher o disco. Kaolan McNamara respondeu à minha mensagem de erro.

Mozilla addons-server 2019.06.06

Tentei compactar bombas contra a instalação local do servidor de addons, que faz parte do software addons.mozilla.org. O sistema lida com a bomba graciosamente, impondo um limite de tempo de 110 segundos na extração de arquivos. A bomba zip se expande rapidamente, tanto quanto o disco permite até esse limite de tempo, mas o processo é interrompido e os arquivos descompactados são limpos automaticamente.

Descompacte 6.0

Mark Adler escreveu um patch para o UnZip para detectar essa classe de bombas zip.

5 de julho de 2019: Observei que o CVE-2019-13232 foi atribuído ao UnZip. Pessoalmente, eu argumentaria que a capacidade / incapacidade do UnZip (ou de qualquer analisador de zip) de processar esse tipo de bomba zip é necessariamente uma vulnerabilidade ou mesmo um bug. Esta é uma implementação natural que não viola a especificação, o que posso dizer. O tipo de bomba neste artigo é apenas um tipo e existem muitas outras maneiras de decifrar um analisador de zip. Como mencionado acima, se você deseja se proteger de ataques de exaustão de recursos, não tente listar, detectar e bloquear todos os ataques conhecidos; em vez disso, é necessário estabelecer restrições externas de tempo e outros recursos para que o analisador não entre nessa situação, independentemente do tipo de ataque encontrado. Não há nada errado em tentar detectar e rejeitar determinados projetos como uma otimização da primeira passagem,mas você não pode parar por aí. A menos que você acabe isolando e restringindo operações com dados não confiáveis, seu sistema provavelmente ainda estará vulnerável. Considere a analogia com o script entre sites em HTML: a proteção certa não é tentar filtrar bytes específicos que podem ser interpretados como código, mas evitar tudo corretamente.

Mecanismos antivírus

O usuário do Twitter @TVqQAAMAAAAEAAA relata : "O antivírus McAfee na minha máquina de teste simplesmente explodiu". Eu mesmo não testei e não tenho detalhes como o número da versão.

Tavis Ormandi indica que o VirusTotal tem vários tempos limite para o zblg.zip ( captura de tela de 6 de junho de 2019 ): AhnLab-V3, ClamAV, DrWeb, Endgame, F-Secure, GData, K7AntiVirus, K7GW, MaxSecure, McAfee, McAfee-GW - Edição, Panda, Qihoo-360, Sophos ML, VBA32. Resultados para zbsm.zip ( captura de tela de 6 de junho de 2019)) são semelhantes, mas com um conjunto diferente de mecanismos de tempo limite: Baido, Bkav, ClamAV, CMC, DrWeb, Endgame, ESET-NOD32, F-Secure, GData, Kingsoft, McAfee-GW-Edition, NANO-Antivírus, Acronis. Curiosamente, não há tempos limite nos resultados do zbxl.zip ( captura de tela de 6 de junho de 2019 ). Talvez alguns antivírus não sejam compatíveis com o Zip64? Vários mecanismos detectam arquivos como uma espécie de "bomba de compressão". É interessante ver se eles continuarão fazendo isso com pequenas alterações, como alterar nomes de arquivos ou adicionar um prefixo ASCII a cada arquivo.

Declaração final

É hora de acabar com o Facebook. Este não é um trabalho neutro para você: todos os dias, quando chega ao trabalho, está fazendo algo errado. Se você possui uma conta no Facebook, exclua-a. Se você trabalha no Facebook, seja demitido.

E não esqueça que a Agência de Segurança Nacional deve ser destruída.