As somas de verificação não são hashes: CRC-32, Adler-32 e para que servem

Três trabalhos que produzem todos um número curto

A confusão começa na saída. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 e SHA-256 recebem bytes quaisquer e devolvem um número de tamanho fixo, pelo que numa API parecem intercambiáveis. Não são. Foram desenhados contra três modelos de ameaça completamente distintos, e escolher a família errada produz falhas silenciosas até se tornarem catastróficas.

Uma soma de verificação responde: estes dados mudaram por acidente no caminho? O seu adversário é um raio cósmico, um cabo no limite, uma escrita truncada, um setor de disco a enfraquecer. Esse adversário é aleatório e não se adapta. O CRC-32 e o Adler-32 são somas de verificação. Um hash criptográfico responde a uma pergunta mais dura: pode alguém, com todo o tempo e hardware que consiga comprar, encontrar uma segunda entrada com a mesma saída? O seu adversário é uma pessoa com orçamento. MD5, SHA-1 e SHA-256 são tentativas disso — com sucesso variável, detalhado no artigo companheiro sobre a escolha de hash.

O terceiro trabalho é o que se esquece. Um hash de tabela responde: como transformo esta chave num índice de balde, depressa e de forma uniforme? O seu adversário é nominalmente ninguém — até as chaves virem de parâmetros de pedidos HTTP, altura em que o adversário é quem as envia. O FNV-1a e o MurmurHash3 vivem aqui. São excelentes no seu trabalho e não oferecem proteção nenhuma nos outros dois.

O CRC-32 é linear, e eis a colisão

O CRC-32 é divisão polinomial sobre GF(2), e a divisão é linear. Em concreto, para três mensagens quaisquer do mesmo comprimento, crc(a XOR b XOR c) é igual a crc(a) XOR crc(b) XOR crc(c). Testado em cinco triplos aleatórios de 32 bytes, a igualdade foi exata todas as vezes — um dos triplos deu, por exemplo, 8975e151 dos dois lados. Nenhum hash criptográfico tem uma identidade dessas, e esse único facto algébrico é toda a diferença entre as duas famílias.

A linearidade permite resolver uma colisão em vez de a procurar. Pegue numa mensagem que um atacante queira alterar, dê-lhe alguns bytes de folga em qualquer sítio — enchimento, um campo de comentário, um cabeçalho reservado, espaços finais — e o valor de folga necessário é a solução de um sistema linear de 32 incógnitas sobre GF(2). A eliminação de Gauss resolve isso em microssegundos.

