Locality Sensitive Hash (LSH) function to approximately match old passwords

Question

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.

Answer 1

A locality-sensitive hash function by definition does not posess the avalanche effect (http://en.wikipedia.org/wiki/Avalanche_effect), which is a key property for a cryptographic hash function. The properties desirable for LSH are essentially the opposite of what is desirable for a cryptographic hash function.

Effectively, storing the locality-sensitive hash of a password is hardly any better than storing the password in the clear.

A simple method that can be used to check if a password is similar to a previous one, without deviating from the recommended practice of only storing a salted cryptographic hash of the password, is to simply use some method to enumerate a bunch of similar passwords to a given password (e.g. altering, adding or removing a letter), and then for each previous password, compute the hash of each similar password with the appropriate salt to see if it matches. If an extremely slow password hash is used, however, this method could be problematic.

Answer 2

This scheme is not secure. Let me explain why.

Salt

One important condition for a password hashing scheme to be secure is that a unique random salt is used which is combined with the password before the hash is computed. A salt is required to hash equal passwords to different hashes. This protects from attacks where a rainbow table is used. Further, an attacker cannot derive any information from the observed frequencies of the same hashes because all hashes are different. If no salt is used an attacker could try to attack the most common hashes first because these are typically very weak passwords.

Using a salt a LSH makes no sense anymore because the combination salt + password differ too much. The resulting hashes would differ too much as well.

---

Attack on LSH hashes without salt

If a LSH without a salt is used and this LSH returns similar (not equal) hashes for similar passwords I can think of one way to attack those hashes:

If an attacker wants to crack a password he could start with hashing an arbitrary password first. Then he can use the difference of the target hash and the hash of his selected password to adapt that password which he will try in the next step. He repeats this until he has found the correct password.

This is a simple optimization problem. There are some well known methods to solve optimization problems. For example, genetic algorithms could be well suited for this attack. You define the fitness function to be the number of bits which do not match and the goal is to minimize that function.

---

Possible solution

There is one possible solution I can think of. Maintain a list of the passwords that a user has used so far and encrypt this list. For encryption/decryption use an HSM (hardware security module). The keys are stored on the HSM and they cannot be accessed (e.g. read) through software. Thus, the key cannot be exposed. The only way for the attacker to get the plaintext passwords is to decrypt the ciphertexts on the hardware where the HSM is installed. You should also monitor the HSM to detect anomalies, e.g. to detect a surge in the number of decryption operations.