From theoretical to real world cryptography: towards practical privacy-preserving outsourced computation and accurate parsing of digital certificates

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.

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.