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, necesito almacenar todas estas imágenes en una sola carpeta plana.
¿Debo preocuparme por las colisiones en el valor hash MD5 que se produce?
Bonificación: ¿Cuántos archivos podría tener antes de comenzar a ver colisiones en el valor hash que produce MD5?
Respuestas:
La probabilidad de colisión accidental de solo dos hashes es 1/2 128, que es 1 en 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billones 768 millones 211 mil 456.
Sin embargo, si mantiene todos los hash, entonces la probabilidad es un poco mayor gracias a la paradoja del cumpleaños . Para tener un 50% de posibilidades de que un hash choque con cualquier otro hash, necesitas 2 64 hashes. Esto significa que para obtener una colisión, en promedio, necesitará hash 6 mil millones de archivos por segundo durante 100 años .
fuente
1 - sPn/s^n, dondeses el tamaño del espacio de búsqueda (2^128en este caso), ynes el número de elementos hash. Probablemente esté pensando en2^64cuál es la cantidad aproximada de elementos que necesitaría para el hash MD5 para tener un 50% de posibilidades de colisión.S3 puede tener subdirectorios. Simplemente coloque una "/" en el nombre de la clave y podrá 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 igual. Puedo pedirle que enumere todos los archivos que comienzan con "usuarios / 1234 /" y me mostrará todos los archivos en ese "directorio".
fuente
Entonces espera, ¿es así?
o:
Si es lo primero, está casi todo el camino hacia un GUID, y no me preocuparía por eso. Si es lo último, entonces vea la publicación de Karg sobre cómo eventualmente se encontrará con colisiones.
fuente
md5(filename) + timestampreduce el riesgo de colisión masivamente porque necesitaría tener una colisión md5 durante exactamente la misma marca de tiempo para tener una colisión en general.md5(filename + timestamp)es lo mismo quemd5(filename), suponiendo que el nombre de archivo es aleatorio para empezar (porque agregar más aleatoriedad a algo aleatorio solo cambia el resultado individual de md5 y el problema de cumpleaños todavía existe en todos los hash de md5).Una regla general aproximada para las colisiones es la raíz cuadrada del rango de valores. Es probable que su firma MD5 tenga 128 bits de largo, por lo que es probable que vea colisiones por encima y más allá de 2 ^ 64 imágenes.
fuente
Aunque las colisiones MD5 aleatorias son extremadamente raras, si sus usuarios pueden proporcionar archivos (que se almacenarán textualmente), entonces pueden diseñar colisiones para que ocurran. Es decir, pueden crear deliberadamente dos archivos con la misma suma MD5 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.
fuente
Si bien ha habido problemas bien publicitados con MD5 debido a colisiones, las colisiones ININTENCIONALES entre datos aleatorios son extremadamente raras . Por otro lado, si está tropezando con el nombre del archivo, no se trata de datos aleatorios, y esperaría colisiones rápidamente.
fuente
Realmente no importa cuán probable sea; es posible. Podría suceder en las dos primeras cosas que hash (muy poco probable, pero posible), por lo que deberás soportar las colisiones desde el principio.
fuente
La colisión MD5 es extremadamente improbable. Si tienes 9 billones de MD5, solo hay una posibilidad en 9 billones de que haya una colisión.
fuente