Update (Feb 6): We have updated the post to clarify a protocol used in the design is centered around private set intersection.
Google helps keep your account safe from hijacking with a defense in depth strategy that spans prevention, detection, and mitigation. As part of this, we regularly reset the passwords of Google accounts affected by third-party data breaches in the event of password reuse. This strategy has helped us protect over 110 million users in the last two years alone. Without these safety measures, users would be at ten times the risk of account hijacking.
We want to help you stay safe not just on Google, but elsewhere on the web as well. This is where the new Password Checkup Chrome extension can help. Whenever you sign in to a site, Password Checkup will trigger a warning if the username and password you use is one of over 4 billion credentials that Google knows to be unsafe.
Password Checkup was designed jointly with cryptography experts at Stanford University to ensure that Google never learns your username or password, and that any breach data stays safe from wider exposure. Since Password Checkup is an early experiment, we’re sharing the technical details behind our privacy preserving protocol to be transparent about how we keep your data secure.
We designed Password Checkup with three key principles in mind:
- Alerts are actionable, not informational: We believe that an alert should provide concise and accurate security advice. For an unsafe account, that means resetting your password. While it’s possible for data breaches to expose other personal data such as a phone number or mailing address, there’s no straightforward next step to re-securing that data. That’s why we focus only on warning you about unsafe usernames and passwords.
- Privacy is at the heart of our design: Your usernames and passwords are incredibly sensitive. We designed Password Checkup with privacy-preserving technologies to never reveal this personal information to Google. We also designed Password Checkup to prevent an attacker from abusing Password Checkup to reveal unsafe usernames and passwords. Finally, all statistics reported by the extension are anonymous. These metrics include the number of lookups that surface an unsafe credential, whether an alert leads to a password change, and the web domain involved for improving site compatibility.
- Advice that avoids fatigue: We designed Password Checkup to only alert you when all of the information necessary to access your account has fallen into the hands of an attacker. We won’t bother you about outdated passwords you’ve already reset or merely weak passwords like “123456”. We only generate an alert when both your current username and password appear in a breach, as that poses the greatest risk.
Settling on an approach
At a high level, Password Checkup needs to query Google about the breach status of a username and password without revealing the information queried. At the same time, we need to ensure that no information about other unsafe usernames or passwords leaks in the process, and that brute force guessing is not an option. Password Checkup addresses all of these requirements by using multiple rounds of hashing, k-anonymity, and private set intersection with blinding.
Our approach strikes a balance between privacy, computation overhead, and network latency. While single-party private information retrieval (PIR) and 1-out-of-N oblivious transfer solve some of our requirements, the communication overhead involved for a database of over 4 billion records is presently intractable. Alternatively, k-party PIR and hardware enclaves present efficient alternatives, but they require user trust in schemes that are not widely deployed yet in practice. For k-party PIR, there is a risk of collusion; for enclaves, there is a risk of hardware vulnerabilities and side-channels.
A look under the hood
Protecting your accounts
Password Checkup is currently available as an extension for Chrome. Since this is a first version, we will continue refining it over the coming months, including improving site compatibility and username and password field detection.
This post reflects the work of a large group of Google engineers, research scientists, and others including: Niti Arora, Jacob Barrett, Borbala Benko, Alan Butler, Abhi Chaudhuri, Oxana Comanescu, Sunny Consolvo, Michael Dedrick, Kyler Emig, Mihaela Ion, Ilona Gaweda, Luca Invernizzi, Jozef Janovský, Yu Jiang, Patrick Gage Kelly, Nirdhar Khazanie, Guemmy Kim, Ben Kreuter, Valentina Lapteva, Maija Marincenko, Grzegorz Milka, Angelika Moscicki, Julia Nalven, Yuan Niu, Sarvar Patel, Tadek Pietraszek, Ganbayar Puntsagdash, Ananth Raghunathan, Juri Ranieri, Mark Risher, Masaru Sato, Karn Seth, Juho Snellman, Eduardo Tejada, Tu Tsao, Andy Wen, Kevin Yeo, Moti Yung, and Ali Zand.