Thread by @XorNinja

How this works (from memory)

Problem:
-Client has a single pair of (username, password) that it wants to check if it was leaked.
-Server has a huge database of leaked (username, password).

https://twitter.com/laparisa/status/1179434811582058496

Security/privacy requirements:
- Server cannot learn the client's password
- Server cannot distinguish between the client's username and k-1 others, i.e., k-anonymity

To check a single password:
1. Client computes a k-bit hash of username, denote U
2. Client computes P = r * H(password), where r is a random scalar, and H(password) hashes the password to a point on NIST P-256
3. Client sends (U, P)

4. The server uses U to look up corresponding leaked passwords
5. The server generates a random scalar n. For each password_i, the server computes Q_i = n * H(password_i)
6. The server sends (n * P, Q_1, Q_2, ...)

7. The client unblinds the password by computing n * P * 1/r to retrieve n * H(password)
8. The client checks if n * H(password) is one of Q_i. If so, the password was leaked

Analysis
- Because the server only learns r * H(password), it cannot brute force for the password
- Because the server only learns k- bit of hash of username, it cannot distinguish between the client's username and k-1 others

If you found any issues, please drop me a message.

github.com/chromium/chrom… is the client-side implementation on Chrome, h/t @julianor

@julianor and of course, because Google, here's an ad: if you want to work on similar problems, please send me your resume at [e-mail]