Semi delle curve NIST svelati: 5 miti sull'origine di ECDSA

Per venticinque anni, i semi delle curve ECDSA del NIST sono stati la cosa più vicina a un cold case irrisolto nella crittografia applicata. Cinque valori da 160 bit apparentemente casuali, consegnati al NIST dalla NSA senza alcuna spiegazione, alla base delle firme di qualsiasi cosa, dalle tue connessioni TLS alle transazioni Bitcoin. Questa settimana il caso è chiuso, e la risposta è quasi imbarazzante: i semi erano l'output del generatore lrand48() della libreria C, inizializzato con timestamp Unix del 1997 e del 1998. Tutto qui. Nessun hash di una passphrase segreta, nessuna macchina esotica — srand48(time(NULL)), esattamente il pattern che ogni corso di sicurezza ti dice di non usare mai.

La scoperta è arrivata da un modello di ricerca di Anthropic, indirizzato sul problema da un dipendente curioso, che ha riconosciuto la firma statistica di un generatore lineare congruenziale degli anni '90 nelle costanti pubblicate e ha fatto girare lo stato all'indietro finché non è arrivato a date del calendario. Ho passato abbastanza anni a fare audit di sistemi crittografici per sapere che questo conta — non perché le curve siano rotte (non lo sono), ma perché demolisce diverse cose in cui il nostro settore credeva con sicurezza. Vediamo i miti uno alla volta.

Mito 1: costanti inspiegate significano una backdoor nascosta

Il sospetto non era assurdo. Quando il NIST ha pubblicato le curve FIPS 186-2 nel 2000, ognuna era accompagnata da un seme il cui hash determina il coefficiente b della curva. Il NIST ha dichiarato che i semi garantivano che le curve fossero «verificabilmente casuali», ma non poteva o non voleva spiegare come fossero stati generati i semi stessi. Koblitz e Menezes hanno scritto un intero articolo sulla controversia, significativamente intitolato «A Riddle Wrapped in an Enigma». La pista migliore della comunità era Jerry Solinas della NSA, che nel 2015 ha ricordato che l'input era l'hash di una frase scherzosa, qualcosa come «Give Bob and Jerry a raise». È morto nel 2023 senza che nessuno recuperasse i dettagli.

Ecco la verità scomoda per i complottisti, me compreso a volte: inspiegato di solito significa non documentato, non malevolo. Il processo di generazione reale era uno sviluppatore che lanciava un piccolo programma in C, lasciando che il PRNG di default si inizializzasse dall'orologio di sistema, e prendeva il primo candidato che produceva una curva utilizzabile. Il seme pubblicato per P-256 era il candidato numero 1.842 di una run iniziata alle 1:52 del 16 agosto 1997. Non è il flusso di lavoro di un'agenzia che pianta una trappola teorico-numerica. È un ingegnere all'una di notte che fa girare un ciclo finché non stampa qualcosa di valido.

Ho visto questo schema nelle postmortem di incidenti più volte di quante ne possa contare. Un valore di configurazione misterioso, una costante magica non documentata, un passaggio di deploy che nessuno sa spiegare — e il postmortem rivela che era una scorciatoia ragionevole di un ingegnere stanco, mai scritta da nessuna parte. Il vero peccato della NSA non è stato backdoorare le curve. È stato spedire costanti crittografiche al mondo intero senza un README.

Mito 2: il metodo di generazione prova che la selezione è stata onesta

Ora la sovracorrezione. Molti commenti di questa settimana trattano «sono solo timestamp» come una assoluzione totale. Non è così, e i ricercatori dietro il lavoro sono attenti a dirlo. Sapere come sono stati generati i candidati non dice nulla su come siano state selezionate le curve finali — e la selezione è avvenuta nell'arco di mesi, da maggio 1997 ad aprile 1998.

Le prove vanno in entrambe le direzioni. Nella run di P-256, anche il candidato 876 produceva una curva di ordine primo della dimensione giusta, costruita con le stesse convenzioni sui parametri — ed è stato scartato. La curva pubblicata era il candidato 1.842. La run di P-224 ha scartato tre curve valide; le run ANSI X9.62 ne hanno scartate altre sette. Non possiamo vedere la storia completa dei candidati scartati, solo quelli raggiungibili nelle run registrate. Se qualcuno volesse una curva con una specifica proprietà rara, avrebbe potuto in linea di principio cercare tra i timestamp finché non ne trovava una, per poi tacere completamente sul timestamp. «Farlo e non dirlo» è sempre stata un'opzione.

