Daniel Günther, researcher at the ENCRYPTO group at TU Darmstadt, with his work on “Optimizing Private Information Retrieval for Compromised Credential Checking” won the first prize among four finalists in the category “Best Master Thesis” at the CAST IT Security Award 2020.
CAST e.V. awards these prizes for outstanding theses by young IT security researchers. Nominated works contain innovative ideas, interesting results, novel views, and directions for current and relevant topics in IT security.
Abstract of the Master Thesis
Credential stuffing attacks allow 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 have been leaked in a data breach. State of the art tools like Google Password Checkup which is now integrated in the Chrome browser (USENIX Security’19) leak a prefix of the hashed credentials of the user.
However, it was shown by Li et al. (ACM CCS’19) that this information alone is sufficient for mounting a credential stuffing attack which would compromise a large fraction of the users. In this thesis, we build 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 from n ≥ 2 non-colluding servers, which learn no information about the client’s query. Since modern PIR schemes are not efficient enough yet for fast online responses at this scale, we introduce Per-Query Preprocessing (PQP) PIR that moves n−1n of the online computation to a local precomputation phase.
We show that C3 with PIR is practical by implementing our PQP-RAID-PIR scheme, whose security and online performance improve linearly with the number of servers n. For n=2 servers, which is our lowest improvement, our PQP-RAID-PIR implementation outperforms the original implementation of RAID-PIR (ACM CCSW’14) by factor 7.7× and our re-implementation of RAID-PIR using the same codebase by exactly the theoretically expected factor of 2×. We measure the performance of our C3 protocol with a database of 5 billion entries resulting in 580ms online runtime over a WAN network with n=2 servers, and 397 ms with n=5 servers.
CV of Daniel Günther
Daniel Günther, M.Sc., studied Computer Science (bachelor) and IT security (master) at TU Darmstadt, works as doctoral researcher at Cryptography and Privacy Engineering Group (ENCRYPTO) at TU Darmstadt since 2019. Research focuses on design, implementation and evaluation of secure and private multi-party computation protocols. Interest in network security, privacy preserving protocols and cryptography.