Costruzione di indici sicuri per la ricerca remota su dati cifrati
7
proporzioni, del mondo reale. In quest’ottica, pertanto, quando si
effettua qualsiasi tipo di operazione, così come accade per il mondo
reale, è molto importante prendere le necessarie precauzioni nel
fornire informazioni personali, onde evitarne un uso fraudolento.
Ed è proprio sulla scia di tali considerazioni che sono state
sviluppate numerose ricerche volte all’implementazione di tecniche
migliorative in campo di sicurezza, o per meglio dire atte a far
fronte a tutti i possibili attacchi che un utente collegato alla rete
possa subire.
In questo contesto si inserisce il seguente lavoro, che si propone di
affrontare il problema della ricerca remota su dati cifrati, analizzando
il protocollo detto di “Searchable Symmetic Encryption” (SSE)
[CGKO06], il quale permette ad un utente di memorizzare in
maniera privata i propri dati su un server remoto non affidabile,
mantenendo allo stesso tempo la possibilità di effettuare ricerche
selettive su di essi senza perderne la confidenzialità.
I server per la memorizzazione dei dati, quali i server mail, i file
server, dovrebbero essere pienamente affidabili, poiché contengono
informazioni private da non rivelarsi, se non dietro autorizzazione.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
8
Tuttavia, quando si ha a che fare con server non affidabili, per
garantire la confidenzialità dei dati è necessario memorizzare i file
in forma cifrata, senza rivelare al server la chiave di cifratura. Il
problema cruciale sorge nel momento in cui l’utente che ha
memorizzato i propri dati sul server, voglia prelevare tutti e solo i
documenti che contengono una determinata parola. In questo
contesto non sarà possibile la ricerca della parola direttamente sui
dati cifrati, poiché il server non affidabile non dispone della chiave
per decifrarli, per cui l’unica soluzione per l’utente è quella di
prelevare tutti i file, decifrarli in locale, ed infine effettuare su di essi
una ricerca di tipo “brute force” per stabilire quali di essi
contengono la parola richiesta. Questa soluzione, dal punto di vista
della sicurezza, è molto efficace, poiché il server non può ottenere
alcuna informazione sul contenuto dei files senza disporre della
chiave di decifratura; ma dal punto di vista dell’efficienza
computazionale i risultati non sono accettabili, soprattutto per utenti
con dispositivi mobili, che dispongono di capacità di calcolo e
larghezza di banda limitate.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
9
E’ quindi auspicabile spostare la computazione sul server; in
questo contesto, il server effettua la ricerca della parola in input
direttamente in remoto, restituendo all’utente unicamente quei
documenti che la contengono effettivamente.
Rispetto alla soluzione naive precedente, quest’ultima snellisce di
molto le risorse consumate dall’utente, ma di contro, rende più
vulnerabile ad attacchi i documenti contenuti sul server. Per ovviare
al problema, una buona soluzione, che fornisce un buon
compromesso tra efficienza e sicurezza, è la progettazione di indici
sicuri associati ad ogni documento che viene memorizzato sul
server. Con l’utilizzo degli indici, la ricerca non viene più effettuata
sul documento cifrato, ma direttamente sull’indice ad esso associato,
che ha una particolare struttura che permette la ricerca della parola
in modo efficiente, senza che il server venga a conoscenza di alcuna
informazione sul testo in chiaro.
L’obiettivo di questa tesi è, dunque, lo sviluppo di un protocollo
che permetta la creazione di indici sicuri per la ricerca su dati cifrati
memorizzati su un server remoto non affidabile, senza la fuoriuscita di
informazioni verso il server stesso.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
10
Per la stesura del seguente lavoro, in primo luogo, si sono
analizzati i risultati di alcuni studi che, negli ultimi anni, hanno
affrontato il problema della ricerca sicura su dati cifrati memorizzati
in remoto [SWP00], [KO97], [CM04], [BCOP03] valutando le
prestazioni ed il livello di sicurezza delle soluzioni proposte; in
secondo luogo si è cercato di unificare il contributo fornito dai
diversi autori, in particolare attingendo a quello di Eu-Jin Goh,
dell’Università di Stanford [GO04], che affronta il problema della
costruzione di indici sicuri utilizzando i Bloom Filters [B70], una
particolare struttura dati, molto utile per testare l’appartenenza di
un elemento ad un determinato insieme.
Dopo una prima fase di analisi dei vari lavori, è stata sviluppata
un’applicazione in linguaggio JAVA che fornisce tutte le
funzionalità richieste dal protocollo SSE. L’applicazione in
questione, su cui sono stati effettuati diversi test per valutarne le
prestazioni, è un Web Service basato sul processore SOAP Axis e
sul DBMS MySQL come sito di memorizzazione dei dati.
Le suddette considerazioni pratiche e teoriche confluiscono nel
seguente elaborato, strutturato in quattro capitoli.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
11
Nel Capitolo 1 viene definito il concetto di ricerca remota e di
Searchable Symmetric Encryption e, vengono passati in rassegna
alcuni studi volti alla progettazione di un protocollo efficiente e
sicuro per la ricerca remota su dati cifrati, effettuando alcuni
paragoni tra essi per stabilire quale sia quello che garantisce il
miglior rapporto tra efficienza e sicurezza.
Nel Capitolo 2 viene posta particolare attenzione alla tecnica di
progettazione di indici sicuri proposta in [GO04]; sono inoltre
definiti ed analizzati i Bloom Filters, per mostrare la loro utilità al
fine della ricerca remota su dati cifrati.
Per poter valutare, a livello pratico, l’effettiva validità del suddetto
protocollo, diviene ora necessario sviluppare un progetto software
che abbia tutte le funzionalità richeste. Tuttavia, prima di passare
alla descrizione del progetto software, è molto importante
descrivere quali sono gli strumenti utilizzati per il suo sviluppo
dando, in particolar modo, grande risalto al processore di messaggi
SOAP Axis, la cui architettura è discussa esaustivamente nel
Capitolo 3, insieme ad informazioni generali sui Web services,
Costruzione di indici sicuri per la ricerca remota su dati cifrati
12
sull’architettura di una SOA, sul Database Management System
MySQL e sull’ambiente in cui il progetto è stato sviluppato.
Il Capitolo 4 contiene la descrizione dettagliata dell’applicazione e
del suo funzionamento. Si passano in rassegna tutte le classi JAVA
sviluppate, sia lato client che lato server, e si mostra come installare
e configurare correttamente l’applicazione e i relativi pacchetti
software necessari al suo funzionamento.
Si è così potuto stabilire, grazie ad una serie di test effettuati
sull’applicazione modificando i parametri per la creazione degli
indici, qual è la configurazione ottimale con cui il protocollo opera.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
13
Capitolo 1
Ricerca Remota e lavori correlati
Costruzione di indici sicuri per la ricerca remota su dati cifrati
14
1. Ricerca remota e lavori correlati
In questo capitolo viene definito il concetto di ricerca remota su
dati cifrati, considerando i possibili scenari in cui essa è applicabile.
Vengono, in seguito, passati in rassegna e confrontati, diversi studi
effettuati sull’argomento, valutando, per ognuno di essi, le
prestazioni ed il livello di sicurezza ottenuti.
1.1 Ricerca remota su dati cifrati
Si può definire il problema della ricerca remota su dati cifrati
descrivendo un suo possibile scenario di applicazione: sia U un
utente che dispone di un dispositivo mobile come un PDA, e sia S
un file server remoto. L’utente U potrebbe voler memorizzare sul
server S alcuni documenti personali contenenti informazioni
strettamente confidenziali, in modo tale da non avere la necessità di
trasportare sempre con sé una grande quantità di dati. Dal momento
che le informazioni contenute nei documenti sono strettamente
confidenziali, U auspica che nessuno, eccetto egli stesso, possa
venirne a conoscenza, per cui memorizza sul server remoto i
Costruzione di indici sicuri per la ricerca remota su dati cifrati
15
documenti dopo averli opportunamente cifrati, così da essere
l’unico a conoscere la chiave per la decifratura.
In un secondo momento, U vuole effettuare una ricerca basata su
una particolare parola chiave, in modo tale da recuperare
unicamente quei file che contengono la parola chiave ricercata,
limitando il dispendio di banda
1
.
Tuttavia, questa ricerca di parole chiave non è possibile nella
pratica quando i files su S sono stati cifrati ed S non conosce la
chiave per la decifratura; l’unica soluzione è quella di rivelare ad S
la chiave, consentendo al server di effettuare la ricerca in remoto, ma
perdendo la confidenzialità dei dati. A tal riguardo, una soluzione
che risolve il problema della conservazione della privacy consiste
nel non fornire la chiave al server, ma scaricare tutti i file in esso
contenuti per poi decifrarli in locale ed effettuare la ricerca della
parola sui file decifrati. La suddetta soluzione non è, però,
accettabile per utenti con dispositivi mobili con larghezza di banda e
spazio di memorizzazione limitati
2
.
1
Si tratta di un obiettivo imprescindibile quando l’utente effettua le query di ricerca tramite un
dispositivo mobile con risorse limitate.
2
Molto spesso, i dispositivi mobili come i palmari o gli smartphone di nuova generazione non
dispongono di un’elevata capacità di calcolo né di un elevato spazio per la memorizzazione dei dati, per
cui un utente non può trasportare con sé una elevata quantità di dati; inoltre, a causa degli elevati costi
Costruzione di indici sicuri per la ricerca remota su dati cifrati
16
Un ulteriore aspetto da tenere in grande considerazione per
garantire la confidenzialità dei dati, è che l’utente, legittimamente,
non vuole in alcun modo che la parola ricercata sia nota al server,
per cui è importante prevedere un metodo per “mascherare” la
parola chiave al server, mantenendo però inalterata la sua capacità
di effettuare ricerche selettive.
Dalle precedenti considerazioni consegue che il problema della
creazione di uno schema sicuro ed efficiente per la ricerca in remoto
su dati cifrati non è banale e di immediata soluzione come potrebbe
apparire ad una prima analisi, in special modo quando si devono
soddisfare le esigenze di utenti con dispositivi mobili.
A tal proposito, l’esigenza di riuscire a creare protocolli di ricerca
che risolvano il problema, ha spinto molti ricercatori ad
intraprendere sull’argomento studi approfonditi, alcuni dei quali
saranno analizzati nei paragrafi successivi, valutandone anche i
risultati per stabilirne gli aspetti positivi e negativi.
di connessione per la trasmissione dati richiesti dai gestori di telefonia mobile, scaricare l’intero set di
documenti contenuti nel database risulta altamente sconveniente per l’utente.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
17
1.2 Private Information Retrieval
Uno dei primi sostanziali contributi alla risoluzione del problema
lo si deve a Kushilevitz e Ostrovsky [KO97], che, per primi, hanno
sviluppato uno schema PIR, acronimo di Private Information
Retrieval.
Si intende, per PIR, uno schema che permette ad un utente di
recuperare informazioni cifrate da un database, mantenendo
nascoste, allo stesso tempo, le query all’amministratore del
database.
Più formalmente, il database è modellato come una stringa x di n
bit, di cui l’utente recupera l’i-esimo bit x
i
, senza fornire al database
alcuna informazione sull’indice i. Il sistema più banale e immediato,
ma altamente inefficiente, per ottenere uno schema PIR, è l’invio
all’utente, da parte del server, dell’intera copia del database.
La prima definizione di schema PIR, sul piano puramente teorico,
la si deve a Chor, Guldreich, Kushilevitz e Sudan [CGKS95].
Costruzione di indici sicuri per la ricerca remota su dati cifrati
18
La suddetta configurazione PIR teorica conduce a due risultati:
• Ogni schema PIR su un singolo database, necessita di Ω(n) bit
per la comunicazione tra utente e database
3
.
• Per ovviare alla precedente limitazione, ed ottenere una
complessità sub-lineare nella dimensione n del database, si
assume che i dati siano replicati su più database non
cooperanti tra loro, che, per tale ragione, non possono
scambiarsi informazioni sui contenuti.
Tali conclusioni indurrebbero a pensare che replicare i dati sia
essenziale per ottenere uno schema PIR, ma Kushilevitz e
Ostrovsky, partendo dalla definizione di schema cPIR, acronimo di
computationally Private Information Retrieval, dimostrano che la
replicazione dei dati non è necessaria e che uno schema cPIR può
essere costruito anche su un database singolo.
La definizione di schema cPIR è introdotta da Chor e Gilboa
[CG97]; questo tipo di schema impone ai database l’esecuzione di
sole computazioni di tempo polinomiale, e la privacy delle query
3
Corrisponde, praticamente, al limite superiore della soluzione “banale”, ovvero quella in cui l’utente
richiede un’intera copia del database per nascondere al server il bit a cui è realmente interessato.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
19
dell’utente viene rilassata, in modo che l’indice i è nascosto solo
computazionalmente al database
4
.
Il limite superiore ottenuto da questo schema è di gran lunga
migliore rispetto ai limiti superiori offerti dai classici schemi PIR;
tuttavia anche per questo schema è necessario che i dati siano
replicati su più database non comunicanti.
Lo studio effettuato da Kushilevitz ed Ostrovsky va in
controtendenza rispetto alla precedente assunzione; essi riescono a
dimostrare che è possibile sviluppare uno schema cPIR utilizzando
un singolo database.
Il risultato principale ottenuto è il seguente:
per ogni c > 0, esiste sempre uno schema cPIR a database singolo con
complessità di comunicazione O(n
c
), assumendo l’intrattabilita del
problema dei quadrati residui.
Il valore del risultato ottenuto è, dunque, basato su un’assunzione
di intrattabilità del problema dei quadrati residui [GM84],
presentato da Goldwasser e Micali.
4
Il server non riuscirà a scoprire l’indice i, poiché, per ottenere questo risultato, necessiterà di
computazioni sub‐lineari; ma poiché lo schema cPIR gli impone esclusivamente computazioni
polinomiali, il server non avrà le risorse necessarie per svelare l’indice.
Costruzione di indici sicuri per la ricerca remota su dati cifrati
20
Il suddetto problema si basa sulla definizione di residuo
quadratico; un numero q si definisce residuo quadratico modulo n
se esiste un intero x tale che:
ݔ
ଶ
ؠ ݍ ݉݀ ݊
Un residuo quadratico modulo n è un numero che ha una radice
quadrata in aritmetica modulare, quando il modulo è n.
La forza dello schema proposto risiede proprio nell’intrattabilità
del problema; difatti, il problema di trovare una radice quadrata in
matematica modulare, risulta di difficile soluzione. Il problema
risulta essere NP-Completo se si cerca di stabilire se esiste una
soluzione per x minore di un certo limite c.
1.3 Searchable Symmetric Encryption
Il protocollo SSE, acronimo di Searchable Symmetric Encryption,
permette a client con risorse limitate di memorizzare a basso costo,
in remoto, un’elevata quantità di dati cifrati utilizzando algoritmi a
chiave simmetrica
5
.
5
Si definisce, per algoritmo di cifratura a chiave simmetrica, un algoritmo che permette la cifratura e la
decifratura di un file utilizzando una singola chiave.