Convert old and busted password encryption to something sensible

Question

Given a TOTALLY HYPOTHETICAL scenario in which passwords for over a million accounts in over 200 databases have been stored using 3DES, a key derived from a (single) MD5 hash of a customer-controlled (rarely changed from the default) pass-phrase, a hard-coded IV (same for every account in every database), and a ciphermode of CFB...

Would it be safe enough (and not totally asinine) to wrap a separate hash mechanism (and salt) around the old encrypted value to introduce some concept of security? If so, would it then be possible to determine if the resulting stored-password is the new type or the old type?

My end goal is better password security and the ability to, on a per-user basis, update their password to the new model immediately after they authenticate.

Answer 1

Sysadmins have switched from one password hash algorithm to another many times. There is a standard process for this switch.

The Modular Crypt Format (MCF) is the standard scheme for formatting encrypted passwords, as used by passwd, crypt, etc. (see Why are there $ signs in my passwd file? ). MCF uses a single column to store the password hash algorithm and the hash of the password (etc.). I don't understand why other answers seem to think you need to add a new column -- that seems non-standard and I don't see any benefit over doing it the standard way.

would it then be possible to determine if the resulting stored-password is the new type or the old type?

Yes. If you use MCF for storing the password hash (and why wouldn't you?), it's pretty obvious whether a stored password hash is the new type or the old type.

As explained in Wikipedia: crypt (c) and Wikipedia: passwd, the printable form of new password hashes begins with dollar-digit. Currently the most widely used password hash algorithms produce a printable form that begins with "\$2y\$", "\$5\$", or "\$6\$".

It is likely that you are storing password hashes in a form that never begins with a dollarsign, and so it will be pretty trivial to determine whether it is the old type or the new type.

If someone, in a TOTALLY HYPOTHETICAL scenario, currently stores password hashes in a format incompatible with MCF, perhaps that person could assign "\$0\$" to represent his old hash algorithm, and convert to a MCF by pre-pending that "\$0\$" to the beginning of all his old-style passwords (and tweaking his login-system so that it recognizes that "\$0\$" as indicating the old password hash algorithm). There's a way to gradually make this change a little at a time, in a way that each step leaves the system in a "working" configuration where people can still log in.

As I may have said before at " Do I have to recompute all hashes if I change the work factor in bcrypt? ",

Rehash passwords one at a time, as people log in

Many UNIX-like systems are already set up so the sysadmin can change the "preferred" password algorithm, work factor, and salt length at any time. Later, whenever a user logs in by typing their password, the system updates that user's row in the passwd file to use the system's current "preferred" work factor etc. See a, b, c, d, e, f, g, h, i, j, k, L, m, n, o for how to tweaking the appropriate configuration file in order to set the "preferred" algorithm etc. Typically this involves pluggable authentication modules (PAM).

Many passwd files (or thier equivalent) store, for each user, not only the the salted hash, but also the user-unique salt, the ID of the hashing algorithm used, and the work factor (often dollar-sign delimited). That allows us to gradually switch to a completely different password hash algorithm and salt width.

details:

For example, let's say we want to switch from inadequate amounts of salt and some obsolete hash to bcrypt with a work factor of 11. The sysadmin sets the "preferred" algorithm, salt, etc. to "bcrypt with a work factor of 11", etc.

The next time a user logs in, resets their password, or changes to a new password -- i.e., uses the login or passwd programs -- those programs:

1) Hold on to the plaintext password the user typed in for a few moments.

2) Check the passwd file to see if that user's hash already uses the latest algorithm, work factor, and salt width. If so, continue with 4.

3) Authenticate the user with whatever old, obsolete algorithm the passwd file indicates for that user. If successful, additionally create a unique new salt with the latest salt width. Run that salt, and the plaintext password that we're still holding on to, through "bcrypt with a work factor of 11" (or whatever today's preferred algorithm is) to get the new hash. Update the passwd file for that user with the new hashing algorithm ID, the new work factor, the new salt, and the new hash.

4) Authenticate the user with the shiny new algorithm the passwd file indicates -- the latest algorithm, work factor, and salt width.

5) Then the server must forget the plaintext password.

After a month or two, if some rows of the passwd file still indicate some old, obsolete hashing algorithm and work factor -- i.e., those users haven't logged in for a month or two since you made the change -- you might send them a mail or call them on the phone and ask them nicely to log in soon.

After a few months, if there's still some user whose row of the passwd file still indicate some obsolete algorithm -- i.e., that user hasn't logged in for months -- perhaps you could reset that password and generate a new random unguessable password, more-or-less the same as if that user had forgotten the password and gone through the normal "I forgot my password" process. If the user ever comes back, go through the normal "I forgot my password" process again to reset the password back to whatever the user wants to use.

See "Migrate old md5 passwords to bcrypt passwords" for more discussion of this approach.

EDIT:

Modular Crypt Format is now common enough to be a de facto standard.

However, because it doesn't have an "official" standardization document, some argue that it isn't a "real" standard: "Modular Crypt Format: or, a side note about a standard that isn't".

I recently learned that the LDAP / RFC2307 Hash format does have an official standardization document (RFC2307). According to passlib.hash - Password Hashing Schemes, The LDAP / RFC2307 Hash format "the basic format {SCHEME}HASH has seen widespread adoption in a number of programs."

Answer 2

Start by naming the current password type (perhaps 3des-cfb) and storing that value on each record as an additional column in the database.

You can now start updating existing records. Enumerate over the values in reasonably sized chunks and hash them securely. bcrypt is a good choice. Store the bcrypted value in the database and change the password type for each modified record to something uniquely reflecting the combination of the two (perhaps 3des-cfb+bcrypt).

Now your passwords are at least securely stored, even if it's a bit of a contrived algorithm. Best at this point would be to simply re-hash user passwords on login with just bcrypt, and update the password type to match (e.g., now just bcrypt).

Answer 3

If you encrypt all records with the same key and IV and using 3DES-CFB, the first 8 octets of all fields will be be of the form $3DES(IV) \oplus MSB_{64}(Password)$. If you are using a decent database engine and most passwords are at most eight octets long, decrypting and re-encrypting a million records in a single transaction might actually be feasible. If not, the best option is to add a new field, as suggest by Stephen Touset, but beware that restructuring the database in such fashion (for some engines) might require a transaction that takes longer to complete, compared to just re-encrypting everything in one go.

Edit: Also, please note that you might have to balance the risk that a significant portion of your users, will not log in to your system again (and be prompted to enter a new password that will be stored securely), any time soon, against the cost of re-encrypting everything in one go.

1. Set up a database server on second machine.
2. Create a table on the second database with four fields - username, password salt and passwordhash.
3. Copy the username and password fields from the original database to the new.
4. Get the encryption key and IV, used by the original database.
5. If you intend to use bcrypt for the password hash, check that the iteration parameter is such that you will able to process a million operations in at most days rather than years. If not, abort and forget about this option.
6. Re-encrypt everything in the second database. The hash operation should ideally take three parameters (iteration, application specific label and a pepper) and three inputs (username, password, salt). Generate a random salt for each record.
7. For each record in the old database, if user exists in the new database and the password fields match, copy the salt and passwordhash fields of the new database to old. If not (new user or changed password), re-encrypt on the fly.