> Lots of security standards require passwords to be changed every so often.

Which is almost as idiotic as storing a complete password history in plaintext, because it pretty much guarantees that passwords either (as you note) follow a simple pattern, or if that is made impossible, are written down in an easily accessible place.

A very convenient place to store and retrieve them is under a "passwords" folder in your private mail account or your Dropbox, both of which get synchronized with your unprotected smartphone...

Draconian password schemes lead to really insecure user behavior. For example, an iTunes account requires upper-case, lower-case, and a number; but it doesn't tell you that until you try "insecure" passwords. So I bet a lot of users, feeling really frustrated, just use their name (capitalized), and birthday, rather than the semi-secure password the they wanted to use (or in my case, a fairly strong pass-phrase with no numbers).

One option might be to store a hash of the password with all digits removed alongside the password used. Then once someone uses Seekrit1 as their password, you have the hash of Seekrit too, so if they try to use Seekrit2 later you can tell them not to. Could apply other normalization rules - remove repeated letters; force all lowercase; remove punctuation and digits. That way once someone's used Seekrit1, because you've hashed 'sekrit', they can no longer use seEeEe_kriT23...

This is an interesting idea, but my very naive question would be:

Even if the datastore contained only password hashes (which is good), wouldn't it be (potentially multiple) orders of magnitude easier to brute-force password attempts in the event of a large number of potential permutations to be eliminated right off the bat?

Even though bruteforcing the stripped passwords wouldn't provide a full set of information, it might be a good starting point and quickly reduce the search or guessing space.

Disclaimer: I have no idea if this is a practical concern, just one that comes to mind when thinking about your suggestion.

To some extent, you're right. Bruteforcing the password becomes a case of first bruteforcing the kernel by searching the much smaller password space of lowercase letters, then once that's matched using that kernel to generate candidates by altering case, adding digits, etc. Obviously a smart search will immediately try uppercasing the first letter, and adding a 1 to the end, and in a lot of cases that's going to be right. So yes, it does reduce the strength of your encryption against bruteforce password search, by several orders of magnitude.

This is where advances in hashing approaches might negate that problem for you, though - and you'd need a proper cryptographer to figure this out. If it was a plain MD5 or SHA of the normalized password, you're absolutely vulnerable to an attacker using a rainbow table of lowercase alphabet words figuring out the 'root' of the actual password; then they could use that to construct password candidates to hash and compare to the full password. But just adding a big block of salt to the normalized password though would take it out of the pure-lowercase searchspace and force you back to bruteforce searching of the (admittedly small) password space. However, multiround salted hashing strategies like bcrypt rule out rainbow tables and allow you to tune how expensive bruteforcing is, and even though the password space of the password kernel is limited, you may be able to turn bcrypt up high enough to make it unfeasible to bruteforce.... maybe?

I might suggest that the password pattern strings are encrypted using a key based on the user's password plus salt. This way, the password pattern list is only recoverable AFTER recovering the users password (via brute force). I think this solves the reduced search space problem of your scheme.

$a = passwO_rd1; $b = ($a striped down to lower case); $c = ($b's metaphone); $d = md5(md5($a.'salt1'.b).$c.'salt2'); $e = md5(md5($c.'salt3').$c.'salt4'); Store $d as encrypted password then store $e as a string to check against. have $e saved in a separate communal database so to brute force $e and then guess the missing characters and the right user it would be. ([missing characters]^[character set])^([password lengh] ^ [users])^2 or something along those lines

I've seen a 30 day password requirement with numeric digits circumvented simply by month + year. jun2001, jul2001, etc.

Instead of storing those pre-calculated hashes of similar strings, generate hashes on many variations of the new password and see if any match the old hash.

"Related plaintext" should not be an issue for any competent password hash (classical crypt and bcrypt are based on a block cipher, which means this should work; PBKDF2 is based on a cryptographic hash, which means this should work; etc.)

I'm not exactly sure what you're saying, but it sounds like you're saying bcrypt is reversible? It's not... it's "based on" a block encryption algorithm in the sense that it uses the encryption algorithm's key scheduling functions. Irreversibility is the intent.

bcrypt isn't reversible (with respect to the password). The point is that Blowfish(key1, "message") is not at all similar to Blowfish(key2, "message"). This is called resistance to related-key attacks (look this up for a formal definition), and is an explicit design goal of every real-world block cipher.

bcrypt is just Blowfish(key-derived-from-salt-and-password, "OrpheanBeholderScryDoubt"), so it inherits this property.

It's not reversible, but block encryption should be easy to compare for similarity. If the old password is 5 blocks, and 4 of 5 blocks match the new password (in order)... I'm guessing this is what the gp was talking about. (of course block size matters, if all passwords are a single block that doesn't help)

That's why we use a fresh salt for each password. Bcrypt incorporates a fresh salt into each new hash. Your and the GP's concern in this area is not warranted.

My personal favorite is the "at least one capital". I've taken mnemonics with a large subset of the asciibet, but I can't memorize case well. So what happens? Every password begins with one capital. "Ehsiwvky" instead of "ehsiwvky", right?

I enjoy the juxtaposition of following the letter of the rule, violating the intent of the rule, but nonetheless honoring the spirit of the rule.