Websites which knows your new password is similar to your old one

[Rakanoth]

Some websites know that my new password is too similar to my old password. How do they know that?

 

1.) They are supposed to store passwords in an encrypted form. Even if a single letter is different in the new password, the encrypted form of the new password must be completely different. So, the system cannot know whether it is similar or not. So, can we say they store passwords in cleartext? If they do not store it in a clear text, how do they know the new password is too similar?

2.) I change my passwords every 6 months. Some websites know my 10 year old passwords which was changed like 546546849897321 times in the past. Do they store all the passwords in the database? How safe is that?

 

Many thanks in advance

[Neftex]

usually when you want to change password you have to confirm the change using your current one

 

other than that id also suspect plaintext passwords stored and thats obviously bad

[fizzlesticks]

4 hours ago, Rakanoth said:

1.) They are supposed to store passwords in an encrypted form.

Hashed, not encrypted.

 

Quote

So, can we say they store passwords in cleartext? If they do not store it in a clear text, how do they know the new password is too similar?

It could be encrypted, though that's almost as bad as plain text.

 

Quote

2.) I change my passwords every 6 months. Some websites know my 10 year old passwords which was changed like 546546849897321 times in the past. Do they store all the passwords in the database? How safe is that?

Yes, many website store your last X passwords so you can't reuse them. They're still hashed and if they're not your current password that shouldn't be a problem.

[vorticalbox]

On 11/24/2018 at 11:02 PM, fizzlesticks said:

It could be encrypted, though that's almost as bad as plain text.

Wouldn't it be more likely to be hashed but with either a fixed or no salt?

[Franck]

By encrypted it doesn't mean it's a one way encryption. They could be decrypting the password and compare to the unencrypted one. One way encryption or hash is stupid to compare to similarity as one way encryption there are thousands of passwords that has the same encrypted results. They most likely use reversible encryption and compare sequences. A bunch of API exist that already do that.

[reniat]

15 minutes ago, Franck said:

They most likely use reversible encryption and compare sequences. A bunch of API exist that already do that.

I'm not a security expert, but reversible encryption isn't intended to be used for the master password. The whole point of zero knowledge reversible encryption (the kind used by most (maybe all) password managers, is that the encryped blob's key is built from the master password, which itself is still secured via salted hash. If the primary password (the one being checked for similarity) is able to be decrypted, I would think that's a major problem. What would the key be to secure the encrypted master password? At that point you're likely looking at a normal reversible encryption, not a zero-knowledge reversible encryption, which is a problem.

 

The lack of "zero knowledge" means that if a malicious entity breaches that site, they can get all your data because that site will have the ability to decrypt your stuff. Zero knowledge means that even if they breach everything for that site, they still couldn't get your data without your master password, which the site does not know.

[0x21]

24 minutes ago, Franck said:

One way encryption or hash is stupid to compare to similarity as one way encryption there are thousands of passwords that has the same encrypted results.

This is simply untrue.

 

On 11/24/2018 at 6:51 PM, Rakanoth said:

How do they know that?

You create your account and set your password, the system will then store the hash of that password.

When changing your password, the system can generate similar passwords, and then compare the hash of each with the stored hash. This is how Facebook used to do it.

[Franck]

16 minutes ago, reniat said:

I'm not a security expert, but reversible encryption isn't intended to be used for the master password. The whole point of zero knowledge reversible encryption (the kind used by most (maybe all) password managers, is that the encryped blob's key is built from the master password, which itself is still secured via salted hash. If the primary password (the one being checked for similarity) is able to be decrypted, I would think that's a major problem. What would the key be to secure the encrypted master password? At that point you're likely looking at a normal reversible encryption, not a zero-knowledge reversible encryption, which is a problem.

 

The lack of "zero knowledge" means that if a malicious entity breaches that site, they can get all your data because that site will have the ability to decrypt your stuff. Zero knowledge means that even if they breach everything for that site, they still couldn't get your data without your master password, which the site does not know.

I agree, one way should be the way to go security wise. I was mentioning the vast use of reversible one. Alot of clients use such methods as they are easy to work with and API that are very easy to implement use that as default. As for hash it is not reversible perfectly. You would use other encryption like Rijndael for strength and reversibility when required.

 

9 minutes ago, mshaugh said:

This is simply untrue.

What part is untrue i don't get it ? multiple password has the same hash. Even by using prime numbers you have a loop back that make clash happen quite often when using a salt which nearly all implementation i have seen use these days. You can technically compute an infinite number of reverse password for a specific hash. Only by knowing the maximum string length allow by the system can reduce the amount of possible values.

[Mira Yurizaki]

To clarify something: When I say "encrpytion", I'm referring exclusively to two-way cryptographic functions because this appears to be the common lexical usage of the term.

 

On 11/24/2018 at 10:51 AM, Rakanoth said:

1.) They are supposed to store passwords in an encrypted form. Even if a single letter is different in the new password, the encrypted form of the new password must be completely different. So, the system cannot know whether it is similar or not. So, can we say they store passwords in cleartext? If they do not store it in a clear text, how do they know the new password is too similar?

They may be storing it in an encrypted form. The problem though is that the database still has to access the key in order to decrypt it... which has to be in plaintext.

On 11/24/2018 at 10:51 AM, Rakanoth said:

2.) I change my passwords every 6 months. Some websites know my 10 year old passwords which was changed like 546546849897321 times in the past. Do they store all the passwords in the database? How safe is that?

