Attacchi del compleanno e delle collisioni

In un gruppo di 23 persone, la probabilità che due abbiano lo stesso compleanno supera il 50%. Con 70 persone supera il 99,9%. Matematicamente, in un insieme di dimensione N, la probabilità di collisione supera il 50% dopo circa √N campioni. Questo è il birthday bound.

Per una funzione hash di n bit, una collisione (H(m1) = H(m2), m1 ≠ m2) può essere trovata con circa 2^{n/2} tentativi casuali. Per SHA-256, a 256 bit, trovare una collisione richiede circa 2^{128} operazioni, una quantità computazionalmente impraticabile. Per MD5, a 128 bit, ne servono circa 2^{64}, una quantità al limite della fattibilità.

Ricerca generica delle collisioni: si generano 2^{n/2} messaggi casuali, se ne calcolano gli hash, si ordinano in base al valore hash e si cercano i duplicati. La memoria richiesta è O(2^{n/2}). L'algoritmo Rho, basato sulla ricerca dei cicli di Floyd, riduce la memoria a O(1) mantenendo lo stesso costo temporale. La ricerca parallela delle collisioni di van Oorschot-Wiener riduce il tempo utilizzando hardware.

Wang e colleghi hanno trovato collisioni pratiche per MD5 nel 2004 utilizzando la crittanalisi differenziale, non l'attacco del compleanno. Due messaggi diversi di 1024 bit con hash MD5 identici possono essere generati in pochi secondi. Hertzbleed e le collisioni con prefisso scelto consentono collisioni tra certificati. MD5 è completamente compromesso per quanto riguarda la resistenza alle collisioni.

È un attacco più potente: dati due prefissi arbitrari P1 e P2, si cercano suffissi S1 e S2 tali che H(P1||S1) = H(P2||S2). Stevens e colleghi (2017) hanno trovato collisioni MD5 con prefisso scelto. La tecnica è stata utilizzata per creare un certificato CA dannoso con una firma MD5 valida. Ha portato al ritiro di MD5 dall'uso nei certificati.

SHAttered di Google (2017) è stata la prima collisione pratica per SHA-1. Due file PDF diversi con lo stesso hash SHA-1. Sono state necessarie 2^{63.1} compressioni SHA-1, equivalenti a 6.500 anni di calcolo su CPU e 110 anni su GPU. Il costo è stato di circa 110.000 dollari. Nel 2017 i browser hanno deprecato i certificati SHA-1.

Per le funzioni hash Merkle-Damgård (MD5, SHA-1, SHA-2): se si conosce H(m), è possibile calcolare H(m||padding||m') senza conoscere m. Questo compromette costruzioni MAC come H(secret||message). Soluzione: usare HMAC (che utilizza un padding interno e uno esterno) oppure SHA-3 (costruzione a spugna, immune all'estensione della lunghezza).

Resistenza alle collisioni: trovare due messaggi distinti qualsiasi con lo stesso hash (2^{n/2} di lavoro). Resistenza alla seconda preimmagine: dato m, trovare m' ≠ m con lo stesso hash (2^n di lavoro). Resistenza alla preimmagine: trovare un messaggio qualsiasi per un determinato hash (2^n di lavoro). La resistenza alle collisioni è sempre la più debole.

Se il MAC utilizza una funzione hash vulnerabile alle collisioni, un attaccante in grado di trovare collisioni in H può falsificare i MAC. HMAC-MD5 è considerato sicuro nonostante le collisioni di MD5, perché la costruzione HMAC richiede attacchi di preimmagine, non soltanto collisioni. Tuttavia, per i nuovi sistemi è consigliabile abbandonare HMAC-MD5.

Joux (2004): per le funzioni hash Merkle-Damgård, trovare collisioni tra 2^k messaggi (2^k messaggi con lo stesso hash) richiede soltanto k volte il lavoro necessario per trovare una singola collisione, non k volte tanto. Questo amplifica le vulnerabilità negli hash concatenati (H1(m)||H2(m) non è così sicuro come si potrebbe pensare).

Usare SHA-256 o SHA-3 per l'hashing resistente alle collisioni. Evitare MD5 e SHA-1 per qualsiasi finalità di sicurezza. Per i MAC: HMAC-SHA-256 o HMAC-SHA-3. Per l'hashing delle password: Argon2 (non SHA-2 direttamente). Usare sempre SHA-3 quando è necessaria la resistenza all'estensione della lunghezza.

Un attacco del compleanno trova collisioni hash con 2^{n/2} di lavoro. MD5 presenta collisioni pratiche a prefisso scelto; SHA-1 è stato violato nel 2017. Gli attacchi di estensione della lunghezza compromettono i MAC ingenui H(key||msg). Usare SHA-256 o SHA-3 e HMAC per l'autenticazione dei messaggi. Prossimo argomento: gli attacchi meet-in-the-middle.