Skip to Main content Skip to Navigation

Security and Privacy of Hash-Based Software Applications

Amrit Kumar 1 
1 PRIVATICS - Privacy Models, Architectures and Tools for the Information Society
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services, Inria Lyon
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [171 references]  Display  Hide  Download
Contributor : Amrit Kumar Connect in order to contact the contributor
Submitted on : Friday, October 28, 2016 - 12:43:00 PM
Last modification on : Friday, March 25, 2022 - 9:42:52 AM


  • HAL Id : tel-01385488, version 2


Amrit Kumar. Security and Privacy of Hash-Based Software Applications. Computer science. Université Grenoble Alpes, 2016. English. ⟨tel-01385488v2⟩



Record views


Files downloads