Seguridad de las funciones hash criptográficas

En criptografía , las funciones hash criptográficas se pueden dividir en dos categorías principales. En la primera categoría se encuentran aquellas funciones cuyos diseños se basan en problemas matemáticos y cuya seguridad se desprende, por tanto, de pruebas matemáticas rigurosas, teoría de la complejidad y reducción formal . Estas funciones se denominan funciones hash criptográficas demostrablemente seguras . Construirlas es muy difícil y se han presentado pocos ejemplos. Su uso práctico es limitado.

En la segunda categoría se encuentran las funciones que no se basan en problemas matemáticos, sino en construcciones ad hoc, en las que se mezclan los bits del mensaje para producir el hash. Se cree que son difíciles de descifrar, pero no se ofrece ninguna prueba formal. Casi todas las funciones hash de uso generalizado pertenecen a esta categoría. Algunas de estas funciones ya están descifradas y ya no se utilizan. Consulte Resumen de seguridad de funciones hash .

En general, la seguridad básica de las funciones hash criptográficas se puede ver desde diferentes ángulos: resistencia de preimagen, resistencia de segunda preimagen, resistencia de colisión y pseudoaleatoriedad.

• Resistencia a la preimagen : dado un hash h , debería ser difícil encontrar cualquier mensaje m tal que h = hash( m ) . Este concepto está relacionado con el de la función unidireccional . Las funciones que carecen de esta propiedad son vulnerables a ataques de preimagen .
• Resistencia de segunda preimagen : dada una entrada m ₁ , debería ser difícil encontrar otra entrada m ₂ ≠ m ₁ tal que hash( m ₁ ) = hash( m ₂ ) . Esta propiedad a veces se conoce como resistencia débil a colisiones. Las funciones que carecen de esta propiedad son vulnerables a ataques de segunda preimagen.
• Resistencia a colisiones : debería ser difícil encontrar dos mensajes diferentes m ₁ y m ₂ tales que hash( m ₁ ) = hash( m ₂ ) . Este par se denomina colisión de hash (criptográfica). Esta propiedad a veces se denomina resistencia a colisiones fuerte. Requiere un valor de hash al menos dos veces más largo que el requerido para la resistencia a la preimagen; de lo contrario, las colisiones pueden detectarse mediante un ataque de cumpleaños .
• Pseudoaleatoriedad : debería ser difícil distinguir un generador de números pseudoaleatorios basado en la función hash de un generador de números aleatorios verdadero; por ejemplo, pasa las pruebas de aleatoriedad habituales .

La pregunta básica es qué significa " difícil" . Hay dos enfoques para responder a esta pregunta. El primero es el enfoque intuitivo/práctico: " difícil significa que es casi seguro que está fuera del alcance de cualquier adversario al que se le debe impedir que rompa el sistema mientras la seguridad del sistema se considere importante". El segundo enfoque es teórico y se basa en la teoría de la complejidad computacional : si el problema A es difícil, entonces existe una reducción formal de la seguridad a partir de un problema que se considera ampliamente irresoluble en tiempo polinómico , como la factorización de números enteros o el problema del logaritmo discreto .

Sin embargo, la inexistencia de un algoritmo de tiempo polinomial no garantiza automáticamente que el sistema sea seguro. La dificultad de un problema también depende de su tamaño. Por ejemplo, la criptografía de clave pública RSA (que se basa en la dificultad de la factorización de números enteros ) se considera segura solo con claves que tengan al menos 2048 bits de longitud, mientras que las claves para el criptosistema ElGamal (que se basa en la dificultad del problema del logaritmo discreto ) suelen estar en el rango de 256 a 512 bits.

