DEFLATE, gzip and zlib

programaçãodesenvolvimento websegurança

O algoritmo de compressão dentro do ZIP, do PNG, do Git e de boa parte da web; o formato de arquivo que o embrulha; e a biblioteca que implementa os dois.

O algoritmo de compressão dentro do ZIP, do PNG, do Git e da maior parte do tráfego web comprimido; o gzip é o formato que o embrulha, a zlib a biblioteca que quase tudo chama.

Três nomes para coisas intimamente ligadas, e separá-las é o primeiro passo para não se confundir com elas. O DEFLATE é o algoritmo. O gzip é um formato de arquivo que embrulha o DEFLATE com cabeçalho, checksum e comprimento. A zlib é outro embrulho ligeiramente diferente e, mais importante, a biblioteca que quase tudo de fato usa para fazer qualquer uma dessas coisas. O DEFLATE em si são duas ideias antigas empilhadas. Primeiro o LZ77: enquanto lê a entrada, substitua o que já viu antes por uma referência curta ao ponto onde viu, de modo que a segunda ocorrência de um trecho repetido custe alguns bytes em vez de seu comprimento inteiro. Depois a codificação de Huffman: tendo produzido esse fluxo de literais e retrorreferências, conte quantas vezes cada símbolo aparece e dê códigos curtos aos comuns e longos aos raros. Nenhuma das metades era nova quando o DEFLATE foi especificado na RFC 1951 - o número da RFC é uma coincidência que vale apreciar - e a combinação não é tanto engenhosa quanto extremamente bem equilibrada: rápida o bastante para rodar em tudo, boa o bastante para que melhorá-la raramente compense a troca. O resultado é provavelmente o algoritmo de compressão mais executado da história, e quase ninguém sabe nomeá-lo. Está dentro de todo arquivo ZIP, toda imagem PNG, todo objeto do Git e toda resposta HTTP servida com content-encoding gzip, ou seja, boa parte da web. A razão de o gzip existir é uma patente, e essa é a parte que vale conhecer. O Unix tinha uma ferramenta chamada compress, que usava LZW - algoritmo coberto por patentes da Unisys, as mesmas que tornaram o GIF juridicamente desconfortável por anos e acabaram empurrando a web para o PNG. Jean-loup Gailly e Mark Adler escreveram o gzip justamente para ser um substituto livre que não infringisse nada, e a zlib veio depois como biblioteca reutilizável. Ambos sobreviveram às patentes, à ferramenta que substituíram e ao formato que as patentes prejudicaram. Uma patente destinada a capturar um mercado acabou motivando a coisa livre que o substituiu - que é a mesma forma do processo que produziu o ZIP, na mesma década, no mesmo canto da computação. Uma consequência de segurança merece ser dita porque surpreende quem entende as duas metades separadamente. Compressão vaza informação sobre o que foi comprimido. Se um atacante consegue injetar texto em algo que é comprimido e depois cifrado, ele descobre se seu palpite aparece em outro lugar do texto claro observando o comprimento comprimido mudar - adivinhando um segredo um caractere por vez sem quebrar criptografia alguma. Esse é o mecanismo por trás dos ataques CRIME e BREACH, ambos com fichas próprias aqui. Criptografia esconde conteúdo; não esconde tamanho, e comprimir antes de cifrar transforma tamanho em canal. A regra prática é sem graça e absoluta: não comprima dados influenciados pelo atacante junto com segredos no mesmo fluxo cifrado.

Também conhecido como: deflate, gzip, zlib, gz, content-encoding gzip, rfc 1951, rfc 1952

← Todos os verbetes do glossário