They would likely have to store the password somewhere, otherwise how else would it know? Is it safe? Probably not because that's more entries for someone to figure out how to crack the system and if you've used similar passwords across your accounts in the past and they know about it, then it gives attackers more things to try.

 

1 minute ago, mshaugh said:

When changing your password, the system can generate similar passwords, and then compare the hash of each with the stored hash. This is how Facebook used to do it.

If the hash doesn't change much with small changes in the input, it's unsuitable to be used as a cryptographic hash function. Suitable cryptographic hash functions should have an output that's significantly different from a very similar input in order to make it harder to figure out a pattern.

[reniat]

2 minutes ago, Franck said:

As for hash it is not reversible perfectly.

It's not reversible at all, and that's the point.

 

2 minutes ago, Franck said:

I was mentioning the vast use of reversible one

As I mentioned in my other post, reversible has uses but i'm pretty sure it fundamentally can't be used to securely encrypt the master password without being vulnerable in the event of a breach. The whole point of zero-knowledge is that the key is not known to the storage site. If you store that key on site in an encrypted form, what key encrypts THAT key? 

[Franck]

8 minutes ago, reniat said:

It's not reversible at all, and that's the point.

 

As I mentioned in my other post, reversible has uses but i'm pretty sure it fundamentally can't be used to securely encrypt the master password without being vulnerable in the event of a breach. The whole point of zero-knowledge is that the key is not known to the storage site. If you store that key on site in an encrypted form, what key encrypts THAT key? 

True, i wouldn't see why a reversible would be used in the case of a master key other than some stupid dev decided on a sketchy design. Any respectful master vaults would use non reversible. As for what encrypt the master key itself it can be done in many different ways. The system i used the most in the past was using an SSH connection and the key is encrypted on the user side using a local encryption key then it sends it to the server securely then that encrypted key is what is actually used by the server to decrypt and open the vault. The actual passwords inside are still encrypted so technically your key really only open the door. The process finish by ensuring the ssh is safe and return the password to the client and which in time reuse the original local key that was used to encrypt the key sent to the server and it decrypt the password locally. Sound complicated but very simple. I do believe the main encryption key is generated at some point by the vault server. I never actually dealt with the account encryption key creation process, i mostly worked with unlocking the vault, getting passwords, decrypting and ensuring SSH security.

[0x21]

2 hours ago, Franck said:

What part is untrue i don't get it ? multiple password has the same hash. Even by using prime numbers you have a loop back that make clash happen quite often when using a salt which nearly all implementation i have seen use these days. You can technically compute an infinite number of reverse password for a specific hash. Only by knowing the maximum string length allow by the system can reduce the amount of possible values.

