Cuando la matemática no alcanza.

Hay una ironía en la historia de la criptografía de clave pública: RSA, el logaritmo discreto y las curvas elípticas bien elegidas resistieron medio siglo de ataques matemáticos sin ceder, y sin embargo las claves se rompieron una y otra vez. Se rompieron por un generador de números aleatorios mutilado, por un número que debía cambiar y no cambiaba, por una biblioteca que fabricaba primos con demasiada estructura. Este artículo reúne los casos más instructivos. Ninguno exigió resolver un problema difícil; todos exigieron que alguien se equivocara en algo que parecía secundario.

Debian, 2008: la entropía que desapareció

En septiembre de 2006, un mantenedor del paquete OpenSSL en Debian quiso silenciar las advertencias de una herramienta de análisis de memoria, que señalaba el uso de datos sin inicializar en el generador aleatorio. Comentó dos líneas. Una de ellas era la que incorporaba entropía real al generador. Desde entonces, la única fuente de variación fue el identificador del proceso, un número que en Linux no superaba 32 768.

Durante unos veinte meses, cada clave SSH, cada certificado y cada clave de cualquier tipo generada con OpenSSL en Debian, Ubuntu y sus derivados salió de un universo de unas 32 000 posibilidades por tipo y tamaño de clave. En mayo de 2008 el desarrollador argentino Luciano Bello lo descubrió, y en pocas horas circulaban listas con todas las claves posibles. Hubo un efecto adicional, menos conocido: las claves DSA generadas en equipos sanos pero usadas para firmar en equipos afectados también quedaron comprometidas, porque los nonces de esas firmas eran predecibles.

Primos compartidos, 2012: el máximo común divisor

En 2012, Nadia Heninger, Zakir Durumeric, Eric Wustrow y Alex Halderman escanearon todas las direcciones de internet y recolectaron millones de claves públicas TLS y SSH. Luego calcularon el máximo común divisor de cada par de módulos RSA, con un algoritmo de árbol de productos que lo hace eficiente a esa escala. Si dos módulos comparten un primo, el máximo común divisor lo revela, y ambas claves quedan factorizadas al instante.

Pudieron obtener la clave privada de un 0,50 % de los servidores TLS y un 0,03 % de los SSH con RSA, y de un 1,03 % de los servidores SSH con DSA, en este caso por nonces repetidos. Casi todos eran dispositivos embebidos: enrutadores, cortafuegos, servidores de administración remota. Generaban sus claves en el primer arranque, cuando el sistema todavía no había acumulado entropía, y dos aparatos del mismo modelo terminaban eligiendo el mismo primer primo y un segundo distinto. Un equipo académico europeo publicó resultados equivalentes ese mismo año.

Una consola, 2010: el nonce que nunca cambió

El artículo sobre cómo se produce una firma mostró que en ECDSA repetir el nonce k entrega la clave privada con dos firmas. En diciembre de 2010, en el Chaos Communication Congress, el grupo fail0verflow mostró que una consola de videojuegos de enorme difusión firmaba sus actualizaciones con ECDSA usando siempre el mismo k. Bastaron dos firmas públicas y la ecuación de una línea para recuperar la clave privada del fabricante y firmar software arbitrario como si fuera oficial. La clave, grabada en millones de equipos, no podía reemplazarse.

En 2013 la historia se repitió con otro decorado: una falla en el generador aleatorio de una plataforma móvil hizo que aplicaciones de monederos de criptomonedas repitieran nonces, y alguien vació las cuentas cuyas claves se podían despejar de la cadena de bloques pública. Desde entonces, la derivación determinista del nonce dejó de ser una sugerencia.

ROCA, 2017: primos con demasiada forma

Este es el caso más relevante para la firma con valor legal, porque golpeó a tarjetas de identidad. Una biblioteca de un fabricante importante de chips seguros, usada en tarjetas inteligentes, módulos TPM y llaves de seguridad, generaba los primos RSA con una estructura particular para acelerar el proceso:

Matúš Nemec, Marek Sýs, Petr Švenda, Dušan Klinec y Vashek Matyáš, de la Universidad Masaryk, mostraron que esa estructura permite aplicar una variante del método de Coppersmith, que encuentra raíces pequeñas de polinomios modulares, y factorizar los módulos. El costo estimado para una clave de 2048 bits era de unos 140 años de CPU en el peor caso, decenas de miles de dólares en la nube; para 1024 bits, menos de cien días de CPU. Caro, pero perfectamente al alcance de quien tuviera un motivo, y paralelizable. Además, las claves vulnerables se reconocían con una prueba instantánea sobre la clave pública.

Entre los afectados estaba el documento de identidad de Estonia, un país con uno de los sistemas de identidad y firma digital más avanzados del mundo, con unas 750 000 tarjetas comprometidas. En noviembre de 2017 las autoridades suspendieron los certificados afectados y organizaron la actualización masiva de claves, la mayor parte de forma remota. Para las firmas ya realizadas, la pregunta pasó a ser cuándo se habían hecho, y la respuesta dependía de la existencia de sellos de tiempo y de evidencia conservada. Es exactamente el escenario para el que existen las firmas de larga duración.

Otros eslabones que ya conocemos

Los artículos anteriores de esta serie presentaron otros tres casos de la misma naturaleza. El certificado de autoridad falso fabricado en 2008 con una colisión de MD5, y la firma de código falsificada por el programa Flame en 2012, explotaron que se siguiera usando una función resumen años después de que se supiera rota. La falsificación de firmas RSA de 2006 explotó verificadores que interpretaban el relleno en lugar de reconstruirlo. Y el compromiso de DigiNotar en 2011 mostró que una cadena de confianza es tan fuerte como la seguridad operativa de su eslabón más débil.

Cómo se construye para fallar bien

De estos casos se desprende un puñado de principios que hoy son parte del diseño de cualquier sistema serio de firma.

1. Claves generadas en hardware evaluado, con entropía verificada. Y con la posibilidad de reemplazarlas todas si aparece un defecto en ese hardware.
2. Algoritmos que no castigan errores pequeños. Firmas deterministas, fórmulas completas, implementaciones de tiempo constante.
3. Verificadores estrictos. Reconstruir la estructura esperada y compararla byte a byte; validar cada punto, cada rango y cada extensión.
4. Agilidad criptográfica. Que cambiar de algoritmo, de curva o de tamaño de clave sea una decisión de configuración y no un proyecto de años.
5. Evidencia que sobreviva a la clave. Sellos de tiempo e información de validación conservada, para que una firma legítima siga siendo demostrable aunque su clave caiga después.

← Todas las notas