SHA-256: ubicuidad, diseño secuencial y su techo

SHA-256 es la función resumen por defecto del mundo y merece que se explique por qué, porque las razones no son las que suele suponer quien la elige. No está en todas partes por ser la más rápida, ni por ser la más elegante, ni siquiera por ser la más moderna: está en todas partes por una combinación de respaldo institucional, ausencia de sorpresas durante más de dos décadas y un efecto de red que se retroalimenta cada vez que alguien la elige por compatibilidad. Entender su diseño interno importa aquí por una razón muy concreta: su estructura, que es la que le dio una demostración de seguridad limpia y una implementación trivial de portar, es también la que la ata a un único núcleo cuando le pides que resuma un fichero grande. Esa tensión no es un accidente de implementación que alguien vaya a corregir en la próxima versión. Es una consecuencia directa de la decisión estructural que se tomó al diseñarla, y por eso la única salida es cambiar de estructura, que es exactamente lo que hace la lección siguiente.

Por qué está en todas partes

La primera razón es normativa. SHA-256 pertenece a la familia SHA-2, publicada por el NIST en el estándar federal de procesamiento de información dedicado a funciones resumen seguras, y esa condición de norma la arrastra a lugares donde la elección técnica no la hace el ingeniero: certificados de servidor, firma de código, módulos criptográficos certificados, requisitos de auditoría, contratos con administraciones públicas. En muchos de esos contextos usar otra función no es una decisión de diseño peor, es directamente una decisión no permitida.

La segunda razón es la ausencia de sorpresas. Lleva más de dos décadas publicada y sometida al escrutinio de la comunidad criptoanalítica sin que aparezca ningún ataque práctico contra la versión completa. Los mejores resultados publicados atacan variantes con un número reducido de rondas, y en el caso de las colisiones no llegan siquiera a la mitad de las sesenta y cuatro rondas del algoritmo real. Su margen sigue siendo cómodo, y ese historial es un activo que ninguna función nueva puede fabricar deprisa: la confianza en criptografía se acumula con el tiempo transcurrido bajo ataque, no con la calidad del argumento de diseño.

La tercera razón es el efecto de red, y es la más determinante en la práctica. Está en la biblioteca estándar de todos los lenguajes que te importan, en las utilidades de línea de órdenes de todos los sistemas operativos, en las API criptográficas de los navegadores, en el silicio de los teléfonos. Cada vez que alguien la elige por compatibilidad, refuerza la razón por la que el siguiente la elegirá. Ese efecto es real, es legítimo y hay que ponerlo en la balanza sin cinismo: interoperar con todo lo que existe tiene un valor que no aparece en ningún banco de pruebas.

# Disponible en todas partes sin instalar nada, que es medio argumento
printf 'hola mundo' | sha256sum
printf 'hola mundo' | openssl dgst -sha256
# Y tambien en el navegador, sin dependencias, desde la API criptografica

Relleno iterado y una función de compresión

El diseño pertenece a la familia del relleno iterado, conocida como construcción de Merkle y Damgård, y consta de tres piezas. Primero, un relleno que lleva el mensaje a un múltiplo del tamaño de bloque, que aquí es de quinientos doce bits, añadiendo un bit a uno, después ceros, y por último la longitud original del mensaje codificada en sesenta y cuatro bits. Segundo, un estado interno de ocho palabras de treinta y dos bits inicializado con constantes fijas. Tercero, una función de compresión que toma el estado actual y un bloque de mensaje y produce el estado siguiente.

Esa función de compresión es un cifrador de bloque usado en modo Davies y Meyer: el bloque de mensaje actúa como clave, el estado actúa como texto en claro, y la salida del cifrado se suma al estado de entrada. Internamente ejecuta sesenta y cuatro rondas sobre un plan de mensaje que expande las dieciséis palabras del bloque hasta sesenta y cuatro mediante desplazamientos y rotaciones. Cuando se acaban los bloques, el estado final es el resumen, sin ninguna transformación adicional.

flowchart LR
IV[estado inicial] --> C1[compresion bloque 1]
C1 --> C2[compresion bloque 2]
C2 --> C3[compresion bloque 3]
C3 --> C4[compresion bloque n]
C4 --> H[resumen final]
M1[bloque 1] --> C1
M2[bloque 2] --> C2
M3[bloque 3] --> C3
M4[bloque n] --> C4
style C1 fill:#89b4fa,color:#11111b
style C2 fill:#89b4fa,color:#11111b
style C3 fill:#89b4fa,color:#11111b
style C4 fill:#89b4fa,color:#11111b

La virtud de este esquema es una demostración: si la función de compresión es resistente a colisiones, la función completa lo es. El teorema reduce la seguridad de un objeto que acepta entradas de longitud arbitraria a la seguridad de un objeto de tamaño fijo que se puede analizar con herramientas concretas. Ese resultado es la razón de que la construcción dominara el diseño de funciones resumen durante décadas, y sigue siendo un argumento de ingeniería excelente: concentra todo el criptoanálisis en una pieza pequeña.

Merece la pena señalar que la longitud del mensaje entra en el cálculo por la puerta del relleno, y que esa decisión también tiene su motivo. Sin ella, dos mensajes que solo difirieran en una cola de ceros podrían dar lugar a construcciones ambiguas, y el relleno con longitud cierra esa puerta imponiendo que dos mensajes distintos nunca produzcan la misma secuencia de bloques. Es un detalle diminuto del que depende buena parte de la demostración, y es también el detalle que un adversario reproduce cuando ejecuta una extensión de longitud: lo único que necesita saber es cuántos bytes ocupaba el mensaje original para reconstruir el relleno exacto.

// La forma del algoritmo, sin la aritmetica interna de las rondas
function sha256(mensaje) {
  let estado = CONSTANTES_INICIALES;             // ocho palabras de 32 bits
  for (const bloque of rellenarEnBloquesDe64(mensaje)) {
    estado = comprimir(estado, bloque);          // 64 rondas por bloque
  }
  return estado;                                  // el estado final es la salida
}
// El bucle no es un detalle de estilo: cada vuelta necesita la anterior

La cadena que no se puede romper

Aquí está el punto de la lección. Mira el bucle del código anterior y localiza la dependencia: el bloque i no se puede comprimir hasta tener el resultado del bloque i menos uno, porque ese resultado es una de las dos entradas de la compresión. No hay ninguna reordenación, ninguna heurística y ninguna optimización de compilador que rompa una dependencia de datos genuina. El tiempo de resumir un mensaje es el número de bloques multiplicado por la latencia de una compresión, y esa multiplicación se ejecuta necesariamente en serie.

La consecuencia es que añadir núcleos no ayuda en absoluto a resumir un fichero. Puedes tener treinta y dos núcleos ociosos mientras uno recorre un fichero de diez gigabytes bloque a bloque, y no hay forma de repartir el trabajo, porque el trabajo es una cadena y no un conjunto. La misma barrera aparece dentro del núcleo con las instrucciones vectoriales: un registro ancho puede operar sobre ocho o dieciséis carriles a la vez, pero aquí no hay ocho valores independientes que meter en esos carriles, hay uno solo que depende del anterior.

Lo que sí acelera SHA-256 y lo que no

Hay dos aceleraciones que funcionan de verdad y una que se cita mal casi siempre. La primera que funciona es el soporte en silicio. Las extensiones de instrucciones dedicadas presentes en los procesadores modernos, tanto en la línea de escritorio como en las arquitecturas de teléfono, implementan varias rondas de SHA-256 por instrucción y reducen el coste por bloque de forma sustancial. Donde ese soporte existe, SHA-256 deja de ser la opción lenta y se acerca mucho a las alternativas en un solo hilo; donde no existe, la diferencia vuelve a abrirse. Esto convierte el argumento de rendimiento en una afirmación dependiente del despliegue, y quien lo enuncie sin decir en qué máquina está midiendo no está diciendo nada.

La segunda que funciona es el procesamiento multibúfer. Si tienes muchos flujos independientes —muchos ficheros pequeños, muchos mensajes, muchos registros de un lote— puedes colocar ocho o dieciséis de ellos en los carriles de un registro vectorial y avanzarlos a la vez, porque entre flujos distintos no hay ninguna dependencia. Es una técnica excelente para un servidor que resume miles de objetos pequeños y es completamente inútil para el caso que nos ocupa aquí, que es resumir deprisa un objeto grande.

// Multibufer: el paralelismo esta entre objetos, nunca dentro de uno
function resumirLote(ficheros) {
  // ocho estados independientes avanzan a la vez en los carriles del registro
  return ficheros.map(sha256);   // escala con el numero de ficheros
}
// Un solo fichero de diez gigabytes usa exactamente un carril y un nucleo

La aceleración que se cita mal es la del hilo secundario. Mover el cálculo a otro hilo no lo hace más rápido, solo lo saca del camino de la interfaz, lo cual está muy bien y no es lo mismo. En un banco de pruebas la diferencia se nota porque el tiempo total no cambia; en la aplicación se nota porque el usuario deja de ver un bloqueo. Confundir las dos cosas lleva a informes de rendimiento donde alguien afirma haber acelerado el resumen cuando lo único que ha hecho es cambiarlo de sitio.

Queda la salida que todo el mundo encuentra sola y que conviene examinar con cuidado, porque tiene un precio escondido. Nada impide construir un árbol propio: trocear el fichero, calcular el resumen de cada trozo con SHA-256 en paralelo, y combinar los resúmenes de los hijos hasta una raíz. Eso paraleliza perfectamente y usa toda la máquina. Pero el valor que sale de ahí ya no es el resumen SHA-256 del fichero, sino un valor que depende de tu tamaño de trozo, de tu aridad, de tu orden de combinación y de tu separación de dominios entre hojas y nodos internos. Es decir, acabas de fabricar una función resumen nueva, no estandarizada y no auditada por nadie, y has perdido exactamente la propiedad por la que habías elegido SHA-256: que cualquiera pueda recalcular tu identificador con las herramientas que ya tiene.

# Estos dos valores no coinciden, y confundirlos es un error frecuente
sha256sum fichero.bin                       # resumen del fichero completo
split -b 1M fichero.bin trozo- && sha256sum trozo-* | sha256sum
# el segundo depende del tamano de trozo, del orden y del formato intermedio

Y hay un peligro añadido en ese árbol casero que conviene enunciar porque no es de rendimiento sino de seguridad. Si al combinar los resúmenes de los hijos no distingues de ninguna manera un nodo interno de una hoja, has construido una función maleable: los mismos bytes intermedios pueden reinterpretarse con otra forma de árbol y dar la misma raíz, lo que produce segundas preimágenes sin necesidad de tocar SHA-256. La cura es la separación de dominios, es decir, mezclar en cada llamada una marca que diga si lo que se está resumiendo es una hoja, un nodo interno o la raíz, además del número de nivel. Es exactamente el problema que la lección siguiente muestra ya resuelto de fábrica.