La función hash criptográfica

Una función hash criptográfica (en inglés, cryptographic hash function) convierte cualquier cantidad de datos, una contraseña (password), un libro o una película entera, en una cadena corta de longitud fija que funciona como su huella dactilar (fingerprint). La más usada hoy, SHA-256, produce siempre 256 bits, que se suelen escribir como 64 cifras hexadecimales. La misma entrada da siempre la misma huella, pero la huella no permite reconstruir la entrada, y dos entradas distintas, aunque se parezcan en todo menos en una coma, dan huellas que no se parecen en nada. Con esas tres propiedades se comprueba que un programa descargado no ha sido manipulado, se guardan contraseñas sin guardarlas, se firman documentos y se encadenan los bloques de Bitcoin.

La figura de esta página calcula SHA-256 en el navegador, sin enviar nada a ningún servidor. Las dos primeras rejillas son los 256 bits de la huella de dos textos, A y B, pintados en negro los unos y en blanco los ceros; la tercera marca en naranja los bits en que difieren. Los dos textos de partida solo se distinguen en una mayúscula, la de «Mancha», que en la codificación de los ordenadores es un único bit, y sin embargo las huellas difieren en cerca de la mitad de sus bits. El botón que cambia un bit al azar de A permite repetir el experimento tantas veces como se quiera, y el resultado se queda siempre alrededor de 128 de 256.

Ese comportamiento se llama efecto avalancha (avalanche effect), y es la propiedad que distingue una función criptográfica de las funciones hash corrientes, como las que reparten las claves de una tabla hash. Aquellas solo necesitan esparcir bien los datos y ser rápidas; esta tiene que resistir a alguien que busca a propósito. Se le piden tres resistencias, de menor a mayor exigencia en la práctica. La primera es que, dada una huella, no se pueda encontrar ninguna entrada que la produzca, lo que la hace útil para contraseñas. La segunda, que dado un mensaje no se pueda encontrar otro distinto con la misma huella, lo que impide sustituir un documento firmado. La tercera, que no se puedan encontrar dos mensajes cualesquiera con la misma huella, lo que se llama una colisión (collision). Colisiones hay por fuerza, infinitas, porque hay infinitos mensajes y solo 2²⁵⁶ huellas; lo que se exige es que nadie sea capaz de encontrar una.

La segunda parte de la figura enseña por qué la tercera resistencia es la más débil. Si se recorta la huella a sus primeros 24 bits, hay unos dieciséis millones de valores posibles, y parecería que habría que probar millones de textos para que dos coincidieran. No hace falta: la figura calcula las huellas de «ikusmira-0», «ikusmira-1» y así sucesivamente, y encuentra una pareja, de media, hacia los cinco mil intentos; la primera vez que se pulsa el botón aparece en el intento 1.136, entre «ikusmira-236» y «ikusmira-1135», que empiezan las dos por las mismas seis cifras hexadecimales. Es la paradoja del cumpleaños, la misma que hace que en un grupo de veintitrés personas sea más probable que improbable que dos cumplan años el mismo día: lo que crece deprisa no es el número de personas sino el de parejas. Para una huella de n bits, la primera colisión llega hacia los 2^(n/2) intentos, la raíz cuadrada del número de valores. Por eso SHA-256 ofrece 128 bits de seguridad frente a colisiones, no 256, y por eso las funciones de 128 bits, como MD5, nacieron con una seguridad teórica de solo 64.

Casi todas las funciones de esta familia se construyen igual. Ralph Merkle e Ivan Damgård demostraron por separado, en el congreso CRYPTO de 1989, que basta con saber comprimir bien un bloque de tamaño fijo: se parte el mensaje en bloques, se rellena el último añadiendo la longitud total, y se pasa cada bloque por una función de compresión junto con el resultado del bloque anterior. Si la función de compresión resiste las colisiones, la cadena entera también. SHA-256 trocea el mensaje en bloques de 512 bits y los mezcla con un estado de 256 en 64 rondas de sumas, rotaciones y operaciones lógicas, con constantes sacadas de las raíces cúbicas de los primeros números primos, elegidas así para demostrar que no esconden nada. La figura usa exactamente ese procedimiento, escrito en unas treinta líneas.

La historia de estas funciones es la de sus roturas. MD5, que Ronald Rivest diseñó en 1991, fue durante una década la huella estándar de internet, hasta que Xiaoyun Wang y Hongbo Yu presentaron en 2005 un método para fabricar colisiones en horas. En 2012 se descubrió que el programa espía Flame había usado una colisión de MD5 para falsificar un certificado de Microsoft y hacerse pasar por una actualización de Windows. SHA-1, publicada por el gobierno estadounidense en 1995, duró más: en 2017, un equipo de Google y del instituto de investigación CWI de Ámsterdam publicó dos ficheros PDF distintos con la misma huella SHA-1, tras un cálculo de unos nueve trillones de operaciones, el equivalente a más de seis mil años de un procesador. SHA-256 pertenece a la familia SHA-2, de 2001, y no se le conoce ningún ataque práctico, pero la norma tiene ya un relevo, SHA-3, elegida en 2012 en un concurso público y construida sobre un principio distinto por si algún día la familia anterior cede.

Las contraseñas merecen un párrafo aparte, porque son el uso donde la velocidad de la función juega en contra. Robert Morris y Ken Thompson explicaron en 1979 cómo Unix guardaba, en lugar de las contraseñas, su huella, y cómo le añadía a cada una un valor al azar, la sal (salt), para que dos usuarios con la misma contraseña no tuvieran la misma huella y no sirviera de nada una tabla precalculada. El problema es que SHA-256 está hecha para ser rápida: la figura calcula decenas de miles de huellas en un instante, y una tarjeta gráfica prueba miles de millones de contraseñas por segundo. Por eso las contraseñas se guardan con funciones lentas a propósito, como bcrypt o Argon2, que hacen el cálculo miles de veces seguidas. Una función hash criptográfica garantiza que la huella no se puede invertir; no garantiza que la contraseña no se pueda adivinar.