La crittazione.

In genere mi metto a fare scritti “stimolati dalle richieste” quando almeno tre persone indipendentemente mi segnalano la stessa cosa. Questa volta tocca ad un articolo , questo http://it.slashdot.org/story/13/09/11/1224252/are-the-nist-standard-elliptic-curves-back-doored, il quale si mette a sospettare di questi “numeri magici” , e si arriva a concludere che siccome i fattori inseriti nell’algoritmo (in tal caso, pero’, AES e’ messa ancora peggio!) sono stati decisi da NSA , allora probabilmente NSA ha una soluzione polinomiale per quello specifico caso matematico di SEC.

Onestamente, concordo sulla parte teorica, e sono contento che la fiducia su credenze che prima tutti credevano “assodate” stiano crollando. Come ho gia’ scritto, la fiducia nelle “istituzioni over-the-top” e’ ormai crollata, e adesso sta avvenendo un processo di “challenge the assumptions”. Siamo ancora all’inizio, perche’ si sta ancora ponendo poca attenzione all’algoritmo in se’.

Anni fa lessi per motivi di lavoro un poco di letteratura riguardante i problemi ellittici inversi, e se il concetto e’ chiaro (usare un problema matematico difficilissimo da risolvere come chiave per crittografare) la sua implementazione mi lasciava perplesso. Voglio dire, ci sono formule “insospettabili” che producono effetti devastanti se provate a trovare la soluzione giusta, e come se non bastasse, potreste trovare che le soluzioni giuste sono…. infinite, e scegliere quale sia quella giusta potrebbe equivalere a provarle tutte.

Un esempio banale e’ l’ equazione di Pell.

Si tratta di una formuletta in apparenza banale, qualcosa come X^2 + n Y^2 = 1 , che (se N non e’ un quadrato perfetto) indica una quantita’ infinita di soluzioni. Questo potrebbe mettere nei guai chiunque volesse rompere un sistema di crittazione per il quale le soluzioni  siano usate come chiavi: chi attaccasse un sistema di crittazione del genere otterrebbe si’ la soluzione minima in pochi secondi, ma otterrebbe INFINITE soluzioni, che richiederebbero “molto piu’ tempo” per spaccare il codice: non conoscendo “n”, avere una chiave pubblica ,come la Xi di una della i–esima soluzione,  non permetterebbe di indovinare insieme  n ed Y.

Ovviamente si tratta di un esempio esplicativo:  la vera domanda e’ “come mai non si sta ancora mettendo in dubbio l’algoritmo in se?”. La stessa scelta degli algoritmi, se proprio vogliamo dirla tutta, e’ sempre abbastanza sospetta. E’ vero tutto quello che volete sulla complessita’ della soluzione della formula riguardante il problema ellittico, ma questo non e’ il peggior problema del mondo.

Anche se in aggiunta ci mettiamo un problema legato ai numeri primi, la domanda che sorge spontanea e’ “come mai usare un problema che ha una soluzione ancora non trovata, anziche’ usarne uno che offra infinite soluzioni per le quali rimane solo il bruteforce?” In realta’ tutti si sono concentrati molto sulla complessita’ della soluzione, anziche’ chiedersi se non fosse il caso di nascondere la soluzione in una montagna infinita di soluzioni, di cui una sola puo’ decrittare il messaggio.

La mia personale opinione e’ che siamo ancora all’inizio: una volta demolita la fiducia in alcuni coefficienti usati per la crittazione, prima o poi il crollo della fiducia riguardera’ anche gli algoritmi. Ma qui occorrera’ superare le autodifese degli accademici. Molti accademici hanno sempre taciuto , nel senso che si, hanno pubblicato molto sulla difficolta’ dell’inversa ellittica, ma nessuno ha mai alzato la manina dicendo “ehi, ma c’e’ un modo migliore, guardate qui!”. Voglio dire, sappiamo dal 1970, con Jurij Vladimirovič Matijasevič , che il decimo problema di Hilbert e’ irrisolvibile, e non esistono metodi generici per equazioni diofantee arbitrarie. DAVVERO dovete scegliere un problema ancora in sospeso per la crittazione, quando ne abbiamo (piu’ di) uno che e’ dimostrato non essere risolvibile?



