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?
Topic: [Password Leak] LinkedIn database hacked - page 2. (Read 12914 times)
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!
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.
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 
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.
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?
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. 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?
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. 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 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.
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. 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.
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.
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)
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).
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. 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.
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.
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.
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.
Jump to: