[Password Leak] LinkedIn database hacked

[proudhon]

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.

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

[1715162811]

1715162811

[mcorlett]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

[proudhon]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

[TangibleCryptography]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

Nope not in a 1000 years either.

Large numbers can mess with people's minds but this might help.

A random 10 digit password (95 possible values per digit) is ~ 2^64 or 64 bit.   256 bit isn't 4x as large it is  6,277,101,735,386,680,000,000,000,000,000,000,000,000,000,000,000,000,000,000 as large (roughly excel needs to round).

If you could crack brute force all possible 64 bit keys in 1 second it would still take roughly   19,904,559,029,003,900,000,000,000,000,000,000,000,000,000,000 centuries to have a 1% chance of brute forcing a private key.  

Another way to look at is our sun doesn't have enough energy remaining to power a computer that could count from 0 to 2^256 much less brute force a specific key.  That is you build a computer who could use the sun's complete energy output and operated at 100% efficiency it still couldn't count to 2^256 before our star burned out.

So the only risk to a private key is if the SHA-256 algorithm is broken or more likely degraded.  By degraded I mean some flaw is discovered that allows you to take a "shortcut" and thus eliminate trillions or quadrillions of keys simultaneously.  Even degraded it would likely be very difficult (maybe only of academic interest) to brute force a private key but that would be a good sign to upgrade Bitcoin (and everything else which uses SHA-2) to a stronger algorithm.

[justusranvier]

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

If every atom in the solar system were a computer capable of performing calculations at 10 GHz (assuming all calculations could be done in a single cycle) it would take 300,000 years to count to 2^256

[sadpandatech]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

Nope not in a 1000 years either.

Large numbers can mess with people's minds but this might help.

A random 10 digit password (95 possible values per digit) is ~ 2^64 or 64 bit.   256 bit isn't 4x as large it is 6277101735386680000000000000000000000000000000000000000000 as large (roughly excel needs to round).

If you could crack a 10 digit password in 1 second it would take roughly 995227951450197000000000000000000000000000000000 centuries to have a 50% chance of brute forcing a private key.  Even if you could build planetary sized supercomputers and capture the entire energy output of our sun and use it to power a perfectly efficient computer, our sun doesn't have enough energy remaining energy to power a computer that could count from 0 to 2^256 much less brute force a specific key.

So the only risk to a private key is if the SHA-256 algorithm is broken or more likely degraded.  By degraded I mean some flaw that allows you to take a shortcut and thus eliminate billions or trillions of keys simultaneously (even that would still mean it would be very difficult to break but would be a good sign to move to a new algorithm).

This. plus its been mentioned before that Bitcoin can be upgraded to 512 bit keys, etc as the need arises.

[proudhon]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

Nope not in a 1000 years either.

Large numbers can mess with people's minds but this might help.

A random 10 digit password (95 possible values per digit) is ~ 2^64 or 64 bit.   256 bit isn't 4x as large it is  6,277,101,735,386,680,000,000,000,000,000,000,000,000,000,000,000,000,000,000 as large (roughly excel needs to round).

If you could crack brute force all possible 64 bit keys in 1 second it would still take roughly   19,904,559,029,003,900,000,000,000,000,000,000,000,000,000,000 centuries to have a 1% chance of brute forcing a private key.  

Another way to look at is our sun doesn't have enough energy remaining to power a computer that could count from 0 to 2^256 much less brute force a specific key.  That is you build a computer who could use the sun's complete energy output and operated at 100% efficiency it still couldn't count to 2^256 before our star burned out.

So the only risk to a private key is if the SHA-256 algorithm is broken or more likely degraded.  By degraded I mean some flaw is discovered that allows you to take a "shortcut" and thus eliminate trillions or quadrillions of keys simultaneously.  Even degraded it would likely be very difficult (maybe only of academic interest) to brute force a private key but that would be a good sign to upgrade Bitcoin (and everything else which uses SHA-2) to a stronger algorithm.

Got it.  Thank you!

[Serge]

a more technical question

what are good standards or principles for generating and handling salts?

