Quanti elementi casuali prima che MD5 produca collisioni?

Question

Ho una libreria di immagini su Amazon S3. Per ogni immagine, 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 archiviare tutte queste immagini in un'unica cartella piatta.

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

Bonus: quanti file potrei avere prima di iniziare a vedere le collisioni nel valore hash che MD5 produce?

Answer 1

La probabilità che solo due hash si scontrino accidentalmente è 1/2¹²⁸ che è 1 su 340 undecilioni 282 decilioni 366 nonillioni 920 ottilioni 938 settili 463 sextillion 463 quintilioni 374 quadrilioni 607 trilioni 431 miliardi 768 milioni 211 mila 456.

Tuttavia, se mantieni tutti gli hash, la probabilità è un po 'più alta grazie al paradosso del compleanno . Per avere una probabilità del 50% di un hash che si scontra con qualsiasi altro hash, devi avere 2⁶⁴ . Ciò significa che per ottenere una collisione, in media, è necessario eseguire l'hash 6 miliardi file al secondo per 100 anni .

Answer 2

S3 può avere sottodirectory. Inserisci 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 funzionalità che le 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 " ;.

Answer 3

Quindi aspetta, è:

md5(filename) + timestamp

o

md5(filename + timestamp)

Se il primo, sei la maggior parte del modo per un GUID, e non mi preoccuperei. In quest'ultimo caso, vedi il post di Karg su come alla fine ti imbatterai in collisioni.

Answer 4

Una regola empirica approssimativa per le collisioni è la radice quadrata dell'intervallo di valori. Il tuo sig MD5 è presumibilmente lungo 128 bit, quindi probabilmente vedrai collisioni sopra e oltre 2 ^ 64 immagini.

Answer 5

Sebbene le collisioni MD5 casuali siano estremamente rare, se i tuoi utenti sono in grado di fornire file (che verranno archiviati alla lettera), possono progettare collisioni. Cioè, possono deliberatamente creare 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 forse usa un hash più forte come SHA-256.

Answer 6

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

Answer 7

La collisione MD5 è estremamente improbabile. Se hai 9 trilioni MD5, c'è solo una possibilità in 9 trilioni che ci sarà una collisione.

Answer 8

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