Targeted attacks using breached credentials exploit the fact that users reuse some semantic or syntactic structure of passwords across websites to make them easy to remember. The adversary tries to log in to a victim’s account using thestolen passwords or variants of these passwords. Protecting accounts from these attacks remains challenging. Adversaries have wide-scale access to billions of stolen credentials from breach compilations, while users and identity providers remain in the dark about which accounts require attention. Our contribution is to show that it is possible to build a large-scale system that allows users to check for vulnerabilities against these attacks without sacrificing the functionality, security, and performance properties. We initiate the work by addressing the core challenge — modeling how humans choose similar passwords. We train models using modern machine learning techniques and exhibit its efficacy by simulating the most damaging attack to date. Then we formalize the security goals for existing breach checking services that warn if the exact credential is publicly exposed. In the process we also propose novel exact-checking protocols with better security guarantees. All this helps educate the design of the second-generation, similarity-aware, and privacy-preserving credential checking service — Might I get Pwned (MIGP). Finally, we collaborate with Cloudflare to deploy MIGP as part of the web application firewall to notify login servers about potential attacks.