En criptografía , la resistencia a colisiones es una propiedad de las funciones hash criptográficas : una función hash H es resistente a colisiones si es difícil encontrar dos entradas que generen la misma salida; es decir, dos entradas a y b donde a ≠ b pero H ( a ) = H ( b ). [1] : 136 El principio del palomar significa que cualquier función hash con más entradas que salidas necesariamente tendrá tales colisiones; [1] : 136 cuanto más difíciles sean de encontrar, más segura criptográficamente será la función hash.
La " paradoja del cumpleaños " establece un límite superior para la resistencia a colisiones: si una función hash produce N bits de salida, un atacante que calcule solo 2 N /2 (o ) operaciones hash sobre una entrada aleatoria probablemente encuentre dos salidas coincidentes. Si existe un método más fácil para hacer esto que un ataque de fuerza bruta , generalmente se considera una falla en la función hash. [2]
Las funciones hash criptográficas suelen estar diseñadas para ser resistentes a colisiones. Sin embargo, muchas funciones hash que alguna vez se creyeron resistentes a colisiones luego se rompieron. MD5 y SHA-1 en particular tienen técnicas publicadas más eficientes que la fuerza bruta para encontrar colisiones. [3] [4] Sin embargo, algunas funciones hash tienen una prueba de que encontrar colisiones es al menos tan difícil como algún problema matemático difícil (como la factorización de números enteros o el logaritmo discreto ). Esas funciones se denominan demostrablemente seguras . [2]
Una familia de funciones { h k : {0, 1} m ( k ) → {0, 1} l ( k ) } generada por algún algoritmo G es una familia de funciones hash resistentes a colisiones, si | m ( k )| > | l ( k )| para cualquier k , es decir, h k comprime la cadena de entrada, y cada h k se puede calcular dentro de un tiempo polinomial dado k , pero para cualquier algoritmo polinomial probabilístico A , tenemos
donde negl(·) denota alguna función despreciable y n es el parámetro de seguridad. [5]
Hay dos tipos diferentes de resistencia a la colisión.
Una función hash tiene una resistencia débil a las colisiones cuando, dada una función hash H y una x, no se puede encontrar ninguna otra x' tal que H(x)=H(x'). En otras palabras, cuando se da una x, no es posible encontrar otra x' tal que la función hash cree una colisión.
Una función hash tiene una fuerte resistencia a colisiones cuando, dada una función hash H, no se pueden encontrar x y x' arbitrarios donde H(x)=H(x'). En palabras, no se pueden encontrar dos x donde la función hash crearía una colisión.
La resistencia a las colisiones es deseable por varias razones.
