up vote 164 down vote favorite
46

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)

share|improve this question
9  
This has been answered below, and confirmed correct by someone who has seen the code! No more speculation required. – Rory Alsop♦ Mar 18 '14 at 23:51
1  
I've noticed numerous websites say things like, "you've already used that password before." So some sites don't just compare the last one. I suppose you could call it a security measure, but I can't help but feel it's unnecessary. – rybo111 Mar 19 '14 at 8:58
    
Sort of a duplicate: security.stackexchange.com/questions/47840/password-security (since you ruled out a recently-entered password, most of the answers there don't quite apply perfectly, but some still do, and one of them is quite close to the top answer here) – apsillers Mar 23 '14 at 9:54
up vote 180 down vote accepted

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

Here is what they can do:

  1. user sets first password to "first" and fb stores hash("first").

  2. later on, users resets password and is asked to provide new password "First2"

  3. 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?

share|improve this answer
110  
This answer is how Facebook does it. Source: I've read and modified the source code for password checking. – Jeff Ferland♦ Mar 17 '14 at 21:54
10  
Why does Facebook bother? – Witness Protection ID 44583292 Mar 19 '14 at 4:10
1  
@TruthOf42 Actually, it seems to be the reverse - the hashes of similar passwords aren't stored. The only time they care about password similarity is when you're making a new password, so they hash variations on your new password, compare them to your old hash, and then throw them out if they don't match (if they do match, they warn you). – cpast Mar 19 '14 at 20:02
3  
@MichałŠrajer Currently, Facebook tests fully inverted case on login. Facebook tests fully inverted case and first letter case inversion on password change. – Jeff Ferland♦ Mar 20 '14 at 19:04
2  
But dont you need to insert yoour current passwort to change to a new password? They could just compare before making the hashsum – BlueWizard Jan 5 '16 at 21:39
up vote 20 down vote

I wouldn't know if they do (don't even use Facebook), but it's also possible that they use Hardware Security Modules (HSM) for their cryptoprocessing that don't store hashed passwords but merely reversibly encrypt them. With the volume of authorization requests they have to deal with, this would make perfect sense, as it's orders of magnitude faster than secure (read: slow) password hashing, while still offering safe password storage.

HSMs could then be programmed to compare stored and new password as an input of one of their functions and merely return result of it (could even be a boolean value in our case), with the original password never even transmitted or stored in plaintext anywhere, besides their internal memory (which is tamper resistant). This is usually referred to as an onboard secure key and application storage/processing.

By the way, many banks use HSMs because a proper implementation of it also requires physical security for the devices themselves and the way they're accessed (plus, they are rather costly), but this obviously provides a great deal more flexibility in the way passwords can be processed securely without them ever being disclosed.

share|improve this answer
2  
I doubt that. HSMs offer secure and fast crypto processing but not large storage capacities. I am not aware of any HSM, which would be able to store the passwords of all Facebook users. – mat Mar 17 '14 at 10:53
    
@user1039462 Ever heard of Tamper Resistant Secure Storage? If it's fine for DoD, why wouldn't it be for Facebook? And yes, you can have perfectly sufficient storage capacity, if you're ready to pay for it. Not all HSMs come in a form of USB keys. ;) – TildalWave Mar 17 '14 at 11:11
    
I do operate a few PCI based HSMs myself, but all of them have a storage capacity of a few hundred keys. Could you point me to an example with large storage? I'm curious. – mat Mar 17 '14 at 12:53
    
How many keys do you need? You could use a network-attached HSM and external encrypted and tamper resistant volumes. Or, for all I know, they might have built their own HSM devices with large internal volumes. Example? Oh dunno, from Luna SA to AWS CloudHSM? – TildalWave Mar 17 '14 at 13:24
up vote 15 down vote

There's only one correct answer to this. Nobody knows (except Facebook).

Facebook could store your Facebook password in plaintext, but there also might be some scheme that uses fuzzy hashes or pre-computed hashes of similar passwords.

There is really no way of knowing unless we were to break into Facebook and audit all of their assets.

share|improve this answer
3  
if you really manage to break into facebook... be kind and rewind ;) – humanityANDpeace Mar 16 '14 at 20:56
26  
Useless answer. Clearly we are looking for ways that facebook (and more importantly, our sites) can do this while still being secure. – Navin Mar 17 '14 at 2:39
22  
This answer is not really correct because, if FB is storing plaintext passwords, there could be evidence to prove that they are doing so (e.g. in the form of something being possible that would not be possible if they were not storing plaintext). I read OP's question as a question about this; in particular, does the observed behavior prove plaintext passwords are being stored? – R.. Mar 17 '14 at 4:13
up vote 7 down vote

Another possibility is that Facebook stores a hash of your password, and a hash of the SOUNDEX of your password. Then when you enter your new password, it can compare the hash of its SOUNDEX with previously stored ones and respond that a password is too similar.

This is, of course, purely conjecture.

share|improve this answer
6  
Welcome to the club, but I sure hope that's not how they do it, that'd be too easy to match with password dictionaries and narrow it down to a few possible choices per most accounts, if their database was breached. Assuming he's free to disclose it, we should really try and summon @JeffFerland to answer it. A mod here and a production engineer at Facebook, that should do it. :) – TildalWave Mar 17 '14 at 0:59
    
Plausible, since password can go through the soundex and encrypt tthe soundex variable afterwards to compare to previous encrypted soundex version. – mootmoot Apr 26 at 13:50
up vote 3 down vote

Another possibility is that fb doesn't hash, but encrypt passwords with their master key. Than they could decrypt it anytime to compare it to your new one.

  1. Let's hope not - they should hash it!
  2. As Rell3oT pointed out, no one knows except fb. So all we can do is throw wild guesses into the ring.
share|improve this answer
    
in the assumed case "facebook uses master key", would that be reasonable to assume asymmetric being used, else the system would need to have the "master key" always in memory and breaking into the server would mean also knowing the "master key" available in memory hence making the encrypted stuff rather plaintextish – humanityANDpeace Mar 16 '14 at 21:01
8  
For security purposes, this is the same thing as storing plaintext passwords. – R.. Mar 17 '14 at 4:13
    
Still often used - also I assume that (hopefully) facebook has some skilled security professionals who know this stuff. – mohrphium Mar 17 '14 at 6:40
up vote 0 down vote

Further confirmation: here's the Passwords 14 talk by Alec Muffett, describing password storage at Facebook in some detail. At the time, he worked for Facebook.

https://video.adm.ntnu.no/pres/54b660049af94

http://www.passwordresearch.com/papers/paper495.html

share|improve this answer

protected by AviD♦ Mar 17 '14 at 9:34

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.