Hacker News Reader

Comment by theophrastus | Hacker News Reader

And: "Must be four characters different than your last password" (this from a particular state's health insurance system). What does this mean? That four characters from the previous password must not appear in the new one at all, or only not in the same position? (fans of the little game Mastermind suffer deja-vu) What if the previous password contained all of the must have set of alternate symbols, then you've got a direct contradiction.

View on HN

I can't think of a way to do that without actually storing the plain text password. If it is in fact plain text, the irony is that by enforcing such "strong" password requirements, they've actually made the overall system less secure.

N choose 4 permutations of hashes could do it

Nah, that is only the character position sets to change, you also have to permutate the characters (which would be 2^(4*8) if we consider byte characters)

Or did I misunderstand you?

I was counting the number of hashes to store; im not sure why the size of each character would matter?

But now that Im writing it out, I was clearly wrong anyways

I thinking something along the lines of taking every substring of 4 characters, and then for all permutations of those 4-tuples, plug it back into the string hash and store. Assuming the goal is to not share any 4-substring with the new string

So I think (N-4) + 1 gives you the number of 4-character windows

4! for the number of permutations of that 4-char window

So 4!*(n-3) total hashes

Which I guess is actually the same work you'd have to do anyways if you stored the plaintext; just without storing each variant

You can permutate all possible character positions for combinations of four changed characters, and for _each_ permutation permutate all four characters and then compare the hash, and if the hash is the same you do not accept the password (even though of course you could have false positives with hashes). It is of course much slower than the change of one character which is only 256 iterations if you mutate the underlying bytes and not Unicode characters.

But I would guess they use plain text :-(

Password change dialogs generally have entries for:

    Previous Password:
    New Password:
    Confirm New Password:

They don't need to store the plaintext password, as you're giving the old password plaintext to them in the same dialog. Now, if such rules were against "any of your last 4 passwords" instead of just the last password, then that's much more difficult to do. (Obviously nobody is going to cooperate with a form requiring the person to submit their last 4 passwords as part of the password change dialog.)

Give each user a random salt. Hash each subsection of the password with their salt and store that. No need for plaintext.

Reply on news.ycombinator.com