Invece di usare la forza della congettura di Riemann, che e’ sotto attacco e magari prima o poi qualcuno ci arriva, perche’ non usare un problema , l’esistenza di soluzioni intere in sistemi diofantei, che e’ provato NON avere algoritmi capaci di attacco sistematico? Se io propongo una cosa del genere, immediatamente mi si risponde che la complessita’ computazionale di una equazione diofantea capace di rappresentare una classe inattaccabile di numeri e’ alta. In realta’ questo non e’ vero: partendo dalle soluzioni durante la creazione di chiavi, costruire l’equazione non e’ difficile. Ma una volta costruite le equazioni, non esiste algoritmo che possa dirvi se ci siano soluzioni intere conoscendone solo una (la chiave pubblica)(1), e questo avviene gia’ per sistemi con 9 variabili intere, (Matijasevič, 1977)  digeribilissime per un calcolatore moderno, e se proprio volete strafare, potete usarne 11 ( Zhi Wei Sun, 1992 ), che sono sempre inattaccabili, e sono sempre un inferno di incompletezza Göedeliana se affrontate come problema inverso.

Inoltre, se proprio volete usare la forza dei numeri primi, una “semplice” equazione diofantea 

k = (x+2)(y+2)

ha soluzioni in N solo quando k non e’ un numero primo, e non e’ “molto differente” da un problema di inversa ellittiva. Con questo banale esempio voglio dire che se si vuole portare a problemi di risoluzione enorme, infilarsi dentro un insieme diofanteo e’ gia’ pericoloso a sufficienza per un ficcanaso.

Se peró andiamo a scegliere una diofantea che abbia significato geometrico, come um problema ellittico, allora siamo stupidi, perché stiamo gettando al vento la nostra forza. Ed é quello che stiamo facendo oggi con i sistemi che usiamo. Di tutte le diofantee di un insieme enorme, proprio una con un senso geometrico dovevamo usare?


Il vero punto non e’ nel fatto di accettare o meno i coefficienti che vengono forniti da NSA. Per qualsiasi coefficiente voi scriviate , in generale avete  un problema di cui “non si sa ancora” se sia attaccabile. Oh, nessuno ci e’ mai riuscito ma… il futuro? Perche’ usare roba che “sinora” non e’ stata accattabile, anziche’ usare qualcosa che e’ PROVATO non essere attaccabile?



Cosi’ occorre andare indietro nel tempo, e capire come sono nati i sistemi di cifratura moderni. E scoprirete una cosa: si trattava di APPALTI del governo USA. Insomma, il governo USA se ne usciva e diceva “Ehi, il mio dipartimento per la difesa ha bisogno di un codice di cifratura difficile difficile che noi possiamo usare per i nostri scopi”: ovviamente, “per i nostri scopi” poteva comprendere SIA la segretezza delle comunicazioni, sia eventuali backdoors per accedere alle comunicazioni altrui. Tra i documenti ufficiali troviamo che si teneva in considerazione anche la facilita’ di implementazione di tali algoritmi sotto forma di circuiti elettronici, in modo da rendere piu’ economica la crittazione dentro sistemi come missili, satelliti, siluri, e quant’altro, ma di fatto e’ del tutto LEGITTIMO che tali sistemi offrano dei vantaggi ad NSA.



In definitiva, quindi, anche se il problema in gioco e’ durissimo, si tratta pur sempre di qualcosa che NSA a suo tempo ha approvato: quell’algoritmo da un lato e’ stato scelto perche’ sicuro, ma dall’altro i criteri di scelta possono essere stati relativi a qualsiasi altro parametro, compresa la facilita’ di intercettare tali cifrari se NSA avesse dovuto.



Qui, dunque, inizia il problema: si e’ mai riunito, a questo mondo, un pool di matematici DAVVERO decisi ad usare un problema di cui sia nota l’ impossibilita’ della soluzione allo scopo di produrre un cifrario? 



Il nocciolo della questione, dunque, non e’ che NSA sia capace di bucare la crittazione: il problema e’ che tutto il mondo sta usando degli standard che furono appalti di NSA allo scopo di crittare. E’ la decisione di adottare metodi di NSA a creare il problema, non il fatto che NSA possa bucarli: trattandosi di un loro appalto, di qualcosa che LORO pagavano, era assolutamente loro diritto piazzarci delle backdoor. Se IO pago per una cassaforte, voglio la chiave. Chiaro, no?



Cosi’ oggi il mondo si stupisce del fatto che, usando tutti la cassaforte della NSA, la NSA abbia una copia della chiave. Aha. Ma state usando la cassaforte che NSA ha commissionato, come potete stupirvi che NSA abbia le chiavi? VOi quando comprate una porta blindata non comprate anche la chiave, forse?