Feito a sério: a mensagem original era «config: mode=safe, retries=3, pad=......», com CRC-32 78aa94ad. A falsificação devia ler-se «config: mode=open, retries=9, pad=» seguido de seis bytes de enchimento a determinar. Resolver esses bytes deu «config: mode=open, retries=9, pad=!9[noI» — o mesmo comprimento de 40 bytes, 11 bytes diferentes, e o CRC-32 idêntico 78aa94ad. Foram tentados vinte e cinco enchimentos candidatos até sair um totalmente imprimível; o programa inteiro correu em 0,11 segundos. Os resumos SHA-256 das duas mensagens começam por d9cddeec e 6b7bdc0c, que é o aspeto de uma função sem identidade de linearidade.

Nada disto exigiu criptanálise, GPU ou dicionário. Exigiu saber que o CRC-32 é uma aplicação linear e dispor de seis bytes da mensagem. É por isso que um CRC que acompanha um ficheiro por um canal não fiável não prova nada contra adulteração: um atacante que possa mudar o ficheiro pode mudar o CRC para condizer, e mesmo que o CRC chegue em separado e seja intocável, ainda pode fabricar outro ficheiro que o produza.

Aquilo em que o CRC-32 é realmente excelente

Nada do que ficou dito faz do CRC-32 uma má função. Faz dele uma função que desempenha outro trabalho, e nesse trabalho é quase ótima. As suas garantias não são estatísticas, são demonstradas: deteta todo o erro de um bit, todo o erro de dois bits dentro de um comprimento de mensagem enorme, todo o erro que afete um número ímpar de bits e todo o erro em rajada até 32 bits — o comprimento da própria soma.

Medido e não afirmado: numa mensagem de 200 bytes, as 1 600 inversões possíveis de um bit alteraram todas o CRC, e as 1 279 200 inversões possíveis de dois bits também o alteraram — nenhuma escapou. Numa trama de 1500 bytes de tamanho Ethernet, 200 000 erros em rajada aleatórios em cada uma de seis larguras (8, 16, 32, 33, 40 e 64 bits) foram todos detetados. As rajadas com mais de 32 bits não são garantidas, apenas esmagadoramente prováveis: a probabilidade de escape é de cerca de 2 elevado a menos 32, uma em 4,29 mil milhões, e é por isso que 200 000 tentativas não encontraram nada.

É por isso que o CRC-32 está nas tramas Ethernet, nos finais de ficheiro gzip, nos blocos PNG, nas entradas ZIP e no SATA. São todos canais cujo modo de falha é um defeito físico que produz uma sequência contígua de bits corrompidos — exatamente a classe de erros que os polinómios CRC são construídos para apanhar com certeza. Um hash criptográfico também os apanharia, mas a várias vezes o custo e sem garantia demonstrada, apenas probabilística.

Adler-32: mais barato de calcular, mais fraco a detetar

O Adler-32, definido no RFC 1950 para o formato zlib, são duas somas correntes módulo 65 521: uma soma simples dos bytes e uma soma dessas somas parciais. Foi desenhado para ser muito mais barato do que um CRC detetando a maioria dos mesmos erros — sem tabela, apenas somas. Na prática o módulo custa o suficiente para que a vantagem prometida muitas vezes se evapore: medido no mesmo motor JavaScript sobre o mesmo buffer de 64 MB, o Adler-32 correu a 174 MB/s contra os 262 MB/s do CRC-32. O Adler-32 foi mais lento.

Tem também um ponto cego que se demonstra em vez de se estimar. O módulo 65 521 é o maior primo abaixo de 65 536. Se aumentar um byte em d e diminuir outro byte em d, a primeira soma não muda, e a segunda muda em d vezes a distância entre eles — o que se anula módulo 65 521 exatamente quando essa distância é 65 521. Assim, qualquer mensagem com mais de cerca de 64 kilobytes tem pares de alterações compensatórias que o Adler-32 não consegue ver de todo.

Demonstrado num buffer de 70 000 bytes: subir o byte 100 em 7 e baixar o byte 65 621 em 7 deixou o Adler-32 em 3fee717c, idêntico byte a byte ao valor limpo, enquanto o CRC-32 passava de abc586b8 para 43c209f4. O Adler-32 também é fraco em entradas curtas — 200 000 entradas aleatórias de quatro bytes produziram apenas 152 364 valores Adler-32 distintos, quando uma função de 32 bits ideal teria produzido cerca de 199 995. O próprio RFC 1950 assinala a fraqueza para mensagens curtas, razão pela qual os fluxos zlib o aplicam a fluxos inteiros e não a registos minúsculos.

FNV-1a e MurmurHash3: a terceira categoria

O FNV-1a e o MurmurHash3 não são somas de verificação nem hashes criptográficos. São hashes não criptográficos desenhados para tabelas de dispersão, filtros de Bloom e particionamento, onde o requisito é distribuição uniforme ao menor custo possível por byte. Cumprem. No mesmo motor e sobre o mesmo buffer, o MurmurHash3 correu a 730 MB/s e o FNV-1a a 520 MB/s, contra os 262 MB/s do CRC-32.

As colisões são triviais de encontrar e o exercício demora menos de dois segundos. Enumerando cadeias de sete carateres, o FNV-1a 32 colidiu em «7yzlaaa» e «e6apaaa», ambas com hash 15111984, ao fim de 700 997 candidatos e 680 milissegundos. O MurmurHash3 com semente 0 colidiu em «rynbaaa» e «ciaabaa», ambas em e5407f96, ao fim de 1 679 907 candidatos e 1,6 segundos. É o esperado — 32 bits significam colisão de aniversário por volta dos 77 163 elementos — e não é um defeito. Torna-se defeito quando alguém escolhe as chaves.

A inundação de hash é o ataque daí resultante, e é fácil de reproduzir. Recolher 20 000 chaves cujo valor FNV-1a cai no balde 0 de uma tabela de 4 096 baldes custou uma fração de segundo de divisão por tentativa. Inseri-las colapsou a tabela numa única cadeia de 20 000 entradas, onde chaves normais davam uma cadeia máxima de 12. Vinte mil pesquisas passaram então a demorar 1 397,9 milissegundos em vez de 11,5 — um abrandamento de 121 vezes, de tempo constante para linear. Cada pedido que toque nessa tabela torna-se um amplificador: é exatamente a classe de negação de serviço que empurrou os motores de linguagem para um SipHash com semente aleatória nos seus dicionários integrados.

Escolher, numa pergunta

Pergunte a quem beneficia se duas entradas diferentes produzirem o mesmo valor. Se a resposta for ninguém — está a apanhar cópias truncadas, cabos instáveis, arquivos corrompidos, apodrecimento de bits num disco de cópia de segurança — uma soma de verificação é o correto e o CRC-32 é o padrão sensato. É pequena, está em todo o lado, tem garantias demonstradas contra exatamente as formas de erro que o hardware produz, e as implementações nativas são rapidíssimas: o CRC-32 do zlib no node atingiu 2 248 MB/s no mesmo buffer, três vezes os 763 MB/s do SHA-256.

Se a resposta for alguém — uma descarga por uma rede que não controla, uma assinatura, um ficheiro de licença, uma carga de atualização, desduplicação de objetos fornecidos por utilizadores, uma cache indexada por algo que um utilizador possa influenciar — precisa de um hash criptográfico, e hoje isso significa SHA-256. O custo é real mas pequeno: 763 MB/s continua a ser mais rápido do que a maioria dos discos e das redes, e é a única família desta comparação em que uma segunda entrada com a mesma saída não é algo que qualquer um consiga simplesmente resolver.

E se o valor nunca sair do seu processo — índice de balde, filtro de Bloom, seletor de partição — use um hash de tabela, mas faça uma pergunta de seguimento: pode um atacante escolher as chaves? Se puder, quer uma função com chave e semente aleatória como o SipHash, não um FNV-1a de semente fixa. A maioria dos motores de linguagem modernos já o faz nos seus mapas integrados; o perigo é uma tabela feita à mão no código da aplicação que não o faça.

Perguntas frequentes

O CRC-32 é uma função de hash?

No sentido mais lato sim — leva uma entrada qualquer a uma saída fixa de 32 bits — mas chamar-lhe isso convida ao erro que este artigo existe para evitar. O CRC-32 é uma função linear, calculada como o resto de uma divisão polinomial sobre GF(2). Essa linearidade dá-lhe a identidade crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), verificada aqui em triplos aleatórios, e dessa identidade decorre uma colisão obtida por resolução de um sistema linear de 32 incógnitas em vez de por procura. Um hash criptográfico é especificamente concebido para que não exista tal atalho algébrico; é isso que a palavra criptográfico faz. Portanto o CRC-32 é uma soma de verificação, e o modelo mental útil é um ótimo código detetor de erros e não um hash fraco. Se uma biblioteca, uma API ou uma revisão de código lhe chamar hash, verifique de que propriedade se depende na realidade: a unicidade perante um adversário é a que ele não pode fornecer, e é a que se assume.

