Semillas NIST de ECDSA resueltas: 5 mitos sobre su origen

Durante veinticinco años, las semillas de las curvas ECDSA de NIST fueron lo más parecido a un caso frío sin resolver en la criptografía aplicada. Cinco valores de 160 bits aparentemente aleatorios, entregados a NIST por la NSA sin ninguna explicación, sostenían firmas en todo, desde tus conexiones TLS hasta las transacciones de Bitcoin. Esta semana el caso se cerró, y la respuesta es casi vergonzosa: las semillas eran la salida del generador lrand48() de la biblioteca C, inicializado con marcas de tiempo Unix de 1997 y 1998. Eso es todo. Nada de hash de una frase secreta, nada de maquinaria exótica: srand48(time(NULL)), justo el patrón que cualquier curso de seguridad te dice que nunca uses.

El descubrimiento lo hizo un modelo de investigación de Anthropic, al que un empleado curioso le planteó el problema. El modelo reconoció la firma estadística de un generador congruencial lineal de los años 90 en las constantes publicadas, y ejecutó el estado hacia atrás hasta dar con fechas de calendario. He pasado suficientes años auditando sistemas criptográficos como para saber que esto importa, no porque las curvas estén rotas (no lo están), sino porque derriba varias cosas que nuestra industria creía con total confianza. Veamos los mitos uno por uno.

Mito 1: las constantes sin explicar esconden una puerta trasera

La sospecha nunca fue descabellada. Cuando NIST publicó las curvas FIPS 186-2 en 2000, cada una venía con una semilla cuyo hash determina el coeficiente b de la curva. NIST afirmó que las semillas garantizaban que las curvas eran «verificablemente aleatorias», pero no pudo o no quiso explicar cómo se generaron las propias semillas. Koblitz y Menezes escribieron un artículo entero sobre la polémica, con el título deliberadamente provocador «A Riddle Wrapped in an Enigma». La mejor pista de la comunidad era Jerry Solinas, de la NSA, quien recordó en 2015 que la entrada era el hash de una frase humorística, algo como «Give Bob and Jerry a raise». Murió en 2023 sin que nadie recuperara los detalles.

Aquí está la incómoda verdad para los aficionados a las conspiraciones, y en ocasiones yo mismo incluido: «sin explicar» suele significar «sin documentar», no «malicioso». El proceso de generación real consistió en un desarrollador ejecutando un pequeño programa en C, dejando que el PRNG por defecto se sembrara con el reloj de pared y quedándose con el primer candidato que produjera una curva utilizable. La semilla publicada de P-256 fue el candidato número 1.842 de una ejecución iniciada a las 1:52 de la madrugada del 16 de agosto de 1997. Eso no es el flujo de trabajo de una agencia escondiendo una trampa de teoría de números. Es un ingeniero a la una de la madrugada ejecutando un bucle hasta que imprime algo válido.

He visto este patrón en revisiones de incidentes más veces de las que puedo contar. Un valor de configuración misterioso, una constante mágica no documentada, un paso de despliegue que nadie puede explicar, y el postmortem revela que era un atajo razonable en su momento, tomado por un ingeniero cansado y nunca anotado. El pecado real de la NSA aquí no fue meter una puerta trasera en las curvas. Fue distribuir constantes criptográficas al mundo entero sin un README.

Mito 2: el método de generación demuestra que la selección fue honesta

Ahora, la sobrecorrección. Buena parte de los comentarios de esta semana trata «son solo marcas de tiempo» como una absolución total. No lo es, y los investigadores detrás del trabajo se cuidan de decirlo. Saber cómo se generaron los candidatos no dice nada sobre cómo se seleccionaron las curvas finales, y la selección ocurrió a lo largo de meses, de mayo de 1997 a abril de 1998.

La evidencia corta en ambas direcciones. En la ejecución de P-256, el candidato 876 también produjo una curva de orden primo y del tamaño correcto, construida con las mismas convenciones de parámetros, y fue descartado. La curva publicada fue el candidato 1.842. La ejecución de P-224 dejó pasar tres curvas viables; las ejecuciones de ANSI X9.62 descartaron siete más. No podemos ver el historial completo de los candidatos descartados, solo los accesibles en las ejecuciones registradas. Si alguien quisiera una curva con una propiedad rara concreta, en principio podría haber buscado entre marcas de tiempo hasta encontrar una, y luego haber guardado silencio sobre la marca de tiempo. «Hacerlo y no decir nada» siempre fue una opción.

