venerdì 27 settembre 2013

Come la NSA ha truccato la crittografia

23 Settembre 2013, Martijn Grooten

Di tutte le rivelazioni fatte da Edward Snowden, trovo quella recente su Dual_EC_DRBG sicuramente la più intrigante e se possibile la più scioccante – anche se non era proprio una notizia.

Mi incuriosisce perché tratta delle curve ellittiche. Amo le curve ellittiche. Le ho studiate abbastanza approfonditamente quando ho lavorato come matematico, e anche se non le uso più, sento ancora una predilezione per loro.

Ma ancora più importante, mi intriga perché inizialmente non mi rendevo conto quanto fosse realmente accaduto – e a giudicare dai commenti e gli articoli che ho visto, non ero l'unico.

La NSA non ha indebolito uno standard crittografico. Piuttosto, ha messo una backdoor all'interno dello standard. C'è una differenza importante. Di conseguenza, se si utilizza Dual_EC_DRBG, sei ancora ben protetto se l'avversario dal quale ti stai difendendo non è l'NSA. Ma se lo è, praticamente sei fritto.

Dual_EC_DRBG è un generatore di numeri pseudo-casuale (o generatore casuale di bit deterministico; da qui il nome). È uno dei quattro del suo genere che sono stati definiti nello standard del 2006 NIST SP 800-90A (PDF). Lo standard è stato scritto con l'aiuto di alcune persone presso la NSA. Per quanto ne sappiamo ora *, di fatto l'NSA ha scritto lo standard.
Riconoscimenti
L'Istituto Nazionale degli Standard e delle Tecnologie (NIST) graditamente ringrazia con riconoscenza e apprezza i contributi di Mike Boyle e Mary Baish dell'NSA per l'assistenza nello sviluppo di questa Raccomandazione. Il NIST ringrazia anche i molti contributi dai settori pubblici e privati.
Beh, questo è fastidioso.

La casualità è una parte essenziale di qualsiasi sistema di crittografia. È anche dove molti sistemi di crittografia hanno debolezze, quindi se si sta implementando la crittografia, ha senso utilizzare uno standard fornito da una rispettabile organizzazione come il NIST.

Quello che fanno i generatori di numeri pseudo-casuali è trasformare un piccolo 'seme' di dati opportunamente casuali in un flusso costante di numeri casuali, che consente di ottenere un numero con entropia arbitrariamente alta. L'entropia è definita solitamente come un modo per misurare la casualità, ma qui (e probabilmente in generale) è meglio vederla come un modo per misurare la sorpresa verso un avversario. Un'alta entropia significa che l'avversario sa molto poco dei numeri casuali che il genera sistema.

Dual_EC_DRBG utilizza una determinata curva ellittica. Le curve ellittiche sono dotate di una struttura supplementare, chiamata una struttura di gruppo. Ai fini di questo post, è sufficiente dire che permette di camminare lungo la curva ma, piuttosto che seguire semplicemente la forma della curva, la passeggiata apparentemente vi fa andare dappertutto. È questo "dappertutto" che le rende utili per generare numeri pseudocasuali (e per la crittografia in generale).
La struttura di gruppo su una curva ellittica. Non preoccupatevi se non ha senso.

A parte la curva, l'algoritmo utilizza anche due punti dati P e Q su questa curva. Come la curva, vengono trattati in un'appendice dello standard del NIST.

Ora esiste una relazione tra questi punti P e Q: se parti da Q e continui a camminare, poi, per alcuni grandi numeri e, dopo e passi si finisce a P. Questo non è un segreto: è una semplice proprietà della struttura di gruppo delle curve ellittiche. Ma se la curva è grande (e quella utilizzata in questo standard lo è), ci vorrà molto tempo per calcolare e. Pensate in termini di milioni di anni. Così nessuno sa e nessuno può sapere quanto sia e.

