190

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)

Community
  • 1
Michał Šrajer
  • 4,154
  • 4
  • 18
  • 21
  • 11
    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 08:58
  • Sort of a duplicate: http://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 09:54
  • 2
    "Does Facebook store plain-text passwords?" [Yes](https://krebsonsecurity.com/2019/03/facebook-stored-hundreds-of-millions-of-user-passwords-in-plain-text-for-years/). – Chris Mar 21 '19 at 15:48

6 Answers6

205

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?

techraf
  • 9,149
  • 11
  • 44
  • 62
Michał Šrajer
  • 4,154
  • 4
  • 18
  • 21
  • 136
    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
  • 11
    [Why does Facebook bother?](http://security.stackexchange.com/questions/53658/why-does-facebook-bother-comparing-old-and-new-passwords) – Witness Protection ID 44583292 Mar 19 '14 at 04:10
  • If hashed, they need to store (at least) two hashes, as they accept passwords as well as the password with flipped case. (KaCkE vs. kAcKe) – bot47 Mar 19 '14 at 12:31
  • I thought a good hash was supposed to make it so one is unable to gleam anything from the hash (changing one bit will change the hash completely)? – TruthOf42 Mar 19 '14 at 14:31
  • @TruthOf42 It's performing a sort of brute-force attack based around the new password, not reversing any hashes, nor comparing hashes except for testing their exact equality. – linuxhackerman Mar 19 '14 at 17:19
  • @Anonymouse I just re-read: it's making a list of passwords that are similar to the password, hashing them and keeping that resulting list. When you then create a new password, if the hash equals any of those previous ones, it says it is too similar – TruthOf42 Mar 19 '14 at 19:13
  • 2
    @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
  • @TruthOf42 what cpast says. That also makes a lot more sense in terms of storage space, don't you agree? – linuxhackerman Mar 20 '14 at 04:15
  • @Anonymouse absolutely, not to mention the fact that storing hashes of similar passwords could lead to issues if the hashing algorithm is found to have a flaw of some sort – TruthOf42 Mar 20 '14 at 13:15
  • @JeffFerland: Jeff, could you share how many similar passwords roughly you trying to guess and hash? 10? 100? 1000? I'm just curious. – Michał Šrajer Mar 20 '14 at 18:43
  • 4
    @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
  • 4
    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 05 '16 at 21:39
  • @JonasDralle That would be sufficient in most cases, but this method may be useful when trying to work out if a new password is similar to any historically-used passwords. I'm not sure if Facebook does this, however. – XtraSimplicity Oct 14 '16 at 13:33
  • @XtraSimplicity they probably don't. – BlueWizard Oct 14 '16 at 14:41
  • 1
    I just noticed Outlook providing this same message, and it was surprising since my password varied by changing the first word entirely -- not just case inversion or number/symbol variance -- but leaving the rest the same. Ex. FluffyDoggy to RambunctiousDoggy. I suspect they must also account for this sort of scenario. – emragins Dec 03 '17 at 18:14
  • Does it means that facebook uses the same salt for every password? – sluge Jan 10 '19 at 07:20
  • @sluge No, it means they generate the hashes of "First2", "fIrst2", "firSt2", ... "first2", ... "first", ... with the same salt as the old stored hash. If one of them matches, they issue an error. If none of them match, they throw them all away and hash the new password with a new salt. – zwol Oct 17 '19 at 18:13
22

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.

Community
  • 1
TildalWave
  • 10,801
  • 11
  • 46
  • 85
  • 3
    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
  • 2
    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](https://encrypted.google.com/search?q=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
18

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.

techraf
  • 9,149
  • 11
  • 44
  • 62
  • 3
    if you really manage to break into facebook... be kind and rewind ;) – humanityANDpeace Mar 16 '14 at 20:56
  • 32
    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 02:39
  • 26
    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.. GitHub STOP HELPING ICE Mar 17 '14 at 04:13
  • Please note that a former Facebook engineer (and current diamond) [confirmed](https://security.stackexchange.com/questions/53481/does-facebook-store-plain-text-passwords#comment84577_53483) that the accepted answer is actually how Facebook does this, so this really isn't correct. Also, the OP wasn't really asking how they *actually* do it - they were only asking how Facebook *could* do this. – EJoshuaS - Stand with Ukraine May 23 '19 at 19:52
7

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.

RJFalconer
  • 293
  • 1
  • 7
Ammusionist
  • 71
  • 1
  • 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](http://security.stackexchange.com/users/836/jeff-ferland) to answer it. A mod here and a production engineer at Facebook, that should do it. :) – TildalWave Mar 17 '14 at 00: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 '17 at 13:50
3

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.
mohrphium
  • 280
  • 1
  • 3
  • 9
  • 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.. GitHub STOP HELPING ICE Mar 17 '14 at 04:13
  • Still often used - also I assume that (hopefully) facebook has some skilled security professionals who know this stuff. – mohrphium Mar 17 '14 at 06:40
1

Supplying a little more detail about the password storage method itself.

The earlier historic answers predate any confirmation from Facebook. But at Passwords 14, Alec Muffett gave a talk in which he explicitly described password storage at Facebook in some detail.

In his talk, he confirms that Facebook is not storing passwords in plain text, but rather uses a multi-step method that is quite resistant to a variety of attacks:

slide from Alec Muffett talk, showing Facebook's password storage method

... as follows:

$cur  = 'plaintext'

# MD5 the plaintext.
$cur  = md5($cur)

# Hash SHA1 with a 160-bit salt.
$salt = randbytes(20)
$cur  = hmac_sha1($cur, $salt)

# Hash SHA256 with a secret salt, using an internally abstracted crypto service.
$cur  = cryptoservice::hmac($cur)
        [= hmac_sha256($cur, $secret)]

# Run the result through the scrypt KDF
$cur  = scrypt(2^14, 8, 1, $cur, $salt)

# Use SHA256 (to reduce and normalize the large scrypt result)
$cur  = hmac_sha256($cur, $salt)

This level of resistance should not be surprising, since Muffett is the author of crack, one of the first efficient password-cracking tools.

So we now have confirmation that Facebook does not store passwords in plain text.

Royce Williams
  • 9,318
  • 1
  • 32
  • 55
  • 1
    "Run the result through the scrypt KDF (using undisclosed tuning parameters)" this was answered in a follow-up question at the conference, https://youtu.be/7dPRFoKteIU?t=1093 at min 18:15. The parameters are `(2^14, 8, 1)` – sox with Monica Dec 14 '20 at 10:50
  • Good catch - updated! – Royce Williams Dec 15 '20 at 01:05
  • Any idea why FB is going through such a long and circuitous password hashing procedure? I mean, isn't one good password hash function like bcrypt/scrypt/Argon2id enough? – nobody Dec 15 '20 at 06:38
  • Some of it is historical/backwards compatibility - wrapping the previous scheme in the new scheme, etc. – Royce Williams Dec 16 '20 at 07:19