Colisão de hash: quando importa de verdade e quando é paranoia.

Toda vez que alguém propõe usar hash como identificador, aparece a pergunta: e se der colisão?

A resposta padrão é citar o número de átomos do universo observável e seguir em frente. O número está certo e a resposta é preguiçosa, porque ela responde a pergunta errada.

Existem dois tipos de colisão, com riscos completamente diferentes, e a conta de probabilidade só cobre um deles.

Colisão acidental

É a que a matemática descreve. Dois valores diferentes produzindo o mesmo hash por azar.

O paradoxo do aniversário diz que, com uma saída de N bits, a probabilidade fica relevante por volta de 2^(N/2) itens.

Para SHA-256, isso é 2^128. Um número que não tem uso prático: se você gerasse um bilhão de hashes por segundo desde o Big Bang, ainda não chegaria perto.

Para uma saída truncada em 64 bits, muda tudo: a chance vira apreciável por volta de 4 bilhões de itens, o que é um volume que sistemas reais alcançam.

E aqui está a primeira armadilha de verdade. Ninguém usa SHA-256 completo como identificador em URL, porque 64 caracteres hexadecimais é feio. Trunca-se pra 12, 16, 20 caracteres. Cada truncamento corta o expoente pela metade.

64 hex (256 bits) -> colisão em ~2^128 itens.  irrelevante
16 hex ( 64 bits) -> colisão em ~2^32  itens.  4 bilhões
12 hex ( 48 bits) -> colisão em ~2^24  itens.  16 milhões
 8 hex ( 32 bits) -> colisão em ~2^16  itens.  65 mil

Oito caracteres, que é o que o Git mostra por padrão, colide de verdade em repositório grande. O Linux kernel já precisou aumentar o padrão por causa disso.

Então a pergunta certa não é “SHA-256 colide?”. É “quantos bits eu realmente guardei?”.

Colisão intencional

Essa é a que importa e a que a probabilidade não descreve.

A pergunta não é se o azar acontece. É se alguém consegue fabricar dois documentos diferentes com o mesmo hash de propósito.

Para MD5, isso é trivial: gera-se um par colidente em segundos num notebook. Para SHA-1, é caro e já foi demonstrado publicamente, o que na prática significa quebrado.

O ataque relevante nem sempre é a colisão pura. É a colisão com prefixo escolhido, que permite construir dois arquivos com conteúdo controlado e mesmo hash. Com isso se assina o documento benigno e se apresenta o malicioso.

Se existe alguém interessado em enganar o seu sistema, a força do algoritmo importa e não tem substituto. SHA-256 ou BLAKE3, sem truncamento agressivo.

O risco que ninguém calcula

Na prática, a maior parte das “colisões” que eu vejo em produção não é colisão criptográfica coisa nenhuma. É serialização instável.

Dois registros diferentes que produzem o mesmo hash porque a forma canônica esqueceu um campo. Ou o mesmo registro produzindo hashes diferentes porque a ordem das chaves do JSON mudou.

// campos concatenados com hífen
["ab", "c"]  -> "ab-c"
["a", "bc"]  -> "a-bc"

// parecem seguros. agora com um valor contendo hífen:
["a-b", "c"] -> "a-b-c"
["a", "b-c"] -> "a-b-c"   // colisão, e não foi o SHA-256 que falhou

Isso não é probabilidade astronômica. É bug de engenharia, acontece com cem registros, e é a causa real de quase todo problema que se apresenta como colisão. Escrevi sobre a forma canônica em system design de rastreabilidade com hash único.

A decisão prática

Três perguntas resolvem o caso.

Existe adversário? Se sim, algoritmo criptográfico forte, sem truncar demais. Se não, um hash rápido não criptográfico serve e é mais barato.

Quantos bits sobram depois do truncamento? Faça a conta com o volume que você espera em cinco anos, com margem. Como regra, 128 bits é confortável pra qualquer coisa, 64 bits exige pensar, 32 bits só serve pra deduplicação com verificação depois.

O que acontece se colidir? Essa é a pergunta que quase ninguém faz, e é a que decide quanto esforço vale.

Se a colisão significa “dois arquivos idênticos foram deduplicados por engano” e existe verificação de conteúdo depois, o custo é baixo.

Se significa “duas transações financeiras diferentes viraram uma”, o custo é alto e você quer margem enorme.

A defesa mais barata

Uma constraint única no banco.

alter table trace_event add constraint trace_event_hash_unique unique (tenant_id, hash);

Se acontecer o improvável, o insert falha, alguém é alertado, e nada corrompe silenciosamente. Custa nada e transforma a categoria “corrupção invisível” em “erro visível”.

É a mesma filosofia da verificação de balanceamento num ledger: não previne o impossível, garante que o impossível não passe despercebido.

O resumo

Colisão acidental em SHA-256 completo não é um risco que mereça o seu tempo.

Colisão em hash truncado é um risco de engenharia, com conta simples.

Colisão intencional é risco real e depende só de escolher um algoritmo que não esteja quebrado.

E a colisão por serialização instável, que é a única que eu vi acontecer de verdade, não aparece em nenhuma dessas contas. Ela vem de não ter escrito a forma canônica antes de escrever o hash.