Anthropic dice que Claude descubrió el origen de las semillas de las curvas del NIST, y un criptógrafo lo reprodujo

Anthropic informó el viernes 16 de octubre que un modelo de investigación interno de Claude descubrió cómo se generaron las «semillas» de las curvas elípticas P-192, P-224, P-256, P-384 y P-521, que el Instituto Nacional de Estándares y Tecnología de los Estados Unidos (NIST) adoptó en 2000 para las firmas digitales ECDSA y cuyo origen nadie había podido explicar desde entonces^[1][5]. Según la empresa, esas semillas no surgieron de pasar una frase por una función de hash, como sostenía la versión más difundida, sino de un generador de números aleatorios común de la biblioteca de C, inicializado con la hora del reloj de una computadora entre mayo de 1997 y abril de 1998^[1]. El criptógrafo Filippo Valsorda, que en 2023 había ofrecido una recompensa a quien resolviera el enigma, informó el mismo viernes que el equipo de Anthropic la reclamó el 15 de octubre a la 1.07, hora universal, y que él reprogramó el método por su cuenta para comprobarlo^[2][3][4].

Qué es una semilla y por qué importaba

Una curva elíptica queda definida por unos pocos números. La norma FIPS 186-2, que el NIST publicó el 27 de enero de 2000, explica que en estas curvas «pseudoaleatorias» uno de esos coeficientes, b, se obtiene al pasar por el algoritmo SHA-1 un número de 160 bits, la semilla, y que publicarla permite verificar que el coeficiente surgió de ese procedimiento^[5]. Para P-256, la más usada de la familia, la semilla es c49d3608 86e70493 6a6678e1 139d26b7 819f7e90; el NIST la sigue publicando en la guía SP 800-186, de febrero de 2023, que habilita la curva para ECDSA y desaconseja las curvas binarias de la misma serie^[5][6].

El hash impide que alguien haya elegido b a mano, pero no dice cómo se eligió la semilla. Las semillas las aportó la Agencia de Seguridad Nacional (NSA) y las generó su matemático Jerry Solinas, que murió a comienzos de 2023^[4]. En correos que se conocieron en 2015 y que cita el investigador Stephen Weis, Solinas escribió: «Construimos todas las semillas mediante hashing (SHA-1, creo)», y admitió que no recordaban «ni el mensaje (exacto) ni los detalles» de cómo lo habían hecho^[7]. Esa laguna dejaba abierta una hipótesis teórica: que quien eligió las semillas hubiera probado muchísimas hasta dar con una curva de una clase débil que sólo él conociera. Valsorda recuerda una técnica de ese tipo, que los criptógrafos Daniel J. Bernstein y Tanja Lange describieron a Neal Koblitz y Alfred Menezes, autores del trabajo «A Riddle Wrapped in an Enigma»^[8]: según Valsorda, podría haber aprovechado 70 bits de libertad en la elección de la semilla para apuntar a una clase hipotética de 2⁶¹ curvas débiles, y Koblitz y Menezes la recogieron en una versión posterior de su trabajo^[2]. En octubre de 2023, Valsorda ofreció US$ 12.288 por los textos originales, una suma que se triplicaba si el ganador la donaba a una entidad benéfica^[4].

Cómo lo encontró Claude

Según Anthropic, un empleado le preguntó al modelo si podía averiguar cómo se habían generado las semillas, sin señalarle ninguna pista, y en menos de media hora el modelo halló el origen de las cinco^[1]. El modelo supuso, siempre según la empresa, que se había usado uno de los generadores débiles habituales en los años noventa y escribió un programa que buscaba sus huellas en 34 combinaciones de generador y porción de la salida^[1]. Notó que en cuatro de las diez semillas, escritas como palabras de 32 bits, el bit superior de cada palabra era cero, una marca de lrand48, un generador congruencial lineal que sólo entrega los 31 bits superiores de un estado interno de 48 bits^[1]. Con el algoritmo de reducción de retículos de Lenstra, Lenstra y Lovász (LLL) recuperó ese estado y, al hacer correr el generador hacia atrás, llegó a valores con la forma que les da la función srand48 al inicializarlo: marcas de tiempo de Unix, es decir, la hora de la computadora^[1]. La semilla de P-256 corresponde así al 16 de agosto de 1997 a la 1.52.34, hora universal^[1][3].

Valsorda describe el mismo mecanismo con drand48, otra función de esa familia que avanza el mismo estado de 48 bits, inicializada con srand48 y la hora del momento: su programa en Go toma de cada llamada los 8 bits superiores de ese estado, los mismos que usa el código de Anthropic, y reproduce las cinco semillas a partir de marcas de tiempo idénticas a las que da Anthropic. La primera, la de P-192, es del 18 de mayo de 1997, y la última, la de P-224, del 3 de abril de 1998^[1][2][3]. El mismo programa recalcula otras cinco semillas de curvas de ejemplo del estándar ANSI X9.62, y Anthropic publicó su propio código en Python, de dominio público, para que cualquiera repita el cálculo^[1][3].

Anthropic agrega que cuatro de las cinco semillas de las curvas binarias del NIST salen del mismo generador, inicializado con la mitad del valor del reloj, que duplicado da el 17 de abril de 1998; la quinta, la de B-163, «sigue sin explicación»^[1]. También atribuye los puntos base, el punto de partida de los cálculos en cada curva, de P-192 y de cinco curvas de ejemplo de X9.62 al generador de FreeLIP, una biblioteca del criptógrafo Arjen Lenstra; los de P-224, P-256, P-384 y P-521, y los de las curvas binarias, siguen sin explicar^[1].

Qué cambia para la confianza en las curvas

«Esto no es una ruptura criptográfica, un ataque nuevo ni una debilidad en las curvas ECDSA», aclara Anthropic, que sostiene que el hallazgo vuelve «mucho menos plausible» la sospecha de puertas traseras^[1]. Valsorda va más lejos: escribe que los resultados «descartan por completo» la técnica de Bernstein y Lange, porque con este método quien eligió las semillas habría tenido «apenas 30 bits de libertad», algo que «no alcanza para insertar ningún tipo de puerta trasera NOBUS», las que sólo puede aprovechar quien las colocó, y que el trabajo «refuerza nuestra confianza en estas primitivas criptográficas críticas»^[2].

Quedan preguntas abiertas. No se sabe con qué criterio se eligió entre las semillas candidatas válidas: según Anthropic, en P-256 la publicada es la candidata 1.842 de su corrida, pero la 876 también daba una curva de orden primo, con parámetros elegidos del mismo modo^[1]. Valsorda señala que hay «aproximadamente el doble de semillas válidas que las publicadas»; además de los controles de X9.62, identificó una regla no documentada, que descarta la semilla cuando el orden de la curva tiene más bits que el campo sobre el que está definida, pero dice que un segundo criterio «todavía se nos escapa»^[2]. Anthropic sostiene que las candidatas salteadas son pocas y que, por eso, una curva debilitada a propósito no resulta plausible^[1].

Ni el texto de Anthropic ni el de Valsorda mencionan una respuesta del NIST^[1][2]. El texto, publicado por el equipo Frontier Red Team de Anthropic, lleva diez firmas, entre ellas las de Henry de Valence y Nicholas Carlini; Valsorda no figura entre los autores^[1][2]. El equipo donó el premio, que con el triple llegó a US$ 36.864, al Internet Security Research Group, la organización sin fines de lucro que opera Let's Encrypt^[1][2].