SHA-1 no celebrará más cumpleaños, ha muerto

Gracias al auge de las criptomonedas, los hashes se han convertido en la operación matemática más veces calculada a lo largo de la historia. Mientras lees estas líneas, millones de GPUs en gigantescas granjas de criptominado están calculando trillones de hashes por segundo. ¿Qué hace que los hashes sean tan valiosos y qué tiene de especial SHA-1?

¿¡Hashes, para qué os quiero!?

Simplificando al máximo, puede decirse que una función de hash calcula resúmenes de datos: recibe como entrada datos de cualquier tamaño y devuelve un valor de longitud fija.

h = H( x )

Es decir, da igual el tamaño de la entrada x, 100 bits, mil megas o un millón de gigas, el valor devuelto h siempre tendrá la misma longitud. Distintas funciones de hash devuelven resúmenes de longitudes distintas, como se muestra en la tabla siguiente. Pero eso sí, la misma función de hash devolverá resúmenes siempre de la misma longitud.

Algoritmo	Tamaño de la salida	Uso legado	Uso futuro
SHA-2	256, 384, 512, 512/256	P	P
SHA-3	256, 384, 512	P	P
SHA-3	SHAKE128, SHAKE256	P	P
Whirlpool	512	P	P
BLAKE	256, 384, 512	P	P
RIPEMD-160	160	P	O
SHA-2	224, 512/224	P	O
SHA-3	224	P	O
MD5	128	O	O
RIPEMD-128	128	O	O
SHA-1	160	O	O

Además, las funciones de hash son unidireccionales: es imposible conjeturar los datos originales a partir del resumen obtenido. Vamos, que no hay marcha atrás. Técnicamente, se dice que son funciones no invertibles.

¿Y para qué sirve calcular resúmenes de longitud fija a partir de datos de tamaño arbitrario? ¡Para todo! Se utilizan para las firmas digitales, para crear cadenas de bloques, para almacenar contraseñas, para autenticar mensajes, para derivar claves a partir de contraseñas, para cifrar los datos con algoritmos impenetrables por los ordenadores cuánticos, para verificar la integridad de archivos, para resolver puzles criptográficos, para organizar estructuras de datos como los árboles de Merkle, para identificar archivos en grandes repositorios, para construir generadores de números pseudoaleatorios, ¡y sigue y sigue!

Como ves, los hashes constituyen un pilar de la criptografía. Eso sí, para considerarse criptográficamente seguros se les exige una serie de requisitos.

Cuándo una función de hash es criptográficamente segura y cuándo no

Para su uso en aplicaciones criptográficas, una función de hash debe poseer una serie de propiedades:

• Resistencia a la preimagen: dado un hash, es imposible encontrar un mensaje cualquiera que produzca el mismo hash.
• Resistencia a la segunda preimagen: dados un mensaje y su hash, es imposible encontrar otro mensaje que produzca el mismo hash.
• Resistencia a colisiones: es imposible encontrar dos mensajes cualesquiera que produzcan el mismo hash.

En la siguiente tabla se resumen los requisitos generalmente aceptados para una función de hash criptográfica. Las tres primeras propiedades son requisitos para su aplicación práctica.  Las siguientes garantizan su aplicación segura en criptografía.

Requisitos	Descripción
Tamaño de entrada variable	H puede aplicarse a un bloque de datos de cualquier tamaño.
Tamaño de salida fijo	H produce una salida de longitud fija.
Eficiencia	H( x ) es relativamente fácil de calcular para cualquier x dada, permitiendo que tanto las implementaciones de hardware como de software sean prácticas.
Resistente a preimágenes (propiedad de unidireccionalidad)	Para cualquier valor hash dado h, es computablemente inviable encontrar x tal que H( x ) = h.
Resistente a la segunda preimagen (resistencia débil a colisiones)	Para cualquier x dado, es computacionalmente inviable encontrar y ≠ x con H( y ) = H( x ).
Resistente a las colisiones (resistencia fuerte a colisiones)	Es computacionalmente inviable encontrar cualquier par (x, y) con x ≠ y, tal que H( y ) = H( x ).
Pseudoaleatoriedad	La salida de H supera las pruebas estándar de pseudoaleatoriedad.

El ataque del cumpleaños

¿Cuántas personas crees que hace falta meter en una sala para que la probabilidad de que dos de ellas cumplan años el mismo día sea superior al 50%? Intuitivamente, pensamos que hará falta un número muy grande: cincuenta, cien personas, mil. ¡Pues no! Basta con 23 personas. Es lo que se conoce como la paradoja del cumpleaños: no porque contradiga la lógica, sino nuestra intuición.

