  To prevent credential stuffing attacks, industry best practice now
proactively checks if user credentials are present in known data breaches.
Recently, some web services, such as HaveIBeenPwned (HIBP) and Google Password
Checkup (GPC), have started providing APIs to check for breached passwords. We
refer to such services as compromised credential checking (C3) services. We
give the first formal description of C3 services, detailing different settings
and operational requirements, and we give relevant threat models.
  One key security requirement is the secrecy of a user's passwords that are
being checked. Current widely deployed C3 services have the user share a small
prefix of a hash computed over the user's password. We provide a framework for
empirically analyzing the leakage of such protocols, showing that in some
contexts knowing the hash prefixes leads to a 12x increase in the efficacy of
remote guessing attacks. We propose two new protocols that provide stronger
protection for users' passwords, implement them, and show experimentally that
they remain practical to deploy.