from above posts i understand it is recommended to use unique large salts per db record, which obviously should not be stored in database in plain sight along with hashes. when user enters password, how is it recommended to generate random salt for a hash which needs be reused later on when user logs back in into a site; as only other supplied data by user usually is username/handle/email, which again presumably are stored in plain sight along with salted hash of a password?

[TangibleCryptography]

a more technical question

what are good standards or principles for generating and handling salts?

from above posts i understand it is recommended to use unique large salts per db record, which obviously should not be stored in database in plain sight along with hashes. when user enters password, how is it recommended to generate random salt for a hash which needs be reused later on when user logs back in into a site; as only other supplied data by user usually is username/handle/email, which again presumably are stored in plain sight along with salted hash of a password?

Don't use user information it has low entropy.   Salt isn't a secret, it is simply a mechanism used to make hashes unique and defeat precomputation attacks.  It can be stored right in the database next to the hash.

bcrypt for example stores everything you need in a single output

Code:

$2a$10$vI8aWBnW3fID.ZQ4/zo1G.q1lRps.9cGLcZEiGDMVr5yUP1KUOYTa

For example you just need to store this single string (bcrypt output is always 60 char).

$2a indicates the version (ensures that if future version are created your hash can always be reconstructed)
$10 indicates a workload of 10 = 2^10 iterations.
$vI8aWBnW3fID.ZQ4/zo1G.q1lRps.9cGLcZEiGDMVr5yUP1KUOYTa is the salt + hash.

vI8aWBnW3fID.ZQ4 is the salt = 128 bit nonce
/zo1G.q1lRps.9cGLcZEiGDMVr5yUP1KUOYTa is the hash (always 184 bit - yeah somewhat unusual).

to verify the password you put the entire string back into bcrypt algorithm along with the plaintext.  bcrypt parses the string to determine the salt, hash, version, and # of rounds and hashes the password and compares it to the stored hash.

