¿Cuántos elementos aleatorios antes de que MD5 produzca colisiones?

Question

Tengo una biblioteca de imágenes en Amazon S3. Para cada imagen, md5 la URL de origen en mi servidor más una marca de tiempo para obtener un nombre de archivo único. Como S3 no puede tener subdirectorios, debo almacenar todas estas imágenes en una sola carpeta plana.

¿Debo preocuparme por las colisiones en el valor de hash MD5 que se produce?

Bonus: ¿Cuántos archivos puedo tener antes de comenzar a ver colisiones en el valor hash que produce MD5?

Answer 1

La probabilidad de que solo dos hashes colisionen accidentalmente es 1/2¹²⁸ que es 1 en 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 607 trillion 431 billones 71 mil 456.

Sin embargo, si mantienes todos los hashes, la probabilidad es un poco mayor gracias a paradoja de cumpleaños . Para tener un 50% de probabilidad de que cualquier hash colisione con cualquier otro hash, necesita hashsados ??2⁶⁴ . Esto significa que para obtener una colisión, en promedio, tendrá que hacer un hash 6 mil millones de archivos por segundo durante 100 años .

Answer 2

S3 puede tener subdirectorios. Simplemente ponga un " / " en el nombre de la clave, y puede acceder a los archivos como si estuvieran en directorios separados. Lo uso para almacenar archivos de usuario en carpetas separadas según su ID de usuario en S3.

Por ejemplo: " mybucket / users / 1234 / somefile.jpg " ;. No es exactamente lo mismo que un directorio en un sistema de archivos, pero la API S3 tiene algunas características que le permiten funcionar casi de la misma manera. Puedo pedirle que enumere todos los archivos que comiencen con " usuarios / 1234 / " y me mostrará todos los archivos en ese " directorio " ;.

Answer 3

Así que espera, es:

md5(filename) + timestamp

o:

md5(filename + timestamp)

Si es el primero, es casi un GUID, y no me preocuparía por eso. Si es lo último, vea la publicación de Karg sobre cómo eventualmente se encontrará con colisiones.

Answer 4

Una regla básica para las colisiones es la raíz cuadrada del rango de valores. Su firma MD5 tiene probablemente una longitud de 128 bits, por lo que es probable que vea colisiones por encima y más allá de 2 ^ 64 imágenes.

Answer 5

Aunque las colisiones aleatorias de MD5 son extremadamente raras, si sus usuarios pueden proporcionar archivos (que se almacenarán literalmente), pueden diseñar colisiones para que ocurran. Es decir, pueden crear deliberadamente dos archivos con la misma MD5sum pero con datos diferentes. Asegúrese de que su aplicación pueda manejar este caso de una manera sensata, o tal vez use un hash más fuerte como SHA-256.

Answer 6

Si bien ha habido problemas bien publicitados con MD5 debido a colisiones, las colisiones no intencionales entre datos aleatorios son extremadamente raro . Por otro lado, si tiene un hash en el nombre del archivo, eso no es información aleatoria, y esperaría colisiones rápidamente.

Answer 7

La colisión de MD5 es extremadamente improbable. Si tiene 9 billones de MD5, solo hay una posibilidad en 9 billones de que habrá una colisión.

Answer 8

Realmente no importa lo probable que sea; es posible. Podría suceder en las dos primeras cosas que hash (muy poco probable, pero posible), por lo que tendrás que soportar colisiones desde el principio.