Optimizing Private Information Retrieval for Compromised Credential Checking

Master Thesis

Published in 31. USENIX Security Symposium (USENIX Security'22)


Daniel Günther


Credential stuffing attacks allows an adversary to hijack an account published in a data breach. To prevent these attacks, the industry provides so-called Compromised Credential Checking (C3) tools that allow users to check if their credentials are leaked in a data breach. However, state of the art tools like HaveIBeenPwned (HIBP) and Google Password Checkup (GPC) Chrome extension (USENIX Security’19) leak a prefix of the hashed credentials of the user which is enough information to exploit a successful credential stuffing attack as shown by Li et al. (ACM CCS’19).

In this thesis, we give the first C3 protocol that achieves perfect anonymity, i.e., it leaks no information about the user’s credentials. For this protocol, we use Private Information Retrieval (PIR) that allows a client to securely query a database entry while the server learns no information about the client’s query. Since modern PIR schemes are not efficient enough for a real-world deployment, we introduce Query-Dependent Preprocessing PIR that moves (n−1)/n of the online computation to an offline phase for n ≥ 2 servers. We show that C3 with PIR is practical by implementing our query-dependent preprocessing optimizations. We measure the performance of the 2-server PIR part of our C3 protocol on a database with 2 billion entries, which results in 1.8 MB communication and 13 seconds runtime over a WAN network.




1st Prize CAST IT-Security Award 2020 Category Master Thesis