Claude resol el misteri de les corbes de la NSA

Unes llavors sense explicació

ECDSA és l'estàndard de criptografia de corba el·líptica més utilitzat, i el NIST (National Institute of Standards and Technology, Institut Nacional d'Estàndards i Tecnologia) el va adoptar el 2000 dins de FIPS 186-2, que fixa una sèrie de corbes estàndard. Segons el NIST, l'organisme es va fundar el 1901 i avui forma part del Departament de Comerç dels Estats Units (U.S. Department of Commerce).

Per a les corbes sobre cossos primers i binaris, l'especificació va publicar un paràmetre anomenat llavor (seed) el hash del qual defineix el coeficient b de la corba. Aquestes llavors les va aportar la NSA sense cap explicació ni justificació. Segons la NSA, l'Agència de Seguretat Nacional és una agència de suport de combat del Departament de Guerra dels Estats Units i lidera la criptologia del Govern.

I no són corbes qualssevol: P-256 i P-384 són les que fan servir els certificats ECDSA que protegeixen bona part del web.

La frase humorística que no va existir mai

La versió més acceptada era que Jerry Solinas, empleat de la NSA durant anys, havia generat les llavors amb el hash d'una frase humorística. Segons Solinas, que ho va explicar el 2015, el missatge era «alguna cosa com “Give Bob and Jerry a raise” o “Bob and Jerry rule”», i el codi el va escriure Bob Reiter, que tampoc no en recordava els detalls.

Solinas va morir el 2023 i els seus col·legues d'aleshores no van aclarir la qüestió. Segons Anthropic, diversos empleats de la companyia van seguir sense èxit la pista de la frase, que va resultar ser falsa.

Segons Filippo Valsorda, que la va organitzar, la recompensa anunciada l'octubre del 2023 arribava a 36.864 dòlars per les cinc llavors de les corbes del NIST si el guanyador la donava a una entitat benèfica 501(c)(3).

La pista era al rellotge

Segons Anthropic, l'octubre del 2026 un empleat curiós va preguntar a un model intern de recerca si podia esbrinar com s'havien generat les llavors, sense donar-li la pista de la frase. En menys de mitja hora, Claude va descobrir l'origen de les de P-192, P-224, P-256, P-384 i P-521.

Segons Anthropic, cap d'elles no va sortir d'un algorisme de hash: són sortides de lrand48, el generador de nombres aleatoris de la biblioteca de C, inicialitzat amb una marca de temps Unix. El programa extreia 20 bytes del generador a cada iteració com a llavor candidata, i per a P-256 van caldre 1.842 iteracions.

El generador lrand48 només retorna els 31 bits alts d'un estat intern de 48 bits. Anthropic afirma que les llavors de corbes de cos primer conservaven menys bits de cada sortida i que Claude en va recuperar l'estat intern amb la reducció de reticles LLL (Lenstra–Lenstra–Lovász); el mateix patró va aparèixer en cinc llavors més de l'estàndard ANSI X9.62. Cada estat recuperat regenera els 160 bits de la seva llavor, cosa que no passa per atzar.

Segons Anthropic, totes les inicialitzacions de les corbes de cos primer són marques de temps d'entre maig del 1997 i abril del 1998. Les de quatre corbes binàries es llegeixen com a febrer del 1984; amb la marca duplicada cauen el 17 d'abril del 1998, dues setmanes després de l'execució de P-224, de manera que el programa podria haver dividit el rellotge per dos.

Els punts base i els caps per lligar

Segons Anthropic, Claude també va explicar els punts base de les sis corbes generades el maig del 1997: P-192 i cinc corbes d'exemple d'ANSI X9.62. Surten del generador de nombres aleatoris de FreeLIP, el paquet d'aritmètica d'enters llargs d'Arjen Lenstra, inicialitzat amb un nombre enter petit; les primeres versions de NTL, la biblioteca de Victor Shoup, incloïen el mateix codi.

Anthropic afirma que, fins on sap, ningú no havia explicat abans cap punt base del NIST.

Segons Anthropic, la llavor de la corba binària B-163 no encaixa amb res del que Claude ha provat, i no se sap com es van generar els punts base de P-224, P-256, P-384 i P-521 ni els de les corbes binàries del NIST.

Tampoc no està clar per què es van saltar candidates vàlides, segons Anthropic. A P-256 la llavor publicada és la candidata 1.842, però la 876 de la mateixa execució també donava una corba vàlida d'ordre primer; l'execució de P-224 va passar per sobre de tres corbes així, i les dues de les corbes d'exemple d'ANSI X9.62, de set més. No se sap amb quin criteri es va fer ni si va ser involuntari.

Més confiança, no menys

Anthropic sosté que no és una ruptura criptogràfica, ni un atac nou, ni una debilitat de les corbes ECDSA. Al contrari, segons l'empresa, la troballa dona més confiança que es van triar sense portes del darrere: les llavors van sortir d'un generador pseudoaleatori comú inicialitzat amb el rellotge, que ara qualsevol pot reproduir, i això deixa molt menys marge per manipular-les.

Segons Anthropic, com que es van saltar poques candidates, no és plausible que es triessin corbes afeblides, perquè això implicaria que les corbes febles són comunes i fàcils de trobar. Tot i així, l'empresa reconeix que, en principi, algú podria haver buscat entre marques de temps una corba amb alguna propietat concreta.

Per a qui fa servir aquestes corbes, no canvia res: segons Anthropic, no cal fer res de diferent, i la majoria dels investigadors ja hi confiava.

Segons Anthropic, la companyia preveu donar els 36.864 dòlars de la recompensa a l'Internet Security Research Group (ISRG), la corporació californiana de benefici públic fundada el 2013 per acollir projectes com Let's Encrypt. Segons l'ISRG, el patrocinen des de petites empreses fins a companyies del Fortune 100.