[Password Leak] LinkedIn database hacked

[zhoutong]

is there only one unique string (password) that corresponds to a given hash?

Theoretically there are are infinite number of inputs that will result in the same hash because the hash function outputs a fixed-length value but the input can be any length.

Yes, thank you. Now, is this statement still true when a typical password is shorter than the 32-byte hash? 

For MD5: http://stackoverflow.com/a/2000014

Alright, does this mean that if my password is a reasonably random string, and the unsalted hash is made public, it may be possible to "reverse" it, but it won't be possible to tell for sure that that was the actual password - there could be another string with the same hash out there.

Also, does this mean that you could still type in a "wrong" password (that hashes into the proper hash), and you would be able to log in just fine, since server is ultimately comparing hashes?

Sorry for silly questions, I'm not versed in this topic but I want to understand the implications of these kinds of leaks.

It's almost impossible for passwords with readonable length. But yes, the server will accept anything if the hash matches.

You may want to read this: http://en.wikipedia.org/wiki/Birthday_problem

[Raoul Duke]

LastPass has your encrypted passwords. They don't, however, have the decryption key.

Will you put your ass on the line to defend that statement as an absolute truth?

[TangibleCryptography]

Alright, does this mean that if my password is a reasonably random string, and the unsalted hash is made public, it may be possible to "reverse" it, but it won't be possible to tell for sure that that was the actual password - there could be another string with the same hash out there.

Also, does this mean that you could still type in a "wrong" password (that hashes into the proper hash), and you would be able to log in just fine, since server is ultimately comparing hashes?

Sorry for silly questions, I'm not versed in this topic but I want to understand the implications of these kinds of leaks.

Yes.  The server never knows the password it only knows the hash. It hashes the password provided and compares it to the hash it has stored.  If they match it logs you in.  

So hypothetically if

"This is my password"  and "86f7e437faa5a7fce15d1ddcb9eaeaea377667b8"
both hash to "eee411109a229046154bc9d75265a9ccb23a3a9c" then the server would let you login with either.

This is why hashes need to be reasonably long.  MD5 (should be considered ancient and horribly broken) is only 128 bit,  SHA-1 is 160 bit, SHA-256 and SHA-512 are 256 and 512 bit.  The larger the keyspace the lower the probability that any two values will produce the same hash.

This same principal applies to Bitcoin.  Since addresses are hashes of the public key it is theoretically possible for two (or more) different public keys to hash to the same address.  Any of the associated private keys could spend the funds.  RIPEMD-160 and SHA-256 are considered cryptographically strong and have very large keyspaces which makes any collision academic at best.   If the algorithms were ever degraded that risk would become more real.

[Gabi]

is there only one unique string (password) that corresponds to a given hash?

Theoretically there are are infinite number of inputs that will result in the same hash because the hash function outputs a fixed-length value but the input can be any length.

Yes, thank you. Now, is this statement still true when a typical password is shorter than the 32-byte hash? 

For MD5: http://stackoverflow.com/a/2000014

Alright, does this mean that if my password is a reasonably random string, and the unsalted hash is made public, it may be possible to "reverse" it, but it won't be possible to tell for sure that that was the actual password - there could be another string with the same hash out there.

Also, does this mean that you could still type in a "wrong" password (that hashes into the proper hash), and you would be able to log in just fine, since server is ultimately comparing hashes?

Sorry for silly questions, I'm not versed in this topic but I want to understand the implications of these kinds of leaks.

Note that for SHA 256, 224, 512, 384 no collision has ever be found. None.

[genjix]

https://intersango.com/security.php

Intersango uses SHA512 + salt + site wide secret

[TangibleCryptography]

https://intersango.com/security.php

Intersango uses SHA512 + salt + site wide secret

Thanks for having that publicly disclosed on your site.  An example for all sites to follow.

[BrannigansLaw]

And remember to always salt your passwords 

I put salt on everything but common I know where to draw the line and its not going to be on a Heart rate monitor!

[BCB]

But are ALL your (email) passwords secure.

Hackers look for and will eventually find a chink in the armor (no offense!)

http://krebsonsecurity.com/2012/06/attackers-target-weak-spots-in-2-factor-authentication/

[zebedee]

Would someone please explain this for the uninitiated: is there only one unique string (password) that corresponds to a given hash?  I believe the technical term is collision resistance, right?  Once you reverse the hash, can you know for sure that you got it right? If password is a dictionary word, it may be obvious, but how about if everyone were using random strings for their passwords? Would the hacker ever be able to know for sure if the reversed hash is the right one?

Lol.  Simple answer to simple question?  There are an *infinite* number of random strings matching your hash.

After all, there are an infinite number of strings, and only len^possibilitiespercharacter unique hashes right?  infinite / finite = infinite

Look up the "pigeon-hole principle".  Simple logic, I'm struggling to even justify calling it mathematics.

[justusranvier]

Will you put your ass on the line to defend that statement as an absolute truth?

I'm confident enough in the company's incentive not to deliberately screw over their users to use the service. I need to trust them not to steal my passphrase, but I don't think that adds very much risk because I also need to trust all the websites I have accounts on to not do nefarious things with my data.

The government could force LastPass to install a backdoor in their plugin that recovers my passphrase (like Hushmail) but so what? They could just as easily force Google to turn over my Gmail account or my bank to give them all my money and they don't need my passwords to do it.

[proudhon]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how they're decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

[defxor]

LastPass has your encrypted passwords. They don't, however, have the decryption key.

Will you put your ass on the line to defend that statement as an absolute truth?

I already do, and have been doing so for quite some time. I personally verified LastPass' crypto architecture including reading through the javascript they serve my browser before trusting them. What I would want to see, but it needs to be dragged through W3C first, is the ability for web clients to verify signatures of code blocks served to them and warn the user if the code block changes.

Yes, my Bitcoin wallet password is stored in LastPass as well.

[mcorlett]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how they're decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

Rainbow tables.

[Xenland]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how their decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

This assumes that LinkedIn didn't really salt their passwords or take any kind of salting precautions but,

TO put it simply when you encrypt a password like "duck" you get a constant output like "2d2370db2447ff8cf4f3accd68c85aa119a9c893effd200a9b69176e9fc5eb98"

Now the act of salting is appending some random but knowable data. so if my salt was "123" (with out the quotes) then my password would like like this, "123duck" and the server would save the encrypted password output as "50a7b5d4016f61fae2a9d86368db862971c0ef4c83e01f3a88d12a78febff81a"

With out a (very long 512+ character) salt its really easy to brute force but just for the sake of a simple example even with a small salt like 123 in front of a password makes the encrypted output completely different.

So back to my point, even with a 255 character password (with out a salt) Its easy to bruteforce with something called a rainbow table (which is a huge database of precomputed encrypted password ouputs). hope that makes more sense and i just wanted rambling

