Le primitive crittografiche sono dei componenti fondamentali per la sicurezza
di un sistema informatico. Tuttavia, le garanzie di sicurezza di queste
primitive non dipendono esclusivamente dalla loro validità formale, ma anche
dalla corretta integrazione delle stesse nelle applicazioni pratiche.
L'adozione di questi componenti è spesso complicato, a causa delle molte
insidie che possono compromettere le loro garanzie di sicurezza, come ad
esempio degli errori implementativi, gli attacchi side channel e un improprio
utilizzo della primitiva. In questa tesi, consideriamo due
problemi rilevanti che emergono nell'adozione in applicazioni reali di due
importanti primitive crittografiche: le notevoli perdite di performance
causate dall'utilizzo di primitive crittografiche che consentono di delegare la
computazione a una macchina non sicura senza compromettere la confidenzialità
dei dati coinvolti nella computazione; le vulnerabilità di sicurezza derivanti
da un'impropria validazione della struttura sintattica dei certificati digitali.
La crittografia omomorfa permette di effettuare una computazione direttamente
su dati cifrati, consentendo quindi di delegare la computazione a una macchina
non sicura mantenendo la confidenzialità dei dati coinvolti nella computazione.
Purtroppo una grossa limitazione all'utilizzo pratico di questa primitiva è la
significativa perdita di performance della computazione, che diventano
proibitive rispetto allo svolgimento dello stesso calcolo su dati non cifrati.
In questa tesi, consideriamo diverse possibili strategie per risolvere questa
importante limitazione della crittografia omomorfa. In primo luogo, valutiamo
le garanzie di sicurezza fornite da un tipo di schemi di crittografia omomorfa
caratterizzati dall'assenza di rumore, che sono di significativo interesse a
causa della loro efficienza rispetto a schemi più comuni. In particolare,
introduciamo due nuove tecniche di attacco contro schemi di crittografia
omomorfa, sfruttando le loro capacità omomorfe per amplificare l'impatto di
alcune vulnerabilità esistenti, portando così alla completa compromissione
delle garanzie di confidenzialità degli schemi vulnerabili ai nostri attacchi.
Le nostre tecniche sono efficaci contro due schemi di crittografia omomorfa
senza rumore, gli unici di questa tipologia disponibili con garanzie di
sicurezza tali da renderli utilizzabili in applicazioni reali, mostrando le
difficoltà nel progettare schemi di crittografia omomorfa senza rumore in
maniera sicura.
Data l'indisponibilità di schemi di crittografia omomorfa senza rumore che
coniugano sicurezza ed efficienza, consideriamo in questa tesi due strategie
alternative per consentire di delegare la computazione a una macchina non
sicura mantenendo la confidenzialità dei dati coinvolti senza sacrificare
l'efficienza del calcolo. Il primo approccio utilizza i cosiddetti schemi
parzialmente omomorfi, che consentono di effettuare un insieme ristretto di
calcoli su dati cifrati rispetto agli schemi di crittografia omomorfa, ma ne
migliorano notevolmente le performance; il secondo approccio basa le sue
garanzie di sicurezza su componenti hardware, come la tecnologia SGX di Intel,
che consentono di eseguire una computazione in maniera sicura su una macchina
il cui software, incluso quello di sistema, è potenzialmente compromesso da un
attaccante. In questa tesi, mostriamo l'efficacia di questi due approcci
progettando due protocolli che consentono di delegare la ricerca di
sottostringhe in un insieme di documenti memorizzato in una macchina non
sicura, garantendo la confidenzialità sia dei documenti che della sottostringa
cercata, e senza rivelare le similarità tra le diverse ricerche. Il primo
protocollo ha un ridotto consumo di banda e consente di effettuare
simultaneamente ricerche diverse da parte di più utenti, rappresentando anche
la prima soluzione che supporta la ricerca di stringhe contenenti metacaratteri
(pattern matching) senza diminuire le garanzie di confidenzialità dei dati;
il secondo protocollo ha un consumo di banda ottimale e offre anche garanzie di
correttezza del risultato della ricerca, ma attualmente non supporta né
ricerche simultanee da parte di più utenti, né le ricerche di stringhe
contenenti metacaratteri. In conclusione, entrambi i protocolli mostrano un
consumo di banda molto ridotto e dei tempi di risposta per le ricerche che
evidenziano la loro applicabilità in casi d'uso reali, sottolineando così
l'efficacia di entrambi gli approcci nel garantire la confidenzialità dei dati
coinvolti in una computazione effettuata su una macchina remota senza
introdurre delle eccessive perdite di performance.
I certificati digitali sono largamente utilizzati nei protocolli di
comunicazione sicuri al fine di garantire la corrispondenza tra una chiave
pubblica e il suo proprietario. Nonostante il ruolo fondamentale di questi
certificati nel prevenire attacchi di impersonificazione, i riconoscitori
sintattici di questi
certificati mostrano ancora una notevole mancanza di accuratezza, che è già
stata sfruttata per effettuare alcuni attacchi estremamente efficaci contro
diversi protocolli la cui sicurezza è basata sui certificati digitali. Per i
certificati X.509, utilizzati nel diffusissimo protocollo di comunicazione
sicura TLS, la generazione automatica di un riconoscitore sintattico a partire
da una grammatica formale ha dimostrato la sua efficacia nel migliorare
l'accuratezza del riconoscimento sintattico; tuttavia, la grammatica formale
utilizzata per i
certificati X.509 è estremamente complessa, e di conseguenza difficilmente
utilizzabile e manutenibile in applicazioni reali. Per risolvere questo
problema, in questa tesi proponiamo un nuovo formato per i certificati digitali
X.509. Il nostro formato, pur mantenendo la stessa capacità espressiva del
formato attuale, può essere descritto con una semplice grammatica regolare,
consentendo così la generazione automatica di un riconoscitore sintattico con
complessità computazionali minime sia in termini di tempo che di memoria. Il
nostro formato ha un preambolo che consente alle implementazioni esistenti di
identificarlo immediatamente come una versione ignota, evitando in questa
maniera di causare errori imprevedibili nelle implementazioni esistenti dovuti
al tentativo di processare un formato sconosciuto; questa possibilità è
cruciale nel consentire una graduale adozione del nostro formato
nell'infrastruttura dei certificati digitali, in quanto consente la coesistenza
tra implementazioni esistenti in grado di riconoscere solo i certificati
attuali e i nuovi certificati costruiti con il nostro formato.
Considerando i buoni risultati in termini di accuratezza mostrati nei
certificati X.509 dai riconoscitori sintattici automaticamente generati a
partire da una grammatica, in questa tesi compiamo anche un primo passo in
questa direzione per OpenPGP, il protocollo distribuito che
rappresenta la principale alternativa al sistema centralizzato di
autenticazione delle chiavi pubbliche basato sui certificati
X.509. In particolare, presentiamo un'analisi del formato dei
certificati e dei messaggi utilizzato nel protocollo OpenPGP, al
fine di determinare se è possibile generare automaticamente un riconoscitore
sintattico per questo formato. La nostra analisi mostra che il formato di
OpenPGP può essere descritto da una grammatica libera dal contesto
deterministica, da cui è possibile generare automaticamente un riconoscitore
sintattico. Tuttavia, la nostra analisi rivela anche che la grammatica che
descrive il formato ha un numero di produzioni estremamente elevato, che
rendono impraticabile il suo utilizzo in qualsiasi infrastruttura di calcolo
attualmente esistente. Di conseguenza, discutiamo in questa
tesi possibili modifiche al formato di OpenPGP che consentono di
ottenere una semplice grammatica libera dal contesto deterministica da cui è
praticabile generare automaticamente un'automa a pila deterministico in grado
di riconoscere certificati e messaggi di OpenPGP. In aggiunta,
presentiamo diversi attacchi basati su alcune falle identificate durante la
nostra analisi del formato del protocollo OpenPGP, valutando
l'efficacia di questi attacchi contro le implementazioni esistenti del
protocollo OpenPGP. La valutazione sperimentale mostra che i nostri
attacchi non sono applicabili su queste implementazioni, principalmente a causa
della bontà delle scelte degli sviluppatori, che hanno adottato la specifica
OpenPGP considerando le implicazioni delle loro scelte sulla
sicurezza dell'implementazione. Tuttavia, questo non dimostra che i nostri
attacchi siano innocui contro una generica implementazione; per questo motivo,
proponiamo anche delle modifiche alla specifica del formato di
OpenPGP che consentono di evitare gli attacchi identificati.
Cryptographic primitives are fundamental building blocks for the security of a
system. Nonetheless, the security guarantees of cryptographic primitives do not
depend only on their theoretical soundness, but also on their proper
adoption in real-world applications. This process is often challenging, as
there are many different issues that may compromise the security
guarantees of cryptographic components, such as implementation flaws,
side-channel attacks and misuses of the primitive. In this work, we focus on
two relevant challenges that arise in the adoption of two cryptographic
primitives in real-world applications: the unpractical performance overhead
exhibited by cryptographic solutions for privacy-preserving outsourced
computation; the security vulnerabilities stemming from the improper parsing
of digital certificates.
Privacy-preserving outsourced computation techniques allow to offload a
computation to an untrusted server while retaining the confidentiality of the
data involved in the computation. Fully Homomorphic Encryption (FHE) is one of
the most suitable techniques to perform privacy-preserving outsourced
computation, as it allows arbitrary computation directly on encrypted data;
nonetheless, its
adoption in real-world applications is currently hindered by its prohibitive
performance overhead. In this work, we aim at evaluating several strategies to
reduce such unpractical performance overhead exhibited by FHE
schemes. First, we investigate the security guarantees of existing noise-free
FHE schemes, which are appealing due to their
higher efficiency than common noisy FHE schemes. Our
investigations lead to the design
of two novel attack techniques against FHE schemes, which
amplify the impact of existing vulnerabilities in the target
FHE scheme by relying on its homomorphic capabilities. Our
attack completely breaks two existing noise-free
FHE schemes, hence showing the difficulty of designing a secure
noise-free FHE scheme. Given the unavailability of secure and
efficient noise-free FHE schemes, we evaluate two alternative
strategies for privacy-preserving outsourced computation: employing
Partial Homomorphic Encryption (PHE) schemes, which restrict
the set of computations that can be performed on ciphertexts to gain some
efficiency over FHE ones; relying on trusted hardware, such as
the Intel SGX technology. We show the effectiveness of these
two approaches by applying them to the design of two Privacy-Preserving
Substring Search (PPSS) protocols, which allow to outsource the look-up of
strings in outsourced documents while retaining the search and access pattern
privacy of the queries as well as the confidentiality of the outsourced
documents.
Both our solutions show an extremely low bandwidth and a practical
response time on real-world use cases, highlighting the effectiveness of our
approach in reducing the performance overhead for privacy-preserving
outsourced computation.
Digital certificates are widely employed in secure communication protocols to
ensure the authenticity of the binding between a public key and its owner.
Despite their crucial role, existing parsers for these certificates still
exhibits a significant lack of accuracy, which has already been exploited to
conduct several powerful attacks against the protocols relying on these
certificates. For X.509 digital certificates, automatically generating a
parser from a grammar
specification has already turned out to be really effective in improving the
parsing accuracy; nonetheless, the formal grammar for X.509 digital
certificates is extremely complex, and thus hardly usable in real-world
implementations. To overcome this issue, in this work we
propose a novel format for X.509 digital certificates; our format, while
retaining the same expressiveness of existing X.509 certificates, can be
described by a simple regular grammar, in turn allowing the automatic
generation of a parser exhibiting optimal time and space complexities.
In addition, given the accuracy showed by automatically generated parsers for
X.509 digital certificates, in this work we also analyze the format of
certificates and messages in the OpenPGP protocol, showing that the
OpenPGP format can be described by a deterministic context-free grammar,
from which an efficient parser can be automatically derived. Nonetheless, we
show that such grammar requires a prohibitively high number of rules and it is
thus unusable in practice. Furthermore, we outline several attacks that rely on
different flaws that we identify in our analysis of the OpenPGP
format, assessing their effectiveness against existing implementations of the
OpenPGP protocol.