È sicuro ignorare la possibilità di collisioni SHA in pratica?

Diciamo che abbiamo un miliardo di immagini uniche, un megabyte ciascuna. Calcoliamo l’hash SHA-256 per i contenuti di ciascun file. La possibilità di collisione dipende da:

  • il numero di file
  • la dimensione del singolo file

Fino a che punto possiamo ignorare questa possibilità, supponendo che sia zero?

La solita risposta va così: qual è la probabilità che un asteroide ribelle si schianta sulla Terra entro il secondo successivo, cancellando la civiltà come lo sappiamo, e uccidendo qualche miliardo di persone? Si può sostenere che qualsiasi evento sfortunato con una probabilità inferiore a quella non è in realtà molto importante.

Se abbiamo una funzione di hash “perfetta” con la dimensione dell’output n e abbiamo messaggi p per l’hash (la lunghezza del singolo messaggio non è importante), allora la probabilità di collisione è di p 2/2 n + 1 (questa è un’approssimazione che è valido per “piccolo” p , cioè sostanzialmente inferiore a 2 n / 2 ). Ad esempio, con SHA-256 ( n = 256 ) e un miliardo di messaggi ( p = 10 9 ), la probabilità è circa 4,3 * 10 -60 .

Uno space rock di assassini di massa avviene in media una volta ogni 30 milioni di anni. Ciò porta ad una probabilità che tale evento si verifichi nel secondo successivo a circa 10-15 . Si tratta di 45 ordini di grandezza più probabili rispetto alla collisione SHA-256. In breve, se trovi che le collisioni SHA-256 sono spaventose, le tue priorità sono sbagliate.

In una configurazione di sicurezza, in cui un utente malintenzionato può scegliere i messaggi che verranno sottoposti a hash, l’autore dell’attacco può utilizzare sostanzialmente più di un miliardo di messaggi; tuttavia, scoprirai che la probabilità di successo dell’attaccante sarà ancora incredibilmente piccola. Questo è il punto principale dell’utilizzo di una funzione di hash con un output a 256 bit: in modo che i rischi di collisione possano essere trascurati.

Ovviamente, tutto quanto sopra presuppone che SHA-256 sia una funzione di hash “perfetta”, che è lungi dall’essere provata. Tuttavia, SHA-256 sembra abbastanza robusto.

La possibilità di una collisione non dipende dalla dimensione dei file, ma solo dal loro numero.

Questo è un esempio del paradosso del compleanno . La pagina di Wikipedia fornisce una stima della probabilità di una collisione. Se si eseguono i numeri, si vedrà che tutti i dischi rigidi mai prodotti sulla Terra non possono contenere abbastanza file da 1 MB per ottenere una probabilità di collisione pari a 0,01% per SHA-256.

Fondamentalmente, puoi semplicemente ignorare la possibilità.

Prima di tutto, non è zero, ma molto vicino allo zero .

La domanda chiave è che cosa succede se si verifica effettivamente una collisione ? Se la risposta è “una centrale nucleare esploderà”, allora probabilmente non dovresti ignorare la possibilità di collisione. Nella maggior parte dei casi le conseguenze non sono così terribili e quindi puoi ignorare la possibilità di collisione.

Inoltre, non dimenticare che il tuo software (o una piccola parte di esso) potrebbe essere implementato e simultaneamente utilizzato in un numero di computer (alcuni piccoli microcomputer integrati che sono quasi ovunque oggigiorno inclusi). In tal caso è necessario moltiplicare la stima ottenuta per il maggior numero ansible di copie.