Collisioni di hash e sfruttamenti

Di Ange Albertini e Marc Stevens.

FAQ (TL;DR)

D: È possibile fare in modo che un file ottenga un MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 arbitrario, o lo stesso hash di un altro file?
R: No.

D: Si possono creare 2 file diversi con lo stesso hash?
R: Con MD5, in pochi secondi su un computer standard. Con SHA1, è possibile ma non pratico per gli utenti finali (Complessità: 2^61.2 Prezzo: $11k).

D: Si può fare in modo che 2 file diversi ottengano lo stesso hash aggiungendo dati?
R: Con MD5, in poche ore su un computer standard. Con SHA1, è possibile ma non pratico per gli utenti finali (Complessità: 2^63.4 Prezzo: $45K)

D: I 2 file rimarranno validi?
R: In generale, sì, poiché la maggior parte dei formati di file tollera dati aggiunti. D'altra parte, le firme dei file saranno probabilmente rotte.

D: Si possono creare 2 file diversi con contenuti arbitrari e lo stesso hash?
R: Sì, può essere immediato facendo affidamento su strutture di file speciali:

1. un header di formato speciale (o una coppia) con trucchi, che funge da interruttore tra 2 contenuti (alcuni formati non permettono tali trucchi).
   
2. collisioni pre-calcolate, basate sull'header o gli header specifici.
   
3. due contenuti di formati specifici, entrambi presenti dopo la collisione (aggiunti dopo il calcolo).

D: Per quali formati posso ottenere una coppia di file con collisione MD5 istantanea?
R: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Basta eseguire lo script specifico.

D: E per SHA1?
R: Per SHA1, JPG in un PDF è calcolato e implementato.

D: E i formati già supportati per MD5 (JPG, PNG...), ma per SHA1?
R: È molto probabile che siano supportati anche con SHA1, ma le loro collisioni non sono state calcolate.

D: I calcoli sono più veloci per contenuti simili (ma diversi)?
R: No. Qualsiasi minima differenza richiede un calcolo completo.

D: Quali formati non hanno questa scorciatoia?
R: ELF, Mach-O, Java Class, TAR, ZIP (tra gli altri...)

D: Le collisioni classiche (in poche ore) sono ancora possibili con questi formati?
R: Sì, purché venga tollerata qualsiasi quantità di dati aggiunti (cioè probabilmente non ZIP o Class).

D: Fornite esempi di collisioni?
R: Sì.

Indice

• Introduzione
• Stato
• Attacchi
  • Prefisso identico
    • FastColl (MD5)
    • UniColl (MD5)
    • Shattered (SHA1)
  • Collisioni a prefisso scelto
    • HashClash (MD5)
    • Shambles (SHA1)
  • Riepilogo degli attacchi
• Sfruttamenti
  • Strategia standard
    • JPG
      • scansioni personalizzate
    • PNG
      • incompatibilità
    • GIF
    • GZIP
    • LZ4 / Zstandard
    • Portable Executable
    • MP4 e altri
      • JPEG2000
    • PDF
      • JPG in PDF
    • ZIP
      • Formati basati su ZIP
    • Altri
  • Strategie non comuni
    • MultiColls: catena di collisioni multiple
      • Hashquines
    • Validità
    • PolyColls: collisioni di diversi tipi di file
      • PE - JPG
      • PDF - PE
      • PDF - PNG
    • PileUps (multi-collisione)
      • PE - PNG - MP4 - PDF
  • Casi d'uso
    • Falli collidere tutti!
    • File incriminanti
  • Fallimenti
    • ELF
    • Mach-O
    • Java Class
    • TAR
  • Riepilogo degli sfruttamenti
  • File di test
• Rilevamento
  • Hash sicuri
• Riferimenti
• Crediti
• Conclusione

Introduzione

L'obiettivo è esplorare a fondo gli attacchi esistenti - e mostrare lungo il percorso quanto sia debole MD5 (collisioni istantanee di qualsiasi JPG, PNG, PDF, MP4, PE...) - e anche esplorare in dettaglio i formati di file comuni per determinare come possono essere sfruttati con attacchi presenti o futuri.

In effetti, lo stesso trucco del formato di file può essere usato su più hash (gli stessi trucchi JPG sono stati usati per MD5, malicious SHA-1 e SHA1), purché le collisioni seguano gli stessi pattern di byte.

Questo documento non riguarda nuovi attacchi (il più recente è stato documentato nel 2012), ma nuove forme di sfruttamento degli attacchi esistenti.

Stato

Stato attuale degli attacchi noti:

• ottenere che un file abbia l'hash di un altro file o un hash dato: impossibile

  • non è ancora nemmeno pratico con MD2 o MD4.
  • funziona per hash più semplici(*)

• ottenere due file diversi con lo stesso MD5: istantaneo

  • esempi: 1 ⟷ 2

• far ottenere a due file arbitrari lo stesso MD5: poche ore (72 ore.core)

  • esempi: 1 ⟷ 2

• far ottenere a due file arbitrari di formati di file specifici (PNG, JPG, PE...) lo stesso MD5: istantaneo

  • leggi sotto

• ottenere due file diversi con lo stesso SHA1: 6500 anni.core

  • ottenere due PDF diversi con lo stesso SHA-1 per mostrare un quadro diverso: istantaneo (i prefissi sono già calcolati)

(*) esempio con crypt - grazie Sven!```

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

# Attacchi

MD5 e SHA1 lavorano con blocchi di 64 byte.