La mia lettura, dopo anni a seguire la ricerca sulle curve deboli: l'ipotesi della backdoor è gravemente ferita ma non formalmente morta. I candidati scartati sono abbastanza pochi che il cherry-picking implicherebbe che le curve deboli siano comuni e facili da trovare — cosa che due decenni di crittoanalisi pubblica dicono non essere. Nessuno ha mai pubblicato un distinguitore capace di separare queste curve da quelle casuali. Ma «nessuna debolezza nota» e «provabilmente nessuna debolezza» sono affermazioni diverse, e la posizione onesta è la prima. Questo è esattamente il divario tra specifica e implementazione che si manifesta a livello di standard: la specifica diceva «verificabilmente casuale», e l'implementazione era «quello che diceva l'orologio».

I semi sono stati generati come farebbe uno studente di dottorato: un PRNG standard e l'orologio di sistema. Lo scandalo non è mai stato la matematica. È stata la documentazione mancante.

Mito 3: i vecchi PRNG deboli sono innocui se li usi una volta sola

È il mito che dovrebbe far drizzare le orecchie a ogni ingegnere che abbia mai digitato srand(time(NULL)). Il velo di mistero lungo venticinque anni esisteva per una sola proprietà di progetto di lrand48(): perde la propria struttura. Il generatore restituisce solo i 31 bit più significativi di uno stato a 48 bit, quindi le sue parole di output hanno sempre il bit più alto a zero. Scritti come parole a 32 bit, quattro dei dieci semi per curve binarie mostrano bit più alti tutti a zero per venti parole consecutive — un evento con probabilità di circa uno su 58.000 con una distribuzione uniforme. La firma era visibile a occhio nudo per chiunque avesse pensato di guardare.

Da lì l'attacco è imbarazzantemente economico. Per recuperare gli stati delle curve binarie, prendi la prima parola di output, fai un brute-force sugli 2^17 bit nascosti più bassi e verifichi se le quattro parole successive seguono. Parliamo di pochi millisecondi di calcolo. Per le curve primi i semi conservavano meno bit per output, quindi recuperare lo stato ha richiesto il classico attacco LCG troncato: modellarlo come problema su reticolo e attaccarlo con la riduzione di base LLL. Materiale da manuale, letteralmente. Una volta ottenuto lo stato, un LCG si può far girare all'indietro con la stessa facilità con cui va in avanti, quindi lo riavvolgi finché non mostra la forma di inizializzazione di srand48 — bit bassi uguali a 0x330E — e leggi il timestamp con cui era stato inizializzato.

# 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 lezione vale ben oltre gli organismi di standardizzazione. Ogni valore «dall'aspetto casuale» che emetti — token di sessione, ID di richiesta, salt, nomi di file — porta l'impronta del generatore che lo ha creato. Se quel generatore è un motore lineare congruenziale o un Mersenne Twister, qualche decina di output ricostruisce lo stato interno, e tutto ciò che hai generato prima e dopo diventa prevedibile. Un singolo uso, venticinque anni fa, in un file progettato per sembrare rumore, è stato completamente invertito. Quando faccio code review di codice che usa RNG non crittografici per qualsiasi cosa un attaccante possa osservare, questa è la storia di guerra che d'ora in poi citerò.

Mito 4: i numeri «nothing-up-my-sleeve» non sono mai stati la vera protezione

L'idea «nothing-up-my-sleeve» — derivare le costanti da qualcosa di palesemente innocente, come le cifre di pi greco — serve a limitare i gradi di libertà del progettista. Se posso mostrarti che la mia costante deriva da una procedura pubblica e rigida, non avevo spazio per infilare una backdoor. I semi del NIST hanno fallito questo test sul piano procedurale: la procedura era segreta, quindi il limite sui gradi di libertà era sconosciuto. Ma ciò che questo episodio davvero espone è che il test della manica è più debole di quanto fingessimo anche quando funziona.

Pensa a cosa ti dà davvero «verificabilmente casuale da un timestamp». Un timestamp vale circa 31 bit di entropia per una finestra plausibile. Chiunque — incluso l'autore originale — può scorrere milioni di timestamp, generare milioni di curve candidate e pubblicare solo quella che vuole, insieme al suo seme dall'aspetto innocuo. Se le curve con una debolezza segreta esistessero con una frequenza di una su un milione, il grinding sui timestamp ne trova una in un pomeriggio. Il seme prova da dove viene il numero e dice quasi nulla sul perché quello specifico sia stato scelto. Lo stesso vale per gli schemi basati sull'hash di una passphrase, ed è per questo che anche la voce sulla frase scherzosa di Solinas non è mai stata davvero rassicurante.

La pratica moderna più solida è la costruzione rigida delle curve: scegliere il coefficiente più piccolo che soddisfa un elenco pubblico di criteri di sicurezza, con le regole di selezione fissate prima che la ricerca inizi. È la filosofia alla base di Curve25519 ed è il motivo per cui gli argomenti di rigidità di Dan Bernstein hanno cambiato il modo in cui la comunità valuta le curve. La vera protezione contro costanti malevole non è mai stata una storia di derivazione carina. Sta nel minimizzare lo spazio di ricerca, pubblicare i criteri in anticipo e avere abbastanza occhi indipendenti sulla matematica da impedire che una proprietà nascosta resti nascosta. Auditare le costanti significa auditare il processo che le ha filtrate — ed è per questo che le domande ancora aperte qui (i candidati scartati, i punti base inspiegati per P-256 e simili, il seme di B-163 ancora non identificato) meritano di restare aperte agli atti invece di essere cancellate dalla celebrazione.

