  Credential stuffing attacks use stolen passwords to log into victim accounts.
To defend against these attacks, recently deployed compromised credential
checking (C3) services provide APIs that help users and companies check whether
a username, password pair is exposed. These services however only check if the
exact password is leaked, and therefore do not mitigate credential tweaking
attacks - attempts to compromise a user account with variants of a user's
leaked passwords. Recent work has shown credential tweaking attacks can
compromise accounts quite effectively even when the credential stuffing
countermeasures are in place. We initiate work on C3 services that protect
users from credential tweaking attacks. The core underlying challenge is how to
identify passwords that are similar to their leaked passwords while preserving
honest clients' privacy and also preventing malicious clients from extracting
breach data from the service. We formalize the problem and explore ways to
measure password similarity that balance efficacy, performance, and security.
Based on this study, we design "Might I Get Pwned" (MIGP), a new kind of breach
alerting service. Our simulations show that MIGP reduces the efficacy of
state-of-the-art 1000-guess credential tweaking attacks by 94%. MIGP preserves
user privacy and limits potential exposure of sensitive breach entries. We show
that the protocol is fast, with response time close to existing C3 services. We
worked with Cloudflare to deploy MIGP in practice.