¿Y qué tienen que ver los cumpleaños con los hashes? La paradoja anterior en realidad plantea un problema de colisiones, en este caso, la probabilidad de que en un grupo de t personas dos cumplan años el mismo día de entre N días. Matemáticamente, esta probabilidad se calcula como:

Puede comprobarse fácilmente que para N = 365 y t = 23, dicha probabilidad es 50,7%.

Ahora bien, si N es muy grande, entonces la probabilidad de que haya una repetición en el conjunto puede aproximarse como la raíz cuadrada de N. Por lo tanto, para un hash de n bits, si seleccionamos bloques de datos al azar, podemos esperar encontrar dos bloques de datos con el mismo valor hash con probabilidad superior al 50% en un número de intentos igual a √(2ⁿ) = 2^n/2. Por consiguiente, si el hash tiene una longitud de 160 bits, un ataque de fuerza bruta o de búsqueda exhaustiva exige probar en promedio 2⁸⁰ posibles valores de hash para encontrar una colisión. Es como reducir la longitud efectiva del hash a la mitad.

Estos ataques siempre son posibles y su complejidad computacional depende del número de bits del hash. Por esta razón, normalmente necesitamos duplicar la longitud de salida de las funciones hash en comparación con el tamaño de la clave de otras primitivas criptográficas. Por ejemplo, si AES se considera seguro hoy con 128 bits, una función de hash necesitará el doble: 256 bits. De hecho, por culpa del ataque del cumpleaños 256 bits es la longitud mínima recomendada hoy para hashes.

Sin embargo, si la función de hash es débil, existen otros mecanismos para encontrar colisiones distintos a la fuerza bruta. Y eso, queridos amigos, es lo que le pasó a SHA-1.

Crónica de la muerte anunciada de SHA-1

Las siglas SHA provienen de Secure Hash Algorithm. SHA constituye toda una familia de hashes. En 1993, el NIST americano creó SHA, el primer miembro de la familia, hoy llamado SHA-0 para distinguirlo de los siguientes: SHA-1, del que luego hablaremos; SHA-2, que a su vez comprende SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 y SHA-512/256; y SHA-3, en sus versiones de 224, 256, 384 y 512 bits, así como las versiones de tamaño arbitrario de salida SHAKE128 y SHAKE256.

En concreto, SHA-1 fue diseñado por la NSA en 1996 como parte de su Algoritmo de Firma Digital (DSA). Durante prácticamente dos décadas SHA-1 ha sido el algoritmo de hash más popular, presente de forma predeterminada o como opción en todas las aplicaciones criptográficas habidas y por haber, incluyendo TLS y SSL, OpenSSL, PGP, SSH, S/MIME, Ipsec, sistemas de control de revisiones como Git, todas las bibliotecas criptográficas y, en general, todas aquellas aplicaciones en las que se usan hashes.

Por desgracia, se le fueron descubriendo diferentes vulnerabilidades con los años. De hecho, ya desde 2010 se desaconsejó su uso y se fue eliminando paulatinamente de protocolos y estándares. El golpe más duro lo recibió en 2017 cuando Google encontró una colisión para SHA-1 completamente documentada en SHAttered, implementando por primera vez, gracias a la evolución de la capacidad de cómputo, un ataque puramente teórico publicado en 2005, con complejidad de 2⁶⁹ en lugar de 2⁸⁰.

El último clavo en el ataúd se lo pusieron dos investigadores en 2020 implementando otro ataque teórico propuesto en 2019 por ellos mismos. Su ataque permite encontrar colisiones con una complejidad de 2^61,2, en dos meses de cálculos, con un coste de computación de 11.000 dólares: tan asequible que SHA-1 se considera muerto y enterrado.

Para demostrar la viabilidad del ataque, crearon dos peticiones de firma de certificados PGP/GnuPG: uno con el nombre de la víctima y otro con el nombre y la foto del atacante, de forma que ambos originaban el mismo hash SHA-1. El atacante podía solicitar una firma de su clave y su imagen a un tercero (de la Web of Trust o de una CA) y transferir la firma a su certificado. A partir de ahí, el atacante podía hacerse pasar por la víctima y firmar cualquier documento en su nombre.

Tras este ataque devastador, SHA-1 se considera completamente inseguro, al mismo nivel que MD5, por lo que se deberían reemplazar inmediatamente por alternativas más seguras como SHA-256 o SHA-3. Revisa las especificaciones de todos tus productos y programas y asegúrate de que ninguno continúa usando SHA-1.