Posso usar um CRC-32 para verificar uma descarga?

Depende inteiramente daquilo contra que verifica. Se está a confirmar que os bytes que chegaram correspondem aos que saíram — que a ligação não caiu a meio, que o arquivo não está truncado, que o disco escreveu o que lhe deram — um CRC-32 é exatamente a ferramenta certa e apanhará qualquer falha de transporte realista. É por isso que cada entrada ZIP e cada fluxo gzip transporta um. Se, em vez disso, pergunta se o ficheiro é o que o editor pretendia, um CRC-32 não responde nada. Um atacante que possa substituir o ficheiro pode substituir também o CRC, e mesmo onde o CRC é publicado à parte e é intocável, pode construir outro ficheiro que lhe corresponda — este artigo fez exatamente isso em 0,11 segundos. Para verificar o editor precisa de um resumo criptográfico publicado por um canal que o atacante não controle, e idealmente de uma assinatura sobre esse resumo e não do resumo sozinho.

Porque é que o gzip usa CRC-32 e o zlib usa Adler-32?

Ambos os formatos embrulham os mesmos dados comprimidos DEFLATE e diferem sobretudo no contentor. O RFC 1952 especifica um CRC-32 no fecho do gzip; o RFC 1950 especifica um Adler-32 no do zlib. O raciocínio da altura era a velocidade: o Adler-32 só precisa de somas e de um módulo, sem tabela de 256 entradas, pelo que nos processadores do início dos anos 1990 era bastante mais barato por byte, e o zlib visava contextos onde o custo da soma pesava face à compressão. Essa vantagem evaporou-se em larga medida. As implementações modernas de CRC-32 usam tabelas slicing-by-8 ou instruções dedicadas, e nas medições feitas aqui o CRC-32 nativo do node atingiu 2 248 MB/s enquanto um Adler-32 direto no mesmo motor JavaScript ficou por 174 MB/s contra os 262 MB/s do CRC-32. Os formatos mantêm-se como estão porque mudar de algoritmo parte todos os leitores existentes, e ambos chegam para a sua missão de apanhar corrupção acidental num fluxo comprimido.

