A02:2021 - Cryptographic failures - Colisiones Hash

¿Qué son los fallos criptográficos?

Un fallo criptográfico ocurre cuando la protección del dato no es adecuada, independientemente de si el fallo sucede por un uso incorrecto de un algoritmo criptográfico, un fallo en la implementación del mismo, o por el uso de prácticas inseguras. Las vulnerabilidades que se dan pueden afectar a la confidencialidad e integridad de la información de una aplicación.

Los fallos criptográficos son un riesgo de seguridad ya que permiten a un posible actor malintencionado, descifrar, manipular o acceder a información que, por diseño, no debería de tener acceso.

Se puede entender la criptografía moderna como el uso de algoritmos robustos, consecuentemente considerados como seguros. Entre ellos destacan AES; RSA o SHA-256, a pesar de ello, su correcta implementación es crucial. Una incorrecta generación de claves, el uso de algoritmos obsoletos, tales como SHA1 o MD5; o la puesta en producción de generadores de números predecibles, pueden resultar en ataques contra la criptografía de la aplicación.

Uso de algoritmos obsoletos

Uno de los fallos criptográficos más comunes es el uso funciones de hash y algoritmos de cifrado obsoletos, anteriormente referenciados, SHA1 y MD5. A pesar de que fueron estándares en su época (1995 y 1992, respectivamente), hoy en día no son considerados seguros debido a los avances en las técnicas de ataque, como la búsqueda de colisiones de hash. Estos ataques permiten que un posible actor malicioso genere dos entradas diferentes que produzcan el mismo hash, lo que podría suponer una suplantación de información.

También se deben tener en cuenta los algoritmos de cifrado simétrico, entre los cuáles también existen algunos considerados como obsoletos, DES o 3DES, los cuales no proporcionan una robustez adecuada a la época en la que nos encontramos, dado que con el tiempo y los recursos suficientes se puede llegar a descifrar los datos.

Historia: MD5 y SHA1

Los algoritmos MD5 (Message Digest 5) y SHA1 (Secure Hash Algorithm 1) son funciones hash que se usaron ampliamente para verificar la integridad de los datos. Sin embargo, con el tiempo se descubrieron vulnerabilidades de alto impacto en ambos algoritmos, permitiendo a actores maliciosos llevar a cabo ataques de colisiones (entre otros), resultando en un fallo de seguridad. Como resultado, tanto MD5 como SHA1 se consideran obsoletos y no son recomendados para su uso en funcionalidad que requiera de alta seguridad.

MD5 - Message Digest 5

Algoritmo diseñado en 1991, genera un hash de 128 bits a partir de un conjunto de datos de cualquier tamaño. Originalmente utilizado para verificar la integridad de archivos e imágenes, y hashes de contraseñas.

• Ataques de colisión: en 2004 los investigadores Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hongbo Yu; demostraron que MD5 es vulnerable a colisiones.

• Xie, T., Liu, F., & Feng, D. (2013). Fast collision attack on MD5. Cryptology ePrint Archive.

• Ataques de preimagen: aunque menos comunes, los ataques de preimagen son teóricamente posibles en MD5, en ellos un actor malicioso podría intentar reconstruir el mensaje original a partir del hash.

• Sasaki, Y., & Aoki, K. (2009). Finding preimages in full MD5 faster than exhaustive search. In Advances in Cryptology-EUROCRYPT 2009: 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings 28 (pp. 134-152). Springer Berlin Heidelberg.

SHA1 - Secure Hash Algorithm 1

SHA1, desarrollado por la NSA en 1993, genera un hash de 160 bits. Se estandarizó su uso, encontrándose en protocolos como SSL/TLS y PGP. En los últimos años se ha demostrado como es vulnerable a ataques de colisión.

En 2017, Google en asociación con la Universidad de Ámsterdam, demostrator que se podrían generar colisiones en SHA1, publicando https://shattered.io/ para libre consulta pública.

Colisiones Hash

Funciones Hash

Una función hash es un algoritmo que toma una entrada de longitud variable y la convierte en una salida variable (hash o digest). Las funciones hash están diseñadas para ser unidireccionales, no siendo posible recuperar la entrada a partir de la salida, y resistentes a colisiones. Sin embargo, en determinados algoritmos ya ha quedado demostrado como esa resiliencia ante colisiones, no siempre es perfecta.

Pero, ¿qué son las colisiones de hash?

Una colisión de hash ocurre cuando dos entradas diferentes producen la misma salida o digest. Esta situación desmonta una de las propiedades esenciales de las funciones hash, la unicidad del digest.

La seguridad de sistemas como las firmas digitales, la integridad de archivos, y los certificados SSL/TLS, puede ser comprometida mediante colisiones de hash. Si un actor malicioso logra modificar el contenido de un mensaje sin que se altere su hash, puede lograr que las modificaciones pasen inadvertidas y se considere legítimo el mensaje.

Ejemplo de colisión en MD5