Nessuno? Beh, se si sceglie semplicemente un punto P sulla curva e si sceglie un numero e (molto grande), è possibile utilizzarlo per calcolare un punto Q. Se poi rilasci questi P e Q a qualcuno, loro avranno ancora bisogno 1 milione anni per calcolare e. Ma tu lo sai.

E questo è esattamente quello che ha fatto la NSA. Hanno fornito la P e la Q nello standard. Loro, come è diventato chiaro dai documenti di Snowden, conoscono e. Noi no. E noi non possiamo calcolarlo.

Questo ha importanza?

Lo ha. Nel 2007, Dan Shumow e Niels Ferguson, due ricercatori che lavoravano per Microsoft, hanno mostrato (pdf) che, se si conosce e, infrangere la generazione di numeri pseudocasuale diventa un po' più facile. Un po' più facile? In realtà, diventa quasi un gioco da bambini. Efficacemente, hanno mostrato che all'NSA, il tuo generatore di numeri pseudocasuali ad alta entropia, genera risultati con pochissime sorprese.

In pratica questo significa che, conoscendo e, si può leggere quasi tutto il traffico TLS crittografato (che include HTTPS) utilizzando un algoritmo basato su Dual_EC_DRBG.

Dopo che la possibile backdoor è stata trovata nel 2007, il NIST ha effettivamente aggiornato lo standard. Ora vi mostra un metodo per scegliere dei 'buoni' P e Q per conto proprio (perché non si possono scegliere dei punti arbitrari). Ma si dice ancora che se volete che la vostra crittografia sia certificata FIPS 140, è necessario scegliere i punti che hanno scelto per voi. "Fidatevi," si legge tra le righe, "sappiamo che funzionano".

Così perché qualcuno dovrebbe fidarsi di loro, soprattutto dopo che è stato dimostrato che qualcuno potrebbe probabilmente aver inserito una backdoor? Questo non sta a me dirlo. Ma lo standard è usato in un bel po' di implementazioni.

Ciò che rende ancora più strano è che, come Matthew Green ha sottolineato in un eccellente post, l'algoritmo è anche abbastanza difettoso in diversi altri modi. Non stupisce che il mondo della crittografia si trovi improvvisamente in una crisi esistenziale.

Ora sarebbe stato un male se la NSA avesse fatto in modo che qualcuno fosse riuscito a rendere più debole la crittografia che tutti noi usiamo. Tuttavia, il campo di gioco sarebbe rimasto allo stesso livello, anche se con minore sicurezza per tutti.

Sarebbe stato un po' peggio, se la NSA conosceva un algoritmo segreto che gli permette di infrangere la crittografia. (È forse una delle future rivelazioni di cui Bruce Schneier ha accennato che mostrerà cosa possono fare per alcuni standard di crittografia). Eppure, in ultima analisi, si tratta solo di battere l'avversario su chi sia il più intelligente.

Ma ciò che la NSA ha fatto è stato puro barare. La crittografia rimane sicura per tutti noi. Ma loro possono infrangerla. Perché la hanno scritta. E ci hanno messo una backdoor. E anche sapere (e lo abbiamo saputo da tempo) che ci fosse una tale backdoor, non ci serve a niente.

Barare con la privacy di miliardi di utenti Internet non è nient'altro che molto, molto sbagliato.

(A parte i post linkati del blog di Matthew Green, c'è questo pezzo su Wired sul Dual_EC_DRBG che Bruce Schneier ha scritto nel lontano 2007, quando Edward Snowden non era che un dipendente Junior della CIA che lavorava in Svizzera. Come qualsiasi cosa Schneier ha scritto sulla crittografia, ne vale la pena leggerla).

* L'NSA non l'ha mai ammesso ed è improbabile che lo farà mai. Mentre nessuno dubita che la NSA abbia inserito una backdoor nel Dual_EC_DRBG, non siamo in grado di dimostrarlo. Durante tutto il post sul blog, ho assunto siamo sicuri. È stato fatto per una lettura più facile. E, francamente, ne siamo abbastanza sicuri.

Il post in inglese sul blog di Martin: How the NSA cheated cryptography