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 deriva, por tanto, de pruebas matemáticas rigurosas, teoría de la complejidad y reducción formal . Estas funciones se denominan funciones hash criptográficas probadamente 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 los bits del mensaje se mezclan para producir el hash. Entonces se cree que son difíciles de romper, pero no se dan pruebas formales. Casi todas las funciones hash de uso generalizado residen en esta categoría. Algunas de estas funciones ya están dañadas y ya no están en uso. Consulte Resumen de seguridad de la función hash .
Tipos de seguridad de las funciones hash
Generalmente, la seguridad básica de las funciones hash criptográficas se puede ver desde diferentes ángulos: resistencia previa a la imagen, resistencia a la segunda imagen previa, resistencia a colisiones y pseudoaleatoriedad.
- Resistencia a la preimagen : dado un hashdebería ser difícil encontrar algún mensaje tal que . Este concepto está relacionado con el de función unidireccional . Las funciones que carecen de esta propiedad son vulnerables a los ataques previos a la imagen .
- Resistencia de la segunda imagen previa : dada una entrada, debería ser difícil encontrar otra entrada, (no igual a ) tal que . Esta propiedad a veces se denomina resistencia a colisiones débil. Las funciones que carecen de esta propiedad son vulnerables a ataques de segundas imágenes previas .
- Resistencia a colisiones : debería ser difícil encontrar dos mensajes diferentes y tal que . Este par se denomina colisión hash (criptográfica). Esta propiedad a veces se denomina fuerte resistencia a las colisiones. Requiere un valor hash al menos dos veces más largo que el requerido para la resistencia previa a la imagen, de lo contrario, se pueden encontrar colisiones por un ataque de cumpleaños .
- Pseudoaleatoriedad : debería ser difícil distinguir el generador de números pseudoaleatorios basado en la función hash de un generador de números aleatorios, por ejemplo, pasa las pruebas de aleatoriedad habituales .
El significado de "duro"
La pregunta básica es el significado de " difícil ". Hay dos enfoques para responder a esta pregunta. Primero está el enfoque intuitivo / práctico: "difícil significa que casi con certeza está más allá del alcance de cualquier adversario al que se deba 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 generalmente se considera insoluble en tiempo polinomial , como un problema de factorización de enteros o un problema de logaritmo discreto .
Sin embargo, la no existencia 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 se basa en la dificultad de la factorización de enteros . Sin embargo, se considera seguro solo con claves que tengan al menos 2048 bits de tamaño.
Caso de contraseña
Además, 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 la velocidad o el costo de calcular la función hash. Un ejemplo común es el uso de hash para almacenar datos de validación de contraseñas . En lugar de almacenar el texto sin formato de las contraseñas de los usuarios, un sistema de control de acceso normalmente almacena un hash de la contraseña. Cuando una persona solicita acceso, la contraseña que envía se codifica y se compara con el valor almacenado. Si se roban los datos de validación almacenados, 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, a menudo, las contraseñas 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 .
Funciones hash criptográficas
La mayoría de las funciones hash se crean sobre una base ad hoc, donde los bits del mensaje se mezclan muy bien para producir el hash. Varias operaciones bit a bit (por ejemplo, rotaciones), adiciones modulares y funciones de compresión se utilizan en modo iterativo para asegurar una alta complejidad y pseudoaleatoriedad de la salida. De esta forma, la seguridad es muy difícil de demostrar y la prueba no suele hacerse. Hace solo unos años , se demostró que una de las funciones hash más populares, SHA-1 , era menos segura de lo que sugería su longitud: las colisiones se podían encontrar 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 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. El caso famoso es MD5 .
El significado de "colisión difícil de encontrar" en estos casos significa "casi con certeza más allá del alcance de cualquier adversario al que se deba evitar que rompa el sistema mientras se considere importante la seguridad del sistema". Por lo tanto, el significado del término depende en cierta medida de la aplicación, ya que el esfuerzo que un agente malintencionado puede realizar en la tarea suele ser proporcional a su beneficio esperado.
Funciones hash demostrablemente seguras
En este enfoque, basamos la seguridad de la función hash en algún problema matemático difícil y demostramos que encontrar colisiones de las funciones hash es tan difícil como resolver el problema subyacente. Esto da una noción de seguridad algo más fuerte que simplemente depender de una mezcla compleja de bits como en el enfoque clásico.
Una función hash criptográfica tiene una seguridad demostrable contra los ataques de colisión si la búsqueda de colisiones es demostrablemente reducible en tiempo polinomial del problema P, que se supone que no se puede resolver en tiempo polinomial. Entonces, la función se llama probadamente segura, o simplemente demostrable.
Significa que si la búsqueda de colisiones fuera factible en tiempo polinomial mediante el algoritmo A, podríamos encontrar y usar el algoritmo de tiempo polinomial R (algoritmo de reducción) que usaría el algoritmo A para resolver el problema P, que se supone que es insoluble en tiempo polinómico. 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 todos los casos de un problema computacionalmente difícil son típicamente difíciles. De hecho, los casos muy grandes de problemas NP-difíciles se resuelven de forma rutinaria, mientras que solo los más difíciles son prácticamente imposibles de resolver.
Las funciones hash con la prueba de su seguridad se basan en funciones matemáticas.
Problemas difíciles
Ejemplos de problemas que se supone que no se pueden resolver en tiempo polinomial
- Problema de logaritmo discreto
- Encontrar raíces cuadradas modulares
- Problema de factorización de enteros
- Problema de suma de subconjuntos
Desventajas del enfoque demostrable
- Los algoritmos hash resistentes a colisiones actuales que tienen reducciones de seguridad comprobables son demasiado ineficientes para usarse en la práctica. En comparación con las funciones hash clásicas, tienden a ser relativamente lentas y no siempre cumplen con todos los criterios que tradicionalmente se esperaban de los hash criptográficos. El hachís 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 solo esperamos que la compleja mezcla de bits en el algoritmo hash sea lo suficientemente fuerte como para evitar que el adversario encuentre colisiones.
- La prueba es a menudo una reducción a un problema con complejidad asintóticamente dura en el peor de los casos o en el caso medio . El peor de los casos mide la dificultad de resolver los casos patológicos en lugar de los casos típicos del problema subyacente. Incluso una reducción a un problema con una complejidad promedio estricta ofrece solo una seguridad limitada, ya que todavía puede haber un algoritmo que resuelva fácilmente el problema para un subconjunto del espacio del problema. 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 función hash que evita estos problemas de seguridad. Se puede demostrar que para cualquier algoritmo que pueda romper SWIFFT con probabilidad P dentro de un tiempo estimado T, podemos encontrar un algoritmo que resuelva el peor de los casos de cierto problema matemático difícil dentro del tiempo T 'dependiendo de T y P. [ cita requerida ]
Ejemplo de función hash demostrablemente segura (poco práctica)
Hash ( m ) = x m mod n donde n es difícil de factorizar el número compuesto y x es un valor base preespecificado. Una colisión x m1 congruente ax m2 revela un múltiplo m1 - m2 del orden de x . Esta información se puede utilizar para factorizar n en el tiempo polinomial asumiendo ciertas propiedades de x .
Pero el algoritmo es bastante ineficaz porque requiere en promedio 1.5 multiplicaciones módulo n por bit de mensaje.
Funciones hash más prácticas y probadamente seguras
- VSH - Función hash muy suave - una función hash resistente a colisiones demostrablemente segura asumiendo la dureza de encontrar números compuestos de módulo de raíces cuadradas modulares no triviales(esto ha demostrado ser tan difícil como factorizar ).
- MuHASH
- ECOH - Función hash de curva elíptica únicamente - basada en el concepto de curvas elípticas, problema de suma de subconjuntos y 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 previo a la imagen.
- FSB: función hash basada en el síndrome rápido : se puede demostrar que romper el FSB es al menos tan difícil como resolver un determinado problema NP-completo conocido como decodificación del síndrome regular.
- 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 del peor de los casos de encontrar vectores cortos en redes cíclicas / ideales .
- Función hash de Chaum, van Heijst, Pfitzmann : una función de compresión en la que encontrar colisiones es tan difícil como resolver el problema del logaritmo discreto en un grupo finito.
- Funciones hash basados en la mochila - Una familia de funciones hash basado en el problema de la mochila .
- La función hash de Zémor-Tillich : una familia de funciones hash que se basan en la aritmética del grupo de matrices SL2 . Encontrar colisiones es al menos tan difícil como encontrar la factorización de ciertos elementos de este grupo. Se supone que esto es difícil, al menos completo con PSPACE . [ dudoso ] Para este hash, finalmente se descubrió un ataque con una complejidad de tiempo cercana a. Esto superó con mucho el límite de cumpleaños y las complejidades ideales previas a la imagen que son y para la función hash Zémor-Tillich. Como los ataques incluyen una búsqueda de cumpleaños en un conjunto reducido de tamañode 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 comprobablemente seguro, específicamente a partir de cualquier protocolo sigma (adecuado) . De esta forma se podría obtener una versión más rápida de VSH (llamada VSH *).
Referencias
- ↑ Goodin, Dan (10 de diciembre de 2012). "El clúster de 25 GPU descifra todas las contraseñas estándar de Windows en <6 horas" . Ars Technica . Consultado el 23 de noviembre de 2020 .
- ^ http://eprint.iacr.org/2008/469.pdf
- ^ Petit, C .; Quisquater, J.-J .; Tillich, J.-P., "Componentes fáciles y difíciles de la búsqueda de colisiones en la función hash de Zémor-Tillich: nuevos ataques y variantes reducidas con seguridad equivalente" (PDF) , Falta o vacío
|title=
( ayuda )