Quanti elementi casuali prima che MD5 produca collisioni?

Ho una libreria di immagini su Amazon S3. Per ogni immagine, ho MD5 l’URL di origine sul mio server più un timestamp per ottenere un nome file univoco. Poiché S3 non può avere sottodirectory, ho bisogno di memorizzare tutte queste immagini in una singola cartella piatta.

Devo preoccuparmi delle collisioni nel valore hash MD5 che viene prodotto?

Bonus: quanti file potrei avere prima di iniziare a vedere collisioni nel valore hash prodotto da MD5?

La probabilità di appena due collisioni accidentalmente in collisione è di 1/2 128 che è 1 su 340 undecillion 282 decillion 366 nonillion 920 ottillion 938 settsillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 miliardi 768 milioni 211 mila 456.

Tuttavia se si mantengono tutti gli hash allora la probabilità è un po ‘più alta grazie al paradosso del compleanno . Per avere una probabilità del 50% di avere un hash in collisione con qualsiasi altro hash hai bisogno di 2 64 hash. Ciò significa che per ottenere una collisione, in media, avrai bisogno di hash 6 miliardi di file al secondo per 100 anni .

S3 può avere sottodirectory. Basta inserire un “/” nel nome della chiave e puoi accedere ai file come se fossero in directory separate. Lo uso per archiviare i file utente in cartelle separate in base al loro ID utente in S3.

Ad esempio: “mybucket / users / 1234 / somefile.jpg”. Non è esattamente la stessa di una directory in un file system, ma l’API S3 ha alcune caratteristiche che gli consentono di funzionare quasi allo stesso modo. Posso chiedergli di elencare tutti i file che iniziano con “users / 1234 /” e mi mostrerà tutti i file in quella “directory”.

Quindi aspetta, è così:

 md5(filename) + timestamp 

o:

 md5(filename + timestamp) 

Se la prima è la maggior parte della strada verso un GUID, non me ne preoccuperei. Se quest’ultimo, poi vedi il post di Karg su come ti imbatterai in collisioni alla fine.

Una regola empirica per le collisioni è la radice quadrata dell’intervallo di valori. Il tuo MD5 sig è presumibilmente lungo 128 bit, quindi è probabile che tu possa vedere collisioni oltre e oltre le immagini 2 ^ 64.

Sebbene le collisioni MD5 casuali siano estremamente rare, se i tuoi utenti possono fornire file (che verranno archiviati letteralmente), possono quindi progettare collisioni. Cioè, possono creare deliberatamente due file con lo stesso MD5sum ma dati diversi. Assicurati che la tua applicazione sia in grado di gestire questo caso in modo ragionevole, o magari usare un hash più forte come SHA-256.

Mentre ci sono stati problemi ben pubblicizzati con MD5 a causa di collisioni, le collisioni non intenzionali tra dati casuali sono estremamente rare . D’altra parte, se si esegue l’hashing sul nome del file, non si tratta di dati casuali, e mi aspetterei che le collisioni si verifichino rapidamente.

La collisione MD5 è estremamente improbabile. Se hai 9 trilioni di MD5, c’è una sola possibilità in 9 trilioni di collisione.

Non importa quanto sia probabile; è ansible. Potrebbe succedere nelle prime due cose che hai (molto improbabile, ma ansible), quindi dovrai supportare le collisioni dall’inizio.