Ataques de aniversário e de colisão

Em um grupo de 23 pessoas, a probabilidade de duas compartilharem a mesma data de aniversário ultrapassa 50%. Com 70 pessoas, ultrapassa 99,9%. Matematicamente: em um conjunto de tamanho N, a probabilidade de colisão ultrapassa 50% após aproximadamente √N amostras. Esse é o limite do aniversário.

Para uma função de hash de n bits: uma colisão (H(m1) = H(m2), m1 ≠ m2) pode ser encontrada com aproximadamente 2^{n/2} tentativas aleatórias. Para SHA-256 (256 bits), uma colisão exige aproximadamente 2^{128} operações, o que é computacionalmente inviável. Para MD5 (128 bits), são aproximadamente 2^{64}, uma quantidade no limite da viabilidade.

Descoberta genérica de colisões: gere 2^{n/2} mensagens aleatórias, calcule os hashes, ordene-os pelo valor do hash e encontre duplicatas. Memória O(2^{n/2}). O algoritmo Rho (detecção de ciclos de Floyd) reduz a memória para O(1), mantendo o mesmo custo de tempo. A busca paralela de colisões de van Oorschot-Wiener reduz o tempo usando equipamento.

Colisões práticas do MD5 foram encontradas por Wang et al. (2004) usando criptoanálise diferencial, não o ataque de aniversário. Duas mensagens diferentes de 1024 bits com o mesmo hash MD5 em segundos. Colisões de prefixo escolhido do Hertzbleed permitem colisões de certificados. O MD5 está completamente comprometido quanto à resistência a colisões.

Mais poderosas: dados dois prefixos arbitrários P1 e P2, encontre sufixos S1 e S2 tais que H(P1||S1) = H(P2||S2). Stevens et al. (2017) encontraram colisões de prefixo escolhido no MD5. Isso foi usado para criar um certificado malicioso de CA com uma assinatura MD5 válida. O MD5 foi retirado do uso em certificados.

SHAttered, do Google (2017): a primeira colisão prática do SHA-1. Dois arquivos PDF diferentes com o mesmo hash SHA-1. Foram necessárias 2^{63.1} compressões do SHA-1, equivalentes a 6.500 anos de CPU e 110 anos de GPU. Custo de aproximadamente US$ 110.000. Os navegadores deixaram de aceitar certificados SHA-1 em 2017.

Para funções de resumo Merkle-Damgård (MD5, SHA-1, SHA-2): se conhecer H(m), poderá calcular H(m||padding||m') sem conhecer m. Isso quebra construções de MAC como H(secret||message). Correção: utilize HMAC (que usa preenchimento interno e externo) ou SHA-3 (construção esponja, imune à extensão de comprimento).

Resistência a colisões: encontrar quaisquer duas mensagens distintas com o mesmo resumo (esforço 2^{n/2}). Resistência à segunda pré-imagem: dado m, encontrar m' ≠ m com o mesmo resumo (esforço 2^n). Resistência à pré-imagem: encontrar qualquer mensagem para um resumo fornecido (esforço 2^n). A colisão é sempre a propriedade mais fraca.

Se o MAC utilizar uma função de resumo vulnerável a colisões: um atacante que consiga encontrar colisões em H poderá forjar MACs. HMAC-MD5 é considerado seguro apesar das colisões do MD5, porque a construção do HMAC exige ataques de pré-imagem, não apenas colisões. Mas migre do HMAC-MD5 em sistemas novos.

Joux (2004): para resumos Merkle-Damgård, encontrar colisões de 2^k vias (2^k mensagens com o mesmo resumo) exige apenas k vezes o trabalho de encontrar uma única colisão, em vez de multiplicar esse custo a cada colisão. Isso agrava as vulnerabilidades em resumos concatenados (H1(m)||H2(m) não é tão forte quanto se poderia imaginar).

Utilize SHA-256 ou SHA-3 para resumos resistentes a colisões. Evite MD5 e SHA-1 para qualquer finalidade de segurança. Para MACs: HMAC-SHA-256 ou HMAC-SHA-3. Para resumir senhas: Argon2 (não SHA-2 diretamente). Utilize sempre SHA-3 quando for necessária resistência à extensão de comprimento.

Aproximadamente quantas avaliações de resumo são necessárias para encontrar uma colisão em uma função de resumo de n bits?

O ataque do aniversário encontra colisões de resumo com 2^{n/2} de trabalho. O MD5 tem colisões de prefixo escolhido práticas; o SHA-1 foi quebrado em 2017. Ataques de extensão de comprimento quebram MACs ingênuos H(key||msg). Utilize SHA-256 ou SHA-3; utilize HMAC para autenticação de mensagens. Próximo: ataques de encontro no meio.