Resistencia a las colisiones

En criptografía , la resistencia a colisiones es una propiedad de las funciones hash criptográficas (CHF): 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 ). ^{[ 1 ] : 136} El principio del palomar significa que cualquier función hash con más entradas que salidas tendrá necesariamente tales colisiones; ^{[ 1 ] : 136} cuanto más difíciles sean de encontrar, más segura criptográficamente es la función hash.

La " paradoja del cumpleaños " establece un límite superior a la resistencia a las colisiones: si una función hash produce N bits de salida, un atacante que calcula solo 2 ^{N /2} (o${\displaystyle \scriptstyle {\sqrt {2^{N}}}}$Las operaciones hash sobre una entrada aleatoria probablemente encuentren dos salidas coincidentes. Si existe un método más sencillo para lograr esto que un ataque de fuerza bruta , generalmente se considera una falla en la función hash. ^{[ 2 ]}

Las funciones hash criptográficas suelen diseñarse para ser resistentes a colisiones. Sin embargo, muchas funciones hash que antes se consideraban resistentes a colisiones fueron posteriormente vulneradas. MD5 y SHA-1, en particular, cuentan con técnicas publicadas más eficientes que la fuerza bruta para encontrar colisiones. ^{[ 3 ] [ 4 ]} No obstante, algunas funciones hash tienen una prueba de que encontrar colisiones es al menos tan difícil como resolver algún problema matemático complejo (como la factorización de enteros o el logaritmo discreto ). Estas 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 puede calcularse en tiempo polinomial dado k , pero para cualquier algoritmo polinomial probabilístico A , tenemos

Pr [ k ← G (1 ⁿ ), ( x ₁ , x ₂ ) ← A ( k , 1 ⁿ ) st x ₁ ≠ x ₂ pero h _k ( x ₁ ) = h _k ( x ₂ )] < negl( n ),

donde negl(·) denota alguna función despreciable , y n es el parámetro de seguridad . ^{[ 5 ]}

Existen dos tipos diferentes de resistencia a las colisiones.

Una función hash tiene baja resistencia a colisiones cuando, dada una función hash H y un x, no se puede encontrar ningún otro x' tal que H(x)=H(x'). En otras palabras, dado un x, no es posible encontrar otro x' tal que la función hash genere una colisión.

Una función hash tiene una fuerte resistencia a las colisiones cuando, dada una función hash H, no se pueden encontrar pares arbitrarios de x y x' tales que H(x)=H(x'). En otras palabras, no se pueden encontrar dos valores de x que generen una colisión con la función hash.

La resistencia a las colisiones es deseable por varias razones.

• En algunos sistemas de firma digital , una parte certifica un documento publicando una firma de clave pública sobre el hash del documento. Si es posible generar dos documentos con el mismo hash, un atacante podría lograr que una parte certifique uno y luego afirmar que certificó el otro.
• En algunos sistemas de contenido distribuido, las partes comparan los hashes criptográficos de los archivos para asegurarse de que tienen la misma versión. Un atacante que pudiera generar dos archivos con el mismo hash podría engañar a los usuarios haciéndoles creer que tienen la misma versión de un archivo cuando en realidad no es así.

Durante la evaluación de los CHF, un enfoque consiste en estudiar ataques a algoritmos similares, ligeramente modificados. Por lo general, se permite la libre elección del valor de inicialización del hash (IV en la construcción Merkle-Damgård ). Si se observa el mismo valor hash para dos tuplas diferentes (valor de entrada, IV) , el resultado se denomina pseudocolisión . Las pseudocolisiones no afectan directamente a la seguridad del algoritmo —ya que el IV es fijo en un diseño práctico de hash—, pero se consideran sospechosas al considerar nuevos estándares criptográficos . ^{[ 6 ]}

• ataque de cumpleaños
• Amabilidad con los rompecabezas
• Ataque por colisión
• Ataque de preimagen
• concurso de funciones hash del NIST
• Función hash criptográfica demostrablemente segura
• Detección y corrección de errores

• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). Manual de criptografía aplicada . Matemáticas discretas y sus aplicaciones. Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8523-0.{{cite book}}: CS1 mantenimiento: referencia duplica el valor predeterminado ( enlace )