Mi lectura, tras años siguiendo la investigación sobre curvas débiles: la hipótesis de la puerta trasera está muy herida, pero no formalmente muerta. Los candidatos descartados son tan pocos que el cherry-picking implicaría que las curvas débiles son comunes y fáciles de encontrar, algo que dos décadas de criptoanálisis público dicen que no es cierto. Nadie ha publicado nunca un distinguidor que separe estas curvas de unas aleatorias. Pero «ninguna debilidad conocida» y «ausencia demostrada de debilidad» son afirmaciones distintas, y la postura honesta es la primera. Esto es exactamente la brecha entre especificación e implementación manifestándose a nivel de estándares: la especificación decía «verificablemente aleatorio», y la implementación fue «lo que marcara el reloj».

Las semillas se generaron como lo haría un estudiante de posgrado: un PRNG estándar y el reloj del sistema. El escándalo nunca fue la matemática. Fue la falta de documentación.

Mito 3: los PRNG viejos y débiles son inofensivos si solo los usas una vez

Este es el mito que debería hacer levantar la cabeza a todo ingeniero que alguna vez haya escrito srand(time(NULL)). Todo el velo de misterio de veinticinco años existió por una propiedad de diseño de lrand48(): filtra su propia estructura. El generador devuelve solo los 31 bits superiores de un estado de 48 bits, así que sus palabras de salida siempre tienen el bit superior a cero. Escritas como palabras de 32 bits, cuatro de las diez semillas de curvas binarias muestran bits superiores todos a cero en veinte palabras consecutivas, un suceso con probabilidad de alrededor de uno entre 58.000 bajo una distribución uniforme. La firma era visible a simple vista para cualquiera que se molestara en mirar.

A partir de ahí el ataque es vergonzosamente barato. Para recuperar los estados de las curvas binarias, tomas la primera palabra de salida, pruebas por fuerza bruta los 2^17 bits bajos ocultos y compruebas si las cuatro palabras siguientes encajan. Eso son unos pocos milisegundos de cómputo. En las curvas primas, las semillas conservaban menos bits por salida, así que recuperar el estado requirió el clásico ataque sobre LCG truncado: modelarlo como un problema de retículos y aplicarle la reducción de base LLL. Literalmente, material de libro de texto. Una vez que tienes el estado, un LCG se ejecuta hacia atrás tan fácilmente como hacia delante, así que lo retrocedes hasta que aparece la forma de inicialización de srand48 (los bits bajos iguales a 0x330E) y lees la marca de tiempo con la que se sembró.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

La lección se generaliza más allá de los organismos de estándares. Cualquier valor «de apariencia aleatoria» que emitas (tokens de sesión, IDs de petición, salts, nombres de archivo) lleva la huella del generador que lo creó. Si ese generador es un motor congruencial lineal o un Mersenne Twister, unas pocas salidas reconstruyen el estado interno, y todo lo que generaste antes y después se vuelve predecible. Un único uso, hace veinticinco años, en un archivo pensado para parecer ruido, fue invertido por completo. Cuando reviso código que usa RNG no criptográficos para cualquier cosa que un atacante pueda observar, esta es la anécdota que citaré de ahora en adelante.

Mito 4: los números «nothing-up-my-sleeve» nunca fueron la verdadera protección

La idea de «nothing-up-my-sleeve» (nada en la manga): derivar constantes de algo obviamente inocente, como los dígitos de pi, sirve para acotar los grados de libertad del diseñador. Si puedo mostrarte que mi constante sale de un procedimiento público y rígido, no tuve espacio para colar una puerta trasera. Las semillas de NIST fallaron esta prueba a nivel procedimental: el procedimiento era secreto, así que la cota de grados de libertad era desconocida. Pero lo que realmente expone este episodio es que la prueba de la manga es más débil de lo que fingíamos, incluso cuando funciona.

Piensa en lo que realmente te da «verificablemente aleatorio a partir de una marca de tiempo». Una marca de tiempo aporta unos 31 bits de entropía para una ventana plausible. Cualquiera, incluido el autor original, puede recorrer millones de marcas de tiempo, generando millones de curvas candidatas, y publicar solo la que quiera, junto con su semilla de apariencia inocente. Si las curvas con una debilidad secreta existieran con una frecuencia de una entre un millón, la búsqueda por marcas de tiempo encuentra una en una tarde. La semilla demuestra de dónde salió el número y dice casi nada sobre por qué se eligió esa. Lo mismo aplica a los esquemas de hash de una frase secreta, y por eso el rumor sobre la frase humorística de Solinas tampoco fue nunca del todo tranquilizador.

La práctica moderna más sólida es la construcción rígida de curvas: elegir el coeficiente más pequeño que cumpla una lista pública de criterios de seguridad, con las reglas de selección fijadas antes de empezar la búsqueda. Esa es la filosofía detrás de Curve25519 y por qué los argumentos de rigidez de Dan Bernstein transformaron la forma en que la comunidad evalúa curvas. La protección real contra constantes maliciosas nunca fue una historia de derivación ingeniosa. Consiste en minimizar el espacio de búsqueda, publicar los criterios por adelantado y tener suficientes ojos independientes sobre las matemáticas para que una propiedad oculta no pueda seguir oculta. Auditar constantes significa auditar el proceso que las filtró, y por eso las preguntas sin respuesta aquí (los candidatos descartados, los puntos base sin explicar de P-256 y similares, la semilla de B-163 aún sin identificar) deben quedar abiertas en el registro en lugar de ser borradas de la memoria por la celebración.

Mito 5: los LLM solo repiten, no pueden hacer criptoanálisis original

Este es el mito que más escuece, porque yo creí una versión de él. El problema abierto llevaba un cuarto de siglo sin resolverse, pese a una recompensa pública de 36.864 dólares y a la atención seria de aficionados expertos. Varios investigadores de Anthropic lo habían perseguido por su cuenta, siguiendo la pista de la «frase graciosa con hash», y no habían encontrado nada. Luego, un modelo de investigación interno, al que se le preguntó sin darle el rumor, probó un enfoque distinto en menos de media hora: en lugar de adivinar la entrada de un hash, se preguntó qué software habría generado las semillas, planteó la hipótesis de un PRNG de la biblioteca C de los años 90, escribió un escáner que recorría cada semilla probando 34 combinaciones de generador y fragmento de salida, detectó el patrón de bit superior a cero, aplicó el ataque de retículos a las salidas truncadas y retrocedió los estados hasta llegar a fechas de calendario.

Fíjate en lo que es ese flujo de trabajo. No es recuerdo: ningún documento de entrenamiento contenía la respuesta, porque la respuesta no existía en ningún sitio. Es generación de hipótesis más uso de herramientas más verificación, que es la forma real del trabajo criptoanalítico. El modelo incluso comprobó su propia cordura a mitad de la ejecución: ¿es esto un entorno de prueba simulado?, ¿de verdad algo tan obvio habría pasado desapercibido durante 25 años?, ¿un acierto de 160 bits a partir de una semilla de 32 bits descarta la coincidencia? Esa autoescepticismo es lo que querría de un analista humano, y, sinceramente, algunos analistas humanos se la saltan. Llevamos un tiempo poniendo a prueba los mitos sobre lo que estos modelos hacen realmente en este sitio, y esto es un dato limpio: los LLM ya pueden ejecutar razonamiento forense de varios pasos sobre artefactos del mundo real, no solo sobre benchmarks.

El contraargumento justo de los practicantes tiene que ver con la procedencia. El modelo no inventó la recuperación de estados LCG ni LLL: se apoya en décadas de criptoanálisis publicado por investigadores con nombre y sin nombre, y no puede decirte de quién eran los artículos que dieron forma a su enfoque. Eso me molesta menos de lo que molesta a otros. El escáner, el código de verificación y el script de reproducción son públicos; las personas del equipo dirigieron la pregunta y validaron el resultado. Reconozcamos honestamente la división del trabajo: la máquina aportó búsqueda incansable de hipótesis, y los humanos aportaron juicio y responsabilidad. Que los 36.864 dólares de la recompensa fueran al Internet Security Research Group fue una forma elegante de cerrar el asunto.

Qué cambia para las auditorías de seguridad

Entonces, ¿dónde deja esto a un ingeniero en activo? Algunos cambios concretos en cómo abordaría las auditorías a partir de ahora. Primero, trata cada constante mágica de un protocolo o de una base de código como un artefacto forense, no como un hecho de la naturaleza. Pregunta qué generador pudo haberla producido, busca huellas estructurales (bits superiores sesgados, palabras sucesivas correlacionadas por un LCG, recuperaciones de estado plausibles en el tiempo) antes de aceptar «es aleatorio» como respuesta. Las herramientas para esto ya están disponibles sin coste.

Segundo, si publicas constantes, publica el generador. Código fuente, entradas exactas, entorno exacto. «Verificablemente aleatorio» sin una receta reproducible te compra veinticinco años de sospechas y una recompensa sobre tu legado. Tercero, sigue usando P-256: el hallazgo aumenta la confianza en las curvas en lugar de reducirla, y el modelo de amenaza real para las curvas elípticas es el hardware cuántico, no el reloj de una estación de trabajo de 1997. Pero lee con honestidad las preguntas abiertas: los puntos base sin explicar y los candidatos descartados son cabos sueltos, y un trabajo de seguridad maduro implica mantenerlos en los libros.

La conclusión más profunda trata sobre la memoria institucional. Jerry Solinas recordaba una broma sobre aumentos de sueldo que resultó ser errónea. Los archivos, según sus propias palabras, probablemente estaban en un disco duro cerca del Arca de la Alianza. La única razón por la que hoy conocemos la verdad es que la propia salida conservó suficiente estructura para confesar. Tus sistemas están escribiendo sus propias confesiones ahora mismo, en cada ID, token y constante que despliegas. Asegúrate de que confiesen algo de lo que estés orgulloso.