Moving old passwords to new hashing algorithm?

Question

I'm switching a site over to rails. It's quite a large site with 50k+ users. The problem is, the existing password hashing method is extremely weak. I have two options:

1) Switch to a new algorithm, generate random passwords for everyone and then email them those passwords and require the change immediately after

2) Implement new algorithm but use the the old one before and then hash the result. For example:

Password: abcdef =Algorithm 1=> xj31ndn =Algorithm 2=> $21aafadsada214

Any new passwords would need to go through the original algorithm (md5) and then have the result of that hashed if that makes any sense? Is there any disadvantage to this?

Answer 1

Normally it's not necessary to reset the passwords, one can just wait until the user logs in the next time.

1. First try to verify the entered password with the new algorithm. New passwords and already converted passwords will not take longer for verification then.
2. If it does not match, compare it with the old hash algorithm.
3. Should the old hash value match, then you can calculate and store the new hash, since you know the password then.

Every password-storing-system must have the option to switch to a better hash algorithm, your problem is not a one-time migration problem. Good password hash algorithms like BCrypt have a cost factor, from time to time you have to increase this cost factor (because of faster hardware), then you need the exact same procedure as you need for the migration.

Your option 2 with hashing the old hash is a good thing, if your first algorithm is really weak, and you want to give more protection immediately. In this case you can calculate a double-hash and replace the old hash in the database with the new double-hash.

$newHashToStoreInTheDb = new_hash($oldHashFromDb)

You should also mark this password-hash (see why), so you can recognize it as double-hash. This can be done in a separate database field, or you can include your own signature. Modern password hash functions also include a signature of the algorithm, so that they can upgrade to newer algorithms, and still can verify older hashes. The example shows the signature of a BCrypt hash:

$2y$10$nOUIs5kJ7naTuTFkBy1veuK0kSxUFXfuaOKdOKf9xYT0KKIGSJwFa
___
 |
 signature of hash-algorithm = 2y = BCrypt

The verification would run like this:

1. Decide whether it is a double-hash.
2. If it is a new hash, call the new hash-function to verify the entered password, and you are done.
3. If it is a double-hash, compare it with the double-hash algorithm new_hash(old_hash($password)).
4. Should the double-hash value match, then you can calculate and store the new hash.

Answer 2

The simplest solution is probably to add a "password hash type" column to the database. Set it initially to "old"; when a user logs in, re-hash the password using the new algorithm and set the database type to "new".

A variant of this method is to store the hash type as part of the hash string. This works just as well, as long as you can unambiguously tell the different hash formats apart, and has the advantage that you can also include any other needed parameters (such as the salt and the work factor for key stretching) in the same string without having to add extra fields for each to your database.

For example, this is the approach typically used by modern Unix crypt(3) implementations (and the corresponding functions in various high-level languages like PHP): a classic DES-based (and horribly weak) password hash would look something like abJnggxhB/yWI, while a (slightly) more modern hash might look like $1$z75qouSC$nNVPAk1FTd0yVd62S3sjR1, where 1 specified the hashing method, z75qouSC is the salt and nNVPAk1FTd0yVd62S3sjR1 the actual hash, and the delimiter $ is chosen because it cannot appear in an old-style DES hash.

---

The method you suggest, where the new hashes are calculated as:

 hash = new_hash( old_hash( password ) )

can be useful in some cases, since it allows all existing records to be updated without having to wait for users to log in. However, it's only safe if the old hash function preserves enough of the entropy in the passwords.

For example, even a fairly old and weak cryptographic hash function, like unsalted MD5, would be good enough, since its output depends on the entire input and has up to 128 bits of entropy, which is more than almost any password will have (and more than enough to withstand a brute force attack, anyway). On the other hand, trying to apply this construction using the old DES-based crypt(3) function as the old hash would be disastrous, since old crypt(3) would ignore all but the first 8 characters of each password (as well as the most significant bits of even those characters).