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.
Comments
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.