Anche qui torniamo al discorso della fiducia. Quando l’ URSS era l’ impero del male e gli USA erano “il bene”, fidarsi di loro era quasi naturale. Se il DoD, che difendeva il mondo dal MALE , aveva scelto una difesa, essa doveva essere buona per tutti. Oggi scopriamo che se URSS era “l’impero del male” magari USA non erano proprio “il bene”, e allora smettiamo di fidarci, ma allora, invece di discutere dei valori iniziali, e di “magic numbers”, dovremmo discutere dell’ingenuita’ con la quale abbiamo deciso di usare tutti il lucchetto di NSA, illudendoci che NSA non avesse un passepartout, e torniamo ancora al problema della fiducia.



Riferendomi anche alla polemica con Linus Torvalds(2), la risposta e’ la stessa: ci fidiamo o non ci fidiamo. Torvalds fa presente di non prendere SOLO dal processore  i seed per la generazione dei numeri random, se non il random di per se’, ma il punto e’ che nel mondo della virtualizzazione e del cloud non sappiamo ancora chi diavolo si occupi di RaRand o di altro. Anche ammettendo che la procedura di hashing effettivamente da’ un peso marginale al valore in questione, il punto e’ che tutto questo arriva sopra una fiducia enorme affibbiata senza porsi troppe domande. 



In definitiva, quindi, vorrei chiudere questi discorsi dicendo una cosa:

  1. La quantita’ enorme di fiducia data si sgretola pezzo per pezzo, e questo fenomeno presto si spostera’ dalle questioni marginali, come la generazione di numeri casuali , alla natura degli algoritmi in se’.
  2. Prevedo facilmente una lenta sequenza di notizie del genere e di discussioni del genere. Non so dire se questo portera’ all’unica soluzione sensata, ovvero alla definizione di un set di strumenti crittografici standard , la cui discussione avvenga “absque strepitu advocatorum”, ovvero senza che ci siano parti interessate in gioco.
Appare chiaro che gli strumenti di crittazione e la fiducia nelle autorita’ di certificazione per le comunicazioni sia stata esageratamente “statunitense” in passato, ma quello che non appare chiaro (ed e’ la ragione del vostro stupore mentre leggete queste notizie) e’ che sotto discussione non c’e’ questo o quel dettaglio della loro implementazione in se’, ma il reale processo che ha portato alla loro adozione.

Sinche’ si continuera’ a discutere di questo o quel dettaglio, di questa o quella implementazione, di questo o quel baco o di questa o quella backdoor, non si capira’ mai il problema iniziale, ovvero la fiducia mal riposta. Se non vi fidate piu’ di chi vi ha venduto la cassaforte, mantenerla in condizioni perfette non ha senso, perche’ il venditore ha una copia della chiave, se non un passepartout.

TUTTA la corrente implementazione di sistemi di crittazione viene da appalti del governo USA. L’intero stack viene da li’. Se abbiamo smesso di fidarci del governo USA, non ha nemmeno senso fidarsi degli algoritmi in se’, poiche’ magari hanno scelto proprio quello che  , volendo, potevano intercettare.
Quindi, di discussioni simili credo che se ne vedranno davvero molte.

Il vero problema e’ se porteranno a qualcosa, ovvero ad uno standard di cifratura che sia davvero discusso da tutte le parti, a livello internazionale,  e specialmente che non si limiti laddove esistono , almeno teoricamente, strade piu’ interessanti da percorrere.

 
Uriel

 
(1) Ovviamente potrebbero dedurre dal fatto che voi usiate quella chiave che essa rappresenti una parte di una delle infinite soluzioni, diciamo un valore su 9 o su 11. Ma anche cosi’, non andrebbero proprio da nessuna parte, qualsiasi quantita’ di risorse impiegassero.


(2) In questo Torvalds ha ragione. Se leggete il codice, vedete che la sorgente in questione e’ l’ultima ad essere usata, e che ogni sorgente viene XOR-ed. Cosi’, siccome XOR e’ facilmente invertibile, con un’altra XOR, chiunque possa prevedere l’ultimo strato puo’ toglierlo, ma puo’ togliere solo questo. Nella peggiore delle ipotesi, quindi, quell’ultima sorgente verrebbe cancellata, esattamente come se si togliesse il codice relativo nel kernel. Non vedo grossi problemi: lasciarla o toglierla non cambia nulla.