La huella de todo.

Un contrato de trescientas páginas, una radiografía, una película entera: cualquier secuencia de bytes puede reducirse a 32 bytes que la representan sin ambigüedad práctica. Esa reducción la hace una función resumen, y es la pieza más usada y menos vista de toda firma digital. Nadie firma un documento; se firma su resumen. Si el resumen falla, falla todo lo demás, por más sólida que sea la clave.

Este artículo recorre qué es una función resumen, qué debe resistir, cómo está construida SHA 256 por dentro, por qué SHA 3 es tan distinta y cómo cayeron MD5 y SHA 1. Hay dos laboratorios para ver la teoría funcionando en el navegador.

Una función que no se puede desandar

Formalmente, una función resumen criptográfica es una función H que toma una entrada de cualquier longitud y devuelve una salida de longitud fija, n bits. Debe ser determinista (la misma entrada da siempre la misma salida) y rápida de calcular. Hasta ahí, cualquier suma de verificación cumpliría. Lo que la vuelve criptográfica es lo que no debe poder hacerse con ella.

Conviene notar algo que a veces sorprende: las colisiones existen, y existen en cantidades inimaginables. Hay infinitas entradas posibles y sólo 2²⁵⁶ salidas, así que por el principio del palomar infinitos mensajes comparten cada resumen. La seguridad no consiste en que no haya colisiones sino en que nadie pueda encontrar una.

Las tres resistencias

• Resistencia a preimagen. Dado un resumen y, debe ser inviable encontrar cualquier x tal que H(x) = y. Es la propiedad de «una vía». El costo genérico es del orden de 2ⁿ intentos.
• Resistencia a segunda preimagen. Dado un mensaje concreto x, debe ser inviable encontrar otro x′ distinto con el mismo resumen. Es lo que impide reemplazar un documento ya firmado por otro. Costo genérico: 2ⁿ.
• Resistencia a colisiones. Debe ser inviable encontrar cualquier par de mensajes distintos con el mismo resumen. Parece una exigencia menor que la anterior, porque el atacante elige los dos mensajes, y justamente por eso es más fácil de atacar: el costo genérico cae a 2^n/2.

Esa caída a la mitad del exponente es la paradoja del cumpleaños. En un grupo de 23 personas, la probabilidad de que dos cumplan años el mismo día ya supera el 50 %, aunque el año tenga 365 días. Con N valores posibles y k intentos al azar, la probabilidad de alguna coincidencia es aproximadamente:

Una buena función resumen tiene además un comportamiento que no figura en las definiciones formales pero que se espera de ella: el efecto avalancha. Cambiar un solo bit de la entrada debe cambiar, en promedio, la mitad de los bits de la salida, sin patrón aparente. Es fácil comprobarlo.

SHA 256 por dentro

SHA 256 forma parte de la familia SHA 2, presentada por NIST en 2001 y especificada hoy en FIPS 180 4. Su arquitectura es la de Merkle y Damgård, que ambos propusieron por separado en 1989: una función de compresión que procesa bloques de tamaño fijo y se encadena. Si la función de compresión resiste colisiones, el resumen completo también las resiste. Ese teorema es la razón por la que todo el esfuerzo de diseño se concentra en una pieza pequeña.

1. Relleno. Al mensaje se le agrega un bit en 1, luego ceros, y al final su longitud original en bits, en 64 bits. El resultado tiene una longitud múltiplo de 512 bits. Incluir la longitud (el «fortalecimiento» de Merkle y Damgård) impide ciertas colisiones triviales entre mensajes de distinto largo.
2. Bloques. El mensaje rellenado se divide en bloques de 512 bits, es decir, dieciséis palabras de 32 bits.
3. Estado inicial. Ocho palabras de 32 bits, a a h, tomadas de la parte fraccionaria de las raíces cuadradas de los primeros ocho números primos.
4. Compresión. Cada bloque se mezcla con el estado durante 64 rondas. Al terminar, el resultado se suma al estado de entrada, y eso es el nuevo estado.
5. Salida. Tras el último bloque, las ocho palabras concatenadas son el resumen de 256 bits.

Dentro de cada ronda intervienen pocas operaciones, todas sobre palabras de 32 bits: rotaciones (ROTR), desplazamientos (SHR), O exclusivo (⊕), Y lógico (∧), negación (¬) y suma módulo 2³². Combinadas, producen funciones que no son lineales en ninguna estructura algebraica cómoda, que es exactamente lo que se busca.

Las 64 constantes K_t son los primeros 32 bits de la parte fraccionaria de las raíces cúbicas de los primeros 64 primos. Elegirlas así no es un capricho: son números «sin nada en la manga», que cualquiera puede recalcular y que por lo tanto no esconden una puerta trasera elegida por el diseñador. Las palabras W_t son las dieciséis del bloque, expandidas a 64 mediante otras dos mezclas de rotaciones, σ0 y σ1.

