HOWTO securely hash passwords

In the wake of a series of very high-profile password leaks, Brian Krebs talks to security researcher Thomas H. Ptacek about the best practices for securing passwords. The trick isn't to merely hash with a good salt -- you must use a slow password hash that takes a lot of work, so that making rainbow tables is impractical.

Ptacek: The difference between a cryptographic hash and a password storage hash is that a cryptographic hash is designed to be very, very fast. And it has to be because it’s designed to be used in things like IP-sec. On a packet-by-packet basis, every time a packet hits an Ethernet card, these are things that have to run fast enough to add no discernible latencies to traffic going through Internet routers and things like that. And so the core design goal for cryptographic hashes is to make them lightning fast.

Well, that’s the opposite of what you want with a password hash. You want a password hash to be very slow. The reason for that is a normal user logs in once or twice a day if that — maybe they mistype their password, and have to log in twice or whatever. But in most cases, there are very few interactions the normal user has with a web site with a password hash. Very little of the overhead in running a Web application comes from your password hashing. But if you think about what an attacker has to do, they have a file full of hashes, and they have to try zillions of password combinations against every one of those hashes. For them, if you make a password hash take longer, that’s murder on them.

So, if you use a modern password hash — even if you are hardware accelerated, even if you designed your own circuits to do password hashing, there are modern, secure password hashes that would take hundreds or thousands of years to test passwords on.

The problem is that you really need to make this design decision from the start -- it's hard to retrofit once you've got millions of users.

How Companies Can Beef Up Password Security

• [SamLL]

  Can’t you retrofit it with the following procedure:

  Start with the old password hashes. Create a new table for the new password hashes, one row per user, and initialize it all to empty.

  Whenever a user attempts to sign in, see if they have an entry in the new hash table. If so, check their password against the new hash table, with the new slow hash, and ignore any entry in the old table.

  If they did not have an entry in the new hash table, check their password against the old table with the old fast hash. If it checks out, calculate the slow hash, fill in the row in the new table, and delete their row in the old password has table.

  Unless I’m missing something, this should let you gradually switch hash algorithms with no disruption to any user. Obviously you might still have legacy users who haven’t signed in for a long time still with their old-system hash, but you never store the same password with two different hashes, which might conceivably expose you to some kind of cryptographic attack.

  • [ahecht]

    Even easier is to just create a database of the slow hashes of your old fast hashes. Yes, it means you have to perform two hash operations when a user logs in, but the fast hash is, by definition, fast, and shouldn’t add a lot of overhead. Assuming the slow hash takes 100ms, it would only take LinkedIn 2 days to generate slow hashes for it’s 161 million members if they can get 100 machines working on it.

    • [corydodt]

      Hashes don’t really work like that? Your “inner” hash is the user’s password. Your “outer” hash is, I guess, the inner hash? If I understand you correctly.

      But nobody ever types the “inner” hash. So when it comes time to log in, you don’t have anything to hash again to compare.

      SamLL’s method seems sane, though.

      Edit Ok i think i get it. You keep both hashes, but you still compute the slow hash at login-time. Annoying in that you have an extra column in your database table, but not unreasonable.

    • [joshhaglund]

      yep, nesting hash functions like:  bcrypt(md5( password )) is the easiest and most immediate fix (waiting for users to log in leaves their accounts vulnerable).  But when you make this change you’ll have to take your site down and run:
      update users set md5password = bcrypt(md5password)

      on your db and that could take a quite a while if you’ve got 1million users.

      oh, or, like you said, do this in a different db. maybe flag accounts that updated pw during the 2day update, run them again at the end

  • [Jeremiah Blatz]

    This is entirely correct. Alternately (and probably easier long-term), add a “version” column to your password table, and overwrite the old password storage value with the new one. Since modern password storage systems like scrypt, bcrypt, PBKDF2, etc are tunable, you’ll want to periodically re-tune your paramaters anyway, so you’ll want the capability to do password versioning anyway.

  • [cfuse]

    Why not just expire people’s passwords and shunt them through the upgraded password procedure?

    If accounts are suspected of being compromised, you lock them and force the user to go through a password change anyway. Aren’t people accepting of this kind of thing by now?

• [nox]

  Rainbow tables are ultimately a sophisticated dictionary attack and need some expectation of what the plaintext passwords are in order to be effective.  Wouldn’t have had any luck with my password: oqN1ILN8C8mDyC. (created before linked-in supported symbols in passwords).

  Users need to be educated to take ownership of their security. Lastpass and yubikey is pretty solid.  

  • [SoItBegins]

     Yes, except you just posted your password in plain view on BoingBoing.

    • [BarBarSeven]

      Decrypt that hash and win a no prize! Excelsior!

  • [HahTse]

    Crappy password.

    See https://xkcd.com/936/ for better alternative.

    EDIT: Crappy for not being easy to memorize and thus being easily forgotten if not written down somewhere. The actual entropy of it is fine.

• [mercedes42]

  But what does it all MEAN?

• [LennStar]

  Even the slowest hash does nothing for security for the top 100 passwords like… password, swordfish and of course 123456

• [Schneems]

  Even if you made the wrong decisions from the start, companies can easily secure this data. I did a write up on how a developer could convert insecure passwords to secure passwords in half a day or less http://schneems.com/post/24678036532/zomg-my-passwords-are-insecure-now-what