Resistencia a colisiones

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Resistencia a colisiones» – noticias  · periódicos  · libros  · académico  · JSTOR ( diciembre de 2009 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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]${\displaystyle \scriptstyle {\sqrt {2^{N}}}}$

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

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]

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.

• En algunos sistemas de firma digital , una parte da fe de un documento publicando una firma de clave pública en un hash del documento. Si es posible generar dos documentos con el mismo hash, un atacante podría lograr que una de las partes dé fe de uno y luego afirmar que ha dado fe del otro.
• En algunos sistemas de contenido distribuido, las partes comparan los hashes criptográficos de los archivos para asegurarse de que tengan 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 la tienen.

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