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

Necesito que preocuparse acerca de colisiones en el valor hash MD5 que se produce?

Bonus: ¿cuántos archivos puedo tener antes de que me gustaría empezar a ver las colisiones en el valor hash MD5 produce?

InformationsquelleAutor Ben Throop | 2008-10-14

8 Comentarios

  1. 277

    Probabilidad de sólo dos hashes chocar accidentalmente se 1/2128 que es 1 en 340 undecillion 282 decillion 366 nonillion 920 octillion 938 cuatrillón 463 sextillion 463 trillones 374 607 mil billones de billones de 431 millones de 768 millones 211 mil 456.

    Sin embargo, si usted mantiene todos los hash entonces la probabilidad es un poco más alto, gracias a la paradoja de cumpleaños. Para tener un 50% de probabilidad de cualquier hash chocar con cualquier otro hash necesita 264 hashes. Esto significa que para obtener una colisión, en promedio, usted necesitará hash 6 mil millones de dólares archivos por segundo de 100 años.

    • +1 para agregar el cálculo. Esto es un poco más precisa: http://www.google.com/search?q=2^64%2F100*(seconds+per+year)
    • No es estrictamente cierto. La probabilidad de una colisión es mucho mayor que este como una nueva URL potencialmente podría chocar con cualquier elemento existente en la tabla. Consulte Esta publicación (descargo de responsabilidad, lo escribí) para una carrera hacia abajo en las matemáticas, y un pequeño script en python que puede ser adaptado para calcular la probabilidad de que un determinado número de direcciones Url.
    • Me hizo tomar la corrección de la paradoja de cumpleaños, que es la razón por la respuesta está en los miles de millones, no quintillions. Yo era incapaz de verificar la probabilidad de la secuencia de comandos PV=2**128; SS=2**64: OverflowError: long int too large to convert to int
    • «la probabilidad de colisión es de 1/2^64» – ¿qué? La probabilidad de colisión depende de la cantidad de elementos que ya están hash, no es un número fijo. De hecho, es exactamente igual a 1 - sPn/s^n, donde s es el tamaño del espacio de búsqueda (2^128 en este caso), y n es el número de elementos de hash. Lo que usted probablemente está pensando es 2^64, que es el número aproximado de los elementos que sería necesario hash MD5 para tener un 50% de probabilidad de colisión.
    • eso es lo que yo tenía en mente, de hecho. Gracias por la corrección.
    • +1 porque siempre he querido saber cómo contar pasado un 999 billones de dólares lol (y, oh, sí, su respuesta fue informativo)
    • Por desgracia, todavía no es correcta. Usted está asumiendo que la función de hash es verdaderamente aleatorio. No es. Esto significa que la probabilidad de colisión es mayor.
    • JørgenFogh: Y todas las leyes de la física no son «correctas», ya sea. Tal nivel de pedantism es innecesario, ya que no cambia la respuesta en forma significativa.
    • (Esto significa que para obtener una colisión, en promedio, usted necesitará hash 6 mil millones de archivos por segundo durante 100 años.); incorrecto. esto significa que por el el tiempo ha sido hash 6 mil millones de archivos por segundo en 100 años, el 50% de los hashes se están generando sería incompatible con el previamente generado hashes.
    • No, eso es ridículamente imposible. Estoy hablando acerca de la generación de 2^64 hashes de 2^128 posibles. Que una trillonésima de el por ciento de todos los posibles valores hash generados.
    • Intuitivamente, si hacemos caso de la paradoja de cumpleaños y simplemente mirar una solución aproximada: Añadir 2^64 hash en una lista. Ahora añadir uno más de hash a esa lista. Que uno más hash ha 1 / 2^128 veces 2^64 la posibilidad de una colisión, es decir, que uno de los más hash tiene una 1 / 2^64 la posibilidad de una colisión. Ahora agregue otro 2^64 hash a la lista y usted debe obtener una colisión. Hacer el mismo cálculo para 2^63 (y nota 2^63 + 2^63 = 2^64).
    • Así que usted está diciendo que hay una oportunidad!
    • Lo tengo 🙂

  2. 25

    S3 puede tener subdirectorios. Sólo hay que poner un «/» en el nombre de la clave, y puedes acceder a los archivos como si estuvieran en directorios separados. Lo utilizo para almacenar los archivos de usuario en carpetas separadas, basándose en su ID de usuario en el S3.

    Por ejemplo: «mybucket/users/1234/somefile.jpg». No es exactamente el mismo que el de un directorio en un sistema de archivos, pero el S3 API tiene algunas características que le permiten trabajar casi de la misma. Puedo pedir a la lista todos los archivos que comiencen con «usuarios/1234/» y me muestre todos los archivos en el «directorio».

    • Este debe ser un contenido creo, ya que en realidad no responder a la pregunta acerca de la probabilidad de una colisión
  3. 17

    Así que espera, es:

    md5(filename) + timestamp
    

    o:

    md5(filename + timestamp)
    

    Si el anterior, usted es la mayoría de la manera de un GUID, y yo no me preocuparía por eso.
    Si la última, después de ver Karg el post sobre cómo se va a ejecutar en las colisiones con el tiempo.

    • Sírvanse explicar en detalle cómo incluida la marca de tiempo aumenta la probabilidad de colisión
    • No. El MD5 riesgo de colisión es la misma que si es en el nombre de archivo o la combinación de nombre de archivo+timestamp. Pero en el primer caso, usted tendría que tener tanto un MD5 de la colisión y una marca de tiempo de la colisión.
    • Esto todavía deja un 2^(128^60) de probabilidad de una collission con dos usuarios por minuto. Literalmente inutilizable.
    • Para ser más claro: md5(filename) + timestamp reduce el riesgo de choque masivamente porque usted tendría que tener un md5 de colisión por exactamente la misma marca de tiempo para tener una colisión en general. md5(filename + timestamp) es el mismo que md5(filename), suponiendo que el nombre de archivo es al azar para empezar (ya que la adición de más de aleatoriedad a algo aleatorio sólo a los cambios que el individuo md5 resultado y el problema del cumpleaños todavía existe en todos los hash de md5).
  4. 10

    Una regla básica para las colisiones es la raíz cuadrada de la gama de valores. Su MD5 sig es de suponer que la longitud de 128 bits, así que, va a estar propensos a ver las colisiones por encima y más allá de 2^64 imágenes.

  5. 7

    Aunque aleatorios MD5 las colisiones son muy raras, si los usuarios pueden proporcionar archivos (que va a ser almacenado verbatim), entonces se puede ingeniero de colisiones que se producen. Es decir, se puede crear deliberadamente dos archivos con el mismo MD5sum pero con diferentes datos. Asegúrese de que su aplicación puede controlar este caso de una manera sensible, o tal vez el uso más seguro como SHA-256.

    • el uso de una sal se haría cargo de el usuario de ingeniería problema, no?
    • Depende de cómo la sal se aplica. Tendría que ser un prefijo de los datos proporcionados por el usuario, o mejor aún, la clave para un HMAC. Es probablemente una buena idea a la práctica de la defensa en profundidad, aunque.
    • Nota aunque SHA256 es de 256 bits de longitud, puede compensar el riesgo de colisiones con la longitud de la clave que se van a almacenar por truncar el SHA256 a menos bits por ejemplo, el uso SHA256 pero truncar a 128 bits (más seguro que el uso de MD5 aunque tienen el mismo número de bits).
  6. 5

    Aunque no han sido bien conocidos problemas con MD5, debido a las colisiones, no INTENCIONAL de colisiones entre los datos aleatorios son muy rara. Por otro lado, si eres de hash en el nombre de archivo, que no aleatoria de los datos, y yo esperaría que las colisiones rápidamente.

    • El único problema que tengo con taylors ejemplo es que si alguien recibe una copia de la base de datos que probablemente podría averiguar los números de tarjeta de crédito usando un arco iris tabla …
    • Mientras yo no elegir el uso de MD5 para tarjetas de crédito, un arco iris tabla de válidos todos los números de tarjeta de crédito entre 10,000,000 (8 dígitos, siendo el más pequeño de la longitud de la tarjeta de crédito que yo he visto) y 9,999,999,999,999,999 (mayor número de 16 dígitos) es todavía un gran tabla para generar. Probablemente hay maneras más fáciles de robar los números.
  7. 1

    Realmente no importa qué tan probable es; es posible. Podría ocurrir que en las dos primeras cosas que usted hash (muy poco probable, pero posible), así que usted necesitará para apoyar a las colisiones desde el principio.

    • Por supuesto, puede ser muchas otras cosas malas que pueden ocurrir con una probabilidad de 1/2^128. Puede que usted no quiera solo esta uno de los que preocuparse.
    • La cosa peor que puede pasar aquí es que usted puede conseguir una foto. Para un número relativamente pequeño no me preocuparía. Ahora si tu software es el control de un piloto automático de aterrizaje de un avión, eso es otra historia.
    • No se puede ser serio. Usted necesitará hash 6 mil millones de archivos por segundo, cada segundo durante 100 años para obtener una buena probabilidad de colisión. Incluso si eres muy, muy mala suerte, es probable que tome más de toda la capacidad de S3 usado por más de la vida del ser humano.
    • Es de miles de millones de veces más probabilidades de que su base de datos y sus copias de seguridad todos fallan. Las colisiones son no vale la pena preocuparse.
    • El uso de la prevención de colisiones en tiempo la construcción de un bunker para poner su servidor! Esos molestos meteoros puede golpear (muy poco probable, pero posible), por lo que necesitará el apoyo de meteoros refugio de la mendicidad.
    • Se necesitarían 100 años para llegar a un 50% probabilidad de colisión en el 6G archivos / seg. Usted tiene un buena probabilidad de colisión en décadas anteriores.

  8. 1

    MD5 de la colisión es extremadamente raro. Si usted tiene 9 billones de Md5, solo hay una oportunidad en 9 billones de que habrá una colisión.

    • Muchas de las otras Respuestas hablar de la probabilidad de una colisión cuando la adición de un elemento más. Creo que mi Respuesta son más útiles, porque habla de la, probablemente, de toda la tabla de tener una dup.
    • Esto no tiene nada que ver con MD5 y no es correcto. Es como decir que si usted tiene los 9 billones de gatos hay un 1 en 9 billones de posibilidades de que alguien más tiene un idéntico gato. El problema clave aquí es que usted puede conseguir el mismo hash con más de un valor.
    • Sí, eso es cierto. Y mucha gente pobre usar eso como una excusa para comprar otro boleto de la Lotería que no pueden permitirse.

Dejar respuesta

Please enter your comment!
Please enter your name here