Upgrading existing password hashes

Still using MD5 or SHA-1 to store user passwords and want to gracefully migrate to e.g. bcrypt? Want to do it properly to protect all passwords in the database? Here's how.

One of the biggest e-commerce sites in the Czech Republic, Mall.cz, has suffered a breach. An unknown attacker has accessed over 750 thousand user accounts, has uploaded them to a Czech file sharing service Ulož.to (“Save it”), and posted the link to Pastebin on July 27th. The company has announced the incident in a quite amazing blog post (in Czech, though), has reset customers' passwords and emailed them to say that they have to create a new password if they want to sign in. The Ulož.to URL says that file is not available anymore but this Czech magazine Lupa.cz has obtained a copy (in Czech). Lupa says the file contains 750 thousand emails and cleartext passwords. Some of the customers have also their phone number listed.

It's not yet known why the file contains cleartext passwords, Mall was supposedly storing hashes:

We've been securing passwords using SHA1 with unique salt since November 2012, and since October 2016 we use bcrypt, one of the strongest hashing functions, to protect login credentials. Until 2012, these were hashed using MD5 which is not considered secure nowadays. Most of the cracked passwords are from around that time when we were using MD5. That's why we have changed passwords for these older accounts and automatically converted them to use bcrypt, the newest hashing function, which we currently use to protect login credentials for all accounts.

Let's forget bcrypt was published in 1999 and that Mall.cz has earlier disclosed just SHA-1 and bcrypt, but we still don't know how and when exactly the passwords hashed with MD5 were upgraded to more secure bcrypt hashes, if at all. In the comments below their blog post Mall says they have been re-hashing passwords upon successful sign-ins.

So how can we do it better to also protect weakly-hashed passwords of inactive users? We've done that a few years ago in Slevomat, the company I was working for at that time. If IKEA had created an instructions for that it would surely look like this:

Hashing upgrade

First things first, what's an unsuitable password hashing algorithm? It's all the MD5, SHA-1, SHA-2, SHA-3 in any variant. No matter if salted or not, or if stretched with several thousand iterations or just one function call. To store user passwords you should use one of these: Argon2i, bcrypt, scrypt, or PBKDF2. They are relatively slow so that it takes crackers a lot of time to crack the passwords. And time is money, right.

I should mention this article is not about an incident response. If you had a database leak (which you've noticed) you need to reset passwords for all your users. Store their new passwords using the “new” hash then.

If you're using PHP then hash passwords with password_hash(..., PASSWORD_DEFAULT) and verify them with password_verify(). The PASSWORD_DEFAULT “algorithm” currently means bcrypt, but in the future it can be changed to e.g. Argon2i. If this change happens, you'll be able to verify hashes created today too. The algorithm is specified only when creating hashes, and is stored in the resulting hash respectively it's a part of the output from password_hash().

You have these options if you want to upgrade password hashing for already registered users:

1. Reset passwords for all users so they have to create a new password which will be hashed with the new hash function. Not the best idea, users will be unhappy and bothered, and will ask legitimate questions why you haven't secured their passwords much earlier. You can reset passwords in an application used by a few hundred employees but not in a service with public sign-ups.
2. You can “re-hash” the password after a successful login, at that moment when the application knows the cleartext password so you can hash it with the new algorithm. This is much nicer for users but there will be some old hashes remaining in the database as users who have not signed in since the change won't get their password re-hashed. This also applies to users with “permanent login” or similar feature activated. Seems that Mall has upgraded their hashes using this method.
3. Re-hash all the old hashes with a new hash at once using a batch job or similar, and when verifying a password, hash it with the old function first and only then send it for a verification using the new hash function. If the password matches do a clean up: hash the password using just the new hash and store it. The first step if this method doesn't require any action from the user so it will protect passwords even for users who have not logged in for a while.
4. Try and crack all the passwords and hash the cracked ones with the new algorithm. Nope, don't do that. You can't possibly justify attacking users' passwords, it might easily become a PRdisaster. And because you'd need to transfer hashes out of the system and keep cracked cleartext passwords elsewhere for some time, it might quickly escalate into a security problem too. Your job is to protect passwords, not attack them or possibly leak them. Just don't.

Let's dive deeper into the third method. I'll use some PHP in the examples below, but the principle stays the same for other languages and environments (this is how you do it in Django). The code here is just to illustrate the process, don't copy and paste it, this ain't no Stack Overflow.

Database changes

Make sure the new hash fits into your password column, it's recommended to set it to VARCHAR(255) or similar. 255 chars would be a good choice for future algorithms too.

You'll need a new column to store the password hashing type for that user. The execution time of the re-hashing script (more on that later) might even be a few days, so there will be both the new hashes and the old hashes in the database. The login process needs to accept all of them. Let's name the new column type. Don't set it NOT NULL, the NULL value will imply the old hash.

If your old hashing uses a unique salt per user (static salt, same for each user, is not a salt per se), add another column old_salt to store the “old” salt.

Actually, you don't need to alter the users table, you can put the type and the old salt into one column with the hash, if you separate it with a double colon or a dollar sign. You can then parse it out when processing the hash. I'll use separate columns for the sake of simplicity.

The re-hashing script

The re-hashing itself is done by a script upgrading all the passwords at once. It will fetch say 1000 rows with type IS NULL and will do this with each of them:

1. Calculate the new hash by “re-hashing” the old one:

   $newHash = password_hash($row->password, PASSWORD_DEFAULT)

2. If the old hash uses a salt, store it to e.g. $oldSalt
3. Run a table UPDATE and store $newHash into the password column (and $oldSalt into old_salt, if used), set type to 1, but all this just in case the type is NULL, otherwise the password changed by the user in the time between the fetch and the update would get overwritten

The code would look something like this:

$rows = $db->query('SELECT ... FROM ... WHERE type IS NULL LIMIT 1000');

foreach ($rows as $row) {
    $newHash = password_hash($row->password, PASSWORD_DEFAULT);
    $oldSalt = ...;
    $db->query('UPDATE ... SET password = ?, old_salt = ?, type = 1
        WHERE username = ? AND type IS NULL',
        $newHash,
        $oldSalt,
        $row->username
    );
}

I'd recommend running the script from the command line. The execution time of this script could be quite long, especially with a lot of users. It might also crash for whatever reason so you'll have to run it again. That's fine, the script will avoid already re-hashed passwords.

Before executing the script we need to update the login to use the new hash, if available.

Login changes

There will be a (new) hash of the original (old) hash stored in the database table, so we need to first hash the user-entered password with the old hashing function before passing it to the verification function which needs to know about the old hash too, otherwise some users might not be able to log in until their password is re-hashed.

We'll use the type column to decide how to verify the password. Don't run the verification using the “new hash over the old one” first, and then the old one if it fails. There would be a performance penalty involved, so just use the column. It's okay if the hashing type is known because you always have to assume the enemy knows the system anyway.

This is the main part of the code:

$row = $db->query('SELECT ... FROM ... WHERE username = ?', $_POST['username']);

switch ($row->type) {
    case null:  // old hash
        $verified = hash_equals($row->password, sha1($row->old_salt . $_POST['password']));
        break;
    case 1:  // new hash over the old one
        $verified = password_verify(sha1($row->old_salt . $_POST['password']), $row->password);
        break;
    default:
        $verified = false;
        break;
}

You can omit the $row->old_salt if the old hash doesn't need a salt. The timing attack safe string comparison function hash_equals() is available since PHP 5.6. If you're using anything older just update. In the worst case, you can just strict-compare using $row->password === sha1(...), that applies to other languages too.

This hashing function “stacking” is not a fully cryptographically clear solution, and generally is not recommended, nor well-researched. But in this particular case it's much better than to use weak hashes for passwords of users which won't sign in for a long time.

Storing a clear new hash

The application knows the cleartext password after a successful login, so we can hash it with the “clear” new hash and drop this cryptographical imperfection. We'll use the type column again, this time to disable any pre-hashing before calling password_verify(). Definitely don't verify the password using the “try the new hash first, then the new over the old, then the old hash” strategy, otherwise it would be possible to sign in using just a hash found in a database leak, as David Grudl correctly pointed out (in Czech).

Let's create a function which will save the new hash, set a new type (that's 2 for a “clear” hash), and possibly clear the old salt as it's not needed anymore:

function saveNewHash($username, $password)
{
    $db->query('UPDATE ... SET password = ? , old_salt = NULL, type = 2 WHERE username = ?',
        password_hash($password, PASSWORD_DEFAULT),
        $username
    );
}

We'll call this function after a successful verification using the new + old hash. We can also call it after the password has been verified using just the old hash, it doesn't really matter, we'll just do the work instead of the re-hashing script. We'll add the case 2 statements for password verification using just the new hash:

$row = $db->query('SELECT ... FROM ... WHERE username = ?', $_POST['username']);

switch ($row->type) {
    case null:  // old hash
        $verified = hash_equals($row->password, sha1($row->old_salt . $_POST['password']));
        if ($verified) {
            saveNewHash($_POST['username'], $_POST['password']);
        }
        break;
    case 1:  // new hash over the old one
        $verified = password_verify(sha1($row->old_salt . $_POST['password']), $row->password);
        if ($verified) {
            saveNewHash($_POST['username'], $_POST['password']);
        }
        break;
    case 2:  // just the new hash
        $verified = password_verify($_POST['password'], $row->password);
        break;
    default:
        $verified = false;
        break;
}

Script execution

We can now execute the wonderful re-hashing script, finally. I'd recommend to properly test it before, and possibly create a backup of the users table, in case something goes wrong. After the script has successfully finished, you can remove the case null statements from the login code, the old hashes should be gone. You can check it with SELECT COUNT(*) ... WHERE type IS NULL, the result should be zero rows.

Now, if you've created a backup, don't forget to securely delete it. This should be done for all other regular backups too, shred them, or remove the old hashes from within. Backups are quite often the source of a leak of the old weakly hashed passwords.

What's next

Don't forget to store just the new hash and set the type to “just new” (we've been using type = 2 for that) during registration or when changing passwords (also the forgotten ones). So basically what the saveNewHash($username, $password) does.

Using a strong (and relatively slow) hashing function won't prevent password cracking attempts, but it will slow them down beyond feasible. Although the attacker will crack weak passwords like passwordquite fast (it's a low-hanging fruit), so it might be a good idea to make cracking virtually impossible. Some people recommend using a pepper (salt and pepper, get it?), an additional static “salt” same for each user. The odds are quite low that the attacker will have access to both the database and the pepper to allow for cracking.

Forget pepper. Password hashing functions are not designed to use it, and there's almost no reasonable research on pepper. You can achieve the same effect by encrypting hashes (not passwords), that's a cryptographically sound operation. But that's for next time.

I've deliberately left out transparent hashing parameter changes and bcrypt-to-Argon2i upgrades. Currently, using bcrypt is still alright, and passwords will be protected even if you use the default cost(which should be at least 10). You can start using Argon2i when it's set as PASSWORD_DEFAULT in PHP. Then you can migrate using the second method, that's re-hashing passwords after a successful login. But that's also for some other time.

Please, keep your users' passwords safe.