That would only be true if it didn't keep history. Let's assume my previous two passwords are "love123" and "hate098". If I try to use a new password "love124", then the permutation checker (which, for the moment, knows the new password in plaintext) should check the hash of "love123" and reject it.

Oh. If you write a permutation checker that happens to output one of your old passwords, then yeah, that'd work. I wonder if that's feasible. It's an interesting idea. Computing hashes is relatively cheap, so I wonder if, say, 1,000 "permutation checks" would be enough.

(Although if you're using bcrypt to store passwords, which you should be, then apparently it's not so cheap.)

But.. 26 letters in the alphabet + ten digits = 36... and 36^n grows really, really fast. So maybe you'd need way more than 1k permutation checks.