Sviluppi della crittografia

Tre ricercatori informatici della University of California hanno dimostrato l'efficacia di un nuovo protocollo crittografico, l'offuscamento indistinguibile

4754

Nel 2018, Aayush Jain, uno studente della University of California (Los Angeles), si è recato in Giappone per esporre le potenzialità di uno speciale strumento crittografico, da lui sviluppato, insieme ad altri colleghi. Tale strumento, noto come offuscamento indistinguibile (iO), ha suscitato non poche perplessità.

Se fosse possibile costruire l’offuscamento indistinguibile, esso sarebbe in grado di nascondere non solo le aggregazioni di dati, ma anche il funzionamento interno di uno stesso programma per computer, creando una sorta di strumento crittografico principale, dal quale sarebbe possibile costruire un qualunque altro protocollo crittografico. Potrebbe essere considerato come un prototipo crittografico, che detta le regole per tutti gli altri algoritmi. Ma sono ancora tanti gli scienziati informatici che nutrono delle perplessità sull’iO.

Già dal 2013, la comunità scientifica informatica ha proposto diverse versioni dell’offuscamento indistinguibile. Con il passare del tempo però, l’eccitazione generata da queste costruzioni è andata scemando, a seguito della scoperta, da parte di altri scienziati, del modo con cui violare la loro sicurezza. A un certo punto, ci si è chiesti se la vittoria sarebbe andata ai produttori o ai demolitori del protocollo crittografico.

Oggi, Jain, Huijia Lin della University of WashingtonAmit Sahai, della stessa Università di Jain, hanno dimostrato per la prima volta come costruire l’offuscamento indistinguibile utilizzando solo degli assiomi di sicurezza standard.

Tutti i protocolli crittografici si basano su degli assiomi – alcuni, tra cui l’algoritmo RSA (Rivest, Shamir, Adleman) partono dal presupposto che i computer tradizionali non saranno mai in grado di fattorizzare velocemente il prodotto di due grandi numeri primi. La sicurezza di un protocollo crittografico è legata alla sicurezza dei suoi presupposti, e le prime versioni dell’iO si basavano su assiomi non testati e poco certi. Di converso, il nuovo protocollo dipende da presupposti di sicurezza che sono stati ampiamente utilizzati e studiati nel passato.

---L'articolo continua dopo la pubblicità---

Sebbene questo protocollo sia lungi dal trovare delle applicazioni nel mondo reale, da un punto di vista puramente teorico esso fornisce una via immediata per costruire un insieme di strumenti crittografici, che in precedenza erano fuori portata. Per esempio, consente la creazione di una crittografia negabile, nella quale è possibile convincere un aggressore che è stato inviato un messaggio completamente diverso da quello effettivamente trasmesso, e di una crittografia funzionale, in cui si possono dare, a degli utenti scelti, dei differenti livelli di accesso per eseguire dei calcoli utilizzando i dati di altre macchine.

I risultati conseguiti dal team coordinato da Jain dovrebbe fugare, in maniera definitiva, ogni dubbio sull’esistenza dell’offuscamento indistinguibile.

Per decenni, gli informatici si sono chiesti se esistesse un modo sicuro e onnicomprensivo per offuscare i programmi dei computer, consentendo agli utenti di usarli senza scoprire i loro segreti interni. L’offuscamento dei programmi potrebbe avere diverse applicazioni utili: per esempio, si può utilizzare un programma offuscato per delegare delle particolari attività bancarie, o degli account di posta elettronica, ad altre persone, senza preoccuparsi che qualcuno possa utilizzare il programma in modo inappropriato o possa leggere le password degli account.

Ma finora, tutti i tentativi per costruire degli offuscatori pratici sono falliti. Gli unici che sono riusciti a vedere la luce, hanno avuto una vita media di qualche ora, contribuendo solo ad aumentare la velocità degli aggressori informatici.

---L'articolo continua dopo la pubblicità---

Nel 2001, anche l’aspetto teorico della questione è stato inibito dalla consapevolezza che è impossibile creare la forma più forte di offuscamento. Definito l’offuscamento della scatola nera, questo richiede che gli aggressori non siano in grado di apprendere assolutamente nulla sul programma, tranne ciò che possono osservare utilizzando il programma e osservando ciò che esso produce. Alcuni programmi rivelano i loro segreti così palesemente, che è impossibile offuscarli completamente.