If you then want to update the strength (say you now want workload of 14 because computers are faster you simply hash the plaintext again w/ bcrypt but using workload 14 instead of 10.  bcrypt will chose a new random nonce and generate a new output say something like this:

Code:

$2a$14$vIcZEiUP1KUQ4/zo1WBnGDMVr5yW3fIG.q18aD.ZGLlRps.9cOYTa

Update the db to store this string instead and TADA the password is now 2^4 = 16x harder to crack.

[Phinnaeus Gage]

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

No, because every additional character exponentially increases the effort required to break the key.

But, in 10 years?  Imagine that in 10 years a single RigBox is 100x as powerful as today's, and that I can rent 100 of them.  That much compute power still isn't enough to get a private key in, say, a few weeks?

Nope not in a 1000 years either.

Large numbers can mess with people's minds but this might help.

A random 10 digit password (95 possible values per digit) is ~ 2^64 or 64 bit.   256 bit isn't 4x as large it is 6277101735386680000000000000000000000000000000000000000000 as large (roughly excel needs to round).

If you could crack a 10 digit password in 1 second it would take roughly 995227951450197000000000000000000000000000000000 centuries to have a 50% chance of brute forcing a private key.  Even if you could build planetary sized supercomputers and capture the entire energy output of our sun and use it to power a perfectly efficient computer, our sun doesn't have enough energy remaining energy to power a computer that could count from 0 to 2^256 much less brute force a specific key.

So the only risk to a private key is if the SHA-256 algorithm is broken or more likely degraded.  By degraded I mean some flaw that allows you to take a shortcut and thus eliminate billions or trillions of keys simultaneously (even that would still mean it would be very difficult to break but would be a good sign to move to a new algorithm).

This. plus its been mentioned before that Bitcoin can be upgraded to 512 bit keys, etc as the need arises.

Given the above, then isn't upgrading to 512 bit keys a mute issue, or am I missing why that upgrade is important?

~Bruno~

[TangibleCryptography]

Given the above, then isn't upgrading to 512 bit keys a mute issue, or am I missing why that upgrade is important?

Probably.  The most likely scenario where an upgraded is required is because SHA-256 has some sort of flaw.  Since all versions of SHA-2 share the same algorithm (with different block sizes) it would be best to choose a new tested algorithm.  NIST is already conducting testing and competitions to find the algorithm which will become SHA-3.

[Serge]

sweet. thanks TangibleCryptography for a simple explanation. i was puzzled before regarding salts whether they need to be secret or obscure, now everything makes perfect sense. Thank you!

[casascius]

$2a$10$vI8aWBnW3fID.ZQ4/zo1G.q1lRps.9cGLcZEiGDMVr5yUP1KUOYTa

$2a$14$vIcZEiUP1KUQ4/zo1WBnGDMVr5yW3fIG.q18aD.ZGLlRps.9cOYTa

 

[TangibleCryptography]

$2a$10$vI8aWBnW3fID.ZQ4/zo1G.q1lRps.9cGLcZEiGDMVr5yUP1KUOYTa

$2a$14$vIcZEiUP1KUQ4/zo1WBnGDMVr5yW3fIG.q18aD.ZGLlRps.9cOYTa

 

Good catch.  That is why I said "output say something like this".   You get the point though.  Actually I have no idea what the plaintext is.

[niko]

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.

Well, this bothers me on two fronts then.  If there are rentable hashing resources with as much as 100x as much computing power as a RigBox, then it doesn't seem implausible to me to see rentable resources in the next decade that could, within a reasonable amount of time, get a private bitcoin key from a public key.  No?  What am I missing?

Isn't it likely that those strong-looking passwords were phished from the unsuspecting victims clicking on links from "LinkedIn" after the hack? The same thing was going on after the gox hack.

[cytokine]

Can someone explain to me the big practical difference between SHA-256 and SHA-512, other than the larger digest for the latter?

[TangibleCryptography]

Can someone explain to me the big practical difference between SHA-256 and SHA-512, other than the larger digest for the latter?

Not much.

SHA-256 block size (input) is 512 bit and SHA-512 block size is 1024 bit.
SHA-256 digest (output) is 256 bit and SHA-512 digest is 512 bit.
The initialization constants are different.
SHA-256 uses 32 bit "chunks".  SHA-512 uses 64bit "chunks"
SHA-256 has 64 rounds (iterations of the algorithm), SHA-512 has 80.

Other than that they pretty much are the same.  Same basic algorithm.

[cytokine]

Can someone explain to me the big practical difference between SHA-256 and SHA-512, other than the larger digest for the latter?

Not much.

SHA-256 block size (input) is 512 bit and SHA-512 block size is 1024 bit.
SHA-256 digest (output) is 256 bit and SHA-512 digest is 512 bit.
The initialization constants are different.
SHA-256 uses 32 bit "chunks".  SHA-512 uses 64bit "chunks"
SHA-256 has 64 rounds (iterations of the algorithm), SHA-512 has 80.

Other than that they pretty much are the same.  Same basic algorithm.

So is there a significant security advantage to using SHA512 over SHA256, or not really enough of one to justify the extra cost?

[TangibleCryptography]

So is there a significant security advantage to using SHA512 over SHA256, or not really enough of one to justify the extra cost?

SHA-512 actually hashes faster on most CPU (x64 capable) and slower on most GPU.  So I would be inclined to use SHA-512 over SHA-256 for passwords.   The extra "cost" (in terms of computing power, storage, memory) is negligible.   Still SHA-2 is very fast algorthm so some sort of chained function like PBKDF2 is necessary.  If it is a new project I see no reason to not just start with SHA-512.

If you mean upgrading Bitcoin from SHA256 to SHA512 well that is likely futile.  SHA-256 is more than strong enough today.  Any advantages of SHA-512 are at this point theoretical.  It is very possible that whatever weakens SHA-256 will weakens all SHA-2 algorithms.    If you are going to do something as disruptive as change Bitcoin's core algorithm you might as well make a clean break and not do a baby step from SHA-256 to SHA-512.

[Xenland]

Anyone know of a website or something that could explain this formula in some kind of dumbed down English, I understand encryption practices fairly well I've always wanted to know what the formula it self is doing be hind the since I just don't know Alien math quite yet