Hash function change

Question

I have user account passwords stored in a database using an unsafe (old) cryptographic hash function.

What is the best/usual approach to changing password hash function? Only two ideas come to my mind:

1. Prompt all users to change their passwords on next log in and hash their passwords with new function when they do. This is not a good option because of many issues (inactive users, long migration period, complicated implementation...)

2. Hash the old hash values with new hash function, and re-write the method for checking passwords against database: newHash(salt + oldHash(salt + password))

This double hashing seems to me like a good idea, both elegant and simple to implement.

I would like to know if there are any caveats I'm not noticing here. Is this the way this is usually done, or there is another method? Is there some known cryptographic vulnerability in using weak hash function's output as strong hash function's input.

If it is a good idea, what about salt? Would it be okay to use the same salt for both hash functions?

Answer 1

Personally, I would probably implement both with new users getting a strong modern hash (bcrypt or other key-strengthened cryptographic hash) and old users having the weak hash wrapped around bcrypt. Before people complain of extra implementation complexity the alternative is to always force new users to use weak hash algorithm wrapped around strong hash algorithm, and that means you'll never be rid of the original scheme.

I would have some documented indicator of the type hash scheme analogous to the $1$, $2a$, $5$, or $6$ in crypt (quote from the crypt man page):

   If  salt is a character string starting with the characters "$id$" fol‐
   lowed by a string terminated by "$":

          $id$salt$encrypted

   ... id  identifies  the  encryption
   method  used  and  this  then  determines  how the rest of the password
   string is interpreted.  The following values of id are supported:

          ID  | Method
          ─────────────────────────────────────────────────────────
          1   | MD5
          2a  | Blowfish (not in mainline glibc; added in some
              | Linux distributions)
          5   | SHA-256 (since glibc 2.7)
          6   | SHA-512 (since glibc 2.7)

In this case, you need three types of password hashes:

1. The old fast weak hashes
2. The old fast weak hashes that is wrapped around a slow hash with a strong salt
3. The new slow hash.

On day 1, I would take everything from category 1 and move it into category 2. New passwords would be put into category 3. Furthermore, as people login, you can even migrate every successfully authenticated hash from category 2 to category 3 while the plaintext password is in memory. At some point, you can even completely eliminate any evidence/legacy maintenance of the weak hashing scheme. (E.g., forcing users with accounts that haven't logged in for 2+ years after the change to reset their passwords).

Answer 2

Your proposal 2 (take the old hash value as the "password" for the new hash) is good if the following conditions all hold true:

• The old hash is sufficiently resistant to preimages.
• The new hash uses all the needed bells'n whistles to deem it "robust" (i.e. that's bcrypt with a lot of rounds, and a new random salt for each password, including for password changes for a given user).
• The old hash can be computed efficiently enough that the whole "configurable slowness" business relies on the new hash exclusively.

Note that MD5, though thoroughly broken with regards to collisions, still appears reasonably strong with regards to preimages.

It would still serve best your interests to include a "type of hash" field in your database, so that migrations could be handled smoothly. You could, for instance, apply your hash-of-hash, and then plan for a migration to a password hashing scheme which uses the new hash only -- passwords would be updated to the new scheme whenever they are created or changed, for a gradual migration. Later on (say in one year), you could setup a forced update (user must reenter the password upon next login) for the passwords which still use the old format.

Even if you do not like migrations (who does ?), it seems only prudent to provision for a possible future migration, if conditions at that time force the migration upon you (e.g. a devastating cryptanalytic break).

Answer 3

I would use bcrypt as the new hash. Otherwise, your solution of "wrapping" the old hashes should be secure, given that you use a good salt for for bcrypt. I've seen this solution work well a few times when systems want to upgrade how they hash their passwords.

Answer 4

If you don't want to bother using the old hash function, but also do not want to force everyone to change your password, there is one elegant solution.

Add a column/value to every user profile. Let's call if HashVersion

When the user goes to login for the first time since your migration, the system will then be able to detect it's using the old hash function. So, if the user supplied password matches up to your hash, then you take the plain text password and hash it with your new algorithm, resetting salts and such as well. And then you bump up HashVersion so you know it's now using the new hash function.

This, in my opinion is the best solution, especially if your previous hash function was really insecure.

Answer 5

As long as the old hash is decent (MD5 or DES-Crypt is fine, CRC32 is not) this approach is secure. Using the same salt shouldn't lead to problems either, assuming the salt is good enough i.e. (almost) globally unique.

For the outer hash function I recommend using one of scrypt, bcrypt or PBKDF2.

Answer 6

You'll find dozens of open-source applications that that have solved this problem. Wordpress comes quickly to mind, but there are others as well. Even Microsoft Windows uses this same technique. The general solution is this:

• The output of each supported hash function is readily distingushed; either by checking the output format or length, or (more appropriately) by prepending some identifier string (e.g.: sha1:salt:_hash_output____) or by adding a new field to your database to identify the hash type.
• You continue to support authentication via all previously-used hash functions, but all new hashes will output only the preferred version.
• Optionally, if a user is authenticated using a previous hash version, the authenticated password will be re-hashed using the preferred algorithm and the stored hash will be updated.