Qual é a probabilidade de uma colisão CRC-32 acidental?

Para uma única mensagem corrompida a resposta é excelente: as rajadas até 32 bits nunca escapam, e além disso a probabilidade de fuga é de cerca de uma em 4 294 967 296. Para uma coleção de ficheiros é muito pior do que a intuição sugere, por causa do efeito aniversário. Dois valores aleatórios de 32 bits colidem com probabilidade de uma em 4,29 mil milhões, mas um conjunto de n valores contém n(n−1)/2 pares, pelo que a marca dos 50 % chega aos 77 163 elementos. Dez mil ficheiros já trazem 1,16 % de hipóteses de algum par partilhar um CRC-32, e cem mil trazem 68,8 %. Isso importa se usar o CRC-32 como chave de desduplicação ou identificador endereçado por conteúdo num corpus grande, onde uma colisão descarta em silêncio um de dois ficheiros diferentes. Para uma verificação de integridade ficheiro a ficheiro contra danos de transporte o efeito aniversário é irrelevante, porque compara um valor com um valor esperado, não procura correspondências numa população.

O FNV-1a e o MurmurHash3 são seguros com chaves fornecidas pelo utilizador?

Sem uma semente aleatória, não. Ambos são sem chave por omissão, pelo que a sua saída é uma função pública que qualquer um pode calcular offline. Isso permite a um atacante pré-calcular chaves que caiam no mesmo balde e enviá-las todas de uma vez: é a inundação de hash. Reproduzida aqui numa tabela de 4 096 baldes: 20 000 chaves fabricadas foram todas parar ao balde 0, transformando uma cadeia máxima de 12 numa única cadeia de 20 000 e fazendo com que 20 000 pesquisas demorassem 1 397,9 milissegundos em vez de 11,5 — 121 vezes mais lento, e recolher essas chaves exigiu menos de um segundo de esforço. A correção não é um hash sem chave mais forte; é um com chave e semente aleatória por processo, que torna impossível o pré-cálculo offline. O SipHash é a escolha padrão e é o que hoje a maioria dos motores usa internamente nos seus dicionários. Se as suas chaves vêm da configuração, da sua própria base de dados ou de um sítio que um atacante não possa influenciar, o FNV-1a e o MurmurHash3 sem semente continuam perfeitos e muito rápidos.

O que devo usar para chaves de cache e desduplicação?

Decida por quem fornece o conteúdo e pelo custo de uma resposta errada. Para uma cache em memória cujas chaves gera o próprio — uma forma de consulta, um nome de modelo renderizado, um identificador interno — um hash não criptográfico rápido é o certo, e o MurmurHash3 a 730 MB/s é boa escolha. Para desduplicação sobre um corpus que controla, onde uma colisão significa guardar em silêncio um de dois objetos diferentes, 32 bits é demasiado estreito: o ponto aniversário dos 50 % chega aos 77 163 elementos. Passe para um hash não criptográfico de 64 ou 128 bits, ou para um SHA-256 truncado. Para tudo em que o utilizador forneça o conteúdo — ficheiros carregados, objetos gerados por utilizadores, um arquivo endereçado por conteúdo, uma cache partilhada por vários inquilinos — use SHA-256 por inteiro. Aí uma colisão não é um acidente mas uma capacidade: permite colocar um objeto escolhido sob um identificador já existente, e só um hash criptográfico torna isso inviável. O custo é modesto: os 763 MB/s medidos aqui ultrapassam a camada de armazenamento em que está a escrever.