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.


2 Answers 2


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.


This scheme is not secure. Let me explain why.


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.

  • Seems to be a bit of a stretch. Knowing where two hashes have local inputs does not necessarily give you enough information. The example is not the only implementation of LSH. Since some LSH just produce the same hash, not similar ones for similar inputs which there is still technically an infinitely large universe of inputs to match against. And even if you made assumptions and shortened it to a list of X character in length, unless the previous hash is stored, you can't necessarily verify your guess. Mar 4, 2014 at 8:04
  • If a hash function maps two similar inputs to the same hash I would not recommend to use this hash function for hashing passwords because the chance that an attacker can find a valid password increases. If the passwords "abcdef", "abc0ef" and "ab!def" map to the same hash all these passwords can be used to sign into an account. Using such a hash function it could be possible that weak passwords (e.g. without symbols) map to the same hash as strong passwords, e.g. passwords with symbols.
    – DanielE
    Mar 4, 2014 at 12:28
  • The hashes that are stored within this proposed schemes are kept only for password reseting to make sure the user doesn't use a like password. The original (secure) hash is not kept for logging in because the password had already expired. An attacker that could find a collision (or all of them) doesn't really have any way of verifying. Mar 4, 2014 at 16:29
  • A secure hashing scheme for passwords must use a random salt and must be slow. For example, bcrypt is well suited for this. Due to the random salt which is combinded with the password a LSH cannot produce a similar hash.
    – DanielE
    Mar 4, 2014 at 18:51
  • Wouldn't having a single salt for each user solve this issue? The LSH would not return similar hashes for different users with similar passwords, and the LSH would retain it's function for newer passwords.
    – Indy
    Apr 4, 2014 at 8:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .