Cada vez que un navegador establece una conexión HTTPS con firma ECDSA, lo más probable es que use la curva P-256. Es una de las curvas elípticas que el NIST publicó en el año 2000 en el estándar FIPS 186-2, junto a P-192, P-224, P-384 y P-521. Y durante 25 años ha arrastrado una pregunta incómoda: sus parámetros salían de unas “semillas” que entregó la NSA, sin explicar de dónde venían. Esta semana se ha resuelto el misterio, y la respuesta es mucho más aburrida de lo que muchos esperaban, que es justo lo que se quería oír.
El problema de las semillas
Las curvas NIST se generaron “al azar” siguiendo el estándar ANSI X9.62: se toma una semilla arbitraria de 20 bytes, se le aplica SHA-1 y con el resultado se calcula uno de los coeficientes de la curva. La idea es que nadie pueda elegir la curva a propósito, porque SHA-1 hace imposible buscar una semilla que dé un resultado concreto. Por ejemplo, la semilla de P-256 es C49D360886E704936A6678E1139D26B7819F7E90.
El fallo de ese razonamiento es que, si puedes probar muchas semillas, sí puedes elegir entre muchas curvas. Y como la NSA nunca explicó cómo eligió esas semillas, siempre quedó la sospecha de que podía haber probado millones hasta dar con una curva débil que sólo ella supiera atacar. Neal Koblitz y Alfred Menezes resumieron toda la polémica en A Riddle Wrapped in an Enigma, y la sospecha creció tras las revelaciones de Snowden y el caso de Dual_EC_DRBG, un generador de números aleatorios del NIST que sí tenía una puerta trasera.
La versión más extendida la contó el propio Jerry Solinas, de la NSA, en 2015: las semillas eran el hash de una frase en broma, algo como “Give Bob and Jerry a raise”, pero no recordaba los detalles, y el código lo había escrito un compañero que tampoco se acordaba. Solinas falleció en 2023 y la pregunta parecía condenada a quedarse sin respuesta. En 2023, Filippo Valsorda ofreció una recompensa a quien encontrara las frases originales.
No eran frases, eran marcas de tiempo
Varias personas de Anthropic habían buscado sin éxito la famosa frase. En octubre, alguien del equipo le pidió a un modelo de investigación interno que intentara averiguar cómo se generaron las semillas, sin darle la pista de la frase. Según el informe de Anthropic, en menos de media hora Claude encontró el origen de las semillas de P-192, P-224, P-256, P-384 y P-521. Y ninguna salía de un hash.
Eran la salida del generador de números pseudoaleatorios de la biblioteca de C, la familia drand48/lrand48, inicializado con la hora del sistema mediante srand48(). El programa iba sacando bytes del generador, probaba cada grupo de 20 bytes como semilla y descartaba las curvas que no cumplían los requisitos. P-256, por ejemplo, es el candidato número 1842 de la ejecución que empezó el 16 de agosto de 1997 a las 01:52:34 UTC.
| Curva | Marca de tiempo (UTC) | Candidato |
|---|---|---|
| P-192 | 1997-05-18 14:45:34 | 139 |
| P-521 | 1997-08-08 01:12:04 | 1136 |
| P-256 | 1997-08-16 01:52:34 | 1842 |
| P-384 | 1997-08-30 14:50:08 | 2688 |
| P-224 | 1998-04-03 12:52:07 | 7026 |
Lo mejor es que cualquiera puede comprobarlo. He reproducido la semilla de P-256 con este código, a partir del que publica Anthropic:
from datetime import datetime, timezone
t = int(datetime(1997, 8, 16, 1, 52, 34, tzinfo=timezone.utc).timestamp())
x = (t << 16) | 0x330E # el estado que deja srand48(t)
seed = ""
for i in range(20 * 1842):
x = (0x5DEECE66D * x + 0xB) % 2**48 # un paso del generador
if i >= 20 * 1841:
seed += "%02X" % (x >> 40) # el byte más alto del estado
print(seed) # C49D360886E704936A6678E1139D26B7819F7E90
Una marca de tiempo de 32 bits y un contador regeneran los 160 bits exactos de la semilla. Que eso pase por casualidad, y además en diez curvas distintas, es imposible.
Cómo lo encontró
La parte técnica me parece preciosa. En lugar de buscar frases, Claude pensó en cómo debía funcionar el software que generó las curvas en los noventa, y supuso que usaría el generador de la biblioteca de C. Esos generadores antiguos son tan simples que su salida se puede reconocer:
- Buscar la huella. Escribió un programa que recorría cada semilla bit a bit comprobando si los fragmentos consecutivos podían ser salidas seguidas de algún generador de la época, con 34 combinaciones distintas.
- Un patrón de ceros. En cuatro de las semillas, el bit más alto de cada palabra de 32 bits era cero. La probabilidad de que pase por azar es de 1 entre 5.810, y es justo la firma de
lrand48, que devuelve 31 bits de un estado de 48. - Recuperar el estado. En las curvas sobre cuerpos primos, cada byte de la semilla eran sólo los 8 bits más altos del estado. Recuperar el estado de un generador congruencial lineal truncado es un problema de libro de retículos, que se resuelve con el algoritmo LLL.
- Ir hacia atrás. Este generador se puede ejecutar al revés tan fácilmente como hacia delante, así que retrocedió hasta encontrar un estado con la forma que deja
srand48(). En todos los casos, lo que aparecía era una marca de tiempo Unix entre mayo de 1997 y abril de 1998.
De regalo, también encontró el origen de algunos puntos base de las curvas, el punto fijo del que se derivan todas las claves públicas. Los de P-192 y cinco curvas de ejemplo de ANSI X9.62 salen del generador de FreeLIP, la biblioteca de aritmética de Arjen Lenstra, inicializado con números pequeños como 20000. Según Anthropic, es la primera vez que se explica el origen de un punto base de las curvas NIST.
Lo que significa para la seguridad
No hay que hacer nada: no es un ataque ni una debilidad, sino al revés. Filippo lo explica con números en su artículo sobre el cobro de la recompensa. En 2017, Daniel Bernstein y Tanja Lange describieron cómo, con unos 70 bits de libertad al elegir la semilla, alguien podría haber apuntado a una hipotética familia de curvas débiles. Ahora sabemos que, aunque la NSA hubiera podido elegir cualquier momento de 1997-98 y cualquiera de los primeros 16 candidatos válidos, habría tenido apenas 30 bits de libertad. No basta para buscar una curva débil a propósito ni para meter una puerta trasera.
Quedan cabos sueltos. Algunas curvas válidas se descartaron sin motivo aparente: en la ejecución de P-256, el candidato 876 también daba una curva válida y no se publicó. Hay un criterio de rechazo que nadie ha sabido explicar, aunque Filippo apunta que estos cálculos, que hoy se hacen en minutos, eran lo último en 1997, y que pudo haber un simple fallo en algún algoritmo. Tampoco se sabe aún cómo se eligieron los puntos base de P-224, P-256, P-384 y P-521.
Filippo, que ha reimplementado el algoritmo en Go para verificarlo, cierra el “arco de rehabilitación” de las curvas NIST: con este hallazgo, las firmas deterministas, las implementaciones verificadas formalmente y las fórmulas de suma completas de 2015, ahora las recomienda personalmente por delante de Curve25519. Con una coletilla muy suya: justo a tiempo de que las retiren en favor de las firmas post-cuánticas.
Lo que me llevo
Me quedo con tres cosas. La primera, que la memoria engaña: Solinas contaba de buena fe lo de la frase, y esa pista falsa tuvo a mucha gente buscando en la dirección equivocada durante años. La segunda, que el equipo de Anthropic ha donado la recompensa a ISRG, la organización que mantiene Let’s Encrypt, y que con esa donación se ha triplicado hasta 36.864 dólares. Un buen final para una historia de criptografía.
Y la tercera es cómo se resolvió. No hizo falta fuerza bruta ni un superordenador, sino plantear el problema desde otro ángulo: pensar en cómo se escribía software en 1997 en lugar de buscar una frase olvidada. Igual que en el caso de la ingeniería inversa de hardware de hace unos días, la clave está en que el resultado se puede comprobar de forma objetiva: 160 bits que coinciden exactamente no admiten discusión, y cualquiera puede verificarlo con diez líneas de Python.
Fuentes: Claude reveals ECDSA curve origins, Anthropic, y The NIST Elliptic Curves Seeds Bounty Has Been Claimed, Filippo Valsorda.
