Colisões de hash e explorações

By Ange Albertini and Marc Stevens.

FAQ (TL;DR)

P: É possível fazer um arquivo obter um MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 arbitrário, ou o mesmo hash de outro arquivo?
R: Não.

P: É possível criar 2 arquivos diferentes com o mesmo hash?
R: Com MD5, em alguns segundos em um computador comum. Com SHA1, é possível mas não prático para usuários finais (Complexidade: 2^61.2 Preço: $11k).

P: É possível fazer 2 arquivos diferentes obterem o mesmo hash anexando dados?
R: Com MD5, em algumas horas em um computador comum. Com SHA1, é possível mas não prático para usuários finais (Complexidade: 2^63.4 Preço: $45K)

P: Os 2 arquivos permanecerão válidos?
R: Em geral, sim, pois a maioria dos formatos de arquivo tolera dados anexados. Por outro lado, as assinaturas dos arquivos provavelmente serão quebradas.

P: É possível fazer 2 arquivos diferentes com conteúdos arbitrários e o mesmo hash?
R: Sim, pode ser instantâneo contando com estruturas especiais de arquivo:

1. um cabeçalho de formato especial (ou par) com truques, atuando como um interruptor entre 2 conteúdos (alguns formatos não permitem tais truques).
   
2. colisões pré-computadas, baseadas no(s) cabeçalho(s) específico(s).
   
3. dois conteúdos de formatos específicos, ambos presentes após a colisão (adicionados após o cálculo).

P: Para quais formatos posso obter um par de arquivos com colisão MD5 instantânea?
R: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Basta executar o script específico.

P: E para SHA1?
R: Para SHA1, JPG em um PDF é calculado e implementado.

P: E quanto aos formatos já suportados para MD5 (JPG, PNG...), mas para SHA1?
R: Eles provavelmente também são suportados com SHA1, mas suas colisões ainda não foram calculadas.

P: Os cálculos são mais rápidos para conteúdos semelhantes (mas diferentes)?
R: Não. Qualquer diferença mínima exige um cálculo completo.

P: Quais formatos não têm esse atalho?
R: ELF, Mach-O, Java Class, TAR, ZIP (entre outros...)

P: Colisões clássicas (em algumas horas) ainda são possíveis com esses formatos?
R: Sim, desde que qualquer quantidade de dados anexados seja tolerada (ou seja, provavelmente não ZIP ou Class).

P: Você fornece exemplos de colisões?
R: Sim.

Índice

• Introdução
• Status
• Ataques
  • Prefixo idêntico
    • FastColl (MD5)
    • UniColl (MD5)
    • Shattered (SHA1)
  • Colisões de prefixo escolhido
    • HashClash (MD5)
    • Shambles (SHA1)
  • Resumo dos ataques
• Explorações
  • Estratégia padrão
    • JPG
      • scans personalizados
    • PNG
      • incompatibilidade
    • GIF
    • GZIP
    • LZ4 / Zstandard
    • Portable Executable
    • MP4 e outros
      • JPEG2000
    • PDF
      • JPG em PDF
    • ZIP
      • Formatos baseados em ZIP
    • Outros
  • Estratégias incomuns
    • MultiColls: cadeia de múltiplas colisões
      • Hashquines
    • Validade
    • PolyColls: colisões de diferentes tipos de arquivo
      • PE - JPG
      • PDF - PE
      • PDF - PNG
    • PileUps (multi-colisão)
      • PE - PNG - MP4 - PDF
  • Casos de uso
    • Tem que colidir todos!
    • Arquivos incriminadores
  • Falhas
    • ELF
    • Mach-O
    • Java Class
    • TAR
  • Resumo das explorações
  • Arquivos de teste
• Detecção
  • Hashes seguros
• Referências
• Créditos
• Conclusão

Introdução

O objetivo é explorar extensivamente ataques existentes - e mostrar no caminho o quão fraco é o MD5 (colisões instantâneas de qualquer JPG, PNG, PDF, MP4, PE...) - e também explorar em detalhes formatos de arquivo comuns para determinar como eles podem ser explorados com ataques atuais ou futuros.

De fato, o mesmo truque de formato de arquivo pode ser usado em vários hashes (os mesmos truques de JPG foram usados para MD5, SHA-1 malicioso e SHA1), desde que as colisões sigam os mesmos padrões de bytes.

Este documento não trata de novos ataques (o mais recente foi documentado em 2012), mas de novas formas de exploração de ataques existentes.

Status

Status atual dos ataques conhecidos:

• fazer um arquivo obter o hash de outro arquivo ou um hash específico: impossível

  • ainda não é prático nem com MD2 ou MD4.
  • funciona para hashes mais simples(*)

• obter dois arquivos diferentes com o mesmo MD5: instantâneo

  • exemplos: 1 ⟷ 2

• fazer dois arquivos arbitrários obterem o mesmo MD5: algumas horas (72 horas.core)

  • exemplos: 1 ⟷ 2

• fazer dois arquivos arbitrários de formatos específicos (PNG, JPG, PE...) obterem o mesmo MD5: instantâneo

  • leia abaixo

• obter dois arquivos diferentes com o mesmo SHA1: 6500 anos.core

  • obter dois PDFs diferentes com o mesmo SHA-1 para mostrar um cenário diferente: instantâneo (os prefixos já estão calculados)

(*) exemplo com crypt - obrigado Sven!```

import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'

# Ataques

MD5 e SHA1 trabalham com blocos de 64 bytes.