Para el ejemplo de colisión, se utilizan dos cadenas de texto, las cuales se diferencian en un byte. Créditos a Marc Stevens por su publicación.

• Cadena1:

TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak 

• Cadena 2:

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

⬆

|

⬇

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

Para poder demostrarlo, se realizar una pequeña prueba de concepto en C:

#include <stdio.h>

#include <openssl/md5.h>

#include <string.h>

int main() {

    char *input1 = "TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";

    char *input2 = "TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";

    unsigned char hash1[MD5_DIGEST_LENGTH];

    unsigned char hash2[MD5_DIGEST_LENGTH];

    MD5((unsigned char*)input1, strlen(input1), hash1);

    MD5((unsigned char*)input2, strlen(input2), hash2);

    for(int i = 0; i < MD5_DIGEST_LENGTH; i++) printf("%02x", hash1[i]);

    printf("\n");

    for(int i = 0; i < MD5_DIGEST_LENGTH; i++) printf("%02x", hash2[i]);

    printf("\n");

    printf(memcmp(hash1, hash2, MD5_DIGEST_LENGTH) == 0 ? "¡Colisión encontrada!\n" : "No hay colisión\n");

    return 0;

}

Y se obtiene una colisión de hash, dos cadenas alfanuméricas diferentes resultan en el mismo hash MD5. Esto llevado a un sistema de acceso en el cuál las credenciales se encuentran almacenadas mediante hash MD5, podría suponer un acceso no autorizado con una credencial distinta a la original.

¿Cómo se encuentran las colisiones de hash? → Chosen Prefix Collision

Identificar una colisión de hash es como encontrar una aguja en un pajar, la cantidad de recursos computacionales que requiere para encontrar dos cadenas (por ejemplo) arbitrarias las cuales resulten en el mismo hash, es descomunal.

Por ello se han desarrollado técnicas como Chosen Prefix Collision (CPC), donde se puede seleccionar dos mensajes con prefijos específicos y crearles variaciones que resulten en una colisión del hash.

Marco teórico

El objetivo del ataque es encontrar dos mensajes M1 y M2, cada uno con prefijos conocidos y controlados P1 y P2, que resulten en el mismo digest. Se puede expresar como:

Donde:

• H es la función hash (MD5 o SHA1).
• P1 y P2 son los prefijos elegidos.
• M1 y M2 son las partes variables a identificar.
• ∣∣ denota concatenación.

El riesgo que supone este ataque en particular es elevado dado que los prefijos pueden ser parte de un archivo o mensaje con una estructura conocida (como un certificado digital), lo que podría permitir manipular datos de manera estratégica con el fin de lograr la colisión sin que se modifiquen elementos visibles o críticos.

Proceso del Ataque

Considerando la estructura de una función hash que se divide en bloques:

Donde Mi representa los bloques de tamaño fijo en la entrada. El cálculo de la función hash, H, se realiza de manera iterativa sobre estos bloques, donde cada bloque modifica un estado intermedio Si.

Durante el ataque CPC los prefijos P1 y P2 se procesarán primero, generando un estado intermedio para el cálculo del hash.

Para lograr el objetivo de encontrar dos bloques M1 y M2, que, concatenados con los prefijos P1 y P2 produzcan el mismo valor final de hash, se los bloques M1 y M2 deben ajustarse de manera que las diferencias entre S1 y S2 se cancelen en los estados intermedios posteriores.

Al menos un bloque Mi debe compensar la diferencia entre los estados intermedios.

Donde:

• ⊕ representa la operación XOR.
• ΔS es la diferencia introducida en los estados intermedios para equilibrar la disparidad entre S1 y S2.

Simplificando, si se asume que se logra forzar una colisión de estados intermedios, al final de los bloques elegidos se obtendría:

Resultando en el ajuste de M1 y M2 de manera que, a pesar de tener prefijos diferentes P1 y P2, se produce el mismo estado intermedio final S1.

Alcanzar la igualdad pasa por introducir diferencias calculadas en los bloques de mensaje M1 y M2, aplicando diferencias en los bits del bloque de mensaje que contrarresten las diferencias en los estados intermedios de la función hash. Estas diferencias se calcularán de manera que su propagación a través de la función hash conlleve al mismo estado final.

Suponiendo que se introducen diferencias en el bloque de mensaje M1, como ΔM de tal manera que:

Con el objetivo de que el estado intermedio después de aplicar el bloque M1⊕ΔM sea igual al estado intermedio después de aplicar el bloque M2.

Conclusión

El ataque Chosen Prefix Collision explota la naturaleza interactiva de las funciones hash. Mediante la manipulación de bloques de datos y la aplicación de diferencias calculadas, se puede lograr que coincidan los estados intermedios, provocando la colisión en la salida del hash final.

Este ataque es una prueba de las debilidades fundamentales de funciones hash como MD5 y SHA1, principalmente ante ataques avanzados que manipulan los datos de entrada de manera controlada.

Autor: Daniel Puente