Si no se coloca una longitud máxima en una contraseña, ¿no pueden ocurrir colisiones?

Para empezar, se supone que las funciones hash son básicamente aleatorias, por lo que la longitud de la cadena de entrada no importa. La probabilidad de que dos cadenas aleatorias de 3 caracteres tengan el mismo efecto es la misma que la probabilidad de que dos cadenas aleatorias de 100 caracteres tengan el mismo.

Para las funciones hash modernas ( SHA1 , SHA2 , no MD5 ) su estructura es matemáticamente lo suficientemente compleja como para que no podamos decir mucho sobre ello algebraicamente. Además, el espacio de posibles cadenas de entrada, incluso de longitud 32, es tan grande que no podemos verificarlas todas experimentalmente. Por lo tanto, no sabemos realmente cuántas colisiones hay dentro de las primeras 2 ¹²⁸ (cadenas cuya representación binaria es 1 , 10 , 11 ... 2 ¹²⁸ ). En teoría, debería haber algunos, pero por lo que sé, aún no hemos descubierto ninguno para SHA1 o SHA2 . Por lo tanto, su intuición de que limitar la longitud de las cadenas de entrada a menos de 2 bits ¹²⁸ eliminará el riesgo de colisiones no es del todo correcto.

En cualquier caso, supongamos que hay pares de contraseñas dentro de las primeras 2 ¹²⁸ que tienen el mismo hash, la probabilidad de que golpee una en su base de datos es aproximadamente <number of entries in db> / 2 ¹²⁸ .

La razón por la que

  

¿El "impacto de las colisiones hash no existe"?

es que 1/2 ¹²⁸ es un número tan inimaginable que incluso si escribiera un programa para generar contraseñas aleatorias hasta que el sol se agotara, no esperaría ver un Colisión única por azar. (Si alguien está intentando activamente hacer un ataque de colisión, entonces esa es una historia diferente).

Considere también cómo el riesgo de una colisión (~ 1/2 ¹²⁸ ) se compara con el riesgo de un ataque de diccionario estándar. Según la pérdida de la contraseña de Adobe 2013 , 1 de las 68 cuentas en Internet usa la contraseña 123456 . 1/68 es un número MUCHO más grande que 1/2 ¹²⁸ , por lo que el hecho de que una suposición de 123456 tenga una probabilidad de 1/68 de estar en lo correcto es una cosa MUCHO más importante de la que preocuparse Que las colisiones teóricamente posibles. Solución: permita (o haga cumplir ) las contraseñas largas que no están en el diccionario, use un salt único para cada hash de contraseña y no se preocupe por las colisiones.

Hay poco de qué preocuparse aquí, pero hablemos de esto:

  

Por supuesto, no existen colisiones hasta que el principio de pingeonhole sea   satisfecho

Este no es el caso. El algoritmo de hash estándar es determinista (de lo contrario no funcionaría). Las contraseñas que colisionarán (y hay un número infinito sin límite de longitud de contraseña). Las colisiones no están relacionadas con el tamaño de su base de datos. Por ejemplo, considere mi nuevo algoritmo de hashing de enteros mod100. La implementación es que modificas un entero por 100 y el resto resultante es tu hash. Si he copiado los números 101, 201 y 301, tengo una tasa de colisión del 100%, aunque mi conjunto es solo el 3% del espacio hash.

Tan seguro que hay una pequeña posibilidad astronómica de que alguien pueda adivinar una de las otras contraseñas que tenga el mismo hash que una contraseña real. Si el algoritmo de hash es bueno, es más probable que adivinen la contraseña real. No pierdas el sueño por ello.