Si el conjunto de entradas al hash es relativamente pequeño o está ordenado por probabilidad de alguna manera, entonces una búsqueda de fuerza bruta puede ser práctica, independientemente de la seguridad teórica. La probabilidad de recuperar la preimagen depende del tamaño del conjunto de entrada y de la velocidad o el costo de calcular la función hash. Un ejemplo común es el uso de hashes para almacenar datos de validación de contraseñas . En lugar de almacenar el texto simple de las contraseñas de usuario, un sistema de control de acceso generalmente almacena un hash de la contraseña. Cuando una persona solicita acceso, la contraseña que envía se convierte en hash y se compara con el valor almacenado. Si los datos de validación almacenados son robados, entonces el ladrón solo tendrá los valores hash, no las contraseñas. Sin embargo, la mayoría de los usuarios eligen contraseñas de formas predecibles, y las contraseñas a menudo son lo suficientemente cortas como para que se puedan probar todas las combinaciones posibles si se utilizan hashes rápidos. ^[1] Se han creado hashes especiales llamados funciones de derivación de claves para ralentizar las búsquedas. Consulte Descifrado de contraseñas .

La mayoría de las funciones hash se construyen sobre una base ad hoc, donde los bits del mensaje se mezclan de forma precisa para producir el hash. Se utilizan varias operaciones bit a bit (por ejemplo, rotaciones), adiciones modulares y funciones de compresión en modo iterativo para garantizar una alta complejidad y pseudoaleatoriedad de la salida. De esta manera, la seguridad es muy difícil de probar y la prueba generalmente no se realiza. Hace solo unos años ^{[ ¿cuándo? ]} , se demostró que una de las funciones hash más populares, SHA-1 , era menos segura de lo que sugería su longitud: se podían encontrar colisiones en solo 2 ^{51 [2]} pruebas, en lugar del número de fuerza bruta de 2 ⁸⁰ .

En otras palabras, la mayoría de las funciones hash que se utilizan hoy en día no son demostrablemente resistentes a las colisiones. Estos hashes no se basan en funciones puramente matemáticas. Este enfoque generalmente da como resultado funciones hash más efectivas, pero con el riesgo de que una debilidad de dicha función se use eventualmente para encontrar colisiones. Un caso famoso es MD5 .

En este enfoque, la seguridad de una función hash se basa en un problema matemático complejo y se demuestra que encontrar colisiones de la función hash es tan difícil como resolver el problema subyacente. Esto proporciona una noción de seguridad algo más sólida que la que se obtiene al confiar únicamente en la mezcla compleja de bits como en el enfoque clásico.

Una función hash criptográfica tiene una seguridad demostrable contra ataques de colisión si la detección de colisiones es demostrablemente reducible en tiempo polinómico a partir de un problema P que se supone que no se puede resolver en tiempo polinómico. La función se denomina entonces demostrablemente segura o simplemente demostrable.

Esto significa que si encontrar colisiones fuera factible en tiempo polinomial mediante el algoritmo A , entonces se podría encontrar y utilizar el algoritmo de tiempo polinomial R (algoritmo de reducción) que utilizaría el algoritmo A para resolver el problema P , que se supone que es irresoluble en tiempo polinomial. Eso es una contradicción. Esto significa que encontrar colisiones no puede ser más fácil que resolver P.

Sin embargo, esto solo indica que encontrar colisiones es difícil en algunos casos, ya que no todas las instancias de un problema computacionalmente difícil son típicamente difíciles. De hecho, instancias muy grandes de problemas NP-difíciles se resuelven rutinariamente, mientras que solo los más difíciles son prácticamente imposibles de resolver.

Algunos ejemplos de problemas que se supone que no se pueden resolver en tiempo polinomial incluyen:

• Logaritmo discreto
• Raíces cuadradas modulares
• Factorización de números enteros
• Suma de subconjuntos

