Credential stuffing attacks, where an attacker compromises a user account by trying to log in with credentials stolen from other websites, are extremely successful due to rampant password reuse across different web services by users. The problem is exacerbated by the never ending list of password data breaches in recent years. To combat the threat of compromised credentials, services like HaveIBeenPwned and Google released APIs that let users check if their passwords are present in the database of compromised credentials (those services collected for years). Privacy concerns of these APIs are paramount as users might end up exposing their (not yet leaked) passwords to the services.
In this talk, I will provide a framework for empirically analyzing the leakage of such protocols, showing that in some contexts current protocol for checking compromised credentials worsen security --- they could lead to a 12x increase in the efficacy of remote guessing attacks. I will show two new protocols we developed that provide stronger protection for users' passwords while being computationally feasible to deploy. I will end the talk with some new work on how to check for similar passwords that might be present among the compromised credentials yet, but are very much susceptible to credential tweaking attacks.pro