Questi programmi, tuttavia, sono stati ideati appositamente per sfidare l’offuscamento e assomigliare poco ai programmi della vita reale. Quindi gli informatici speravano che potesse esistere qualche altro tipo di offuscamento che fosse abbastanza debole da essere realizzato e abbastanza forte da nascondere i segreti a cui gli utenti tengono particolarmente. Gli stessi ricercatori che avevano dimostrato l’impossibilità dell’esistenza dell’offuscamento della scatola nera, hanno proposto una possibile alternativa: l’offuscamento indistinguibile.

A prima vista, iO non sembra un concetto particolarmente utile. Invece di richiedere che siano nascosti i segreti di un programma, semplicemente richiede che il programma sia offuscato in modo che, disponendo di due programmi che svolgono lo stesso compito, non è possibile distinguere qual’è la versione originale del programma che genera la versione offuscata.

---L'articolo continua dopo la pubblicità---

Invece, l’iO dimostra di essere più robusto di quanto si pensi. Per esempio, si supponga di avere un programma che svolge delle attività legate a un conto bancario; questo programma contiene la password non crittografata, rendendo l’utente vulnerabile verso chiunque si impossessi del programma stesso. Quindi, fino a quando esiste qualche programma in grado di eseguire la stessa attività mantenendo la password nascosta, un offuscatore indistinguibile sarà abbastanza forte da nascondere, efficacemente, la password stessa. D’altra parte, se così non fosse, ovvero mettendo entrambi i programmi attraverso l’offuscatore, ci sarebbe la possibilità di individuare la versione originale del programma che ha generato la versione offuscata.

Nel corso degli anni, gli scienziati informatici hanno mostrato che è possibile utilizzare l’iO come base per quasi tutti i protocolli di crittografia che si possano realizzare (tranne che il protocollo di offuscamento della scatola nera). Ciò comprende sia la classiche attività crittografiche, come la crittografia a chiave pubblica (utilizzata nelle transazioni online), sia le nuove forme di crittografia, come quella omomorfica, nella quale un computer in modalità cloud può svolgere dei calcoli su dati criptati senza avere alcuna informazione sui dati stessi. Infine, vengono compresi anche i protocolli crittografici che nessuno sapeva come costruire, come i protocolli negabili o quelli funzionali.

Rafael Pass, della Cornell University, definisce questo come una specie di gioiello della corona, nel senso che una volta determinato, si può avere completamente tutto.

---L'articolo continua dopo la pubblicità---

Nel 2013, Sahai, insieme con altri 5 ricercatori, ha proposto un protocollo iO che suddivide un programma in una serie di elementi più piccoli, come le tessere di un puzzle, quindi utilizza degli oggetti crittografici, chiamati mappe multilineari, per ingarbugliare ogni singolo pezzo. Se gli elementi sono messi insieme in maniera corretta, allora l’ingarbugliamento si elimina e il programma funziona secondo le aspettative, ma ogni singolo pezzo sembra senza alcun significato. Il risultato fu visto come una svolta e ha prodotto diversi articoli di approfondimento. Ma, nel giro di qualche anno, altri ricercatori hanno dimostrato che le mappe multilineari utilizzate in questo processo di ingarbugliamento non erano abbastanza sicure. E quindi sono seguiti altri esempi di iO , anch’essi, a loro volta, superati.

La preoccupazione degli informatici era che, di fatto, non fosse possibile creare l’offuscamento indistinguibile.

Nel 2016, Huijia Lin ha iniziato a valutare se fosse possibile aggirare i punti deboli delle mappe multilineari, semplicemente chiedendone di meno. Le mappe multilineari sono essenzialmente dei modi segreti per eseguire dei calcoli con i polinomi – espressioni matematiche costituite da somme e prodotti di numeri e variabili, come 3xy +2yz^2. Queste mappe sono da considerare come una macchina per il calcolo polinomiale, connessa a un sistema di contenitori segreti che contengono i valori delle variabili. Un utente che inserisce un polinomio accettato dalla macchina può guardare all’interno di un contenitore finale per scoprire se i valori nascosti fanno sì che il polinomio venga valutato a zero.

Affinché lo schema sia sicuro, l’utente non dovrebbe conoscere nulla in merito ai contenuti dell’altro contenitore, o dei numeri che intanto sono stati generati. Finora, in tutte le possibili mappe multilineari proposte, il processo di apertura del contenitore finale ha rivelato delle informazioni sul calcolo, che si supponeva fossero nascoste.

