¿Cómo puedo evaluar la probabilidad de colisión hash?

Question

Estoy desarrollando una aplicación de back-end para un sistema de búsqueda. El sistema de búsqueda copia archivos en un directorio temporal y les da nombres aleatorios. Luego pasa los nombres de los archivos temporales a mi aplicación. Mi aplicación debe procesar cada archivo dentro de un período de tiempo limitado; de lo contrario, se cierra; esa es una medida de seguridad similar a la de un perro guardián. Procesar archivos es probable que tome mucho tiempo, así que necesito diseñar la aplicación capaz de manejar este escenario. Si mi aplicación se cierra la próxima vez que el sistema de búsqueda quiera indexar el mismo archivo, probablemente le dé un nombre temporal diferente.

La solución obvia es proporcionar una capa intermedia entre el sistema de búsqueda y el back-end. Pondrá en cola la solicitud al back-end y esperará a que llegue el resultado. Si la solicitud expira en la capa intermedia, no hay problema, el servidor continuará funcionando, solo la capa intermedia se reinicia y puede recuperar el resultado del servidor cuando el sistema de búsqueda repite la solicitud.

El problema es cómo identificar los archivos. Sus nombres cambian aleatoriamente. Tengo la intención de utilizar una función hash como MD5 para hash el contenido del archivo. Conozco bien el birthday paradox y usé una estimación del artículo vinculado para calcular la probabilidad. Si asumo que no tengo más de 100   000 archivos, la probabilidad de que dos archivos tengan el mismo MD5 (128 bit) es aproximadamente 1,47x10 ^-29.

¿Debo cuidar esa probabilidad de colisión o simplemente asumir que los valores de hash iguales significan el mismo contenido de archivo?

Answer 1

Equal hash significa archivo igual, a menos que alguien malicioso esté jugando con sus archivos e inyectándose colisiones. (Este podría ser el caso si están descargando cosas de Internet) Si ese es el caso, vaya a una función basada en SHA2.

No hay accidentes accidentales MD5, 1,47x10 ^-29 es un número realmente muy pequeño.

Para solucionar el problema de volver a procesar archivos grandes, tendría un esquema de identidad de 3 fases.

1. Tamaño solos
2. Tamaño del archivo + un hash de 64 K * 4 en diferentes posiciones en el archivo
3. Un hash completo

Así que si ves un archivo con un nuevo tamaño que sepa seguro que no tienes un duplicado. Y así.

Answer 2

Creo que no deberías.

Sin embargo, debe hacerlo si tiene la noción de que dos archivos iguales tienen nombres diferentes (nombres reales, no basados ​​en md5). Al igual, en el sistema de búsqueda, dos documentos pueden tener exactamente el mismo contenido, pero son distintos porque están ubicados en lugares diferentes.

Answer 3

Inventé un enfoque de Monte Carlo para poder dormir de forma segura mientras uso el UUID para sistemas distribuidos que tienen que serializarse sin colisiones.

from random import randint 
from math import log 
from collections import Counter 

def colltest(exp): 
    uniques = [] 
    while True: 
     r = randint(0,2**exp) 
     if r in uniques: 
      return log(len(uniques) + 1, 2) 
     uniques.append(r) 

for k,v in Counter([colltest(20) for i in xrange(1000)]): 
    print k, "hash orders of magnitude events before collission:",v 

imprimiría algo como:

5 hash orders of magnitude events before collission: 1 
6 hash orders of magnitude events before collission: 5 
7 hash orders of magnitude events before collission: 21 
8 hash orders of magnitude events before collission: 91 
9 hash orders of magnitude events before collission: 274 
10 hash orders of magnitude events before collission: 469 
11 hash orders of magnitude events before collission: 138 
12 hash orders of magnitude events before collission: 1 

que había oído la fórmula antes: Si necesita almacenar claves (x/2) registrar, utilizar una función hash que tiene por lo menos espacio de claves e * *(X).

Experimentos repetidos muestran que para una población de 1000 log-20 espacios, a veces se produce una colisión tan pronto como log (x/4).

Para uuid4 que es de 122 bits, eso significa que duermo de forma segura, mientras que varias computadoras eligen el uuid aleatorio hasta que tengo aproximadamente 2 ** 31 elementos. Las transacciones pico en el sistema en las que estoy pensando son aproximadamente 10-20 eventos por segundo, supongo que un promedio de 7. Eso me da una ventana operativa de aproximadamente 10 años, dada esa paranoia extrema.

Answer 4

Aquí es una calculadora interactiva que le permite estimar la probabilidad de colisión para cualquier tamaño de hash y el número de objetos - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

Answer 5

El hecho de que la probabilidad es de 1/X no significa que no te va a pasar hasta tienes X registros. Es como la lotería, no es probable que ganes, pero alguien por ahí gana.

Con la velocidad y la capacidad de las computadoras en estos días (ni siquiera se habla de seguridad, solo confiabilidad) realmente no hay razón para no usar una función de hash más grande/mejor que MD5 para cualquier cosa crítica. Ascender a SHA-1 debería ayudarlo a dormir mejor por la noche, pero si quiere ser extremadamente cauteloso, vaya a SHA-265 y nunca vuelva a pensar en ello.

Si el rendimiento es realmente un problema, utilice BLAKE2, que en realidad es más rápido que MD5, pero admite 256+ bits para evitar colisiones con el mismo o mejor rendimiento. Sin embargo, aunque BLAKE2 ha sido bien adoptado, probablemente requiera agregar una nueva dependencia a su proyecto.