Nombres sense trampa: P-256 va sortir d'un rellotge

Constants que tothom pot tornar a calcular

SHA-256 és l'exemple de manual. Les seves seixanta-quatre constants de 32 bits, que comparteix amb SHA-224, representen els primers 32 bits de les parts fraccionàries de les arrels cúbiques dels seixanta-quatre primers nombres primers. Tothom pot repetir el càlcul: la primera de la llista és 428a2f98.

Corbes amb la recepta a la vista

Altres estàndards de corbes el·líptiques apliquen la mateixa idea als seus paràmetres. Un d'ells descriu així el seu mètode de generació: «pretén ser tan objectiu com sigui raonablement possible perquè quedi clar que cap consideració indeguda no va influir en l'elecció de la corba». El contrari, una constant que ningú no explica, deixa oberta la sospita que algú la triés a dit.

Les corbes del NIST i la seva llavor sense història

El NIST, el National Institute of Standards and Technology dels EUA, fundat el 1901 i avui part del Department of Commerce (Departament de Comerç), va adoptar ECDSA el 2000 dins de FIPS 186-2. Aquesta norma inclou una llista de corbes estàndard: P-192, P-224, P-256, P-384 i P-521. Molta criptografia actual s'hi recolza, sobretot en P-256 i P-384.

En cada corba, el coeficient b surt de passar una llavor per SHA-1, seguint el mètode d'ANSI X9.62 per generar corbes «verificablement a l'atzar». SP 800-186 ho descriu així: b es va derivar «de manera difícil d'invertir» a partir d'un valor pseudoaleatori. El problema és que aquestes llavors les va aportar la NSA, agència de suport al combat del Departament de Guerra dels EUA que dirigeix la criptologia del Govern, sense cap explicació ni justificació.

Una frase graciosa que ningú no recordava

L'explicació més repetida era una frase. Segons Jerry Solinas, veterà empleat de la NSA, les llavors van sortir del hash d'un missatge humorístic «de l'estil de “Doneu un augment al Bob i al Jerry”», tot i que el 2015 ja no en recordava els detalls. Solinas va morir el 2023 i la pregunta va quedar oberta.

L'octubre del 2023, Filippo Valsorda, que va organitzar la recerca, va oferir una recompensa per desxifrar els cinc hashes, que es triplicava fins a 36.864 dòlars si el guanyador la donava a una organització benèfica. Això sí, Valsorda sosté que el temor que la NSA triés les llavors per colar-hi corbes febles no està ben fonamentat.

Dual_EC_DRBG: quan la sospita va tenir conseqüències

Segons l'informe del Visiting Committee on Advanced Technology, el principal comitè assessor federal del NIST, durant l'elaboració de l'estàndard els criptògrafs van assenyalar dos problemes: la possibilitat d'una porta del darrere lligada als paràmetres concrets i un biaix estadístic en la sortida, «com un dau trucat». Es va afegir un mètode per generar paràmetres alternatius, però els originals van continuar sent els recomanats i eren obligatoris per validar mòduls criptogràfics davant del NIST.

La pregunta equivocada

Segons el NIST, en avaluar Dual_EC_DRBG es va preguntar «creiem que hi ha una trampa?» quan s'hauria d'haver preguntat «hem d'incloure en els nostres estàndards un algorisme que podria tenir una trampa?». L'organisme sosté que llavors creia improbable una porta del darrere, i xifra en més de 50 els mòduls criptogràfics validats que l'implementaven.

El setembre del 2013, informacions de premsa van provocar preocupació pública sobre la fiabilitat de Dual_EC_DRBG. El NIST afirma que en va desaconsellar l'ús immediatament i que l'abril del 2014 el va retirar de l'esborrany de SP 800-90A «basant-se en la seva pròpia avaluació i en resposta a la manca de confiança pública». Segons el NIST, qui encara el faci servir ha de passar a un dels tres algorismes restants «com més aviat millor».

El que va trobar Claude

Segons Anthropic, l'octubre del 2026 un dels seus empleats va demanar a un model intern de recerca que esbrinés com s'havien generat les llavors, sense donar-li la pista de la frase. En menys de mitja hora, Claude va descobrir que les de P-192, P-224, P-256, P-384 i P-521 no sortien de cap hash, sinó del generador lrand48 de la biblioteca de C, iniciat amb una marca de temps Unix.

Segons Anthropic, cada inicialització de srand48 de les llavors de les corbes sobre cossos primers va ser una marca de temps Unix d'una data entre el maig del 1997 i l'abril del 1998. Per a P-256, la sortida del codi publicat mostra la marca «1997-08-16 01:52:34», i la seva llavor és el candidat número 1.842 d'aquella execució.

Anthropic afirma que la troballa no és un trencament criptogràfic, ni un atac nou, ni una debilitat de les corbes ECDSA, i que fa «molt menys plausible» que es triessin amb portes del darrere: les llavors van sortir d'un generador corrent iniciat amb el rellotge, cosa que ara tothom pot reproduir.

Fes-ho tu: reprodueix la llavor de P-256

Anthropic publica a la mateixa pàgina el codi que reprodueix les llavors. N'hi ha prou de desar-lo en un fitxer, per exemple llavors.py, i executar-lo amb Python. El programa converteix cada data en una marca de temps Unix, engega l'estat de lrand48 tal com ho faria srand48, amb els 16 bits baixos fixats, i va traient candidats de 20 bytes fins a arribar al número indicat.

A la sortida hi ha una línia per corba. La de P-256 diu: «P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90». L'última columna coincideix amb la llavor publicada de P-256, C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, i amb la que figura a la llista de Filippo Valsorda.

El que continua sense resposta

Segons Anthropic, queden caps per lligar. La llavor de la corba binària B-163 no encaixa amb res del que ha provat Claude, i no se sap com es van generar els punts base de P-224, P-256, P-384 i P-521. Tampoc no se sap per què es van saltar candidats viables: a P-256, el 876 de la mateixa execució també donava una corba d'ordre primer de la mida adequada.

Anthropic sosté que, com que els candidats saltats són pocs, no creu plausible que es triessin corbes debilitades. Segons Anthropic, es preveu donar els 36.864 dòlars de la recompensa a l'Internet Security Research Group.