SHA-512 w/ per User Salts is Not Enough

Chris Lyon

14

Back in January, I was having a causal conversation about passwords at a local gathering about security and was asked what we use for storing the passwords. I stated that we are using sha-512 w/ per user salts but we are looking at moving away from this standard to something much stronger. The response that I received from this person was pretty much in line with other comments I have received and seen on some of our forums. The two most common responses are: “Oh good, you are using per user salts” and “yeah, using sha-512 is much better than md5.” Granted, these comments are true, using sha-512 is better than using md5 and better than not using per user salts but there is still a weakness that I feel is overlooked.

Per user salts do provide value, but the problem is that they are typically stored with the hash. So the entry in the database looks something like this:

sha512${salt}${hash}

Or perhaps the hash is stored in a separate column or table and is grabbed as needed during password verification. Either way, both the hash and salt are stored in the same database.

In the event the hash was disclosed or the database was compromised, the attacker will already have one of the two values (i.e. the salt), used to construct the hash. All the attacker needs to do now is figure out the password entered into the hash formula and the order in which it was used. Order being:

hash = hash_operation({password} + {salt}) or;
hash = hash_operation({salt} + {password})

The two issues with this are: 1) since our source code is public, the order in which we salt is also public and; 2) due to our scale and usability, we store the hash and salt in the same place.

What am I getting at? The real problem is that we shouldn’t be solely replying on hashing algorithms to secure this data. Once the salt is known, it would be pretty trivial to dictionary a bunch of hashes in little or no time and get a pretty significant hit rate. (More to follow on this subject to follow in another post)

What is the solution? Right now the solution is moving away from sha-512 w/ per user salts to something like bcrypt but with a twist. The twist is adding in a layer of defense plus adding some controls over who can unlock the password equation. In pseudo code, this is what I mean:

{hmac_result} = hmac_create_operation( user_password + system_shared_password )
{bcrypt_result} = bcrypt_create_operation(( hmac_result + salt ) bcrypt iterations)

The bcrypt result would be stored in the database like this:

bcrypt$bcrypt_result$shared_key_version

The system_shared_password (aka nonce) is not stored within the database. Instead this data is stored on the operating system within a protected file. Using this configuration a SQL injection vulnerability that provides access to the password hash data would not provide access to the system_shared_password. Only under the scenario of a full system compromise would both secrets (password hashes, system_shared_password) be compromised.

We feel this solution gives us better controls around who can unlock the hashes and provides a layer of defense around the hashes. We also have put some code together thanks to fwenzel:

Why use per user salts at all? Two reasons, first per user salts ensure that two users with the same password will not have the same hash. Second, the use of salts prevents an attacker from using a precomputed rainbow table against the hashes.

More to come on this subject, as our goal is to increase security and the time in which it would take in order to brute or dictionary the hash. Our goal is and always to provide better protection around authentication systems.

Chris Lyon
Director of Infrastructure Security
a.k.a the hash buster.

