hash - online - Cuál es la diferencia entre resistencia débil y fuerte

hash online

Question

He leído algunos textos sobre la fuerte resistencia a la colisión y la débil resistencia a la colisión, pero no pude entender la diferencia. Lo único que puedo entender es que hay una baja probabilidad de colisión en las funciones hash que tienen una resistencia a la colisión débil, y una mayor probabilidad de colisión en las funciones hash resistentes a la colisión. No pude entender qué es lo real, cuál es el significado de estos parámetros. Puede alguien ayudarme con esto ?

Answer 1

La propiedad de resistencia a la colisión débil a veces también se denomina segunda resistencia de preimagen :

Dada una x arbitraria, no existe x ''con x''! = X, por lo que h (x) = h (x '')

La fuerte resistencia a la colisión, por otro lado, se define como:

No existen x y x ''con x! = X'' por lo que h (x) = h (x '')

La diferencia obvia en sus definiciones es que para la resistencia a colisiones débiles suponemos que estamos vinculados a una elección particular de x, mientras que en la definición de fuerte resistencia a la colisión somos libres de elegir arbitrariamente nuestra x y x ''. Todavía esto parece ser muy similar, así que veamos dos ejemplos.

Resistencia a colisiones débil

Un buen ejemplo en el que en realidad solo estamos interesados ​​en la resistencia a colisiones débiles sería un simple esquema de almacenamiento de contraseñas. Supongamos que almacenamos las contraseñas proporcionadas por el usuario en una base de datos al almacenar su hash. La autenticación tendría éxito cuando el hash de alguna contraseña que proporciona un usuario es igual al valor que se almacenó previamente (aunque este es un esquema intrínsecamente inseguro, por favor, tenga paciencia). Ahora, en ese caso, la x dada es la contraseña original (desconocida) que se proporcionó anteriormente. Si un atacante fuera capaz de resolver el problema de la "segunda preimagen" de manera eficiente, podría obtener una x ''cuyo valor hash sea el mismo que el de la x original, y así se autenticaría con éxito. Tenga en cuenta que la capacidad de producir colisiones arbitrarias (es decir, resolver el fuerte problema de colisión) es inútil en general en este escenario porque no es muy probable que las x y x ''se asemejen a las contraseñas reales cuyos hash ya han sido almacenados en la base de datos .

Fuerte resistencia a la colisión

Un escenario diferente donde nuestra preocupación es la fuerte resistencia a la colisión es, por ejemplo, una aplicación en la que se desea poder buscar datos arbitrarios almacenados en una base de datos con la ayuda de identificadores únicos. En lugar de emitir consultas sobre los datos originales (que a menudo serían muy lentos debido al tamaño potencialmente ilimitado de los datos), en su lugar calcularía los valores hash de los datos. Los hash son muy compactos, de tamaño limitado y, por lo tanto, pueden ser consultados de forma mucho más eficiente. De hecho, en estos casos, a menudo no le importa la (segunda) propiedad de resistencia a la imagen previa de una función hash, sobre todo porque las propias imágenes no son un secreto. Lo que sí te importa, sin embargo, es que desearías evitar dos conjuntos de datos distintos para hash con el mismo valor, que es esencialmente una colisión. No le importa una colisión en particular, pero desea que esta propiedad se mantenga de forma universal; es decir, no desea que dos conjuntos de datos tengan el mismo valor (imagine que hay una "restricción única" definida en esa columna). Debido a que la seguridad a menudo no es un problema en estas aplicaciones, a menudo usamos hashes no criptográficos, principalmente porque funcionan mejor.

La relación entre ambos

Intuitivamente y también implícito en sus nombres, supondríamos que una fuerte resistencia a la colisión es algo más difícil de proporcionar que una resistencia a la colisión débil. Afortunadamente para nosotros, nuestra intuición puede ser correcta según el modelo de Oracle aleatorio. Podemos probar esto por contrapositivo asumiendo que si tuviéramos un algoritmo polinomial probabilístico eficiente para resolver "segunda preimagen", entonces esto también nos daría un algoritmo eficiente para resolver "colisión".

Considere una función hash h y este siguiente algoritmo probabilístico simple [1]:

Permita que 2ndPreimage sea otro algoritmo probabilístico (e, Q) que resuelva "segunda preimagen" para la función hash h.

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x'' (!= x) -> return (x, x'')

Es fácil ver que este es también un algoritmo (e, Q) que resuelve el fuerte problema de colisión. Esto implica que dado que tenemos un algoritmo para resolver "segunda preimagen", también podemos usar este algoritmo que probablemente produzca una colisión. Como no hicimos suposiciones sobre la función hash subyacente h, ahora podemos decir con seguridad que

La fuerte resistencia a la colisión implica una resistencia a la colisión débil, pero lo contrario no necesariamente se sostiene.

[1] e es la probabilidad de éxito del algoritmo, 0 <= e <1. Q es el número máximo de consultas de oráculo (es decir, "evaluaciones" del algoritmo). En caso de éxito, el algoritmo devuelve una solución válida, de lo contrario, devuelve un valor que indica la falla.