I'm going to have to disagree with the premise that sites should stop users from choosing a password which happens to have been cracked offline at some point in the past -- to the tune of blacklisting half a billion potential secrets.

What exactly is the end goal, and at what cost? Well, there are 3 ways to steal a password. You can steal it from the user -- either by phishing or with malware -- in which case it matters not a bit how complex the password is. You could attempt to crack it online, that is, by attempting to login as the user through the front door. In this case, a simple counter should limit the number of attempts before a second factor is required, such as clicking a link in an email, and a list of half a billion candidates isn't going to help here either. Finally, you can steal the password verifier database and attempt to crack the password offline.

So, the theory must be that passwords in a known attacker's dictionary are more likely to be used as candidates in an offline attack. This is likely true. But once the verifier database is stolen, if an attacker is able to run the password hashing function, then every password which is not raw entropy already must be assumed to be cracked. Regardless of how hostile your password policy is. So what exactly is this policy saving you?

On the flip side, it's reasonable to ask, what would such a policy cost you? It's hard to say without actual data, but I'd love to see some data on what percentage of candidate passwords offered by a user trying to signup on their mobile device would be rejected under this policy? How many attempts on average would it take a user to find a password which was not rejected? And what's the increase in bounce rate, and therefore lost signups, that would result? How many increased password resets would be required from users choosing passwords that they inevitably don't remember? How many additional lock-outs which require customer support capital to resolve?

Password policies on average are pretty horrendous. But password policies which are arbitrary black boxes to the end user are about the worst you can find. Sitting on my mobile device, not knowing if a chosen password will be accepted, having to type it twice each time, is a wretched user experience which would need extremely lofty benefits to outweigh the cost. I fail to see any benefits to this approach which couldn't be solved with better hashing which wouldn't impact the user experience whatsoever.

I'll say one more thing on the idea of blacklists. Users just trivially work around them. Password quality (entropy, guessability) does not generally increase. Bad password policies often decrease password quality, particularly in the case of password expiry. But a frustrating opaque blacklist could be just as bad. (I'm not aware of any studies on this).

An attacker who knows a particular blacklist was in place will use munging rules to find derivatives from the master list which are not on the blacklist. How much will their crack rate (percentage of clears recovered from an offline attack of a given magnitude) be affected? But more importantly, potentially driving down the crack rate through user hostile password policies is a game which has huge dividends at first (getting a password which can't be attacked online) and very little dividends after that point.

Disclaimer: Founder of BlindHash, which is the "better hashing" I refer to above.