28

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?

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
h9lpq0u
  • 383
  • 3
  • 6
  • 1
    Second is most likely OK, unless `oldHash` is extremely bad(far worse than md5). Some people will recommend separate salts, but I don't think that's really necessary. – CodesInChaos Aug 27 '12 at 14:05
  • Can you post what kind of hashes you're using(old and new), and how you generate the salt? – CodesInChaos Aug 27 '12 at 14:06
  • Old hash is unix crypt (DES based) and new is not decided yet. Salt is random for each user. – h9lpq0u Aug 27 '12 at 14:10
  • I'm pretty sure we have a duplicate question here or on crypto. But I didn't find it. – CodesInChaos Aug 27 '12 at 14:23
  • @CodesInChaos: Are you thinking of [Do I have to recompute all hashes if I change the work factor in bcrypt?](http://crypto.stackexchange.com/questions/3003/do-i-have-to-recompute-all-hashes-if-i-change-the-work-factor-in-bcrypt) ? – David Cary Aug 27 '12 at 19:13
  • If you're not worried about the extra database query, you could implement a password history option. It would let you add hashing versions forevermore, and also let you reset to old passwords, monitor changes, etc. – arxanas Aug 27 '12 at 19:33
  • Also look at http://en.wikipedia.org/wiki/Scrypt. With massively parallel GPU and FPGA cracking machines available for just a few hundred dollars, it's memory that becomes the bottleneck, not ALU instructions. – drxzcl Aug 28 '12 at 06:47

6 Answers6

19

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

dr jimbob
  • 38,936
  • 8
  • 92
  • 162
  • I like the idea of migrating users automatically, behind the scenes when they log in. Kudos. – John Aug 28 '12 at 14:38
  • What is the benefit of gradual migration? Only benefit I see is that after given period of time I will be able to "retire" the old password scheme. But why do I need to do so? I already have the methods for using it, so it doesn't bother me. – h9lpq0u Aug 29 '12 at 08:01
11

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

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • What is the benefit of gradual migration? Only benefit I see is that after given period of time I will be able to "retire" the old password scheme. But why do I need to do so? I already have the methods for using it, so it doesn't bother me. – h9lpq0u Aug 29 '12 at 08:01
  • @h9lpq0u If the old scheme is discovered to be broken in terms of pre-images, then your combined password scheme may become insecure. – jpmc26 Aug 27 '16 at 00:44
7

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.

Community
  • 1
Oleksi
  • 4,839
  • 2
  • 20
  • 26
  • Thanks. Why do you recommend bcrypt over SHA-2 (and soon SHA-3), which is NIST standard for cryptographic hash? Is it (only) because bcrypt can be made arbitrarily slow? – h9lpq0u Aug 27 '12 at 14:23
  • Partially. Bcrypt, and more generally adaptive hash algoritms, seems to be the current trusted solution in the industry. I suspect things like bcrypt will survive longer. For example, there are already GPU-based attacks that can compromise a lot of SHA-512 hashed passwords. – Oleksi Aug 27 '12 at 14:27
  • 2
    The core problem is the same; Those hash methods are meant for speed of hashing, which is the opposite of what you want for a password hashing method. – Oleksi Aug 27 '12 at 14:28
  • Thanks for the clarification. I will definitely take that into consideration. – h9lpq0u Aug 27 '12 at 14:33
  • @h9lpq0u There are [only two good ways to hash a password (maybe three if you're adventurous)](http://security.stackexchange.com/a/1164/1983). SHA-2/SHA-3 are not designed for this. – Brendan Long Aug 27 '12 at 15:36
  • bcrypt I believe is the only hashing function which can not be sped up by GPUs, nor compromised by quantum computers – Earlz Aug 27 '12 at 17:45
  • @h9lpq0u See [Do any security experts recommend bcrypt for password storage?](http://security.stackexchange.com/q/4781/836) on this site. – Jeff Ferland Aug 27 '12 at 18:11
  • 1
    @Earlz bcrypt *can* be sped up by GPUs, but not by a factor anywhere near that of traditional functions. scrypt is even better, due to the memory-hard function. GPUs may have a large amount of onboard RAM, but the per-core bandwidth chokes performance. – Polynomial Aug 28 '12 at 07:46
7

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.

Earlz
  • 604
  • 2
  • 6
  • 15
  • 3
    While similar to ThomasPornin and my earlier answers, your solution leaves weak hashes in the database until the user logs in next, which is less than ideal as the old hashes could be attacked in the interim if the hashes are ever leaked. Assuming the old way was `md5(salt+pw)` and the new hash is bcrypt, h9lpq0u should first move to a scheme like `bcrypt(bcrypt_salt(log_rounds=12), md5(salt+pw))`. Otherwise, if the hashes were compromised during the interim (before next login) say for an infrequently used account, an attacker could easily brute force a user's password. – dr jimbob Aug 27 '12 at 19:15
  • 2
    @dr j, Ah, well then for the best of both worlds, replace the old hash value with `NewHash(old_hash_value)`. And then when they login for the first time replace it with only `NewHash(password+salt)` – Earlz Aug 27 '12 at 20:55
  • With the hash version number you leak information to the attacker about the strength and possible type of the algorithm. It is not much info though, but it would be still better to use some sort of random id as HashingAlgorithmIdentifier instead of versioning it. – inf3rno Jan 11 '20 at 21:58
3

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.

CodesInChaos
  • 11,964
  • 2
  • 40
  • 50
1

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.
tylerl
  • 82,665
  • 26
  • 149
  • 230
  • Keeping weak hashes around until the user in question logs in is a bad idea IMO. If this is a typical website, most users won't log in for a long time if ever. – CodesInChaos Aug 28 '12 at 17:51
  • @CodesInChaos Security is always a trade-off. You can, if you choose, disable accounts with old hashes or reset all the old password or whatever you want, really. But what you can't do is update the hash without having the plaintext password. So whether or not you think this is a good idea, it's what very nearly everybody does. – tylerl Aug 28 '12 at 19:00
  • 1
    You can use the double-hash update technique this post is about. Possibly together with a cleanup on the next login. – CodesInChaos Aug 28 '12 at 19:06
  • @CodesInChaos Yes -- it's an interesting solution, which makes it more interesting that you don't see this solution more in real-world use. I wonder why not. – tylerl Aug 28 '12 at 19:16