I was about to reset my Facebook password and got this error:


  Your new password is too similar to your current password. Please try another password.


I assumed that Facebook stores only password hashes, but if so, how can they measure passwords similarity? This should be impossible with good hashing function, right?

Question is - how is this possible and what are the implications?

Thanks in advance. 

UPDATE

I didn't make it clear - I was not asked to provide old and new password. It was the "reset password" procedure, where I only provide a new password, so most of answers of suggested duplicate are not applicable.

UPDATE2

mystery solved - see comment (from Facebook engineer)

Let's hope and assume that Facebook stores only hashes of current password (and potentially previous passwords).

Here is what they can do:


user sets first password to "first" and fb stores hash("first").
later on, users resets password and is asked to provide new password "First2"
Facebook can generate bunch of passwords (similar to the new one): ["First2", "fIrst2", "firSt2", ... "first2", ... "first", ... ] and and then compare hash of each with the stored hash.


This is the only solution that comes to my mind. Any other?
