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 produzcan la misma salida; es decir, dos entradas a y b donde a ≠ b, pero H(a) = H(b).Goldwasser, S. y Bellare, M. «Lecture Notes on Cryptography» . Curso de verano sobre criptografía, MIT, 1996-2001.
El principio del palomar implica que cualquier función hash con más entradas posibles que salidas necesariamente tendrá este tipo de colisiones; cuanto más difíciles sean de encontrar, mayor será la seguridad criptográfica de 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 una salida de N bits, es probable que un atacante que realice únicamente 2N/2 (o ) operaciones hash sobre entradas aleatorias encuentre dos salidas coincidentes. Si existe un método más sencillo para lograrlo que un ataque de fuerza bruta, normalmente se considera una debilidad de la función hash.Pass, R. «Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme». Curso sobre criptografía, Universidad Cornell, 2009.
Las funciones hash criptográficas suelen diseñarse para ser resistentes a colisiones. Sin embargo, muchas funciones hash que originalmente se consideraban resistentes a colisiones fueron posteriormente vulneradas. En particular, para MD5 y SHA-1 se han publicado técnicas para encontrar colisiones que son más eficientes que la fuerza bruta.
Sin embargo, algunas funciones hash cuentan con una demostración de que encontrar colisiones es al menos tan difícil como resolver determinados problemas matemáticos considerados computacionalmente difíciles, como la factorización de enteros o el logaritmo discreto. Estas funciones se denominan funciones hash criptográficas con seguridad demostrable.
Definición
Una familia de funciones {hk : {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, hk comprime la cadena de entrada, y cada hk puede calcularse en tiempo polinómico dado k. Sin embargo, para cualquier algoritmo probabilístico de tiempo polinómico A, se tiene:
Pr [k ← G(1n), (x1, x2) ← A(k, 1n) tal que x1 ≠ x2, pero hk(x1) = hk(x2)] < negl(n),
donde negl(·) representa una función despreciable y n es el parámetro de seguridad., definición 1.
Resistencia débil y fuerte a colisiones
Existen dos tipos distintos de resistencia a colisiones.
Una función hash tiene resistencia débil a colisiones cuando, dada una función hash H y una entrada x, no es posible encontrar otra entrada x tal que H(x) = H(x)'. En otras palabras, dada una entrada concreta x, no debería ser computacionalmente viable encontrar otra entrada diferente que produzca una colisión.
Esta propiedad también suele denominarse resistencia a la segunda preimagen cuando la primera entrada ya está fijada.
Una función hash tiene resistencia fuerte a colisiones''' cuando, dada una función hash H, no es posible encontrar arbitrariamente dos entradas diferentes x y x tales que H(x) = H(x)'. En otras palabras, no debería ser computacionalmente viable encontrar ningún par de entradas distintas que produzcan una colisión.
Motivación
La resistencia a colisiones es una propiedad deseable por diversas razones.
En algunos sistemas de firma digital, una parte certifica un documento publicando una firma realizada con su clave privada sobre el hash del documento, que puede verificarse mediante su clave pública. Si fuera posible producir dos documentos con el mismo hash, un atacante podría conseguir que una parte firmara uno de ellos y posteriormente afirmar que esa firma correspondía al otro.
En algunos sistemas distribuidos de contenido, las partes comparan los hashes criptográficos de los archivos para asegurarse de que poseen la misma versión. Un atacante capaz de producir dos archivos diferentes con el mismo hash podría engañar a los usuarios haciéndoles creer que poseen la misma versión de un archivo cuando en realidad no es así.
Seudocolisiones
Durante la evaluación de las funciones hash criptográficas, uno de los métodos utilizados consiste en estudiar ataques contra algoritmos similares pero ligeramente modificados. Normalmente se permite elegir libremente el valor de inicialización del hash (IV, por sus siglas en inglés, en una construcción de Merkle-Damgård).
Si se obtiene el mismo valor hash para dos tuplas distintas formadas por un valor de entrada y un IV, el resultado se denomina seudocolisión'''.
Las seudocolisiones no afectan directamente a la seguridad del algoritmo, ya que en el diseño práctico de una función hash el IV está fijado. Sin embargo, se consideran una señal potencialmente preocupante durante la evaluación de nuevos estándares criptográficos.
Véase también Ataque de cumpleaños Ataque de colisión Detección y corrección de errores
Referencias
Bibliografía
Categoría:Funciones hash criptográficas