14 responses

  1. Justin Dolske wrote on :

    Interesting. Probably also worth mentioning that using the PKCS#5 PBKDF2 mechanism is better than just hash(salt+pw). Basically the same, but the looping imposes an unavoidable time-penalty on someone attempting to brute force it.

    But even that’s still vulnerable when an attacker is just skimming a large DB for top-100 passwords (unless the time-penalty is huge, but then it’s not suitable for production use). The separate-key idea is interesting for that…

  2. zula wrote on :

    While storing the salt together with the password does make things slightly bad, I don’t see the issue with the tables.

    You cannot extract the salt part from the computed hash.
    You have to generate a list of tables for that salt.

    Thus, the salt is still doing it’s job.

    The only difference is that you now have a way to find out the password, but while it’s faster than trying through the network, it’s still pretty slow.

    Here are a few more interesting points:
    – NIST recommends SHA2, but not bcrypt (not that they would be right, but in the past they “magically” have been)
    – bcrypt is super slow, good against brute force, but for authentication it might be an issue on huge server farms
    – while there is indeed an issue with storing salt & hash, what about HMAC-SHA512 instead of bcrypt ? the key could be stored separately as well
    – how do you provide access to this key (also called system-shared-key or nonce in your article) ?
    While using a text file does stop SQL attacks by design, we could also just store all hashes in a text file, and this will stop any SQL issue.
    But this does not stop the core issue:

    The web app needs access to the key, hash, salt.

    In my mind, the key to such security is detailed separation.

    If the whole website is compromised and it’s not just a SQL injection, the key will be found anyway, because the web app NEEDS access to it.

    So,solutions, on top of this are:

    – have the authentication mechanism running elsewhere (kerberos, etc)
    – change the design (probably not possible) to use e.g. one time passwors, etc
    – change the design (same) to use cryptographic keys instead of passwords (eventually that is one good solution however)
    – secure and separate as much as possible on the system (but that won’t help in case of full compromise)

    ps: additionally, this HTTPS page posts to a HTTP page. 😉 Firefox says he’s unhappy!

    1. Chris Lyon wrote on :

      I will be posting data on how BAD this really is soon and mainly around doing offline attacks. What you are missing here is that the salt is stored with the hash and isn’t just part of the hash. So the only job the salt is doing is protecting the entire table against precomputed tables.

      We are still looking at the performance side of bcrypt but really don’t have much concern around the impact.

      As to your concern around separation and total system compromise, if somebody owns , we have bigger issues than how we store passwords.

  3. ron wrote on :

    “Why use per user salts at all? Two reasons, first per user salts ensure that two users with the same password will not have the same hash”

    Isn’t including username in the hash:

    hash = hash_operation({username} + {password} + {salt})

    better than

    hash = hash_operation({password} + {salt})

    The former would create unique hashes for each user, so no need to have different salts per user. Am I missing something?

    1. Chris Lyon wrote on :

      @ron adding in the username is fine but when a user changes their name, you will need to keep track of it. Don’t forget, what you put into creating the hash, you need to verify it.

      Also, one key thing here, you still have what is required to unlock the hash if you get in contact with it, short of having the password.

  4. Anonymous Coward wrote on :

    Can you change your CSS to use black text instead of light gray? Might help if you want people to read your posts.

  5. Rakkhi wrote on :

    Chris, would be interested in reading your post on “how bad” this is. Assume it’s along the lines of this: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html

    Nevertheless it does seem to be the default situation around the web. Maybe Mozilla implementing something better will spark a change.

    What do you think about this from Lastpass? “We’re also taking this as an opportunity to roll out something we’ve been planning for a while: PBKDF2 using SHA-256 on the server with a 256-bit salt utilizing 100,000 rounds. We’ll be rolling out a second implementation of it with the client too. In more basic terms, this further mitigates the risk if we ever see something suspicious like this in the future. As we continue to grow we’ll continue to find ways to reduce how large a target we are.”

    http://blog.lastpass.com/2011/05/lastpass-security-notification.html

    1. Chris Lyon wrote on :

      @rakkhi it isn’t as bad as rainbow tables, more around the ease and timing of figuring out which passwords are being used in these hashes. This is giving us the ability to create blacklists of passwords which are custom to us but more on that later.

  6. Abraham Aranguren wrote on :

    Hi Chris,

    While this is a nice post, I think you can achieve similar results with a much simpler solution like (dot used for concatenation as if this was PHP) ;):

    hash_function($username.hash_function($password, BIG_RANDOM_SALT))

    or even:

    hash_function($username.$password.BIG_RANDOM_SALT))

    (calling the hash function twice as in the first example is a bit stronger due to additional computing time)

    Given that:
    – BIG_RANDOM_SALT is a system constant on the application (NOT the database). Therefore something like SQL injection or even full database server compromise (given the global salt is in a separate web server) does NOT provide access to the salt.
    – The username acts as an additional salt (i.e. two identical passwords will be hashed differently for two given users)
    – You can still use an additional random salt per user if you want and this can be stored in the database, this just complicates things a bit more but I think it does not significantly increase the time required for cracking (but yes, more hassle for the attacker is always better).

    As mentioned by others, the only purpose of the salt is to defeat rainbow tables, the defense against avoiding access to the salt in case of SQL injection can be achieved by simply having another (very random and big) salt on the web application side.

    If the web server is compromised you can complicate it all you want but it is game over (given that it needs access to everything).

  7. rsw wrote on :

    Chris, wouldn’t you get the same job done just with

    hash (salt + nonce + password)

    as with the method you’ve described? It seems to me you’ve described an attempt to solve the stated problem plus another implicit problem that you don’t think SHA512 is sufficient and for some reason want to use a few rounds of bcrypt instead. These are orthogonal issues, no?

  8. David Magda wrote on :

    If you’re worried about the strength of hashes, why not just start using the Secure Remote Password (SRP) protocol:

    v = g^x, x = H(s,p)

    H is some hash function (SHA-256 in SRP-6a), s is a salt, p is the password. You store ‘s’ and ‘v’ on-disk.

    http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol

    Solving the problem is not dependent on the hash, but rather on basically breaking Diffie–Hellman.

  9. Neil wrote on :

    A few years ago I read a method of computing a password hash that went like this:

    Say the user’s password is “abcdefgh”.

    Hash to store = SHA512(salt1 + “abcd” + salt2 + “efgh”)

    What I found interesting about something like this is that it appears, to me, to protect against the case where the attacker knows the salt values. This design forces the attacker to additionally know the length of the password.

    Would an algorithm like this still require brute force, or am I misunderstanding it?

  10. Stephen Coley wrote on :

    Perhaps I’m naive, but why not just store the salts in a different database accessible only by one account with only privileges to that database? Why not on a different server entirely?

  11. Bennet Yee wrote on :

    SHA-256 is a hash function that uses the Merkel-Daamgard construction, just like SHA-1. That means that hash(password | salt) and hash(salt | password) actually are quite different from a cryptanalytic viewpoint, due to the internal block chaining of input blocks into the compression function.