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.


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

No comments:

Post a Comment