9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Private set intersection and Private information retrieval are relevant (though I doubt either of these has the required performance). $\endgroup$
    – CodesInChaos
    Jul 26, 2017 at 23:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Jul 26, 2017 at 23:24
  • $\begingroup$ 1. Website requests the full list of passwords (or hashes). 2. Website checks if the user's password is in that list. $\endgroup$
    – otus
    Jul 28, 2017 at 13:54
  • $\begingroup$ I'm just thinking out loud, but would a ZKP offer any benefits? $\endgroup$
    – floor cat
    Jul 28, 2017 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – dandavis
    Jul 29, 2017 at 0:54

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ You say we don't want "the password holder to learn anything about the db", but there is no such restriction in the question. $\endgroup$
    – otus
    Jul 29, 2017 at 6:40
  • 1
    $\begingroup$ Without such a restriction, send him the db. $\endgroup$
    – Meir Maor
    Jul 29, 2017 at 9:31
  • $\begingroup$ 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. $\endgroup$
    – Anon Coward
    Jul 30, 2017 at 22:02
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Your proposed solution leaks lots of information about the DB to the extent we could even efficiently reconstruct it. $\endgroup$
    – Meir Maor
    Jul 28, 2017 at 15:12
  • $\begingroup$ 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?) $\endgroup$
    – Anon Coward
    Jul 30, 2017 at 22:09
  • $\begingroup$ @MeirMaor the threat does not come from user acquiring server databse, only server learning about user. those leaked passwords corpus are usually open material. $\endgroup$
    – Sajuuk
    Aug 15, 2021 at 15:37
  • $\begingroup$ 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. $\endgroup$
    – Meir Maor
    Aug 15, 2021 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.