¿No colisionarán todos los hashes después de suficientes iteraciones con una sal estática?

Al iterar una función hash, se produce una reducción de espacio, pero no se reduce a un solo punto. Para una función elegida al azar (que se supone que su "amazing_hash" debe acercarse), con una salida de n -bit, puede esperar alcanzar un ciclo de tamaño 2 ^{n / 2} o algo así, es decir, todavía lo suficientemente grande si usa un tamaño de salida decente (por ejemplo, n = 256 ).

Consulte esta respuesta para explicaciones más detalladas. Aquí reproduzco el esquema de esa respuesta, porque es un buen punto de atención:

Por supuesto , una "sal estática" no es una sal; solo significa que está utilizando una función hash personalizada. El objetivo de la sal es disuadir ataques paralelos: cuando el atacante intenta descifrar 10 contraseñas, le cuesta 10 veces el costo de descifrar una. Con una "sal estática", el craqueo de 10 contraseñas no cuesta más que el craqueo 1, es decir, un fallo total de la salazón.

Las sales no tratan de evitar colisiones, especialmente porque las colisiones no son un problema para el hashing de contraseñas. Es la resistencia de preimagen de la que debería preocuparse.

No lo creo, solo porque el hash seguramente alcanzaría "common_thing" en diferentes puntos. Una contraseña podría tener que ser "algo común" en el paso 10,000 y otra en el paso 100,000. Las cadenas se seguirán en paralelo, pero no necesariamente estarán en el mismo punto cuando finalice el algoritmo.

Si los ciclos son grandes o pequeños, la probabilidad sigue siendo baja. Si hay muchos ciclos pequeños, es menos probable que un valor termine en alguno de ellos en particular; Si hay algunos ciclos grandes, es menos probable que el valor finalice la cadena en el mismo punto.

Como han dicho otras personas, la razón por la que no usas sal estática es para evitar que los atacantes creen tablas arco iris. No estoy seguro de que la sal estática tenga algún efecto en el número de colisiones a lo largo del tiempo, aparte de que, por supuesto, los valores idénticos tendrán el mismo valor.

Sin embargo, toma todo esto con un grano de sal; Soy un entusiasta de la criptografía, pero no un experto. Me encantaría saber más sobre los ciclos en algoritmos hash si otras personas están más informadas en esta área.

El problema relacionado con la sal estática, no es que haya mayores posibilidades de colisión (no hay). La ejecución repetida del mismo algoritmo no provocará un aumento de las colisiones (con una buena función de hash) siempre que todas las contraseñas tengan el mismo número de iteraciones.

El problema real es un juego de probabilidades.

Si un atacante conoce el código utilizado para generar la contraseña con hash (el mecanismo utilizado para inyectar la sal y el número de iteraciones a través del bucle hash), entonces el atacante puede reproducir su algoritmo. Supongamos que el atacante también conoce el resultado real de hash. ¿Pueden calcular su contraseña actual?

Con el algoritmo, el atacante puede ingresar un diccionario de contraseñas comunes al algoritmo y buscar coincidencias con el resultado de hash. Es cierto que puede llevar mucho tiempo, pero, eventualmente, el atacante podría adivinar su contraseña.

El problema es que puedes tener una contraseña "difícil de adivinar" ... pero, ¿qué pasa con todos los demás en el sistema? Tu contraseña hash es solo una de muchas. Si el sitio es 'intercambio de pila', entonces hay miles de usuarios. Si todos usan la misma sal, entonces, un ataque de diccionario como este puede verificar la coincidencia con las contraseñas de hash de todos los usuarios. Si consiguen una coincidencia, también han adivinado la contraseña de ese usuario. Es un juego de números. Si hay 10,000 usuarios en un sistema, las probabilidades de encontrar una contraseña fácil se mejoran en 10,000, probablemente mucho más que eso.

Ahora, si usa un Salt único para cada usuario, obtener un hash coincidente para un usuario es inútil a menos que ese usuario también tenga el mismo Salt que tiene en su algoritmo.

En otras palabras, con un salt único, solo puede atacar una cuenta de usuario a la vez. Con una sal estática, puedes atacarlos todos a la vez ... y las posibilidades de un golpe son mucho mayores.

En teoría, sí, eso definitivamente sucederá, para definiciones suficientes de "mucho" y "muchos". En la práctica, no, eso nunca sucederá. El punto de una función hash criptográfica segura es que "muchos" y "muchos" son números ridículamente grandes que no se pueden alcanzar. Si puedes alcanzarlos, hay un ataque severo contra el algoritmo, y no deberías usarlo, o no es lo suficientemente grande, y no deberías usarlo.

Por ejemplo, tomar MD5. Un hash tiene 128 bits de longitud. Idealmente, en promedio, debería encontrar una colisión con 2 intentos ⁶⁴ , o aproximadamente 18 quintillones. Esto sería muy costoso, pero es posible hacerlo con suficiente hardware. Sin embargo, MD5 ha sufrido catastróficamente de criptoanálisis, y hay ataques que pueden encontrar colisiones en momentos.

