Security and Privacy of Hash-Based Software Applications
Sécurité et protection de la vie privée des logiciels basés sur des fonctions de hachage
Résumé
Hashing and hash-based data structures are ubiquitous. Apart from their role in the
design of efficient algorithms, they particularly form the core to many sensitive software
applications. Whether it be in authentication on the Internet, integrity/identification of
files, payment using Bitcoins, web proxies, or anti-viruses, the use of hashing algorithms
might only be internal but yet very pervasive.
This dissertation studies the pitfalls of employing hashing and hash-based data structures
in software applications, with a focus on their security and privacy implications.
The mainstay of this dissertation is the security and privacy analysis of software solutions
built atop Bloom filters — a popular hash-based data structure, and Safe Browsing — a
malicious website detection tool developed by Google that uses hash functions. The software
solutions studied in this dissertation have billions of clients, which include software
developers and end users.
For Bloom filters and their privacy, we study a novel use case, where they form an
essential tool to privately query leaked databases of personal data. While for security,
we study Bloom filters in adversarial settings. The study encompasses both theory and
practice. From a theoretical standpoint, we define adversary models that capture the different
access privileges of an adversary on Bloom filters. We put the theory into practice
by identifying several security related software solutions (employing Bloom filters) that
are vulnerable to our attacks. This includes: a web crawler, a web proxy, a malware filter,
forensic tools and an intrusion detection system. Our attacks are similar to traditional
denial-of-service attacks capable of bringing the concerned infrastructures to knees.
As for Safe Browsing, we study vulnerabilities in the architecture that an adversary
can exploit. We show several attacks that can simultaneously increase traffic towards both
the Safe Browsing server and the client. Our attacks are highly feasible as they essentially
require inverting hash digests of 32 bits. We also study the privacy achieved by the service
by analyzing the possibility of re-identifying websites visited by a client. Our analysis and
experimental results show that Safe Browsing can potentially be used as a tool to track
specific classes of individuals.
This dissertation highlights the misunderstandings related to the use of hashing and
hash-based data structures in a security and privacy context. These misunderstandings
are the geneses of several malpractices that include the use of insecure hash functions,
digest truncation among others. Motivated by our findings, we further explore several
countermeasures to mitigate the ensuing security and privacy risks.
Les fonctions de hachage et les structures de données qui leur sont associées sont omniprésentes
dans le monde numérique. En dehors de leurs rôles dans la conception d’algorithmes efficaces, elles
sont aussi essentielles dans le domaine de sécurité et de protection de
la vie privée. Elles permettent de protéger les mots de passe stockés sur les serveurs d’authentification
ou protéger l’intégrité lors d’échange de fichiers. Elles sont omniprésentes
dans tous les protocoles cryptographiques comme ceux de signature électronique.
L’objective de cette thèse est d’analyser la sécurité et la protection de la vie privée des
logiciels basés sur des fonctions de hachage. Dans ce contexte, nous nous intéressons plus
particulièrement à deux applications. La première concerne les logiciels basés sur des filtres
de Bloom — une structure de données basée sur le hachage. La deuxième est le service
de “Safe Browsing”. Ce service, développé par Google, fournit une méthode sécurisée
pour naviguer sur Internet tout en détectant les sites malveillants (sites de phishing ou
malwares). Les deux applications sont très populaires, ayant des milliards d’utilisateurs.
Pour des filtres de Bloom, nous étudions un nouveau cas d’utilisation, où ils constituent
un outil essentiel pour interroger une base de données en respectant la vie privée. Nous
analysons aussi la sécurité associée aux utilisations des filtres de Bloom dans un logiciel
sensible. Notre étude aborde aussi bien les aspects théoriques que pratique. D’un point de
vue théorique, nous définissons des modèles d’adversaire qui captent les différents accès au
filtre pour un adversaire. Nous mettons la théorie en pratique en identifiant la vulnérabilité
de plusieurs logiciels basés sur des filtres de Bloom. Cela comprend: un robot web, un
proxy, un filtre de malware, les outils de forensique et un système de détection d’intrusion.
Nos attaques ressemblent aux attaques par déni de service.
En ce qui concerne le service de “Safe Browsing”, nous étudions les vulnérabilités dans
l’architecture qu’un adversaire puisse exploiter. Nous montrons plusieurs attaques qui
peuvent simultanément augmenter le trafic vers le serveur et le client. Nous étudions également
le niveau de la vie privée assuré par le service en analysant la possibilité de ré-indentifier des
visites aux certains sites web. Notre analyse et les résultats expérimentaux montrent que le
service de “Safe Browsing” pourrait être potentiellement utile comme un outil pour tracer
certaines classes des individus sur Internet.
Cette thèse met en lumière les idées fausses liées à l’utilisation de hachage et les
structures de données basées sur le hachage dans le contexte de sécurité et de protection
de la vie privée. Motivés par nos résultats, nous explorons en outre plusieurs contremesures
pour augmenter le niveau de sécurité et de protection de la vie privée.