Around 2 years ago Google launched Password Checkup (related Google post), their own solution that complements Troy Hunt’s Have I been Pwned API. Both solutions have the same goal: gather and maintain a database of leaked credentials, and allow users to safely check if their current password is present in the database of leaked passwords or not. Safely here means the end-user shouldn’t be disclosing the password to any of these services, or at least not in a way where the service can go back to the password.
Troy along with Cloudflare designed a solution to preserve anonymity of the password being checked. They used k-anonymity. The scheme relies on having the leaked database hashed, in this case with SHA1, and for querying the Database the user applies SHA1 to the password, gets some bits of the output and sends that to the HIBP API to get the list of hashes that match that chunk, if any. So though the password has not been sent in plain text, you could argue that the service gained some knowledge of what the password could be. Another downside of Troy’s implementation is it’s quite easy to get the DB of SHA1 leaked passwords.
Google's approach is different, though they still use k-anonymity, they leverage state of the art homomorphic encryption to implement Private Set Intersect. I’ve been fascinated for some time with these two subjects, not that much from the math point of view but from what they enable. When they released Password checkup I tried to understand what they were doing by looking into this diagram:
I couldn’t, so I put it on my long to-do list of things to understand. One year later I was designing a product for the Company I work for, and thought Private Set Intersect could be useful. We didn’t go with this approach in the end, but it kept circling in my mind, till a few weeks ago, when I decided to really understand it. What I did was translate this diagram into a sequence diagram, my goal was not to understand the math used, but how the underlying primitives are used.
This is the final sequence diagram, I also made the UML file available here.
