Introduction

A secure password based authentication system does not store the password directly, but instead stores a salt and a digest (hash) of the password produced by a key derivation function.

When the user needs to be authenticated again, the system creates a new digest of the plaintext password, using the same key derivation function and parameters as the stored password, and compares the new digest to the old one.

Less secure systems do not use a salt, and instead, simply store a hash of the passwords. While this displays a security intent, it is inadequate because an attacker with access to the database will be able to decrypt some proportion of the passwords.

Many secure systems do not have a plan or method to update key derivation functions or their parameters and, as a result, become less secure over time as attacker resources increase and are rarely designed to be quickly updated if/when a flaw is discovered.

This post details how to set up an upgradeable password system. While the focus is on a web system, this method can be used for any kind of client/server system.

Data Details

First digest should be created by a strong key derivation function such as Scrypt, Bcrypt, or Pbkdf2. With increases in computational power, it is critical to use functions with tunable work factors and update them frequently. SHA1 and MD5SUM hashes of the password are not acceptable.

In addition to the salt and digest, store a digest code, which identifies the digest method, as well as any required parameters for the particular digest. Bcrypt, for instance, requires a work factor parameter, whereas Pbkdf2 requires a work factor as well as a pseudorandom generator (generally sha1) and Scrypt has three parameters. Given the variety, it is useful to encode the parameters so they fit in a single field. Comma separated name=value pairs work well here.

SQL Schema

Assuming you already have a password field, you would need to add a salt, if you are not already using them, as well as the digest code and parameters. An SQL schema would look something like this:

password char(256)
salt char(64)
digest_code char(10)
digest_params char(50)

This would probably work well for whatever digest mechanism is currently in use. However, upgrading may require some of the field sizes to change so, for long term evolution, it would be simpler and less brittle to allocate a text field to a single value like so:

password text

and encode the content in Modular Crypt Format (MCF).

Modular Crypt Format is a format used in unix password files that allows each password to identify the digest scheme used to generate it. Effectively, this allows each password to use a different scheme and encode all the required regeneration parameters, which also allows them to be independently upgradeable. The same mechanism can be used in a web application.

In the /etc/password file, the password field consists of four components, separated by a ‘$’:

* identifier - Unique code assigned to the scheme used for *that* entry.

* scheme parameters - Scheme parameters for the scheme.
  Multiple values will need to be encoded in some fashion.

* salt - random value added to the password to thwart dictionary attacks.

* digest - value produced by key derivation function named by identifier.

While it generally violates good design to shove multiple components into a single field, this is one area where good design actually calls for it; as far the database and most of the application are concerned, passwords are an opaque field, consumed and generated by a small subsystem, so there is no reason to break it out if the subsystem does not require it.

Web Setup

In the application, use a list of digests with a struct like:

digests = []struct{
    name string
    params []struct{Name:string, Value String}
}

Once a digest is added to the list, and used in production, it is never removed while there are dependent password records in the database. New digests are added to the front of the list.

The first digest on the list is used to create new passwords, using the current parameters, and the password is stored. It is important to store the parameters with the password so that the defaults can be later updated without invalidating stored passwords.

When a password needs to be verified, the following steps are used:

1. Lookup the password record by user id

2. Use the digest_code or identifier value in the password record to find the corresponding digest

3. Use the digest (and the stored parameters) to generate a new digest of the plaintext.

4. Compare them for authentication. At this point, some will claim that the comparison should be immunized against timing attacks. While there is no harm in doing so, there is also no real benefit or danger in not.

The extra level of indirection during authentication provides two major benefits.

1. The system can simultaneously contain passwords created with different digest schemes or different parameters.
2. Users can be seamlessly upgraded to new digests very easily.

Upgrades:

Since upgrades require a user password, they can either happen implicitly when the user signs in or explicitly by invalidating user passwords and forcing them to all change passwords.

For simplicity and friendliness, we will assume the implicit method: After every successful user authentication, a comparison is made between the current password identifier and the user password identifier. If they differ, an upgrade is required. Similarly, if the schemes correspond but have different parameters, an uprade must performed. Of course, the assumption here is that the scheme configuration changes denote a more secure system, not less. There are no provisions for security downgrades, inadvertent or intentional.

If an upgrade is required, the user’s plaintext password is used to create a new digest, using a new salt, and stored back in the database.

Implementation

My mcf library in Go, implements all the ideas discussed here and allows Go based services to start off secure and remain that way over time. It is my hope that others will re-implement my mcf library for other languages. The code is released under an open source license and I encourage all implementers to review it.

Conclusion

The authentication subsystem of any public web application must be able to withstand attacks from all over the world. Making correct design decisions for such a critical part of the infrastructure requires careful thought and the use of well understood systems that work. The mcf system outlined here, in conjuction with good overall security, ensures that the authentication component will keep up with advances in computation and new threats.