¿Con qué seguridad puedo asumir la unicidad de una parte del hash SHA1?

Question

Actualmente estoy usando un SHA1 para acortar un poco una url:

Digest::SHA1.hexdigest("salt-" + url) 

¿Es seguro utilizar sólo los primeros 8 caracteres del SHA1 como un identificador único, como GitHub hace para parecer se compromete?

Answer 1

Para calcular la probabilidad de una colisión con una longitud determinada y el número de hashes que tiene, consulte birthday problem. No sé la cantidad de hash que va a tener, pero he aquí algunos ejemplos. 8 caracteres hexadecimales son 32 bits, por lo que para 100 hashes la probabilidad de una colisión es de aproximadamente 1/1,000,000, para 10,000 hashes es aproximadamente 1/100, para 100,000 es 3/4 etc.

Consulte la tabla en el Birthday attack artículo en Wikipedia para encontrar una buena longitud de hash que satisfaga tus necesidades. Por ejemplo, si desea que la colisión sea menos probable que 1/1,000,000,000 para un conjunto de más de 100,000 hashes, entonces use 64 bits o 16 dígitos hexadecimales.

Todo depende de cuántos hashes va a tener y qué probabilidad de colisión está dispuesto a aceptar (porque siempre hay alguna probabilidad, incluso si es terriblemente pequeña).

Answer 2

Si está hablando de un SHA-1 en hexadecimal, solo obtendrá 4 bits por carácter, para un total de 32 bits. Las posibilidades de una colisión son inversamente proporcionales a la raíz cuadrada de ese valor máximo, por lo que aproximadamente 1/65536. Si su acortador de URL se usa mucho, probablemente no le tomará mucho tiempo antes de que comience a ver colisiones.

En cuanto a las alternativas, probablemente lo más obvio sea mantener un contador. Como necesita almacenar una tabla de URL para traducir su URL acortada al original, básicamente solo almacena cada nueva URL en su tabla. Si ya estaba presente, da su número existente. De lo contrario, lo inserta y le da un nuevo número. De cualquier manera, le das ese número al usuario.

Answer 3

Depende de lo que está tratando de lograr. La salida de SHA1 es efectivamente aleatoria con respecto a la entrada (la salida de una buena función hash cambia en la mitad de sus bits en base a un cambio de un bit en la entrada, y SHA1, aunque no es perfecto, es bastante buena), y tomando un subconjunto de 32 bits (suponiendo 8 dígitos hexadecimales) de la salida de 160 bits, se reduce el espacio de salida de 2^160 a 2^32 valores. Si todo sigue igual, lo que nunca ocurre, esto reduciría significativamente la dificultad de encontrar una colisión.

Sin embargo, si la entrada de la función hash debe ser una URL válida, eso reduce significativamente el número de entradas posibles. @rsp señala el problema del cumpleaños, pero dado esto, no estoy seguro de qué tan aplicable sea, al menos en su forma simple. Además, supone en gran medida que no hay otras precauciones en su lugar.

Estaría más interesado en por qué estás haciendo esto. ¿Se trata de URL que el usuario deberá recordar y escribir? Si es así, hacer tachuelas en un grupo de dígitos hexadecimales aleatorios probablemente sea una mala idea. ¿Es un parámetro de URL o URL que se pasará de forma programática? Entonces, no me importaría mucho la longitud. De cualquier manera, hay probablemente mejores formas de hacer lo que estás tratando de lograr.

Answer 4

Si utiliza binario salida para SHA1 y Base64 codifica el resultado, obtendrá una densidad de información mucho mayor por carácter; puede tener los mismos nombres de 8 caracteres, pero en lugar de solo 16^8 (2^32) posibilidades, tendrá 64^8 (2^48) posibilidades.

Suponiendo que el 50% de probabilidad de colisión escala con 1.177*sqrt(N), utilizando una codificación de tipo Base64 requerirá 256 veces más entradas que la salida hexadecimal antes de alcanzar el 50% de posibilidades de probabilidad de colisión.