Por otro lado, hay SHA-256. Es de 256 bits: no es posible calcular 2 hashes ¹²⁸ y no hay ataques significativos en su contra.

Entonces, esto no es una preocupación si estás usando un hash decente como SHA-256 o SHA-512. Tampoco debería ser una preocupación, incluso si no lo eres. No puedo pensar por qué un usuario intentaría crear una contraseña que intencionalmente provoca una colisión, y no es práctico usar un número significativo de iteraciones, a menos que desee que se realicen décadas de cálculos para que sus usuarios inicien sesión. ( Esto es aparte de las consideraciones mencionadas en las otras respuestas.)

  

Esencialmente, mi pregunta es: con un salt no aleatorio por contraseña, ¿aumenta la posibilidad de una colisión con cada iteración agregada?

Sí, lo hace, de "tan cerca de cero que nunca sucederá" a "todavía tan cerca de cero que nunca sucederá".

En cuanto a la teoría, cada salida de la función amazing_hash tiene un tamaño fijo, y se asigna a otra salida de la función hash, y otra, y así sucesivamente.

Entonces, dejando de lado la primera entrada, tiene una función desde un conjunto finito a sí mismo. La función puede o no ser biyectiva, pero no es una propiedad requerida de una función hash. El dominio de la función necesariamente se divide en:

• uno o más ciclos, más
• cero o más "colas", es decir, secuencias que conducen a uno de los ciclos o a otra cola. Cuando se unen dos colas, se considera arbitrario cuál de ellas conduce a la otra, pero luego usaré el número de colas, por lo que debe definirse de esa manera :-) Defina también el "final" de una cola para sea el punto donde se une otra cola o un ciclo.

Cada punto, cuando se itera, es parte de un ciclo para comenzar o de lo contrario sigue una cola, y las colas que se unen a la cola, hasta que se unen a un ciclo. Esa es una propiedad necesaria de una función desde un conjunto finito a sí mismo. Una ruta no puede ejecutarse para siempre sin ingresar un ciclo, porque solo hay un número finito de valores, por lo que eventualmente debe repetir uno. Por lo tanto, puedes imaginar la función visualmente como muchos círculos, con ramas sobresaliendo de los lados de ellos. Todas las ramas llevan a los círculos.

Con una iteración (es decir, un hash más después del hash inicial), ¿cuántas colisiones hay? Bueno, está relacionado con el número de colas, ya que el final de una cola es un lugar donde dos valores no iguales tienen el mismo hash. Cada punto de unión implica que hay un número de valores en colisión igual al número de estructuras que se unen en ese punto. Cada cola termina en una unión, así que si definimos "colas" y "colisiones" cuidadosamente, entonces el número de colisiones es solo la cantidad de colas.

Después de dos iteraciones, ¿cuántas colisiones hay? Es el número de colas (ya que una vez que dos valores se colisionan, permanecen colisionados), más el número de nuevas colisiones causadas por la iteración adicional. La iteración adicional provoca una colisión si "ambos lados" de un punto de unión tienen al menos 2 nodos de longitud. Entonces, cuando dos colas se unen, deben tener al menos 2 nodos de longitud, y cuando una cola se une a un ciclo, debe tener al menos 2 ciclos.

Después de n iteraciones, las colas son generadas por colas de al menos n nodos de longitud y n-ciclos.

En el caso extremo, una función hash que es biyectiva no tiene cola. Este es el teorema de las funciones finitas: cada permutación divide su dominio en ciclos. Entonces debería ser fácil ver que no importa cuántas iteraciones haga, hay no colisiones (además de las causadas por el hash inicial, por supuesto). Cada punto simplemente se mueve alrededor de su ciclo. Al mover cada punto un número igual de pasos alrededor de un ciclo, siguen todos en diferentes posiciones.

De lo contrario, para comenzar con más iteraciones que hagas, más colisiones se generan a medida que las colas se unen en los ciclos. Sin embargo, hay un límite superior para este proceso, porque cada cola y cada ciclo tienen una longitud finita. Eventualmente no causará más colisiones cuando haga más iteraciones. Eso no sucederá hasta que haya alcanzado la longitud de la cola más larga en su función.

Todo esto es en teoría: en la práctica, la cola más larga podría ser bastante más grande de lo que tienes tiempo de iterar. Si es así, seguirías aumentando el número de colisiones durante el tiempo que puedas en la práctica.

Sin embargo , el número de colisiones que introduce cada iteración es aún muy pequeño en comparación con el espacio hash, tan pequeño que es increíblemente improbable que encuentre una colisión de esta manera. Cómo sabemos esto? Porque si no lo fuera, entonces el algoritmo de búsqueda de ciclos de Floyd sería un medio eficaz para encontrar colisiones en la función hash. La función hash no sería "asombrosa" según los supuestos de la pregunta, se sabría que está rota :-)

  

