Huellas dactilares de los datos

Una función hash criptográfica $H$ transforma una entrada de cualquier longitud en una salida de longitud fija $n$, normalmente 256 bits, llamada resumen. No hay clave. Debe ser rápida de calcular y, en un sentido preciso, imposible de dirigir: el resumen SHA-256 de «abc» es ba7816bf…, y el de «abd» algo sin relación visible con él. Los hashes son la primitiva criptográfica más usada de todas: identifican los commits de Git, los bloques de la cadena de Bitcoin y los ficheros de las actualizaciones de software; están dentro de cada firma, de cada base de datos de contraseñas y de cada negociación TLS.

§Tres tipos de resistencia

Las colisiones tienen que existir, porque infinitas entradas comparten $2^n$ salidas; lo que se exige es que nadie pueda encontrar una. Para un hash ideal de $n$ bits, encontrar una preimagen cuesta unos $2^n$ intentos. Encontrar una colisión cuesta muchos menos.

§La avalancha

Un buen hash se comporta como una función aleatoria: cada bit de salida depende de todos los de entrada, y cambiar la entrada invierte cada bit de salida con probabilidad un medio, independientemente de los demás.

§La paradoja del cumpleaños

En una sala con 23 personas, la probabilidad de que dos cumplan años el mismo día es mayor que un medio. La paradoja, que no es tal, es que comparamos parejas, y 23 personas forman 253 parejas. La misma aritmética gobierna las colisiones.

Demostración de la aproximación

La extracción $i$-ésima evita las $i-1$ anteriores con probabilidad $1-(i-1)/N$, así que no hay colisión con probabilidad $\prod _{i=1}^{q-1}(1-i/N)$. Como $1-x\le e^{-x}$, esto es como mucho $\exp (-\sum _{i}i/N)=e^{-q(q-1)/2N}$, y para $q\ll N$ la aproximación es ajustada. Igualándola a $1/2$ sale $q^2\approx 2N\ln 2$, es decir, $q\approx 1,18\sqrt{N}$.

Así que un hash de 128 bits solo ofrece 64 bits de resistencia a colisiones, al alcance de un cálculo grande; por eso los hashes modernos tienen al menos 256 bits. La misma cota limita a los cifrados con bloques de 64 bits (Sweet32) y a los nonces aleatorios.

§Merkle–Damgård

¿Cómo se resume una entrada de cualquier longitud con una función de tamaño fijo? Ralph Merkle (en su tesis de 1979) e Ivan Damgård (1989) encontraron por separado la construcción en la que se basan MD5, SHA-1 y SHA-2. Se toma una función de compresión $f$ que transforma un valor encadenado y un bloque del mensaje en un nuevo valor encadenado. Se rellena el mensaje (con su longitud al final), se corta en bloques $m_1,\dots ,m_{\ell }$ y se itera:

Demostración

Supongamos que $H(m)=H(m^{\prime })$ con $m\ne m^{\prime }$. Si sus longitudes difieren, los últimos bloques difieren (codifican las longitudes) y $f(h_{\ell -1},m_{\ell })=f(h_{{\ell }^{\prime }-1}^{\prime },m_{{\ell }^{\prime }}^{\prime })$ ya es una colisión de $f$. Si no, se recorre hacia atrás desde el final: en el primer paso $i$ (desde el final) en que $(h_{i-1},m_i)\ne (h_{i-1}^{\prime },m_i^{\prime })$ pero $f$ de ambos es igual, tenemos una colisión de $f$. Ese paso existe porque las entradas difieren en algún sitio.

La construcción tiene una peculiaridad: $H(m)$ es el estado interno tras procesar $m$, así que quien conozca $H(m)$ y la longitud de $m$, pero no $m$, puede calcular $H(m\Vert \mathit{pad}\Vert x)$ para cualquier $x$. Este ataque de extensión de longitud rompe la etiqueta de autenticación ingenua $H(k\Vert m)$, como aprendió la API de Flickr en 2009, y es la razón de ser de HMAC.

§La caída de MD5 y SHA-1

Ron Rivest diseñó MD5 en 1992; la NSA diseñó SHA-1 (160 bits) en 1995. En agosto de 2004 la criptógrafa china Xiaoyun Wang y su equipo presentaron colisiones de MD5 y de varios hashes emparentados, calculadas en horas; un año después mostraron que SHA-1 era mucho más débil que su cota del cumpleaños de 80 bits. Las consecuencias tardaron años en llegar:

