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

language-agnostic md5

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 backend. 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. Soy muy consciente de la paradoja del cumpleaños y utilicé 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 bits) es de aproximadamente 1,47x10 ^-29 .

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

Answer 1

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

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

El hecho de que la probabilidad sea 1 / X no significa que no le pase a usted hasta que tenga registros X. Es como la lotería, no es probable que ganes, pero alguien ganará.

Con la velocidad y la capacidad de las computadoras actualmente (ni siquiera se habla de seguridad, solo confiabilidad) realmente no hay razón para no usar simplemente 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 más de 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.

Answer 4

Equal hash significa archivo igual, a menos que alguien malicioso esté jugando con tus archivos e inyectando 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 colisiones accidentales MD5, 1,47x10 ^-29 es realmente un número muy pequeño.

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

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

Entonces, si ve un archivo con un tamaño nuevo, seguro que no tiene un duplicado. Y así.

Answer 5

Se me ocurrió una aproximación de Monte Carlo para poder dormir de forma segura mientras usaba 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

Ya había escuchado la fórmula antes: si necesita almacenar claves de registro (x / 2), use una función de hash que tenga al menos espacio de teclado 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.