Recently, I ran across a website that requires me to change my password after X number of days had passed since I had last created one. Intelligently, the service made sure that the password did not (approximately) match any others that I had used before (something that clearly did not use permutations). However, I was intrigued by how it might of have done this, since my naive understanding at the time was that they would have to store plain-text in order to calculate a distance between two strings.
Trying not to assume the worst of the website (its run by a multi-billion dollar organization, for internal-employee use), I delved a bit more into methods that have been used. The first I pondered was sub-string hash comparison (I immediately threw this out due to the possible weakening of plain-text). I thought they might do permutation-hashing (Again, threw this out because it matched approximates, and even with quite a few modifications, it appeared to do quite well).
That's when I ran across LSH as a concept. I thought it was a pretty cool idea, that allowed for some zero-knowledge-esque data comparison. That is, building a hash that has a high likelihood of matching things similiar to itself, but compresses and doesn't necessarily contain the information of the plaintext it was derived from.
Something along the lines of http://ixazon.dynip.com/~cmeclax/nilsimsa.html
773e2df0a02a319ec34a0b71d54029111da90838cbc20ecd3d2d4e18c25a3025 spam1 47182cf0802a11dec24a3b75d5042d310ca90838c9d20ecc3d610e98560a3645 spam2
The nilsimsa of these two codes is 92 on a scale of -128 to +128. That means that 36 bits are different and 220 bits the same. Any nilsimsa over 24 (which is 3 sigma) indicates that the two messages are probably not independently generated.
Is this secure, and if not, is there a secure version of said method? Thank you.