Poiché le macchine, per generare mappe multilineari proposte avevano tutte delle criticità legate alla sicurezza, Lin si è chiesta se vi fosse un modo per costruire un iO, utilizzando delle macchine che non devono calcolare tanti tipi diversi di polinomi. Quattro anni fa, la ricercatrice ha spiegato come costruire un offuscatore indistinguibileutilizzando delle mappe multilineari che eseguono calcoli polinomiali, con un grado fino a 30 o meno (significando con ciò che ogni termine è il prodotto di almeno 30 variabili, contando le ripetizioni).  Nel corso dei due anni successivi, LinSahai, e altri ricercatori hanno compreso come abbassare il più possibile il grado del polinomio, finché non sono stati in grado di dimostrare come costruire un iO utilizzando delle mappe multilineari di grado 3.

Le uniche mappe multilineari che i ricercatori erano in grado di costruire in modo molto sicuro, erano quelle che calcolavano polinomi di grado 2 o inferiore a 2. Quindi i tre ricercatori hanno avviato uno studio per comprendere come costruire un offuscatore indistinguibile da mappe multilineari di grado 2.

Dopo un lungo tempo di inattività, i tre ricercatori, insieme a Prabhanjan Ananth della University of California, Santa Barbara e Christian Matt, del progetto blockchain Concordium, hanno formulato un’idea per una sorta di compromesso: poiché sembrava che la creazione di un iO necessitasse di mappe di grado 3, ma gli informatici disponevano di costruzioni sicure con mappe di grado 2, perchè non ipotizzare qualcosa di mezzo, per esempio una mappa di grado 2,5?

I ricercatori hanno immaginato un sistema in cui alcuni dei contenitori avesse delle finestre chiare, in modo che l’utente possa vedere i valori che vi sono contenuti. In questo modo la macchina è liberata dal dover proteggere molte informazioni nascoste. Per trovare un equilibrio tra la potenza delle mappe multilineari di grado superiore e la sicurezza delle mappe di grado 2, si permette alla macchina di lavorare con polinomi di grado superiore a 2, ma con una restrizione: il polinomio deve essere di grado 2 solo sulle variabili nascoste. La strada è quella di non nascondere troppo. I ricercatori sono riusciti a mostrare che questi sistemi di contenitori ibridi possono essere costruiti con sufficiente sicurezza.

Per passare da queste mappe multilineari meno potenti all’offuscatore indistinguibile, il team necessitava di un altro ingrediente: un nuovo tipo di generatore pseudo-casuale, qualcosa in grado di espandere una stringa di bit casuali in una stringa più lunga che sembri ancora abbastanza casuale da ingannare i computer. Ed è ciò che JainLinSahai hanno esposto nel loro nuovo articolo.

Il risultato è un protocollo iO che finalmente evita le criticità di sicurezza delle mappe multilineari.

La sicurezza dello schema si basa su quattro presupposti matematici che sono stati ampiamente utilizzati in altri contesti crittografici. Persino l’ultimo dei presupposti studiati, la parità di apprendimento con rumore fa riferimento a un problema che viene studiato fin dagli anni ’50.

Vi è solamente un oggetto che potrebbe rompere il nuovo schema: un computer quantistico, quando ne verrà costruito uno a piena potenza. Uno dei quattro presupposti è vulnerabile agli attacchi quantistici, ma recentemente, alcuni lavori di vari gruppi di ricerca, hanno fatto emergere delle linee di lavoro che offrono delle possibilità affinché l’iO possa contrastare anche un attacco di natura quantistica. Queste versioni dell’iO si basano su presupposti di sicurezza meno consolidati rispetto a quelli di JainLinSahai. Ma è possibile che, nel futuro, i due approcci vengano utilizzati in combinazione per creare una versione di iO che faccia riferimento a presupposti di sicurezza standard e che contrasti attacchi di natura quantistica.

Prima che il protocollo possa trovare applicazioni reali, serve ancora tanto lavoro per la costruzione di JainLinSahai. Ma ciò è normale per questo tipo di ricerca. Vi sono molte nozioni di crittografia che, quando sono state introdotte, venivano considerate come pura teoria e, invece, dopo 20 anni, rappresentano elementi di applicazione di colossi come Google.

Ovviamente la strada dalla teoria a un protocollo con implicazioni pratiche può essere molto lunga, ma si può immaginare che, tra 50 anni, i libri di testo sulle criptovalute riporteranno le costruzioni di iO da cui far derivare tutto il resto della crittografia.

Fonte: quantamagazine.org