What wrong with this system to proactively check if customers' passwords have been found in a breach?

Question

Let's say that during account creation, I already prohibit passwords known to be reused from breaches of other sites, like if it's in the Have I Been Pwned list. But breaches happen all the time, so what if my customers' passwords show up in the list later, after they've already created their account?

I'm of course storing the passwords hashed, salted, and peppered, the whole point of which is to make it intractably expensive to try lots of guesses, such as every newly leaked password. Any information I can think of to store alongside the salted hash to enable checking the newly leaked passwords would also weaken the salted hash. I could wait til they next sign-in and check against the leaked passwords list then, but how can I notify them proactively? I could force re-sign-in by expiring all current sessions, but how can I avoid inconveniencing unaffected customers (especially if that's usually 100% of them)?

What if:

1. during the sign-in process, the server generates a 160-bit cryptographically random nonce, sends it to the client, and also associates it with the session in ephemeral storage like Memcached
2. when sending the sign-in request to the server, the client hashes the password with SHA1, XORs it with the nonce, and stores the result locally while forgetting the nonce
3. when the server learns about a new breach, it pushes the nonce to the client
4. the client can then XOR the nonce with the encrypted SHA1 and check the SHA1 hash with Have I Been Pwned or whatever

Notes:

• the nonce never touches disk/durable storage, anywhere
• the customer's password never touches disk/durable storage, anywhere (nor any value from which the password can be easily extracted, e.g. unsalted SHA1)
• without the nonce, the encrypted SHA1 is useless because the XOR pad/one-time pad encryption is cryptographically perfect, so no vulnerability to XSS or compromise of the client's computer
• the server can expire the nonce after a while, and/or limit how many such nonces it keeps around per customer account, either of which render the encrypted SHA1 irreversibly useless

If my systems were completely pwned, of course, then next time the client updates it could include malicious code to combine the nonce with encrypted SHA1 and exfiltrate the cleartext SHA1 the attacker's server, but that seems like a much higher barrier than my database dumps being compromised.

One tiny way to potentially strengthen this that I can think of is that it might be possible, instead of storing the full SHA1 hash, to just store a prefix of enough bits such that the relatively small number of newly leaked passwords would collide with only very few of my customer's SHA1 prefixes, but few enough bits that it would only filter a dictionary attack down to dozens or hundreds of guesses, which is sufficiently many to not be usable on a properly ratelimited online service. I don't think this mitigation is very useful, though, even if such a number of bits existed, because it's difficult to imagine the attacker not having the Argon2-hashed password and salt, which would be very easy to crack if guesses have been narrowed to hundreds or even thousands.

Answer 1

I think what you are pursuing is quite ambitious but it is overkill. In my opinion you should simply:

• enforce a minimum level of password complexity
• add two-factor authentication (2FA) - this will make up for weak or compromised passwords
• if possible make 2FA mandatory or try to enroll as many users as possible
• devote your free time toward tightening and auditing your systems - you may have some vulnerabilities present, that could nullify all your security efforts

So the answer is not to rely on the password alone for authentication purposes.

Checking the password supplied at signup against pwnlists is a good idea. Do it offline, that is against password lists that are stored on a local drive. Do not submit the password to an online service for verification.
You can repeat this check whenever the user changes their password.

Regarding implementation of 2FA you have a number of options. It would be good to offer some choice, for example many users could be satisfied with a Google authenticator but others may more comfortable with an alternative solution.

SMS is not considered safe these days but it depends on the value of the assets you are trying to protect.

Answer 2

You don't need any of that. You already have the hashed, salted password, and you have the salt. If the service you use for leaked passwords provides you with the plaintext passwords, you can employ a "dictionary attack" against all your accounts, and see if any leaked password matches your clients.

The HIBP API service allows you to search for partial SHA-1 hashes, so you could add a field on your table to store the 5 first chars of the SHA-1 hash of the password. Periodically, you probe HIBP for the hashes and see if any of your clients got a leaked password.

I got the top 96016 password on the RockYou password dump, ran sha1sum on them. I retrieved only the first 5 chars (like HIBP API), sorted, and counted unique entries. Of that universe, I got 91753 unique values. Less than 4% were duplicates. Only one entry had 6 copies. 110 got between 3 and 6. So if this system detects that your password probably leaked, you have at least 95% chance it really leaked.