Resumo

  • O RFC 1186 registrou 1.450.000 bytes por segundo em um Sun SPARC, cerca de 70.000 em um DEC MicroVAX II e 32.000 em um 80286 de 20 MHz. A dificuldade de criar duas mensagens com o mesmo resumo era uma conjectura.
  • O RFC 1320 substituiu a versão de 1990 por uma implementação de referência mais portátil. O RFC 6150 levou MD4 ao estado Historic em 2011, após ataques documentados.

Ronald Rivest entregou aos leitores de 1990 uma função de resumo e um desafio. O RFC 1186 descrevia como obter uma impressão digital de 128 bits de uma mensagem de qualquer tamanho. Uma aplicação prevista era resumir um arquivo antes de assiná-lo com RSA. O desafio era fazer dois arquivos diferentes produzirem a mesma impressão. A resposta inicial do documento para essa segunda parte foi uma estimativa, não um resultado de laboratório.

Já o desempenho tinha bancada. Em um Sun SPARC, o MD4 processava 1.450.000 bytes por segundo; em um DEC MicroVAX II, aproximadamente 70.000; em um 80286 de 20 MHz, aproximadamente 32.000. O texto também destacava a ausência de grandes tabelas de substituição. A especificação descrevia palavras de 32 bits, blocos de 512 bits, preenchimento e o tamanho original da mensagem. No apêndice, interface C, implementação, programa de teste e execução de exemplo davam aos implementadores um objeto concreto para reproduzir.

O cálculo de resistência seguia outro caminho. Rivest conjecturava aproximadamente 2^64 operações para encontrar uma colisão e 2^128 para produzir uma mensagem com um resumo previamente escolhido. Ele chamava o algoritmo de novo e pedia mais análise. Os três computadores mostravam quanto custava executar MD4 sob condições conhecidas. Não podiam medir a criatividade de um adversário futuro. A distinção cabia na mesma página que os números de velocidade.

MD4 foi colocado em domínio público para exame e possível adoção como padrão. O RFC de outubro de 1990 era informativo. A publicidade ajudava tanto quem precisava implementar quanto quem queria tentar quebrar a hipótese. Em abril de 1992, o RFC 1320 tomou o lugar do RFC 1186. Sua principal mudança declarada foi tornar a implementação de referência mais portátil; o texto acrescentou um identificador para aplicações OSI. O código viajava melhor. A pergunta sobre colisões continuava sendo feita.

O RFC 6150, de março de 2011, registrou a resposta acumulada. Um ataque prático de 1996 exigia cerca de 2^20 operações MD4; um resultado de 2004 reduziu a estimativa a 2^8. A promessa de 2^64 de 1990 já tinha perdido o chão. O IETF moveu o RFC 1320 para Historic e recomendou abandonar MD4 em favor de alternativas existentes, como SHA-256.

O documento de retirada também listava usos remanescentes, inclusive uma rota de compatibilidade da Microsoft. A etiqueta Historic organiza o arquivo de normas; os programas instalados e seus parceiros ainda exigem migração. Em duas décadas, a função que era barata de executar acumulou uma conta cara de dependências.

Fontes