• Los algoritmos hash resistentes a colisiones actuales ^{[¿ cuándo? ] que tienen} reducciones de seguridad demostrables son demasiado ineficientes para ser utilizados en la práctica. En comparación con las funciones hash clásicas, tienden a ser relativamente lentos y no siempre cumplen con todos los criterios que tradicionalmente se esperan de los hashes criptográficos. El hash muy suave es un ejemplo.
• Construir una función hash con seguridad demostrable es mucho más difícil que usar un enfoque clásico en el que uno simplemente espera que la compleja mezcla de bits en el algoritmo hash sea lo suficientemente fuerte para evitar que el adversario encuentre colisiones.
• La prueba es a menudo una reducción a un problema con una complejidad de caso promedio o peor asintóticamente difícil . La complejidad de caso peor mide la dificultad de resolver casos patológicos en lugar de casos típicos del problema subyacente. Incluso una reducción a un problema con una complejidad de caso promedio difícil ofrece solo una seguridad limitada, ya que todavía puede haber un algoritmo que resuelva fácilmente el problema para un subconjunto del espacio de problemas. Por ejemplo, las primeras versiones de Fast Syndrome Based Hash resultaron ser inseguras. Este problema se resolvió en la última versión.

SWIFFT es un ejemplo de una función hash que evita estos problemas de seguridad. Se puede demostrar que, para cualquier algoritmo que pueda descifrar SWIFFT con probabilidad p dentro de un tiempo estimado t , se puede encontrar un algoritmo que resuelva el peor escenario de un determinado problema matemático difícil dentro del tiempo t ′ dependiendo de t y p . ^{[ cita requerida ]}

Sea hash( m ) = x ^m mod n , donde n es un número compuesto difícil de factorizar y x es un valor base preestablecido. Una colisión x ^{m ₁} ≡ x ^{m ₂} (mod n ) revela un múltiplo m ₁ − m ₂ del orden multiplicativo de x módulo n . Esta información se puede utilizar para factorizar n en tiempo polinomial, suponiendo ciertas propiedades de x .

Pero el algoritmo es bastante ineficiente porque requiere en promedio 1,5 multiplicaciones módulo n por bit de mensaje.

• VSH (Very Smooth Hash), una función hash resistente a colisiones y demostrablemente segura que supone la dificultad de encontrar raíces cuadradas modulares no triviales módulo un número compuesto n (se ha demostrado que esto es tan difícil como factorizar n ).
• MuHASH
• ECOH ( función hash de curva elíptica únicamente) : basada en el concepto de curvas elípticas , el problema de la suma de subconjuntos y la suma de polinomios. La prueba de seguridad de la resistencia a la colisión se basó en suposiciones debilitadas y, finalmente, se encontró un segundo ataque de preimagen.
• FSB ( función hash basada en síndrome rápido) : se puede demostrar que romper FSB es al menos tan difícil como resolver la decodificación del síndrome regular , que se sabe que es NP-completo.
• SWIFFT —SWIFFT se basa en la transformada rápida de Fourier y es demostrablemente resistente a las colisiones, bajo una suposición relativamente leve sobre la dificultad en el peor de los casos de encontrar vectores cortos en redes cíclicas/ideales .
• Chaum, van Heijst, Pfitzmann Función hash: una función de compresión donde encontrar colisiones es tan difícil como resolver el problema del logaritmo discreto en un grupo finito F _{2 p +1} .
• Funciones hash basadas en la mochila: una familia de funciones hash basadas en el problema de la mochila .
• Función hash de Zémor-Tillich: una familia de funciones hash que se basa en la aritmética del grupo de matrices SL ₂ . Encontrar colisiones es al menos tan difícil como encontrar la factorización de ciertos elementos en este grupo. Se supone que esto es difícil, al menos PSPACE-completo . ^{[ dudoso – discutir ]} Para este hash, finalmente se descubrió un ataque con una complejidad temporal cercana a 2 ^{n /2} . Esto superó por lejos las complejidades del límite de cumpleaños y de la preimagen ideal, que son 2 ^{3 n /2} y 2 ^{3 n} para la función hash de Zémor-Tillich. Como los ataques incluyen una búsqueda de cumpleaños en un conjunto reducido de tamaño 2 n , de hecho no destruyen la idea de seguridad demostrable ni invalidan el esquema, sino que sugieren que los parámetros iniciales eran demasiado pequeños. ^[3]
• Funciones hash de los protocolos Sigma: existe una forma general de construir un hash demostrablemente seguro, específicamente a partir de cualquier protocolo Sigma (adecuado). De esta manera, se podría obtener una versión más rápida de VSH (llamada VSH*).