Propiedades de las funciones de hash criptográficas

Las funciones de hash criptográficas son una clase especial de funciones de hash. Las cuales poseen ciertas propiedades que las hacen adecuadas para su uso en criptografía. Como se ha visto en otra entrada, las funciones de hash son algoritmos matemáticos que mapea datos de tamaño arbitrario a una cadena de tamaño fijo. Además, están diseñados para ser una función unidireccional. De modo que, la única forma de obtener los datos de entrada a partir del código hash es mediante la búsqueda por fuerza bruta de las posibles entradas o utilizar una tabla de hashes coincidentes.

Las funciones de hash criptográficas son imprescindibles en gran cantidad de aplicaciones. Por ejemplo, las cadenas de bloques (Blockchain) utilizadas en criptomonedas. También son utilizadas habitualmente para el guardado de contraseñas de forma segura.

En esta entrada se repasarán las cinco propiedades que deben tener las funciones de hash ideales.

Propiedad 1: Determinista

Las funciones hash criptográficas han de ser deterministas. Esto significa que para un conjunto de datos dado siempre se ha de obtener el mismo valor del código hash. Esta propiedad es clave, ya que si el código hash fuese diferente cada vez seria imposible emplearlos para verificar que los datos de origen son los mismos.

Propiedad 2: Computacionalmente eficiente

El algoritmo ha de ser computacionalmente eficiente. Esto significa que la función ha de obtener el valor del código hash rápidamente. En el caso de que el proceso no sea lo suficientemente rápido, las aplicaciones desarrolladas simplemente no serán eficientes.

Propiedad 3: No reversible

No ha de existir una forma directa de obtener el conjunto de datos original a partir del código hash. En esta ocasión se utiliza la expresión "de forma directa" porque siempre existe la posibilidad de conseguirlo indirectamente. Mediante un ataque de fuerza bruta se puede buscar el conjunto de datos que genere el código hash de forma indirecta.

Ataque por fuerza bruta

Por ejemplo, si tenemos el código hash de un PIN de 4 dígitos se puede obtener el valor original probando valores. En este escenario se comienza calculando en código hash del PIN 0000 y se verifica si es este. En caso afirmativo, se ha encontrado el conjunto de datos original. Esto lo garantiza el hecho de que las funciones son deterministas.
En caso negativo se prueba con el siguiente: 0001.

La implementación de método requiere una potencia computacional proporcional al tamaño del conjunto de datos original. En el ejemplo anterior se han de generar entre, en el mejor de los casos, 1 y, en el peor de los casos, 10.000 códigos hash. Aunque en promedio será necesario obtener generar 5.000 códigos. Por lo que este método solamente es viable cuando el conjunto de posibles datos de entrada es limitado y reducido. Aumentado el tamaño de los datos de entrada, el número de combinaciones que han de probarse crece de modo que no se puede realizar en un tiempo razonable. Este es el motivo por el que se recomienda utilizar contraseñas largas para evitar el éxito de los ataques de fuerza bruta.

Propiedad 4: pequeños cambios en la entrada cambian completamente el código hash.

Al realizar un pequeño cambio en la entrada, por ejemplo, un solo bit, los cabios en el código hash han de ser enormes. Esto significa que los algoritmos han de ser sensibles a cualquier mínimo cambio en el conjunto de datos de entrada.

Esta propiedad se puede comprobar obteniendo el código MD5 de dos palabras similares como pueden ser "Hash" y "hash":

MD5 ("Hash") = fae8a9257e154175da4193dbf6552ef6
MD5 ("hash") = 0800fc577294c34e0b28ad2839435945

Incluso este pequeño cambio de un único carácter ha modificado completamente el resultado.

Propiedad 5: Resistente a colisiones

Mediante la resistencia a colisiones se hace referencia a que la probabilidad de que dos conjuntos de datos diferentes generen el mismo código hash ha de ser altamente improbable. Esta propiedad nos indica que si obtenemos el mismo código hash para dos conjuntos de datos podemos asegurar con una gran probabilidad que ambos son el mismo. Por ejemplo, al generar el hash de dos contraseñas podemos asegurar que ambas son la misma cuando ambos códigos coinciden.

El problema de la colisión no se puede evitar completamente. Esto es debido a que el tamaño de los códigos hash es finito y, por lo tanto, el número de posibilidades esta acotado. Por otro lado, el conjunto de datos de entrada es prácticamente infinito. Por ejemplo, el código hash del algoritmo MD5 es de 128 bits, el del SHA-1 es de 160 bits y el de SHA-256 es de 256 bits.

Ataque de cumpleaños

La probabilidad de colisión accidental en un algoritmo de hash esta relaciono con la paradoja del cumpleaños. Esta paradoja indica que para un conjunto de 23 personas hay una probabilidad aproximadamente del 50% de que dos cumplan años el mismo día. Contradiciendo a la intuición que dice que esta probabilidad debería de ser mas baja.
En el caso de tener dos personas la probabilidad de que ambas tengan el cumpleaños el mismo día es de 1/365 (aproximadamente 0,27 %). A medida que aumenta el número de personas en el grupo la probabilidad aumenta. Cuando hay 23 hasta el 50,7% y hasta al 99% para 57. Es decir, en un conjuro de 365 posibilidades (366 en los años bisiestos) la probabilidad de colisión es del 99% solamente con 57 muestras.

Los cálculos anteriores se pueden generalizar para las funciones hash criptográficas. En base al tamaño del código se puede determinar el número de casos necesarios para observar una colisión. Partiendo de la probabilidad de colisión p y el número posible de resultados únicos H. Se puede utilizar la siguiente expresión para obtener el número de códigos necesarios para observa una colisión:

n(p) \approx \sqrt{2 H \ln(\frac{1}{1-p})}

Asignando una probabilidad de colisión del 50% se puede observar que el valor es:

n(p) \approx 1,774 \sqrt{H}

En el caso de un algoritmo MD5 es necesario obtener 2 x 10 ¹⁹ códigos hash para que la probabilidad de colisión sea del 50%. En el caso del algoritmo SHA-256 el número de pruebas necesarias aumenta hasta 4 x 10 ³⁸.

Conclusiones

En esta entrada se ha realizado un repaso de las principales propiedades que se le piden a las funciones hash criptográficas. Al verificar estas propiedades se puede garantizar que aplicaciones en las que se emplean se encuentren protegidas freten a ataques.