(Ps. With out a long salt the rainbow table most likely will contain the output that was appended to the password as if their was no salt. so even if linked in did use a salt it wasn't long enough and the rainbow table contained the precomputed out put).

[TangibleCryptography]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how they're decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

Rainbow tables.

Longer answer.  By not using salt they made passwords deterministic.

The SHA-1 of "password" will ALWAYS be 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8.   The password can be precomputed.   It is made worse by the fact that SHA-1 (and SHA-256) are insanely fast.  A single GPU can hash up to a billion passwords per second.   In a year one can pre-hash and store 31 quadrillion passwords with a single graphics card.  A community of hackers can work together to hash a magnitude more.

The use of a fast hash algorithm combined with no salt dooms even the longest and most complex passwords.  They are already "pre-cracked" the hackers are simply looking them up in a lookup table.  One can obtain or purchase rainbow tables for just about any unsalted algorithm (or weakly salted like WPA2). 

Now using salt changes that:
The SHA-1 hash of "password" with a salt prefix of "123456789" is aa2cc735aa01f661a39d6a03214d2e551eb0d8ad
The SHA-1 hash of "passwrod" with a salt prefix of "123456780" is 5571911de78b7bdffcfa11ef75d93a6cab3d6540

Precomputation becomes impossible.  SHA-1 is still very very fast algorithm (which is bad) but salt at least makes the attacker work "in real time" which gives users with more complex passwords time to change them.  But even moderately complex passwords are going to fail because Moore's law is a monster.  I mean a GPU is a hashing engine.  Think about Bitcoin.  A Rigbox is 25 GH/s.  What does that mean?  It means it can perform 50 billion SHA-256 hashes per second.  If reprogrammed to crack passwords it could crack ever possible combination of 8 digit password in 9 hours.  All 9 digit passwords in 30 days.  Known, prior hacked, and dictionary passwords would fall in minutes.

Using "slow multi-round password function" (like bcrypt) AND a pre record salt eliminates all the short cuts.  The only option is to sllllllllllllllllloooooooooooooooooooooowwwwwwwwwllllllllllly brute force the passwords one record at a time.  That means exhaustively trying say all 8 digit passwords for a single account takes weeks if not months.   All but the weakest of the weak are just not economical to even attempt to attack"

Using a strong passwords is only half the answer.  You are also dependent on the service provider using proper password storage.

So now is the time to start asking sites "how are you storing my password?":
If they are using no salt (or a fixed per site salt) they don't care about your security.
If they are using a small salt (anything less than 64 bit, well 32bit is borderline) they don't care about your security.
If they are using a weakened or obsolete algorithm (SHA-1, MD5, etc) they don't care about your security.
If they are using a "fast hash" algorithm* (SHA-256, SHA-512, RIPEMD-160, etc) they don't care about your security.

* Unless iteratively performed.  PBKDF2 for example can use SHA-256 as it's "core cipher" but it strengthens it by hashing it tens of thousands of times:
SHA-256(salt+(SHA-256(salt + (SHA-256(salt + (SHA-256 .... SHA-256(salt + password)

[Xenland]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how they're decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

Rainbow tables.

Longer answer.  By not using salt they made passwords deterministic.

The SHA-1 of "password" will ALWAYS be 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8.   The password can be precomputed.   It is made worse by the fact that SHA-1 (and SHA-256) are insanely fast.  A single GPU can has up to a billion passwords per second.   In a year one can pre-hash and store 31 quadrillion passwords with a single HD 5970.

The use of a fast hash algorithm & no salt dooms even the longest and most complex passwords.  They are already "pre-cracked" the hackers are simply looking them up in a lookup table.

Now using salt changes that.
The SHA-1 hash of "password" with a salt prefix of "123456789" is aa2cc735aa01f661a39d6a03214d2e551eb0d8ad
The SHA-1 hash of "passwrod" with a salt prefix of "123456780" is 5571911de78b7bdffcfa11ef75d93a6cab3d6540

Precomputation becomes impossible.  Now SHA-1 is still very very fast algorithm (which is bad) but salt at least makes the attacker work "in real time" which gives users with more complex passwords time to change them.

Using "slow multi-round password function" (like bcrypt) AND a pre record salt eliminates all the short cuts.  The only option is to sllllllllllllllllloooooooooooooooooooooowwwwwwwwwllllllllllly brute force the passwords one record at a time.

That means exhaustively trying say all 8 digit passwords for a single account takes weeks if not months.   All but the weakest of the weak are just not economical to even attempt to attack"

And now I know why people prefer Bcrypt
Might have to update myCheaper In Bitcoins Library to have this option.

[proudhon]

I don't understand how so many long and seemingly secure LinkedIn passwords have been brute-forced?  Will somebody help me understand how they're decrypting 20+ character passwords?  Last I read over 60% of the leaked hashes have been decrypted.  I can understand that being the case if most of them were really short and simple passwords, but it looks like a lot of them followed password security standards pretty well.  Help me understand.

Rainbow tables.

Longer answer.  By not using salt they made passwords deterministic.

The SHA-1 of "password" will ALWAYS be 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8.   The password can be precomputed.   It is made worse by the fact that SHA-1 (and SHA-256) are insanely fast.  A single GPU can has up to a billion passwords per second.   In a year one can pre-hash and store 31 quadrillion passwords with a single HD 5970.

The use of a fast hash algorithm & no salt dooms even the longest and most complex passwords.  They are already "pre-cracked" the hackers are simply looking them up in a lookup table.

Now using salt changes that.
The SHA-1 hash of "password" with a salt prefix of "123456789" is aa2cc735aa01f661a39d6a03214d2e551eb0d8ad
The SHA-1 hash of "passwrod" with a salt prefix of "123456780" is 5571911de78b7bdffcfa11ef75d93a6cab3d6540

Precomputation becomes impossible.  Now SHA-1 is still very very fast algorithm (which is bad) but salt at least makes the attacker work "in real time" which gives users with more complex passwords time to change them.

Using "slow multi-round password function" (like bcrypt) AND a pre record salt eliminates all the short cuts.  The only option is to sllllllllllllllllloooooooooooooooooooooowwwwwwwwwllllllllllly brute force the passwords one record at a time.

That means exhaustively trying say all 8 digit passwords for a single account takes weeks if not months.   All but the weakest of the weak are just not economical to even attempt to attack"

I understand that they didn't salt and that that makes it easier to get the passwords.  I guess what's worrisome is that from what I've read there were some reasonably secure passwords whose hashes were decrypted - passwords along the lines of "34IDdka]o43';s/A".  I don't think passwords like that can be decrypted in a few days, even using a bunch of GPUs.  So, are we to understand that passwords like that are in some giant rainbow table?  That's what's bothering me about this.

[mcorlett]

So, are we to understand that passwords like that are in some giant rainbow table?  That's what's bothering me about this.

Yes, but you shouldn't worry; most services salt their passwords, and many use multiple iterations making brute-force attacks infeasible.

[TangibleCryptography]

I understand that they didn't salt and that that makes it easier to get the passwords.  I guess what's worrisome is that from what I've read there were some reasonably secure passwords whose hashes were decrypted - passwords along the lines of "34IDdka]o43';s/A".  I don't think passwords like that can be decrypted in a few days, even using a bunch of GPUs.  So, are we to understand that passwords like that are in some giant rainbow table?  That's what's bothering me about this.

Yes.  It should bother you.

Without salt it is easy to precompute and store passwords years in advance.  When you get a hacked password database you simply "look them up". The hash of an input will never change so the hash of  "34IDdka]o43';s/A was "7c6fbf7e2bfceb28c7be5e5e669864a8f0fb079b in 1992, it is still the same today, and it will still be the same in 2099.

Now with salt they can't precompute the passwords but they can still brute force them much much easier than many people think if the hashing algorithm is fast.

A rig box = 50 billion hashes per second.  To put that into perspective, to brute force SHA-256 hashed passwords even with a 64 bit random per password salt would only take:
<1 sec to attempt a database of 20 million (known, leaked, common, and dictionary based) passwords.
<15 seconds to attempt all 6 digit or smaller passwords (A-Z,a-z,0-9, and all printable symbols).
< 30 minutes to attempt  all 7 digit passwords.
< 2 days to attempt  all 8 digit passwords.

Now that is with a single RigBox.  Botnets can easily be 10x, or even 20x more powerful.  A hacker which needs password fast (before users change them) can rent 100x as much computing power.    Hell if you need a metric the Bitcoin network is ~10TH/s.  If "rented out" it has the computing power to brute force all 9 digit and smaller passwords in less than a day.

A strong password is not enough.  Three elements are required (and sadly even some in the Bitcoin community treat it as optional):
1) A strong password (which means website checking new password against lists of know and compromised passwords)
2) A slow hashing function (bcrypt, scrypt, pbkdf2, etc)
3) A large random per record (64 bit) salt

Anything less is insecure.  How insecure varies (from trivial to tough) but it can and will be broken given enough time and resources.


On edit: clarified a few points and fixed some horrible spelling.

[justusranvier]

Yes.  It should bother you.

Without salt it is easy to precompute and store passwords years in advance.  When you get a hacked password database you simply "look them up". They password will never change so the hash of  "34IDdka]o43';s/A was "7c6fbf7e2bfceb28c7be5e5e669864a8f0fb079b in 1992, it is still the same today and it will still be the same in 2099.

Now with salt they can't do that but as I pointed out people way way way way (20 magnitudes of way) understimate how easy it is to brute force passwords if the hashing algorithm is fast.

A rig box = 50 billion hashes per second.  To put that into perspective EVEN WITH SALT:
To brute force a database of 20 million (know, leaked, common, and dictionary based) passwords would take: <1 second
To brute force all 6 digit or smaller passwords would take ~ 14 seconds.
To brute force all 7 digit passwords would take ~ 23 minutes.
To brute force all 8 digit passwords would take ~ 1.5 days.

A strong password is not enough.  Three elements are requried (and sadly even some in the Bitcoin community treat it as optional):
1) A strong password (which means website checking new password against lists of know and compromised passwords)
2) A slow hashing function (bcrypt, scrypt, pbkdf2, etc)
3) A large random per record (64 bit) salt

Anything less is insecure.  How insecure varies but it can and will be broken given enough time and resources.

I wonder what it's going to take for authentication systems like gpgAuth to see adoption.