• 2008: Marc Stevens, Alexander Sotirov y sus colegas usaron una colisión de MD5 para crear una autoridad de certificación falsa en la que confiaban todos los navegadores.
• 2012: el malware Flame, atribuido a actores estatales, falsificó un certificado de firma de código de Microsoft con un nuevo ataque de colisión contra MD5 y se propagó por Windows Update.
• 2017: Google y el CWI de Ámsterdam anunciaron SHAttered, dos ficheros PDF distintos con el mismo SHA-1, tras $2^{63,1}$ cálculos de SHA-1 (unos 6.500 años de CPU y 110 años de GPU).
• 2020: «SHA-1 is a Shambles», de Gaëtan Leurent y Thomas Peyrin, produjo una colisión con prefijo elegido por unos 45.000 dólares de GPU, suficiente para suplantar claves PGP.

Git, que lo identificaba todo con SHA-1, añadió detección de colisiones en 2017 y admite repositorios con SHA-256 desde 2020. La aplicación de escritorio conserva MD5 y SHA-1 para comprobar sumas de control antiguas, marcados como rotos.

§SHA-2, SHA-3 y BLAKE

SHA-2 (2001: SHA-224, SHA-256, SHA-384, SHA-512) también es Merkle–Damgård, con una función de compresión mucho más fuerte, y sigue sin romperse. Pero tras los ataques de Wang el NIST quiso una reserva construida con otros principios, y en 2007 abrió otro concurso público. Se presentaron sesenta y cuatro candidatos; en 2012 el NIST eligió Keccak, de Guido Bertoni, Joan Daemen (codiseñador de AES), Michaël Peeters y Gilles Van Assche, publicado como SHA-3 en FIPS 202 (2015).

Keccak es una esponja. Su estado de 1.600 bits se divide en una tasa de $r$ bits y una capacidad de $c$ bits. En la fase de absorción, cada bloque de $r$ bits del mensaje se combina con XOR en la parte de la tasa y todo el estado se permuta con una permutación fija $f$; en la fase de exprimido, la salida se lee $r$ bits cada vez de la parte de la tasa, permutando entre medias. La capacidad nunca la tocan directamente ni la entrada ni la salida.

Como la capacidad está oculta, una esponja no tiene extensión de longitud. La estructura de Keccak da además funciones de salida extensible (SHAKE128, SHAKE256), que se usan dentro de los estándares poscuánticos. BLAKE2 (2012), derivado del finalista de SHA-3 BLAKE de Jean-Philippe Aumasson y sus colegas, es más rápido que MD5 en software y tan seguro como SHA-3; BLAKE3 (2020) organiza el cálculo como un árbol de Merkle, así que resume en paralelo en todos los núcleos.

§HMAC: un hash con clave

Un hash no prueba nada sobre quién hizo un mensaje: cualquiera puede recalcularlo. Un código de autenticación de mensajes mezcla una clave secreta, así que solo quien la conoce puede producir o comprobar la etiqueta. Mihir Bellare, Ran Canetti y Hugo Krawczyk diseñaron HMAC en 1996 para que fuera seguro con los hashes Merkle–Damgård:

con dos constantes fijas $\mathit{ipad}=\text{0x36}\dots$ y $\mathit{opad}=\text{0x5c}\dots$. El hash exterior oculta el estado interno, lo que neutraliza la extensión de longitud, y la construcción es demostrablemente una función pseudoaleatoria si la función de compresión lo es. HMAC autentica los registros de TLS, los JSON Web Tokens (HS256), las peticiones a la API de AWS y las contraseñas de un solo uso (TOTP). La verificación debe comparar las etiquetas en tiempo constante, o el tiempo empleado revela cuántos bytes coincidían; la aplicación de escritorio lo hace así.

§Para saber más

1. Ralph Merkle, Secrecy, Authentication and Public Key Systems, tesis doctoral, Stanford (1979); Ivan Damgård, «A Design Principle for Hash Functions», CRYPTO 1989.
2. Xiaoyun Wang y Hongbo Yu, «How to Break MD5 and Other Hash Functions», EUROCRYPT 2005.
3. Marc Stevens et al., «The first collision for full SHA-1», CRYPTO 2017 (shattered.io).
4. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, «On the Indifferentiability of the Sponge Construction», EUROCRYPT 2008.
5. Mihir Bellare, Ran Canetti, Hugo Krawczyk, «Keying Hash Functions for Message Authentication», CRYPTO 1996.