Calculadora de Probabilidade de Colisão de Hash
Entradas
| Tamanho do hash | 128 |
|---|---|
| Número de itens | 1.000.000 |
Calculadora de Probabilidade de Colisão de Hash
Estime a probabilidade de uma colisão aniversário em um conjunto de valores de hash e descubra quantos itens são necessários para atingir 50% de chance de colisão para um tamanho de hash específico.
Entradas
Parâmetros do Hash
Resultados
Insira um valor para ver os resultados.
Probabilidade de Colisão
Probabilidade de Colisão em Funções de Hash
Uma função de hash mapeia uma entrada de comprimento arbitrário para uma saída de comprimento fixo chamada de resumo (digest). Idealmente, duas entradas distintas não produzem o mesmo resumo — propriedade denominada resistência a colisões. Na prática, como o espaço de saída é finito, colisões necessariamente existem; a questão é quantas entradas precisam ser processadas antes que uma seja provável. Esta calculadora quantifica essa probabilidade usando a aproximação do aniversário, nomeada em referência ao paradoxo do aniversário.
O Paradoxo do Aniversário
Em um grupo de 23 pessoas escolhidas uniformemente ao acaso ao longo de um ano de 365 dias, já há mais de 50% de probabilidade de que duas compartilhem a mesma data de aniversário. A probabilidade é muito mais alta do que a intuição sugere porque considera qualquer par dentro do grupo, não uma coincidência com uma data específica. A mesma assimetria governa as colisões em funções de hash: encontrar duas entradas com o mesmo hash (uma colisão) é muito mais fácil do que encontrar uma entrada que produza um hash alvo específico (uma pré-imagem).
Fórmula
Para uma função de hash com bits de saída, o espaço de busca possui valores igualmente prováveis. Dado itens com hashes gerados aleatoriamente, a probabilidade exata de colisão é o complemento da probabilidade de que todas as saídas sejam distintas:
p=1−k=0∏n−1(1−2bk)Para grande e moderado, a aproximação do aniversário oferece uma forma fechada mais simples:
p≈1−e−n2/(2⋅2b)Resolvendo para o número de itens em que a probabilidade atinge 50%:
n50%=2⋅2b⋅ln2Exemplo
Para um hash de 32 bits (como o CRC32 usado em checksums):
n50%=2×232×ln2=2×4294967296×0,6931≈5954124768≈77163Com apenas 77.163 arquivos em um repositório, há aproximadamente 50% de chance de que dois compartilhem o mesmo CRC de 32 bits. Confirmando com a fórmula de aproximação:
p=1−e−771632/(2×232)≈1−e−0,693≈0,50Por isso o CRC32 é inadequado como identificador único em grandes coleções, embora seja um excelente código de detecção de erros em pequenos fluxos de dados.
Implicações de Segurança
O limite do aniversário estabelece que uma função de hash com bits oferece apenas bits de resistência a colisões. Um atacante precisa de aproximadamente avaliações de hash para encontrar uma colisão — não . Por isso, funções de hash criptográficas são projetadas com saídas maiores do que o nível de segurança desejado:
| Função de hash | Saída | Resistência a colisões |
|---|---|---|
| MD5 | 128 bits | ~ (comprometido na prática) |
| SHA-1 | 160 bits | ~ (comprometido na prática) |
| SHA-256 | 256 bits | ~ (padrão atual) |
| SHA-3-512 | 512 bits | ~ (alta segurança) |
MD5 e SHA-1 são classificados como "comprometidos" não apenas pelo limite do aniversário, mas porque pesquisadores encontraram fraquezas algorítmicas que produzem colisões muito mais rapidamente do que operações. Colisões no MD5 podem ser computadas em hardware comum em questão de minutos usando técnicas publicadas.
Para uma análise relacionada sobre espaços de busca de senhas, consulte Calculadora de Entropia de Senha.
Perguntas frequentes (FAQ)
O que é o paradoxo do aniversário na criptografia?
O paradoxo do aniversário é o resultado contraintuitivo de que, em um grupo de apenas 23 pessoas, já existe mais de 50% de chance de que duas compartilhem a mesma data de aniversário — apesar de haver 365 datas possíveis.
A mesma matemática se aplica às funções de hash: um atacante precisa de aproximadamente √(2^b) = 2^(b/2) itens com hash para atingir 50% de probabilidade de encontrar dois com a mesma saída. Esse é o ataque do aniversário (birthday attack). Para um hash de 128 bits como o MD5, esse limiar é cerca de 2^64 ≈ 1,8 × 10¹⁹ itens — muito menos do que as 2^128 combinações que um ataque de pré-imagem exigiria.
Por que um ataque do aniversário exige apenas a metade dos bits para ser bem-sucedido?
Um ataque de pré-imagem precisa encontrar uma saída de hash específica e, portanto, deve percorrer todo o espaço de 2^b. Um ataque do aniversário precisa apenas que dois quaisquer itens colidam e, pelo limite do aniversário, a probabilidade de encontrar tal par cruza os 50% após aproximadamente 2^(b/2) amostras.
Por isso, funções de hash criptográficas são projetadas com o dobro de bits de saída em relação ao nível de segurança desejado: um hash de 256 bits oferece 128 bits de resistência a colisões.
Por que MD5 e SHA-1 são considerados inseguros?
MD5 (128 bits) e SHA-1 (160 bits) foram comprometidos por ataques práticos de colisão — não apenas ataques probabilísticos baseados no limite do aniversário, mas fraquezas algorítmicas que encontram colisões muito mais eficientemente do que o limite do aniversário prevê. Em 2004, pesquisadores demonstraram colisões no MD5; em 2017, o projeto SHAttered do Google produziu a primeira colisão publicamente conhecida no SHA-1.
Essas funções ainda são seguras para usos não criptográficos, como checksums e endereçamento de conteúdo, mas não devem ser utilizadas onde a resistência a colisões é essencial, como em assinaturas digitais ou autoridades certificadoras.
Qual é a diferença entre uma colisão e uma pré-imagem?
Uma colisão consiste em encontrar dois quaisquer valores distintos x e y tais que hash(x) = hash(y). Uma pré-imagem consiste em encontrar uma entrada x que produza um valor alvo específico h — mais difícil porque não é possível escolher livremente ambas as entradas. Uma segunda pré-imagem consiste em encontrar uma entrada y diferente com o mesmo hash de um x conhecido.
Essas propriedades estão listadas em ordem crescente de dificuldade: a resistência a colisões é a propriedade mais fraca, e a resistência a segunda pré-imagem é a mais forte. Funções de hash usadas em assinaturas digitais precisam resistir a ataques de segunda pré-imagem; as usadas em tabelas de hash ou filtros de Bloom precisam apenas de resistência fraca a colisões.