Tuesday, April 16, 2013

I don't care what you believe

I want to make one thing perfectly, crystalline clear: I don't care what you believe.

If you want to believe that the entire universe was created 500 years ago when a magical purple manatee shat it out while swimming through the Æther, fantastic. You go ahead. I hope it brings you much happiness.

Here's what I actually care about:

  1. You accept that your individual successes and failures are strongly related to the communities in which you live, work, and play
  2. You take tangible action to help those in need
  3. You use whatever privilege you have (earned or unearned) to help those less fortunate than yourself
  4. You make an effort to adopt and follow a rational code of ethics
  5. You respect and value a diversity of being, ideas, backgrounds, and cultures
If your love for the magical purple manatee motivates you to do the above, yay for you. I'm glad you found a way of processing the world that helps make you a good person. But the moment your love for the magical purple manatee becomes more important than being a good person who does good things, you fail humanity.

So, again: I don't care what you believe, but dammit, I care what you do with it.

Thursday, April 11, 2013

UserID-based salts are insufficient

When storing "inbound" passwords -- passwords your application will use to authenticate people and other applications to it -- there are a handful of options:

  1. Clear-text in some "secured" data store. Bad idea because if it's compromised, 100% of your accounts are breached.
  2. Encrypted. Bad idea because it relies on the discovery of a single secret (the private key); again, if breached, 100% of your accounts are breached.
  3. Hashed. Not too bad, assuming a modern hash function. But vulnerable to Rainbow Table attacks, so not exactly "good" either.
  4. Hashed with a "salt" (a.k.a. a "nonce"). If you do this correctly -- one salt per password stored, using a modern hash algorithm -- considered best practice.
As with most security things, the devil is in the details. Many developers I've spoken with worry about generating unique salt values for performance reasons. A solution I've seen in more and more code is to use the User ID (often an e-mail address) as the salt. The logic is that the salt is already stored, so there's no overhead to generate it and no database engineering work to accommodate salt storage.

Unfortunately, using a UserID -- especially if it's an email address -- is simply not good enough.

The goal of using a salt is to make it computationally unfeasible to generate rainbow tables. Rainbow table attacks work on "unsalted" hashes because you only need to hash every possible password once, after which you can simply look up the hash. Salting the hash means that you have to generate a complete rainbow table for every possible salt value -- a task that is orders of magnitude harder (computationally) than generating a single rainbow table.

However, generating a single rainbow table for SHA-256 8-character passwords on a commodity GPU only takes a bit over 90 days. If I'm attacking an individual, that's worth it. And if people are using the UserID as a salt, then I only have to do this once to build a rainbow table that will attack every such hash the user has. In other words, if multiple services use UserID for a hash, then with one rainbow table, I can attack a given user's account on all of those services.

Defense

Firstly, generate a unique, long, cryptographically-sufficient salt every time a new password is set. Not per-user.  It really doesn't take that much of a performance hit -- and if every bit counts, pre-generating a pool of salts from which to pull is a possibility.

Secondly, increase the hash work factor. After selecting a salt, do:

hash = sha256( salt + password );
for (i=1..work_factor) {
    hash = sha256( salt + hash );
}

This means that the time to brute-force is multiplied by "work_factor"; this hurts the attacker far more than the provider. Setting the work_factor to 10,000 or more should stymie all but the most determined attackers while having negligible performance impact on your application (remember you only have to do this when the password is set or checked, it isn't being done with every request or every operation).