Yes, it is true that hashes have collisions, but your claim that they are common isn't. The bitcoin network generates hundreds of quadrillions of these hashes a second, and to date there are no known examples of hash collisions using SHA-256,

 

2 hours ago, M.Yurizaki said:

If the hash doesn't change much with small changes in the input, it's unsuitable to be used as a cryptographic hash function. Suitable cryptographic hash functions should have an output that's significantly different from a very similar input in order to make it harder to figure out a pattern.

The system I describe is what Facebook did/does to determine whether a password is too similar.

[Franck]

1 hour ago, mshaugh said:

Yes, it is true that hashes have collisions, but your claim that they are common isn't. The bitcoin network generates hundreds of quadrillions of these hashes a second, and to date there are no known examples of hash collisions using SHA-256,

Oh that's what you meant. Now i get it. That is not the same thing. It's technically only one entity that generate the keys. But such system can check if the hash is used or not and obviously a clash in a system like this is unlikely to happen for couple millions of years. If the source of the creation of the keys are every people on the planet your hash cannot be disregarded because it already exist. It just is that value.

 

I don't know if your are a developer or not but i'll use that simple analogy which is not exactly that in real life but it explain the core of the issue. Let say Human A pick the number 12 while it's seed is 10 and Human B pick the number 6 and his seed is 16. They both have 2 differents number picked but the actual "hash" is 22 for both. Like i said those are technically irreversible as you can compute a lot of possible values. The main problem is they all loopback. If you limit is a number from 1 to 15 and the computer value 16 the container will loop back pass 15 and store the value 1. so any hash value resulting in 1, 16, 31 .etc are actually a result of 1 at the end on the computing. The final hash are all the same.

 

A good real life example is excel sheet hash password protections. No matter the password you put that was hashes it is possible the the right combination of capital "A" or "B" to get the same hash and unlock the sheet.

[0x21]

32 minutes ago, Franck said:

That is not the same thing.

What isn't?

[Neftex]

4 hours ago, Franck said:

snip

hash is consider broken when you find collision aka you can use different "password" than the original to get into someones account. sure they wont know what your password was but they didnt need it to get your stuff

 

also about your ssh thingy, were talking server breach so basically the whole ssh encrypting and sending is skipped there

the attacker gets the "key" to open the vault, its the same as if he dumped the database on website - if the content itself in the vault/db isnt secured (hashed or encrypted by different key thats not on the server) then its a problem

[vorticalbox]

18 hours ago, Franck said:

One way encryption or hash is stupid to compare to similarity as one way encryption there are thousands of passwords that has the same encrypted results.

That is not how hashing works, without using salt each password will be different but the same password will always give the same hash but if you use salt every password will be different regardless if they are the same.

 

const bcrypt = require('bcrypt')
const hashPassword = (password, saltRounds) =>{
  return new Promise((resolve, reject) =>{
    bcrypt.hash(password, saltRounds, function(err, hash) {
        err ? reject(err) : resolve((hash))
    });
  })
}
 
const plainPassword = 'hello'
const saltRounds = 10;

(async() =>{
  console.log(await hashPassword(plainPassword, saltRounds))
  console.log(await hashPassword(plainPassword, saltRounds))
})()

event though we are hashing the same passed in this case 'hello' the hashes will always be different

 

example

$2b$10$Vn7upkjk5Kq5kYOjS1ThZ.3MTd.bakQ0MJEzFM1RHXlhm.o05jN/S
$2b$10$.h1W7BEvZqCTjA.zqXTALepbQ3tA.EPbHlyJh1rv8JdZNWDS3NmPu

 

Live example

 

https://repl.it/@vorticalbox/FrugalVillainousInterfacestandard

[.Ocean]

On 11/26/2018 at 2:25 PM, mshaugh said:

The system I describe is what Facebook did/does to determine whether a password is too similar.

This simply isn't true. No self respecting intern worth their salt (see what I did there) would attempt to compare the similarity between digests to infer the similarity of the string that got you that digest. The entire point of a digest is that even a single bit change in the input will give you a unique and wildly different output. One of the core principals of hash algorithm design is that they are not predictable.