¿En teoría, muchas contraseñas chocarán?

En su ejemplo, lo que está viendo es lo fácil que es que dos entradas obtengan la misma salida, conocida como colisiones . Esta es un área importante en criptografía, se usa para evaluar la fuerza de los algoritmos y varía para cada algoritmo.

El número de iteraciones no importa, incluso en tu ejemplo, porque todo lo que es interesante es lo siguiente:

hash(n,mznxc,mnzxc)     > common_thing 
hash(ioasjdknckauyieuh) > common_thing 

Dado que está tomando la salida de un hash y luego la está empujando hacia atrás como entrada, la entrada y la salida son del mismo tamaño (excepto la primera entrada).

Algoritmos, como MD5 , se han mostrado algunos vulnerabilidades de colisión . También se sabe que las colisiones MD5 se han explotado en Flame virus , aunque cuando se inventó MD5 como reemplazo seguro de MD4 . Y así, la criptografía se basa en la revisión e investigación de un gran número de criptógrafos para descubrir qué algoritmos aún no han mostrado ninguna debilidad.

Por lo tanto, en cualquier momento, debe observar qué funciones de hash no tienen vulnerabilidades conocidas y diseñar su sistema de manera que en el futuro pueda reinvertir la función de hash (es decir, ser criptográfico).

  

Con un sal no aleatorizado por contraseña, tiene la posibilidad de   colisión subir con cada iteración añadida?

Las sales no aleatorias no resuelven este problema. Resuelven el problema de las tablas arcoiris y las colisiones de contraseñas (es decir, si dos usuarios tienen el mismo nombre, la misma contraseña y el mismo número de contraseñas). iteraciones, obtienes el mismo hash.) Desde una perspectiva de diseño, debes asumir que la sal y la cantidad de iteraciones se conocen públicamente (incluso si logras ocultarlas).

Dado que muchos usuarios comparten las mismas contraseñas ("123456", "password", "abcdefgh", etc.), con sales e iteraciones no aleatorias, predecir las contraseñas se vuelve mucho más fácil utilizando análisis de frecuencia debido a los mismos hashes que resultan de las mismas contraseñas.

En pocas palabras, ¿cuáles son las probabilidades de que la entrada A y la entrada B tengan la misma cosa después de N iteraciones? (La sal no cambia nada acerca de esto). Debido a que H (A) y H (B) deben distribuirse de manera uniforme y aleatoria para una buena función hash, esto es casi lo mismo que las probabilidades de H (A) y H (B). ) no chocando las probabilidades de H (A) y H (B) no chocando después de N - 1 rondas más. Para SHA-256 con 2 ²⁵⁶ posibles salidas (idealmente), eso es 1 - ((2 ²⁵⁶ - 1) / 2 ²⁵⁶ ) ^N & approx; 2.59 × 10 ⁻⁵⁹ para 3 quintillones de iteraciones.

Eso no es muy probable.

También puede estimar la probabilidad de ingresar al bucle que otras respuestas han mencionado con la aproximación del problema de cumpleaños, aunque, como también lo han mencionado otras respuestas, esto no provocará una colisión a menos que las dos entradas estén sincronizadas en este bucle. .

Para las iteraciones SHA-256 y 3 × 10 ¹⁸ nuevamente, eso es 1 - e ^{- (3 × 10 18 ) 2 / (2 × 2 256 )} & approx; 3.89 × 10 ⁻⁴¹ .

Tampoco es muy probable.

No.

Se trata de entropía.

Dada una función hash criptográfica "no rota", produce N bits de salida pseudoaleatoria para cualquier entrada de longitud M , que no es más que extraer N bits de entropía de esos M bits. ¹
Por supuesto, esto solo funciona de manera razonable si M >= N , ya que difícilmente se pueden extraer N bits de entropía si la entrada no contiene nada.

La probabilidad de colisiones está descrita por la conocida paradoja del cumpleaños (que, irónicamente, no funciona en absoluto con los cumpleaños , ¡ya que estos se distribuyen de manera muy desigual!). La probabilidad de que los usuarios elijan contraseñas idénticas es mucho, mucho mayor que eso. O dicho de otra manera, la entropía contenida en una contraseña de usuario (incluso una relativamente buena) es abismal.

La sal agrega entropía a la entrada. Lo que significa que la primera iteración con una estática (¡supongo que "estática" todavía significa "por usuario"!) En realidad reduce la probabilidad de una colisión en comparación con la contraseña simple.

Ahora, ¿qué sucede en la segunda, tercera y con iteración? La función hash toma como entrada la salida de la ronda anterior, que contiene N bits de entropía (que ya incluye la entropía en la sal estática, por lo que agregar la sal todavía la deja en N ), y genera N bits de entropía.
La CPU gira, los bits se voltean, los números se ven diferentes, pero nada cambia en cuanto a la entropía o la probabilidad de colisión. N bits de entrada, N bits de salida.

Así que no, no empeora (pero tampoco mejora)