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.
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 80 .
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:
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 1 ≡ x m 2 (mod n ) revela un múltiplo m 1 − m 2 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.
{{citation}}: Falta o está vacío |title=( ayuda )