[0x21]

11 hours ago, .Ocean said:

This simply isn't true. No self respecting intern worth their salt (see what I did there) would attempt to compare the similarity between digests to infer the similarity of the string that got you that digest. The entire point of a digest is that even a single bit change in the input will give you a unique and wildly different output. One of the core principals of hash algorithm design is that they are not predictable.

Except this has been confirmed by an ex-employee of Facebook?

[kuhnertdm]

The closest thing I could think of while properly hashing and salting passwords is: Take the new password as given (unencrypted), make some arbitrary small change to it (perhaps deleting a character off the end), hash with the same salt as the old hash, and see if it matches the old hash. Have some fancy algo that does this a lot of times for different ways of making a change to it. If it matches at any point, reject. If it never matches, then use the new password.

[reniat]

3 hours ago, kuhnerdm said:

make some arbitrary small change to it (perhaps deleting a character off the end), hash with the same salt as the old hash, and see if it matches the old hash

Unless I'm misunderstanding something, I don't think this could ever work. for any string x, i'm pretty sure outside of normal collision probability (which is very very very tiny), you would never expect hash(x) == hash(x[:-1] ). Salt or no salt.

[.Ocean]

7 hours ago, mshaugh said:

Except this has been confirmed by an ex-employee of Facebook?

I would greatly like you to provide a source for this. It does not make any sense for a Cryptographic Hash function to have similar outputs for similar inputs, it just doesn't make sense. At this point I am sure there is some misunderstanding taking place and I would like to read up on the process myself so I can try to determine what is going on here.

 

While it may be true that collisions are guaranteed with hash functions (mapping infinite inputs to a finite number of outputs). The entire purpose of the design is to avoid predictability between the input and the output.

 

To drive this point home please take a look at the Avalanche Effect wikipedia page

https://en.wikipedia.org/wiki/Avalanche_effect

this is one of the main properties that all good hash algorithms will maintain and hopefully this clarifies the idea for you.

[kuhnertdm]

2 hours ago, reniat said:

Unless I'm misunderstanding something, I don't think this could ever work. for any string x, i'm pretty sure outside of normal collision probability (which is very very very tiny), you would never expect hash(x) == hash(x[:-1] ). Salt or no salt.

You're misunderstanding. Think more like: if hash(x) == hash(y[:-1]), then y[:-1] == x, and therefore, y is similar to x

[reniat]

31 minutes ago, kuhnerdm said:

You're misunderstanding. Think more like: if hash(x) == hash(y[:-1]), then y[:-1] == x, and therefore, y is similar to x

it wouldn't be similar though, it'd be exact. x == y. I'm still not entirely understanding how this allow similarity. If they give you anew password x, and you have hash(y), are you saying take x and make like 30 similar string to x, hash them all, and see if any match hash(y)?

[0x21]

3 hours ago, .Ocean said:

I would greatly like you to provide a source for this. It does not make any sense for a Cryptographic Hash function to have similar outputs for similar inputs, it just doesn't make sense. At this point I am sure there is some misunderstanding taking place and I would like to read up on the process myself so I can try to determine what is going on here.

Took some time to find again: https://security.stackexchange.com/questions/53481/does-facebook-store-plain-text-passwords#comment84577_53483

 

49 minutes ago, reniat said:

If they give you anew password x, and you have hash(y), are you saying take x and make like 30 similar string to x, hash them all, and see if any match hash(y)?

Yes. Taken from the linked answer:

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.

[kuhnertdm]

49 minutes ago, reniat said:

it wouldn't be similar though, it'd be exact. x == y. I'm still not entirely understanding how this allow similarity. If they give you anew password x, and you have hash(y), are you saying take x and make like 30 similar string to x, hash them all, and see if any match hash(y)?

Yes, that's the first thing that comes to mind for a way to check for similarity while still handling passwords securely. I'm just throwing ideas around because this doesn't 100% mean they're throwing security out the window.