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 (seems they have been cracked), 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: bcrypt, Argon2 (the Argon2id or the Argon2i variant but only if you want password hashing to take more than one second, for anything faster use 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 something else. 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, it's a part of the output from password_hash(), respectively. See for example the result of calling password_hash('foo', PASSWORD_DEFAULT) (which is the same output as from password_hash('foo', PASSWORD_BCRYPT) currently, but the value of PASSWORD_DEFAULT will change in the future):

 bcrypt (2y)
 ┌┐ cost (2¹⁰ = 1024 rounds)
 ││ ┌┐
$2y$10$7REcgj13ZZTW9XSYGWfZVODMB0uIPn3c2jZmse1kjz7LHGzTdUnGm
       └────────────────────┘└─────────────────────────────┘
            128-bit salt              184-bit hash
             both encoded as non-standard Base64

The output also includes a cryptographic salt, automatically and correctly generated by password_hash(). You don't need to add another salt manually and you should not even do it, because you may screw up the algorithm. Bcrypt implementation in PHP truncates the password to a maximum length of 72 characters (and that's fine), so if you'd prefix the password with 80 characters of salt, then you wouldn't even need the password to sign in. Don't bother with salt, password_hash() and password_verify() will take care of it for you.

Argon2i (PASSWORD_ARGON2I) is available since PHP 7.2, and Argon2id (PASSWORD_ARGON2ID), the recommended variant, is available since PHP 7.3. The output from password_hash(..., PASSWORD_ARGON2ID):

  algo.   ver.   parameters
┌───────┐ ┌──┐ ┌────────────┐
$argon2id$v=19$m=1024,t=2,p=2$<128-bit salt>$<256-bit hash>

Both salt and hash are Base64-encoded. Version number v is 1.3 (the latest Argon2 version at the time of PHP 7.3 development) represented as dec 19, hexdec 0x13. The parameters:

• A memory cost m that defines memory usage of the algorithm (in kilobytes, from 8p to 2³² – 1)
• A time cost t that defines the execution time of the algorithm and the number of iterations (from 1 to 2³² – 1)
• And a parallelism factor p, which defines the number of parallel threads (from 1 to 16777215)

The defaults in PHP are as displayed: memory cost 1024 kB, 2 iterations, 2 threads. The salt should be generated by password_hash() in this case as well.

Let's go back to upgrading password hashing for already registered users. You have these options if you want to do that:

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 PR disaster. 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.

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 password quite 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 and algorithm changes using password_needs_rehash(). Currently, using bcrypt is still alright, and passwords will be protected even if you use the default cost. It should be at least 10, will be 12 starting with PHP 8.4) and you can then migrate using the second method, that's re-hashing passwords after a successful login. But that's also for some other time.

For authentication, according to Jeremi and Steve (both were on the Password Hashing Competition panel), bcrypt is still stronger than Argon2, especially if you want to hash a password in less than a second.

Please, keep your users' passwords safe.

---

Recommended reading

• Cracking passwords, or why use password_hash(), my talk about password cracking and secure storage, with a lot of detailed notes
• How to Safely Store Your Users' Passwords in 2016 by Scott Arciszewski, applies in 2018, too