La suma final del estado de entrada, conocida como construcción de Davies y Meyer, es lo que vuelve irreversible a la compresión. Sin ella, conociendo el bloque se podrían deshacer las rondas una por una. El laboratorio siguiente muestra el proceso completo con el mensaje que se escriba: el relleno byte por byte, cada una de las 64 rondas y la suma final. Con «abc», el resultado coincide con el primer vector de prueba de la norma.

El talón de Aquiles: extender sin conocer

La construcción de Merkle y Damgård tiene una propiedad incómoda. El resumen que entrega es el estado interno completo después del último bloque. Quien conoce H(s ‖ m) y la longitud de s ‖ m, aunque ignore el secreto s, puede retomar el cálculo desde ese estado y obtener H(s ‖ m ‖ relleno ‖ m′) para el agregado m′ que quiera. Es el ataque de extensión de longitud.

No afecta a la firma digital, que nunca usa un secreto concatenado así, pero sí a quien construye autenticadores ingenuos del tipo «resumen de clave más mensaje». La respuesta estándar es HMAC, que anida dos aplicaciones de la función. Las variantes truncadas, como SHA 512/256, y la familia SHA 3 son inmunes por diseño, porque no exponen el estado entero.

SHA 3: la esponja

Cuando en 2005 aparecieron ataques teóricos contra SHA 1, NIST temió que la misma familia de ideas alcanzara a SHA 2, que comparte su arquitectura. En 2007 abrió un concurso público. Se presentaron 64 propuestas, 51 pasaron a la primera ronda y en 2012 ganó Keccak, de Bertoni, Daemen, Peeters y Van Assche. FIPS 202 lo estandarizó en 2015 como SHA 3.

Keccak no usa compresión encadenada sino una construcción de esponja. Tiene un estado de 1600 bits, organizado como un cubo de 5 × 5 × 64, que se divide en dos partes: la tasa r, que entra en contacto con los datos, y la capacidad c, que nunca se toca desde afuera.

1. Absorción. Cada bloque de r bits del mensaje se combina con O exclusivo sobre la parte de tasa, y se aplica la permutación completa: 24 rondas de cinco pasos llamados θ, ρ, π, χ e ι.
2. Exprimido. Terminada la entrada, se leen r bits de la tasa como salida; si hacen falta más, se vuelve a permutar y se sigue leyendo.

La seguridad genérica queda determinada por la capacidad: c/2 bits. SHA3 256 usa r = 1088 y c = 512. Como la salida nunca revela la capacidad, no hay extensión de longitud. Y como la permutación no se parece en nada a la compresión de SHA 2, un avance contra una no se traslada a la otra. SHA 3 no vino a reemplazar a SHA 2, que sigue sana, sino a darle una alternativa de diseño independiente.

Cómo cayeron MD5 y SHA 1

La historia de las funciones resumen enseña que no se rompen de un día para otro. Se agrietan primero en teoría, luego en laboratorio y por último en la práctica, y entre cada etapa suelen pasar años que alcanzan para migrar, si se aprovechan.

La diferencia entre los dos tipos de colisión es decisiva. En una colisión de prefijo idéntico, los dos mensajes comparten el comienzo y difieren sólo en unos bloques calculados por el atacante; para explotarla hay que esconder esa diferencia en un formato que la interprete, como hizo SHAttered con imágenes dentro de PDF. En una colisión de prefijo elegido, el atacante parte de dos comienzos arbitrarios y distintos, por ejemplo dos certificados con titulares diferentes, y calcula sufijos que igualan los resúmenes. Es mucho más cara y mucho más peligrosa, porque permite falsificar exactamente lo que se quiera.

Qué usar, y por cuánto tiempo

Para firma digital, SHA 256 es hoy la elección por defecto, y SHA 384 o SHA 512 son preferibles cuando la firma debe sostenerse muchos años o acompañar claves de mayor nivel de seguridad. SHA3 256 y SHA3 512 son alternativas igualmente válidas. MD5 y SHA 1 no deben usarse para firmas nuevas y, en documentos antiguos, sólo pueden sostenerse si un sello de tiempo posterior, hecho con algoritmos fuertes, prueba que existían antes de que fuera posible falsificarlos.

¿Y la computación cuántica? El algoritmo de Grover reduce el costo de buscar una preimagen de 2ⁿ a unas 2^n/2 evaluaciones, y los mejores algoritmos cuánticos de colisión no mejoran en la práctica sobre el clásico por sus exigencias de memoria. Con 256 bits de salida, el margen sigue siendo amplio. A diferencia de RSA y de las curvas elípticas, las funciones resumen bien diseñadas sobreviven a la computación cuántica con, a lo sumo, salidas más largas.

← Todas las notas