L'incidente della backdoor Dual EC DRBG

Il Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) era uno dei quattro DRBG standardizzati da NIST in SP 800-90A (2006). Genera bit pseudocasuali usando due punti della curva ellittica, P e Q: a ogni passaggio calcola r_i = x(s_i * P) (la coordinata x della moltiplicazione di un punto), quindi s_{i+1} = x(r_i * P) aggiorna lo stato e output = x(r_i * Q) genera i bit. Il generatore appariva legittimo nella notazione accademica. Fu incluso in NIST SP 800-90A e successivamente approvato da RSA Security come impostazione predefinita nella sua libreria crittografica BSAFE, diffondendosi così nei software aziendali e governativi.

La backdoor di Dual EC DRBG sfrutta la relazione tra P e Q. Se un avversario conosce uno scalare segreto e tale che Q = e * P, allora, dato un qualsiasi blocco di output, può calcolare quanto segue: partendo da output = x(r * Q), può provare per forza bruta la coordinata y di r*Q, quindi calcolare r*P = (1/e) * (r*Q) mod n. Da r*P può prevedere tutti gli output futuri e recuperare lo stato interno. La conoscenza di e costituisce la backdoor: equivale al logaritmo discreto di Q rispetto a P. Lo standard NIST forniva i valori di P e Q senza spiegare come fossero stati scelti, rendendo impossibile verificare che fossero stati generati casualmente senza una trapdoor.

Nell'agosto 2007, Dan Shumow e Niels Ferguson presentarono un articolo fondamentale durante la Rump Session di CRYPTO, intitolato "Sulla possibilità di una backdoor nel NIST SP800-90 Dual Ec Prng". Dimostrarono formalmente che, se qualcuno conoscesse e (l'ECDLP di Q rispetto a P), potrebbe prevedere tutto l'output di Dual EC DRBG disponendo di circa 32 byte di output. Lo dimostrarono con un esempio semplificato. La loro presentazione attirò ampiamente l'attenzione della comunità della crittografia. Bruce Schneier scrisse: "non abbiamo modo di sapere se la NSA sia in grado di leggere o meno l'output di Dual_EC_DRBG". Nonostante questo avvertimento, Dual EC DRBG rimase nello standard per altri sei anni.

Nel settembre 2013, The New York Times, The Guardian e ProPublica pubblicarono articoli basati su documenti fatti trapelare da Edward Snowden, dai quali emergeva che la NSA aveva introdotto segretamente vulnerabilità negli standard crittografici. Un documento, intitolato "Sigint Enabling Project", descriveva un programma da 250 milioni di dollari all'anno per "influenzare segretamente" gli standard e i prodotti di cifratura. Sebbene il documento non nominasse esplicitamente Dual EC DRBG, insieme alla dimostrazione matematica di Shumow e Ferguson portò la comunità della crittografia a concludere ampiamente che la NSA avesse inserito la backdoor scegliendo P e Q con una relazione e nota, mantenendo segreta e mentre sottoponeva le costanti a NIST.

Nel dicembre 2013 Reuters riferì che la NSA aveva pagato 10 milioni di dollari a RSA Security affinché rendesse Dual EC DRBG l'impostazione predefinita nel toolkit crittografico BSAFE di RSA. RSA Security, allora una divisione di EMC, distribuiva BSAFE all'interno di software aziendali utilizzati da istituti finanziari, aziende sanitarie e appaltatori governativi. La dichiarazione di RSA negava di aver implementato consapevolmente una backdoor, ma riconosceva di aver accettato il contratto. La rivelazione fu particolarmente dannosa: BSAFE era commercializzato come prodotto di sicurezza e i suoi clienti lo avevano scelto proprio per le garanzie crittografiche offerte. L'incidente danneggiò gravemente la reputazione di RSA Security e portò ai boicottaggi della RSA Conference nel 2014.

In seguito alle rivelazioni di Snowden, NIST intraprese diverse azioni. Nel settembre 2013, NIST riaprì SP 800-90A per i commenti pubblici e raccomandò di non utilizzare Dual EC DRBG mentre era in corso la revisione. Nell'aprile 2014, NIST pubblicò SP 800-90A Revision 1, che rimosse completamente Dual EC DRBG: rimasero soltanto Hash_DRBG, HMAC_DRBG e CTR_DRBG. NIST avviò inoltre una revisione di tutti i propri standard e linee guida crittografici, esaminando in particolare se l'influenza della NSA avesse compromesso altri standard. Fu creato il gruppo di lavoro NIST Cryptographic Standards and Guidelines Process per aumentare la trasparenza e la partecipazione pubblica nelle future attività di standardizzazione.

La backdoor di Dual EC DRBG ebbe profonde conseguenze sulla fiducia della comunità della crittografia negli enti di standardizzazione. Dimostrò che un'agenzia di intelligence nazionale era disposta a indebolire deliberatamente standard crittografici utilizzati in tutto il mondo, con conseguenze non solo per gli avversari, ma anche per alleati, aziende e cittadini privati. L'incidente accelerò l'adozione di algoritmi aperti e verificabili, con numeri nothing-up-my-sleeve: Keccak, l'algoritmo di SHA-3, usava un algoritmo documentato per generare le proprie costanti; BLAKE2 e BLAKE3 derivano le costanti dalle parti frazionarie di costanti matematiche; Curve25519 usa un numero primo (2^255 - 19) scelto appositamente per essere verificabile. La generazione verificabilmente casuale dei parametri delle curve ellittiche divenne una pratica standard.

Lo scandalo di Dual EC DRBG rese popolare il concetto di costanti "nothing-up-my-sleeve" (NUMS), cioè parametri crittografici generati a partire da fonti pubblicamente verificabili che non possono contenere trapdoor nascoste. Esempi: SHA-2 usa valori iniziali dell'hash derivati dalle radici quadrate dei primi 8 numeri primi; le costanti dei round derivano dalle radici cubiche dei primi 64 numeri primi. BLAKE2 deriva le costanti dagli sviluppi frazionari di pi greco e di altre costanti matematiche. Ed25519 usa il numero primo 2^255 - 19 e un punto base il cui logaritmo discreto rispetto a qualsiasi altro punto è dimostrabilmente sconosciuto (è scelto come hash di una stringa). Queste pratiche consentono a chiunque di verificare che le costanti non siano state scelte sulla base di conoscenze segrete.

Nel dicembre 2015, Juniper Networks rivelò che in ScreenOS, il proprio sistema operativo per firewall, era presente codice non autorizzato dal 2012. L'indagine rivelò due backdoor: una sostituiva la costante Q di Dual EC DRBG con un valore controllato dall'attaccante, consentendo all'attaccante che conosceva la e corrispondente di decifrare il traffico VPN; la seconda backdoor riguardava la password amministrativa SSH. La sostituzione di Q in Dual EC era particolarmente sofisticata: Juniper utilizzava già un valore Q non standard e l'attaccante lo sostituì con il proprio, sfruttando due volte la struttura trapdoor di Dual EC. Questo dimostrò che anche le implementazioni che si discostavano dai valori P/Q di NIST potevano essere attaccate da chiunque avesse inserito il proprio Q.

L'incidente di Dual EC DRBG insegna diverse lezioni. (1) Trasparenza: i parametri crittografici devono avere origini verificabili; le costanti prive di documentazione sulla loro derivazione sono sospette. (2) Progettazione degli algoritmi: gli algoritmi non dovrebbero avere strutture che possano nascondere trapdoor (la relazione Q/P di Dual EC non offre alcun vantaggio in termini di sicurezza rispetto a progetti DRBG più semplici). (3) Conflitto di interessi: gli enti di standardizzazione devono gestire con rigore i conflitti con le agenzie di intelligence. (4) Revisione da parte della comunità: i crittografi accademici devono poter sollevare dubbi prima della pubblicazione degli standard, non dopo. (5) Vigilanza sulla distribuzione: le organizzazioni dovrebbero verificare quali DRBG utilizzano le proprie librerie crittografiche e rimuovere preventivamente le opzioni non raccomandate.

Dopo la rimozione di Dual EC, il panorama dei DRBG raccomandati si è concentrato su Hash_DRBG, HMAC_DRBG e CTR_DRBG. La comunità open source ha adottato anche DRBG non NIST nei contesti in cui gli standard NIST non godono di fiducia: gli RNG basati su ChaCha20 (utilizzati nel kernel Linux dalla versione 5.17, in OpenBSD e in libsodium) sono ampiamente considerati resistenti alle backdoor, perché ChaCha20 è un semplice cifrario a flusso privo di strutture trapdoor. Fortuna, utilizzato in FreeBSD e nelle versioni meno recenti di macOS, precede SP 800-90A e continua a essere considerato affidabile. L'incidente di Dual EC ha inoltre riacceso l'interesse per gli RNG hardware (RDRAND) come fonti di entropia, sebbene anche RDRAND abbia dovuto affrontare accuse di possibile inserimento di backdoor; ciò ha portato a raccomandare di combinare RDRAND con l'entropia software invece di utilizzarlo esclusivamente.

Quale relazione matematica rende possibile la backdoor di Dual EC DRBG?

Dual EC DRBG fu standardizzato in NIST SP 800-90A nel 2006. Nel 2007 Shumow e Ferguson dimostrarono che conoscere e (dove Q=e*P) consente di prevedere tutto l'output a partire da 32 byte. Le fughe di documenti di Snowden nel 2013 confermarono l'influenza della NSA sugli standard crittografici. Secondo quanto riferito, RSA Security ricevette 10 milioni di dollari per rendere Dual EC l'impostazione predefinita in BSAFE. NIST rimosse Dual EC in SP 800-90A Revision 1 (2014). L'incidente Juniper del 2015 mostrò lo sfruttamento della trapdoor in un prodotto reale. Le lezioni includono: costanti NUMS, derivazione trasparente, gestione dei conflitti di interesse e processi di audit successivi alla standardizzazione. Gli RNG basati su ChaCha20 emersero come alternativa affidabile.