... and, I assume you'd agree, if your password storage mechanism involves a single ultra-fast SHA1 or MD5 hash, salts are deck chairs on the Titanic anyways.
I'm not sure I agree, or else I'm missing your point.
Assuming a scenario of using a single MD5 hash action on a user password, and a user with a password of "password1", no salt means that the simplest dictionary + number rainbow attack will find your password early on.
Add in a randomly generated multi character salt, and now you'd need a 100% coverage 12 or 16+ character/byte rainbow file, which even with a single MD5 sum hash is I believe still well beyond the abilities of a modern comp farm.
So while I don't recommend using MD5 anymore for password hashing, a randomized multi-character salt still makes the difference between easily hackable, and virtually impossible to extract the password.
Yes: Users pick stupid passwords; and each user's salt is stored along with the hashed password.
Suppose someone has a password of "a" and you get access to a password file containing (user, salt, MD5(salt || password)) tuples. You start with single-letter passwords, and you promptly find this user's password. The salt meant that you had to check if each user's password was "a" individually instead of checking them all at once -- but if the password function is fast enough and a user's password is simple enough, you'll break it anyway.
Sure, but if someone has a password of 'tim5RaWk5', you'll waste a year trying to crack that one account.
With out any salt you could have 30-50% of all the accounts cracked using an existing rainbow table in about an hour.
Also, most sites require minimum password lengths (while this does shrink the overall attack space, it dramatically increases the minimum attack space per password). So brute forcing a salted password of 'a' seems like an unreasonable example. I agree, salted or unsalted, a password of 'a' is a bad password. The differnce is when it's a salted or unsalted password of 'my1pass' or 'T1mmy' much less an actually secure/random/long password.
The space of passwords consisting of two english-y words, possibly encoded in one of several elitespeak alphabets, seperated by a non-alphabetic character? Still much smaller than the 2^56 you get from fully random isprint() passwords.
Again: we can go back and forth about how likely it is I will crack your excellent passwords, and I hear you, but from 1991 through ~2004, iterative password cracking was the only way it was done, and it was and is freakishly effective.
Salts don't do anything at all to slow down iterative cracking tools. bcrypt kills them completely.
Yes. You're missing the attack that actually happens in the real world:
aardvark<salt> ac23b37db0039dda62896bb21f312755
abandon<salt> 5877f7f5836225442bf103c2e7d41a3f
abdominal<salt> 93e399d54bcf903ce686122118a5f52f
etc etc etc etc
The problem is that MD5 is lightning fast, as is SHA1 and even, for this application, SHA256. Unix password schemes have been designed for decades with the goal of not being as fast as message digest functions, so that attackers can't burn through entire dictionaries on the fly in reasonable amounts of time.
Wait. You're suggesting that a fast algorithm allows a real-time comprehensive dictionary + variant attack with modern hardware?
My understanding is that a Xeon 3 GHz proc can do about 4 million hashes per second, and a quad core intel core2 can do about 4.3 million hashes per second, so for a potentially mixed case, alpha numeric password of 8 chars, that's at least 2 years. Figure that you'll find it by the midway point, that's 1 year of CPU burnt on a single account.
I'm not sure what you mean by the attack that happens in the real world. Do you mean instead of doing lookups against a rainbow table, people just brute force the password with billions of login attempts? Or something else?
I know people who have used rainbow tables for attacks in the real world using either password files that weren't protected, or db table backup dumps they gained access to. Those attacks would have been useless with any sort of salt. Without a salt, they were trivial (in my personal experience with large corporate databases, 2-3 out of ten m5d hashed passwords can be found by Googling for the hash (and hence finding it in someone's rainbow table).
Can you further explain what you mean by a real world attack, and how a salt doesn't help?
1) That's only useful if the password for the account you're trying to hack uses a word in dict/words. Obviously attack spaces can be reduced by rules and whatnot, but I'm not sure that's really the part I'm missing.
2) The "thousand, with a 't'" remark seems unnecessarily snarky. I don't have thin skin here, but from my end I've been trying to communicate my understandings of password attacks, my confusion, and either educate or learn in the process.
3) I will certainly look at bcrypt for future projects. It looks interesting. I still think salting hashes is a good idea. I don't agree that the impact of salting is so minor as to be compared to deck chairs on the titanic. For corporations which have a standard/requirement to use a SHA (or god forbid MD5) hashing algorithm, hashing is a VERY VERY VERY good idea.
(1) The point is, if you're considering "average length 8 character passwords", there's a temptation to assume you're working with 2^56 bits of entropy. In reality, you're getting nothing even close to that; only a tiny minority of users use truly random passwords. If you're not using random passwords, the speed of your hash starts to matter a lot.
(2) Sorry. I meant to sound emphatic, not nasty.
(3) These are all hashing schemes; I'm arguing against using blazingly-fast hashing for password storage. If you're stuck with SHA, Colin's right; use a "stretched" version that iterates several thousand times (just re-hash the hash in a loop), and use a 32 bit nonce (err salt), generated on the fly for each user every time their password is changed, stored in an integer column in the user table.
You're absolutely right that a slow password hash should be used -- I left that part out because I wanted to make the non-saltiness of the "salt" clear without confusing people by talking about all the other things that they could do wrong.
Something else I think you'll probably agree with, even though it sounds hyperbolic: if this stuff sounds complicated, it's because it's supposed to be complicated.
There's an "easy" answer, which is simply "don't hack this stuff up yourself". The free options here are strong. Why waste your time with trivia?
Doesn't having a hash function that takes, say, 100x as long to compute as md5, only increase the cracking time by a factor of 100? Is that all there is to it?
Yes, but typically password hashes are constructed to be 1000x slower or more. A common construction is to iterate the hash, e.g., to store MD5(MD5(MD5(...(MD5(salt || password)...))) -- this allows you to trade password verification performance against password cracking time however you like, just by varying the number of times you iterate the hash.
Well take the case of bcrypt and md5. Assuming bcrypt takes about 300 times as long^ as md5, then that would be the difference between cracking a password in a day versus a year.
You'd need someone very patient to wait a whole year for your reddit password. And if you change your password every 6-12 months anyway, they are most likely screwed.
^ I picked 300 out of a hat, I think that bcrypt is usually 2-3 orders of magnitude slower, but no reason you can't recursively apply it to stretch it out even further.
The time it takes bcrypt to verify one password is a tunable parameter; that's the fundamental feature of the algorithm. If you want a password check to take one full second, you can do that. A dictionary attack against one six-character password on that system, even offline against a captured hash, would take years.
Comments
... and, I assume you'd agree, if your password storage mechanism involves a single ultra-fast SHA1 or MD5 hash, salts are deck chairs on the Titanic anyways.
I'm not sure I agree, or else I'm missing your point.
Assuming a scenario of using a single MD5 hash action on a user password, and a user with a password of "password1", no salt means that the simplest dictionary + number rainbow attack will find your password early on.
Add in a randomly generated multi character salt, and now you'd need a 100% coverage 12 or 16+ character/byte rainbow file, which even with a single MD5 sum hash is I believe still well beyond the abilities of a modern comp farm.
So while I don't recommend using MD5 anymore for password hashing, a randomized multi-character salt still makes the difference between easily hackable, and virtually impossible to extract the password.
Or am I missing something?
Or am I missing something?
Yes: Users pick stupid passwords; and each user's salt is stored along with the hashed password.
Suppose someone has a password of "a" and you get access to a password file containing (user, salt, MD5(salt || password)) tuples. You start with single-letter passwords, and you promptly find this user's password. The salt meant that you had to check if each user's password was "a" individually instead of checking them all at once -- but if the password function is fast enough and a user's password is simple enough, you'll break it anyway.
Sure, but if someone has a password of 'tim5RaWk5', you'll waste a year trying to crack that one account.
With out any salt you could have 30-50% of all the accounts cracked using an existing rainbow table in about an hour.
Also, most sites require minimum password lengths (while this does shrink the overall attack space, it dramatically increases the minimum attack space per password). So brute forcing a salted password of 'a' seems like an unreasonable example. I agree, salted or unsalted, a password of 'a' is a bad password. The differnce is when it's a salted or unsalted password of 'my1pass' or 'T1mmy' much less an actually secure/random/long password.
The space of passwords consisting of two english-y words, possibly encoded in one of several elitespeak alphabets, seperated by a non-alphabetic character? Still much smaller than the 2^56 you get from fully random isprint() passwords.
Again: we can go back and forth about how likely it is I will crack your excellent passwords, and I hear you, but from 1991 through ~2004, iterative password cracking was the only way it was done, and it was and is freakishly effective.
Salts don't do anything at all to slow down iterative cracking tools. bcrypt kills them completely.
Yes. You're missing the attack that actually happens in the real world:
aardvark<salt> ac23b37db0039dda62896bb21f312755
abandon<salt> 5877f7f5836225442bf103c2e7d41a3f
abdominal<salt> 93e399d54bcf903ce686122118a5f52f
etc etc etc etc
The problem is that MD5 is lightning fast, as is SHA1 and even, for this application, SHA256. Unix password schemes have been designed for decades with the goal of not being as fast as message digest functions, so that attackers can't burn through entire dictionaries on the fly in reasonable amounts of time.
Wait. You're suggesting that a fast algorithm allows a real-time comprehensive dictionary + variant attack with modern hardware?
My understanding is that a Xeon 3 GHz proc can do about 4 million hashes per second, and a quad core intel core2 can do about 4.3 million hashes per second, so for a potentially mixed case, alpha numeric password of 8 chars, that's at least 2 years. Figure that you'll find it by the midway point, that's 1 year of CPU burnt on a single account.
I'm not sure what you mean by the attack that happens in the real world. Do you mean instead of doing lookups against a rainbow table, people just brute force the password with billions of login attempts? Or something else?
I know people who have used rainbow tables for attacks in the real world using either password files that weren't protected, or db table backup dumps they gained access to. Those attacks would have been useless with any sort of salt. Without a salt, they were trivial (in my personal experience with large corporate databases, 2-3 out of ten m5d hashed passwords can be found by Googling for the hash (and hence finding it in someone's rainbow table).
Can you further explain what you mean by a real world attack, and how a salt doesn't help?
http://majuric.org/software/cudamd5/
According to the calculations on the above site you could exhaust the 8 character key space in 16 days.
The part you're missing: /usr/share/dict/words is 234,000 (thousand, with a 't') "hashes" long.
1) That's only useful if the password for the account you're trying to hack uses a word in dict/words. Obviously attack spaces can be reduced by rules and whatnot, but I'm not sure that's really the part I'm missing.
2) The "thousand, with a 't'" remark seems unnecessarily snarky. I don't have thin skin here, but from my end I've been trying to communicate my understandings of password attacks, my confusion, and either educate or learn in the process.
3) I will certainly look at bcrypt for future projects. It looks interesting. I still think salting hashes is a good idea. I don't agree that the impact of salting is so minor as to be compared to deck chairs on the titanic. For corporations which have a standard/requirement to use a SHA (or god forbid MD5) hashing algorithm, hashing is a VERY VERY VERY good idea.
(1) The point is, if you're considering "average length 8 character passwords", there's a temptation to assume you're working with 2^56 bits of entropy. In reality, you're getting nothing even close to that; only a tiny minority of users use truly random passwords. If you're not using random passwords, the speed of your hash starts to matter a lot.
(2) Sorry. I meant to sound emphatic, not nasty.
(3) These are all hashing schemes; I'm arguing against using blazingly-fast hashing for password storage. If you're stuck with SHA, Colin's right; use a "stretched" version that iterates several thousand times (just re-hash the hash in a loop), and use a 32 bit nonce (err salt), generated on the fly for each user every time their password is changed, stored in an integer column in the user table.
Now you're making things complicated. :-)
You're absolutely right that a slow password hash should be used -- I left that part out because I wanted to make the non-saltiness of the "salt" clear without confusing people by talking about all the other things that they could do wrong.
Something else I think you'll probably agree with, even though it sounds hyperbolic: if this stuff sounds complicated, it's because it's supposed to be complicated.
There's an "easy" answer, which is simply "don't hack this stuff up yourself". The free options here are strong. Why waste your time with trivia?
Doesn't having a hash function that takes, say, 100x as long to compute as md5, only increase the cracking time by a factor of 100? Is that all there is to it?
Is that all there is to it?
Yes, but typically password hashes are constructed to be 1000x slower or more. A common construction is to iterate the hash, e.g., to store MD5(MD5(MD5(...(MD5(salt || password)...))) -- this allows you to trade password verification performance against password cracking time however you like, just by varying the number of times you iterate the hash.
Well take the case of bcrypt and md5. Assuming bcrypt takes about 300 times as long^ as md5, then that would be the difference between cracking a password in a day versus a year.
You'd need someone very patient to wait a whole year for your reddit password. And if you change your password every 6-12 months anyway, they are most likely screwed.
^ I picked 300 out of a hat, I think that bcrypt is usually 2-3 orders of magnitude slower, but no reason you can't recursively apply it to stretch it out even further.
The time it takes bcrypt to verify one password is a tunable parameter; that's the fundamental feature of the algorithm. If you want a password check to take one full second, you can do that. A dictionary attack against one six-character password on that system, even offline against a captured hash, would take years.