# What math makes it safe to offer a stolen-password check service?

The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to select a password that is known to have already been stolen.

HIBP is not trusted.

1. Does a way exist for a website to ask HIBP some question, and receive some result, that never allows HIBP to determine the password being inquired about (including against dictionary attacks) assuming that the password is NOT in the database.

2. Is the above possible, even if the password is in the database? e.g. can I check HIBP for existence of the string "password123", and get a result that I can understand means "yes, that exists", but which leaves HIBP with no way to know what string I queried, nor whether it was found?

This sounds like an interesting homomorphic challenge to me, but I don't know this field in depth.

• Private set intersection and Private information retrieval are relevant (though I doubt either of these has the required performance). Jul 26, 2017 at 23:22
• A downloadable bloom filter or list of truncated hashes (say 40 bit hashes) is a more realistic approach instead of an API, though it will result in some false-positives. Jul 26, 2017 at 23:24
• 1. Website requests the full list of passwords (or hashes). 2. Website checks if the user's password is in that list.
– otus
Jul 28, 2017 at 13:54
• I'm just thinking out loud, but would a ZKP offer any benefits? Jul 28, 2017 at 17:16
• the closest i can think of would be to bcrypt the pw on the client first. On the other end, you had to take all the bad passwords, shuffle the order, bcrypt them, and concat all the results into one long string. You can now literal search the big blob for the client-generated hash w/o revealing what caused a match. There might be some false-positives, but no false negatives. Jul 29, 2017 at 0:54

If we think of this as secure multi party computation then we want to calculate a function on two inputs the DB and the password. We want to know if the password exists. We don't want the db holder to learn anything about the password and the password holder to learn anything about the db beyond the answer to the question does the password exist. This is definitely solveable with generic secure multi party computation solutions. You had an extra requirement of the db holder not getting the answer to the question which I suspect may not be possible(it might be). See: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation

• You say we don't want "the password holder to learn anything about the db", but there is no such restriction in the question.
– otus
Jul 29, 2017 at 6:40
• Without such a restriction, send him the db. Jul 29, 2017 at 9:31
• A 4-billion-row proprietary database of passwords is far better not shared or revealed as best as possible [notwithstanding the impractical nature of trying to share such a big dataset itself]; I didn't say this in the question, but it is a highly desirable feature to keep it private. Jul 30, 2017 at 22:02

Not sure if your question is about implementing a solution around what exist in HIBP today or if you're asking a hypothetical, where we're able to change their API behavior. I'm going to assume the latter.

What if the client were able to send up a few sequential characters of the password at a time, and the API will return a series of numbers that represent indexes of those characters for words it found in the DB? For example, if I wanted to check for the existence of "password", I'd make a call and pass up "word". Then let's assume their DB found "password", "mypassword", and "wordless". The returned response would be {[4,5,6,7,-1],[6,7,8,9,-1],[0,1,2,3]}. The value -1 represents the end of a word.

Then I would make another call and pass up "pass" and the result would be {[0,1,2,3],[2,3,4,5]}. From those two results, I'd be able derive if my password was in the DB and the server won't know what my actual password is (but it can make a good guess). If I made the segments of my password smaller (for example just passing up two characters), it'll obfuscate my password even more. Of course using only two characters will add network and computational overhead.

• Your proposed solution leaks lots of information about the DB to the extent we could even efficiently reconstruct it. Jul 28, 2017 at 15:12
• Very interesting concept! So at a high-level; we changed the question into a bunch of smaller questions, and large answers... So the problem: how to prevent server working out the password, even if it threw it's own dictionary attack of it's own DB into the equation: I wonder if the client can encrypt it's request password using RSA, and pass the public key to the DB which the DB then uses to encrypt every single one of it's 4 billion password with; and now somehow work with these encrypted things instead (sequential partial discovery of cipherbits, with some decoys included maybe?) Jul 30, 2017 at 22:09
• @MeirMaor the threat does not come from user acquiring server databse, only server learning about user. those leaked passwords corpus are usually open material. Aug 15, 2021 at 15:37
• If the Database is not secret, it can be replecated to the system doing the check. And nothing at all is leaked by querying an external service. Aug 15, 2021 at 19:50

As far as I understand the question - you are looking for k-anonymity, don't you?

In my opinion, k-anonymity is explained best in this video: Have You Been Pwned? - Computerphile

Even if the password 'password123' exists in the database, you can use the Searching Pwned Passwords By Range API to send just the first 5 characters of the SHA-1 hash code string.

I would not trust HIBP entering passwords in clear text in a text box, but you can trust the Searching Pwned Passwords By Range API from HIBP, because of the explained method, where you don't send a password.

The server replies a list of remaining hash code characters in which you can search locally to see whether there is a match.

There is a program that may fulfills the job for you:

pwnedk

• Not returning the bytes you searched for saves a bit of transmission time. But also if an attacker could read the servers response, finding a password from a hash is impossible, and finding one from a hash with a few digits missing is even more impossible. Dec 24, 2023 at 16:54

I remember reading about this: You calculate a hash of your password, the database also has hashes of all passwords. You send a few digits of your hash, the database returns all hashes containing those digits. The number of digits is chosen so that on average maybe thousand hashes are returned. Then you check if the hash of your password is in the list.

The only thing an attacker can do is find password hashes (which should not allow finding passwords), and find out whether a known password is in the database, which shouldn’t help an attacker.