En criptografía , las funciones hash criptográficas se pueden dividir en dos categorías principales. En la primera categoría están aquellas funciones cuyos diseños se basan en problemas matemáticos, y cuya seguridad se deriva de pruebas matemáticas rigurosas, teoría de la complejidad y reducción formal . Estas funciones se denominan funciones hash criptográficas demostrablemente seguras. Construirlos es muy difícil y se han introducido pocos ejemplos. Su uso práctico es limitado.
En la segunda categoría están 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 estos son difíciles de romper, pero no se proporciona ninguna prueba formal. Casi todas las funciones hash de uso generalizado residen en esta categoría. Algunas de estas funciones ya están rotas y ya no están en uso. Consulte Resumen de seguridad de la función hash .
En general, la seguridad básica de las funciones hash criptográficas se puede ver desde diferentes ángulos: resistencia previa a la imagen, segunda resistencia previa a la imagen, resistencia a la colisión y pseudoaleatoriedad.
La pregunta básica es el significado de " duro ". 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 a quien se debe evitar 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, existe una reducción de seguridad formal de un problema que se considera irresoluble en tiempo polinomial , como un problema de factorización de enteros o un problema de logaritmos discretos .
Sin embargo, la inexistencia de un algoritmo de tiempo polinómico 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 se basa en la dificultad de la factorización de enteros . Sin embargo, se considera seguro solo con claves de al menos 2048 bits de tamaño.