¿Cuánto puede truncar un hash SHA1 y estar razonablemente seguro de tener una ID única?

Question

Estoy haciendo una aplicación que almacena documentos y le da a cada uno un UID basado en un resumen de SHA1 de algunas cosas, incluida la marca de tiempo. El resumen contiene muchos caracteres, y quiero permitir que los usuarios identifiquen los documentos utilizando los primeros x caracteres del resumen completo. ¿Cuál es un buen valor para x si la cantidad de documentos es aproximadamente de 10K a 100K?

Answer 1

Adaptación de las fórmulas en el wikipedia for the Birthday problem, se puede aproximar la probabilidad de colisión como e^(-n^2/(2^(b+1))), donde n es el recuento de documentos y b es el número de bits. Graphing this formula with n=100,000, parece que querrá b> 45 al menos. Estaría más inclinado a ir con 64 para que sea un número agradable y redondo. Dicho esto, ¿tiene un plan para hacer frente a las colisiones si se producen (tal vez alterar la marca de tiempo ligeramente, o agregar un nonce?)

Para el caso, si el sha1 se basa en algo más que el contenido del documento, ¿por qué no simplemente convertirlo en una identificación aleatoria? En este caso, las colisiones son un problema menor, ya que siempre puedes generar un nuevo número aleatorio y volver a intentarlo (la probabilidad de una colisión con un solo intento es la misma).

Answer 2

Realmente no hay un valor para esto; Parte de lo que hace que SHA sea un buen algoritmo de hashing de propósito general es que datos similares no necesariamente producen valores hash similares. Su mejor opción (sin saber nada más sobre su sistema) sería simplemente buscar en la lista de documentos cuyos hashes comienzan con el valor proporcionado por el usuario, luego presentarlos con una lista de documentos para seleccionar o ir directamente al documento si solo hay uno

Answer 3

Bueno, aquí hay un posiblemente demasiado simplista de una respuesta ..

Si con plena SHA1 se obtiene aproximadamente 1 de cada 2^160 posibilidades de colisión, a continuación, truncando un carácter a aumentar las probabilidades de colisión por 16 (todos los valores posibles del carácter truncado) ... que son 2^4 .. Entonces, si truncas x personajes obtienes 1 en 2^(160 - 4 * x) posibilidades de colisión ... ¿no?

Answer 4

Es un generalization de the birthday problem. En su caso n es el número de documentos, y en lugar de 365 constantes, tiene varias posibilidades que le da el límite (por lo que para k bits es 2 ^k).

Por supuesto, el cálculo exacto está descartado, pero puede usar approximation.

Answer 5

Tenga cuidado con el truncamiento ya que no hay una reducción en la prueba de que el hash más pequeño es seguro. Vea Kelsey's http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf. Kelsey da argumentos heurísticos que dicen lo mismo ("Salidas Hash Relacionadas" y "Colisiones Cercanas"). Biham/Chen ofrecen ejemplos de colisiones cercanas; y Knudsen demuestra Diferenciales truncados.

Al final, es probable que tipo de carga de datos en un HMAC con el tamaño truncada (el tamaño es digerido por el HMAC, también) y luego usar la truncada HMAC.