En criptografía , la resistencia a las colisiones es una propiedad de las funciones hash criptográficas : una función hash H es resistente a las 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 de casillero 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 " pone un límite superior a la resistencia a la colisión: si una función hash produce N bits de salida, un atacante que calcula sólo 2 N /2 (o ) operaciones hash en entradas aleatorias probablemente encontrará dos salidas coincidentes. Si existe un método más sencillo para hacer esto que el 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 pensaron que eran resistentes a colisiones se rompieron posteriormente. MD5 y SHA-1 en particular han publicado técnicas 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 complicado (como la factorización de 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 del tiempo polinomial dado k , pero para cualquier algoritmo polinomial probabilístico A , tenemos
donde negl(·) denota alguna función insignificante 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 a la colisión débil cuando, dada una función hash H y una x, no se puede encontrar ninguna otra x' tal que H(x)=H(x'). En palabras, cuando se da una x, no es posible encontrar otra x' tal que esa función hash cree una colisión.
Una función hash tiene una fuerte resistencia a la colisión 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.
