Calcolatore di probabilità di collisione hash
Dati di input
| Dimensione hash | 128 |
|---|---|
| Numero di elementi | 1.000.000 |
Calcolatore di probabilità di collisione hash
Stima la probabilità di una collisione di compleanno tra un insieme di valori hash e calcola quanti elementi sono necessari per raggiungere il 50% di probabilità di collisione per una dimensione hash data.
Dati di input
Parametri hash
Risultati
Inserisci un valore per visualizzare i risultati.
Probabilità di collisione
Probabilità di collisione hash
Una funzione hash mappa un input di lunghezza arbitraria in un output a lunghezza fissa denominato digest. Idealmente nessun input distinto produce lo stesso digest — una proprietà chiamata resistenza alle collisioni. In pratica, poiché lo spazio di output è finito, le collisioni devono esistere; la domanda è quanti input devono essere sottoposti a hashing prima che una collisione sia probabile. Questo calcolatore quantifica tale probabilità utilizzando l'approssimazione del compleanno, che prende il nome dal paradosso del compleanno.
Il paradosso del compleanno
In un gruppo di 23 persone estratte a caso da un anno di 365 giorni, la probabilità che due di esse condividano il giorno del compleanno è già superiore al 50%. La probabilità è molto più alta di quanto suggerisca l'intuizione perché considera qualsiasi coppia all'interno del gruppo, non una corrispondenza con un obiettivo specifico. La stessa asimmetria regola le collisioni hash: trovare due input con lo stesso hash (una collisione) è molto più semplice che trovare un input che produca un hash obiettivo specifico (una preimmagine).
Formula
Per una funzione hash con bit di output, lo spazio di ricerca ha valori equiprobabili. Dati elementi sottoposti a hashing in modo casuale, la probabilità di collisione esatta è il complemento della probabilità che tutti gli output siano distinti:
p=1−k=0∏n−1(1−2bk)Per grande e moderato, l'approssimazione del compleanno fornisce una forma chiusa più semplice:
p≈1−e−n2/(2⋅2b)Risolvendo per il numero di elementi al quale la probabilità raggiunge il 50%:
n50%=2⋅2b⋅ln2Esempio
Per un hash a 32 bit (come CRC32 utilizzato nei checksum):
n50%=2×232×ln2=2×4294967296×0.6931≈5954124768≈77163Con appena 77.163 file in un repository, esiste circa il 50% di probabilità che due condividano lo stesso CRC a 32 bit. Confermando con la formula dell'approssimazione:
p=1−e−771632/(2×232)≈1−e−0.693≈0.50Questo spiega perché CRC32 non è adatto come identificatore univoco in raccolte di grandi dimensioni, anche se è un ottimo codice di rilevamento degli errori su flussi di dati ridotti.
Implicazioni per la sicurezza
Il bound del compleanno stabilisce che una funzione hash con bit offre solo bit di resistenza alle collisioni. Un attaccante ha bisogno di circa valutazioni hash per trovare una collisione — non . Per questo motivo le funzioni hash crittografiche vengono progettate con output più grandi rispetto al livello di sicurezza obiettivo:
| Funzione hash | Output | Resistenza alle collisioni |
|---|---|---|
| MD5 | 128 bit | ~ (violata in pratica) |
| SHA-1 | 160 bit | ~ (violata in pratica) |
| SHA-256 | 256 bit | ~ (standard attuale) |
| SHA-3-512 | 512 bit | ~ (alta sicurezza) |
MD5 e SHA-1 sono classificate come "violate" non solo a causa del bound del compleanno, ma perché i ricercatori hanno scoperto debolezze algoritmiche che producono collisioni molto più velocemente di operazioni. Le collisioni MD5 possono essere calcolate su hardware comune in pochi minuti utilizzando tecniche pubbliche.
Per un'analisi correlata degli spazi di ricerca delle password, vedere Calcolatore di entropia delle password.
Domande frequenti (FAQ)
Cos'è il paradosso del compleanno in crittografia?
Il paradosso del compleanno è il risultato controintuitivo secondo cui in un gruppo di sole 23 persone esiste già una probabilità superiore al 50% che due di esse condividano il giorno del compleanno, nonostante ci siano 365 compleanni possibili.
La stessa matematica si applica alle funzioni hash: un attaccante ha bisogno di circa √(2^b) = 2^(b/2) elementi sottoposti a hashing per raggiungere il 50% di probabilità di trovarne due con lo stesso output. Questo è l'attacco del compleanno. Per un hash a 128 bit come MD5, tale soglia è circa 2^64 ≈ 1,8 × 10¹⁹ elementi — molto meno delle 2^128 combinazioni richieste da un attacco di preimmagine.
Perché un attacco del compleanno richiede solo la metà dei bit?
Un attacco di preimmagine deve trovare uno specifico output hash e quindi deve esplorare l'intero spazio 2^b. Un attacco del compleanno ha bisogno soltanto che due input qualsiasi collidano; per il bound del compleanno, la probabilità di trovare tale coppia supera il 50% dopo circa 2^(b/2) campioni.
Per questo motivo le funzioni hash vengono tipicamente progettate con il doppio dei bit di output rispetto al livello di sicurezza desiderato: un hash a 256 bit offre una resistenza alle collisioni di 128 bit.
Perché MD5 e SHA-1 sono considerati insicuri?
MD5 (128 bit) e SHA-1 (160 bit) sono stati violati da attacchi di collisione pratici — non solo attacchi probabilistici basati sul bound del compleanno, ma debolezze algoritmiche che trovano collisioni con un'efficienza ben superiore a quanto il bound del compleanno prevede. Nel 2004 i ricercatori dimostrarono collisioni MD5; nel 2017 il progetto SHAttered di Google produsse la prima collisione SHA-1 pubblicamente nota.
Queste funzioni rimangono sicure per usi non crittografici come checksum e content-addressing, ma non devono essere utilizzate nei contesti in cui la resistenza alle collisioni è importante, come le firme digitali o le autorità di certificazione.
Qual è la differenza tra una collisione e una preimmagine?
Una collisione consiste nel trovare due input distinti x e y tali che hash(x) = hash(y). Una preimmagine consiste nel trovare un input x il cui hash corrisponde a un valore obiettivo h specifico — più difficile perché non è possibile scegliere liberamente entrambi gli input. Una seconda preimmagine consiste nel trovare un input y diverso che produce lo stesso hash di un x noto.
Queste proprietà sono elencate in ordine crescente di difficoltà: la resistenza alle collisioni è la proprietà più debole, mentre la resistenza alla seconda preimmagine è la più forte. Le funzioni hash utilizzate nelle firme digitali devono resistere agli attacchi di seconda preimmagine; quelle usate in hash table o filtri di Bloom richiedono solo una debole resistenza alle collisioni.