When someone uses a password, it proves that it is not very "unique"; just being used once either proves it was already low-entropy, or makes it lower-entropy (because the user could have it written down, the system that accepted it might store it in the clear, etc). So no one, anywhere, ever, should be allowed to create an account with that password again.
How to you prevent a password from every being used again? Simple, create a public, universal blacklist for passwords. This one stroke, by itself, forces users to invent ever-more-entropy-laden passwords as time passes.
Of course, you need to do it securely. Which is the rest of this blog post.
Part 1:
My first thought (from a few years ago) is that when passwords are replaced (invalidated) in anyone's system, those passwords should be published, totally publicly.
When you change your password, you always have to enter your old password, and the new password. Also, when you delete an account, you usually have to enter your old password to do it. Either way, this transaction includes a "delete this password" component.
Some systems would automatically store this as a local blacklist of some kind, maybe just in the hashed form; but as far as I know, no one has tried to share these blacklists with other companies, and certainly no one publishes them to the world, which is basically what I am proposing.
If you're on board with black-listing these passwords from your system forever, why not publish them? They're no good anymore, so you could even store these now-obsolete password in the clear! (there are actually potential down-sides to storing in the clear, but since I remove this below, I won't go into them)
So send the now-blacklisted password to a giant repository in-the-sky (cloud). Get a bunch of companies to adopt this common system, and you are on your way to creating a Universal Password Blacklist. You could have a bunch of separate services implement this independently, and source extra black-listed values from each other, in any way that each one finds acceptable.
You end up with a distributed database, kindof block-chain style, but where it may be perfectly acceptable that some databases never end up agreeing with each other.
Part 2:
The "blacklist" part would necessitate checking if a new password is pre-existing. And this would always require a server-side check -- because no client-side system is going to download a terabyte of passwords just to create a new account, that'd be ka-razy. So you need a secure way to check if your new password exists in this Universal Password Blacklist. Luckily, we know how to do that.
1) Adopt a "cryptographic hash" that everyone is happy with
2) Run you tentative new password through this hash
3) Call new-service, to check if this hashed-value exists in their database of passwords
If it exists, it's a no-go, you need to input a better password. If it doesn't exist, go ahead and create the account.
Bonus: No Part 1 Necessary!
Alert security-wonks may have realized that this "read" can also function as a "write", So in Part 2, the "read" to check if that hashed value exists, can be implemented as a "write", like a SQL "insert". If the value already exists, you get a "duplicate key error", and you return to the caller that they should not allow the password that translated into this hashed value. If it did not exist, you successfully write it to the Universal Password Blacklist, and return to the client that this password has never been used before.
Side Note:
This hash should be used only for this system. That is, if someone else used exactly the same process for their internal password-storage, then everyone could "brute-force" attack the hashed values, and reverse it to find original passwords. Ideally this is still very difficult, but there is no reason to not add your own salt-and-pepper-hash to your system, that is distinct from the one adopted for the Universal Password Blacklist, and then this problem is non-existent.
Extra Risk & Mitigation
Risk: The only real reason I can think of to not accept random inputs from all-comers is if you're worried about DOS-style flooding. Imagine someone hates security, so they just flood you with random "passwords", and you have to just soak up all this data and store it permanently, which is a burden that gives no benefit.
Migitation: I think you could force a client to solve a "hard" problem (burn a number of CPU cycles) per use. This should give a sufficient disincentive to fill your system with noise.
Thoughts?