Mito 5: gli LLM si limitano a ripetere — non possono fare crittoanalisi originale

È il mito che punge di più, perché io ci credevo in una sua versione. Il problema aperto è rimasto irrisolto per un quarto di secolo nonostante una taglia pubblica di 36.864 dollari e un'attenzione seria da parte di appassionati esperti. Diversi ricercatori di Anthropic lo avevano inseguito seguendo la pista della «funny phrase hash», senza successo. Poi un modello di ricerca interno, interrogato senza che gli venisse fornita la voce, ha provato un approccio diverso in meno di mezz'ora: invece di indovinare l'input di un hash, si è chiesto quale software avesse generato i semi, ha ipotizzato un PRNG della libreria C degli anni '90, ha scritto uno scanner che scorreva su ogni seme testando 34 combinazioni di generatore e porzione di output, ha individuato lo schema dei bit più alti a zero, ha eseguito l'attacco su reticolo sugli output troncati e ha riportato gli stati a date del calendario.

Nota cosa rappresenta quel flusso di lavoro. Non è richiamo di memoria — nessun documento di training conteneva la risposta, perché la risposta non esisteva da nessuna parte. È generazione di ipotesi più uso di strumenti più verifica, cioè la vera forma del lavoro crittoanalitico. Il modello ha persino controllato il proprio buon senso a metà esecuzione: è un ambiente di test simulato? Possibile che una cosa così ovvia sia rimasta non trovata per 25 anni? Una corrispondenza di 160 bit a partire da un seme a 32 bit esclude la coincidenza? Questa autocritica è ciò che vorrei da un analista umano, e francamente alcuni analisti umani la saltano. Su questo sito stiamo da un po' mettendo alla prova i miti su ciò che questi modelli fanno davvero, e questo è un dato pulito: gli LLM ora sono in grado di eseguire ragionamento forense in più passaggi su artefatti del mondo reale, non solo sui benchmark.

Il contrappunto onesto dei professionisti riguarda la provenienza. Il modello non ha inventato il recupero dello stato LCG né LLL — poggia su decenni di crittoanalisi pubblicata da ricercatori noti e ignoti, e non può dirti di quali articoli abbia plasmato il suo approccio. Questo mi preoccupa meno di quanto preoccupi alcuni. Lo scanner, il codice di verifica e lo script di riproduzione sono pubblici; le persone del team hanno indirizzato la domanda e validato il risultato. Riconosciamo onestamente la divisione del lavoro: la macchina ha fornito una ricerca di ipotesi instancabile, gli umani hanno fornito giudizio e responsabilità. La taglia da 36.864 dollari andata all'Internet Security Research Group è stato un modo elegante di chiudere la questione.

Cosa cambia per gli audit di sicurezza

Quindi dove lascia un ingegnere al lavoro? Alcuni cambiamenti concreti nel modo in cui affronterei gli audit da ora in poi. Primo, tratta ogni costante magica in un protocollo o in un codebase come un artefatto forense, non come un dato di natura. Chiediti quale generatore potrebbe averla prodotta, verifica le impronte strutturali — bit alti sbilanciati, parole successive correlate da LCG, recuperi di stato plausibili con un timestamp — prima di accettare «è casuale» come risposta. Gli strumenti per farlo sono ormai banalmente disponibili.

Secondo, se pubblichi costanti, pubblica anche il generatore. Codice sorgente, input esatti, ambiente esatto. «Verificabilmente casuale» senza una ricetta riproducibile ti compra venticinque anni di sospetti e una taglia sulla tua eredità. Terzo, continua a usare P-256 — la scoperta aumenta la fiducia nelle curve invece di diminuirla, e il vero modello di minaccia per le curve ellittiche è l'hardware quantistico, non l'orologio di una workstation del 1997. Ma leggi onestamente le domande aperte: i punti base inspiegati e i candidati scartati sono fili sciolti, e un lavoro di sicurezza maturo significa tenerli registrati.

La lezione più profonda riguarda la memoria istituzionale. Jerry Solinas ricordava una battuta sugli aumenti di stipendio che si è rivelata sbagliata. Gli archivi, con le sue parole, probabilmente stavano su un hard disk vicino all'Arca dell'Alleanza. L'unico motivo per cui oggi conosciamo la verità è che l'output stesso conservava abbastanza struttura da confessare. I tuoi sistemi stanno scrivendo le proprie confessioni proprio ora, in ogni ID, token e costante che rilasci. Assicurati che confessino qualcosa di cui sei orgoglioso.