Tomemos MD5 por ejemplo:
Produce un hash de 128 bits. ¿Tiene sentido (en teoría) elegir una entrada (contraseña) que tenga más de 128 bits?
¿Aumenta la probabilidad de una colisión de alguna manera?
Sé que MD5 está dañado, ¿qué pasa con los algoritmos más modernos como bcrypt o scrypt?
Si considera un conjunto de contraseñas potenciales de tamaño P , con una función hash con N valores de salida posibles, entonces existe la probabilidad de que exista al menos una colisión en este conjunto es bastante baja cuando P es menor que la raíz cuadrada de N , y bastante más allá. Consulte el problema de cumpleaños . Como dice la página de Wikipedia, esa probabilidad es aproximadamente igual a 1-e-P2/2·N .
Con cifras: si usa contraseñas de 10 caracteres (letras mayúsculas, letras minúsculas y dígitos), entonces P = 62 10 = 839299365868340224 ; con una función hash de 128 bits, N = 2 128 . La fórmula anterior significa que puede existir al menos un par en colisión entre todas estas contraseñas con una probabilidad cercana al 0.1%. Por otro lado, si agrega un carácter a sus contraseñas (es decir, las contraseñas potenciales tienen una longitud de 11, no 10), entonces la probabilidad de que exista al menos una colisión aumenta a 98.1%.
Ahora todo esto tiene que ver con la probabilidad de existencia de una colisión; no es probable que golpee una colisión.
Las colisiones no son relevantes para el hashing de contraseñas . El hash de contraseña funciona en resistencia de preimagen : dado el hash, es difícil o fácil adivinar la contraseña correspondiente. Tenga en cuenta que dije "a", no "the": para el atacante, no importa si encuentra la misma contraseña que el usuario eligió; él solo quiere una contraseña que conceda acceso, y cualquier contraseña que coincida con la salida de hash hará el truco.
Tenga en cuenta que si bien MD5 está "roto" para colisiones, no lo es para imágenes previas (bueno, para imágenes previas está "ligeramente abollado", pero no significativamente para los propósitos de esta pregunta).
Hay dos formas de romper la resistencia de preimagen:
Adivina la contraseña. Esto significa probar todas las contraseñas potenciales hasta que se encuentre la correcta. Si hay P posibles contraseñas con probabilidad uniforme, entonces esto tiene un costo como máximo P / 2 porque el usuario hizo elegir una de las contraseñas, y el atacante necesitará, en promedio, probar la mitad antes de ingresar la contraseña exacta.
Ten suerte. Pruebe las contraseñas (aleatorias, consecutivas ... no importa) hasta que se encuentre un valor hash coincidente. Esto tiene un costo promedio N/2.
La fuerza de hashing de la contraseña no será más que el inferior de los dos. En ese sentido , usando un conjunto de posibles contraseñas que es más grande que la salida de la función hash (por ejemplo, P > 2 128 para una La función de hash de 128 bits) no ofrece seguridad adicional, porque más allá de ese punto, el ataque "tener suerte" se convierte en una mejor ganga para el atacante que el ataque "adivina la contraseña", y el ataque "tener suerte" no depende de Cómo el usuario realmente elige su contraseña. Tenga en cuenta que digo "tamaño del conjunto de contraseñas" y NO "longitud de la contraseña". Todo el análisis anterior se basa en cuántos valores de contraseña se podrían haber elegido, con probabilidad uniforme. Si usa solo contraseñas de 200 letras, pero solo puede elegir diez mil de ellas (por ejemplo, porque cada "contraseña" es una oración de su libro favorito y el atacante conoce ese libro), entonces el tamaño del conjunto de contraseñas potenciales es 10000, no 62 200 .
En la práctica , P está limitado por el cerebro del usuario (el usuario debe recordar la contraseña) y es invariablemente más bajo que N . Una contraseña "muy fuerte" es una contraseña de un proceso de selección que utiliza una P de 2 80 o más; eso es suficiente para la seguridad y, sin embargo, muy por debajo de 2 128 de MD5 o 2 192 de bcrypt. Pero parece poco realista esperar que los usuarios promedio elijan contraseñas muy fuertes en promedio. En su lugar, debemos hacer frente a las contraseñas débiles, con P alrededor de 2 30 o más (lo que significa: intente con mil millones de contraseñas posibles y habrá roto las contraseñas de la mitad de su usuarios). Las medidas de mitigación son, por lo tanto, hash lento (encarece cada suposición) y sales (no permita que el atacante ataque varias contraseñas a un costo reducido). Consulte esta respuesta .
Hashing reduce un espacio infinito, es decir, posibles entradas de datos, a un espacio finito, es decir, posibles hashes. Por lo tanto, siempre habrá colisiones.
Técnicamente, si restringes tu conjunto de entrada a un tamaño inferior a 2 h , donde h es el tamaño de tu hash de salida en bits, entonces Disminuye tus posibilidades de colisión. De hecho, como len (m) tiende a h , la probabilidad de una colisión al realizar un hash exhaustivo de todos los valores en el conjunto M tiende a 1 .
Dicho esto, dado un valor lo suficientemente grande de h , el hecho de hacer hash de forma exhaustiva todo M es muy poco práctico. Para SHA256, tendría que realizar 2 255 operaciones antes de alcanzar un 50% de probabilidad de colisión con un valor preseleccionado.
Lo importante a recordar es que, para una cadena más larga que h , su seguridad nunca es menor que un mensaje de h -bit, suponiendo que no haya vulnerabilidades específicas en el hash que hace que los mensajes de varios bloques sean menos seguros.
Para ser franco: sí, estadísticamente, un mensaje más corto que la longitud de salida de hash tiene una menor probabilidad de colisión, pero el número de operaciones necesarias para encontrar esa colisión varía con la longitud.
Sí, es absolutamente lógico elegir las contraseñas más largas que el tamaño de salida de hash. ¿Por qué?
Lo que esto le dice es que la entropía de una contraseña típica de n es mucho, mucho más baja que la entropía que se puede codificar en un n -byte etiqueta de contraseña. En términos más simples, las contraseñas de texto simple son muy predecibles, por lo que una base de datos de texto real de contraseñas de byte n puede comprimirse fácilmente a menos de n bytes por contraseña. Así que, en cierto sentido, las contraseñas de byte n no están utilizando toda la capacidad que proporciona el hash de byte n .