Skip to main content

Password Rehash

Posted by evanx on May 1, 2013 at 5:42 AM PDT

We continue our Password Salt adventures with PBKDF2, in order to store multiple revisions of the crypto parameters, and migrate hashes on the fly.

 Password Rehash: The second part of a trilogy, part of "The Enigma Posts"

In the Password Salt prequel, we suggested that the most secure passwords are no passwords, e.g. using Google Login, Facebook Connect, Mozilla Persona or what-have-you. Such an approach is simpler for developers and more convenient for end-users. However for internal enterprise apps, those identity services might not be suitable, so...

In said prequel, we presented an implementation using PBKDF2WithHmacSHA1, with a high number of iterations.

In this article, we cater for multiple revisions of the number of iterations and key size, and migrate hashes to the latest revision when the user logs in.

PBKDF2 recap

Paraphrasing an earlier version OWASP Password Storage Cheat Sheet (before they gone done changed the whole thing, after this series was drafted),

General hashing algorithms (e.g. MD5, SHA) are not recommended for password storage. Instead an algorithm specifically designed for the purpose should be used such as PBKDF2 or scrypt.

As presented in Password Salt, we salt, hash and match our passwords using PBKDF2 as follows.

public class Passwords {
    public static final String ALGORITHM = "PBKDF2WithHmacSHA1";
    public static final int ITERATION_COUNT = 30000;
    public static final int KEY_SIZE = 160;

    public static byte[] hashPassword(char[] password, byte[] salt)
            throws GeneralSecurityException {
        return hashPassword(password, salt, ITERATION_COUNT, KEY_SIZE);
    }

    public static byte[] hashPassword(char[] password, byte[] salt,
            int iterationCount, int keySize) throws GeneralSecurityException {
        PBEKeySpec spec = new PBEKeySpec(password, salt, iterationCount, keySize);
        SecretKeyFactory factory = SecretKeyFactory.getInstance(ALGORITHM);
        return factory.generateSecret(spec).getEncoded();
    }

    public static boolean matches(char[] password, byte[] passwordHash, byte[] salt)
            throws GeneralSecurityException {
        return matches(password, passwordHash, salt, ITERATION_COUNT, KEY_SIZE);
    }

    public static boolean matches(char[] password, byte[] passwordHash, byte[] salt,
            int iterationCount, int keySize) throws GeneralSecurityException {
        return Arrays.equals(passwordHash, hashPassword(password, salt,
                iterationCount, keySize));
    }
}

where we check if the supplied password, and its salt, matches our hash, using the given PBKDF2 parameters.

Measuring time

According to the aforecited earlier version of the OWASP Password Storage Cheat Sheet,

One should measure the time required and make sure that it's as large as possible without providing a significantly noticeable delay when users authenticate.

Let's measure the time required, albeit on our dev machine.

    @Test
    public void testMatchesEffort() throws Exception {
        char[] password = "12345678".toCharArray();
        byte[] saltBytes = PasswordSalts.nextSalt();
        long startMillis = System.currentTimeMillis();
        byte[] hashBytes = Passwords.hashPassword(password, saltBytes, 30000, 160);
        System.out.printf("hash duration (30k, 160bit): %dms\n", Millis.elapsed(startMillis));
        startMillis = System.currentTimeMillis();
        assertTrue(Passwords.matches(password, hashBytes, saltBytes, 30000, 160));
        System.out.printf("matches duration (30k, 160bit): %dms\n", Millis.elapsed(startMillis));
        startMillis = System.currentTimeMillis();
        Passwords.hashPassword(password, saltBytes, 100000, 160);
        System.out.printf("100k hash duration: %dms\n", Millis.elapsed(startMillis));
        startMillis = System.currentTimeMillis();
        Passwords.hashPassword(password, saltBytes, 300000, 160);
        System.out.printf("300k hash duration: %dms\n", Millis.elapsed(startMillis));
        assertFalse(Passwords.matches(password, hashBytes, saltBytes, 30001, 160));
        assertFalse(Passwords.matches(password, hashBytes, saltBytes, 30000, 128));
        assertFalse(Passwords.matches("wrong".toCharArray(),
                hashBytes, saltBytes, 30000, 160));
    }

which prints the duration of the hashing and matching operations, as follows.

hash duration (30k, 160bit): 146ms
matches duration (30k, 160bit): 141ms
100k hash duration: 542ms
300k hash duration: 1711ms

which shows the duration in milliseconds for 30k iterations, and also 10x that, for a key size of 160 bits.

Naturally we expect the duration to be linearly dependent on the number of iterations. Also, as matches() invokes hashPassword(), we expect those durations to be similar.

The above test indicates that iteration counts in the range 30k to 100k take less than 500ms, which might be our chosen time limit. But this is on our dev machine, and we should measure this in production, under varying loads.

Storage

In order to revise the algorithm parameters e.g. if we migrate to a faster host, we need to store these parameters, together with the salt and the password hash, for each user.

We might extend our SQL credential table to include the PBKDF2 parameters as follows.

   LOGIN VARCHAR(100) PRIMARY KEY,
   PASSWORD VARCHAR(32),
   SALT VARCHAR(32),
   PASSWORD_ITERATION_COUNT INTEGER,
   PASSWORD_KEY_SIZE INTEGER,  

In the next sequel we'll consider encrypting the salt, which would require a further field named SALT_IV (for the AES "initialization vector").

But let's try to migrate to salted passwords without changing our database schema, by packing the password hash, salt and parameters into one field to be stored in the PASSWORD column. We can differentiate our legacy hash stored therein by its shorter length, and migrate.

public class PasswordHash {
    private static final byte VERSION = 255;   
    int iterationCount;
    int keySize;
    byte[] hash;
    byte[] salt;
    byte[] iv;

    public PasswordHash(byte[] hash, byte[] salt, byte[] iv,
            int iterationCount, int keySize) {
        this.hash = hash;
        this.salt = salt;
        this.iv = iv;
        this.iterationCount = iterationCount;
        this.keySize = keySize;
    }
    ...

Given a new password and specific algorithm parameters, we generate salt, and hash the password as follows.

    public PasswordHash(char[] password, int iterationCount, int keySize) 
            throws GeneralSecurityException {
        this.iterationCount = iterationCount;
        this.keySize = keySize;
        this.salt = PasswordSalts.nextSalt(); // e.g. random 16 byte array
        this.hash = Passwords.hashPassword(password, salt, iterationCount, keySize);
        this.iv = new byte[0];
    }

We mash the hash et al into a byte array as follows, for storage purposes.

    public byte[] getBytes() throws IOException {
        ByteArrayOutputStream stream = new ByteArrayOutputStream();
        stream.write(VERSION);
        writeObject(new ObjectOutputStream(stream));
        return stream.toByteArray();
    }
                   
    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.writeInt(iterationCount);
        stream.writeShort(keySize);
        if (hash.length > 255) {
            throw new IOException("Hash length not supported");
        }
        stream.write(hash.length);
        stream.write(salt.length);
        stream.write(iv.length);
        stream.write(hash);
        stream.write(salt);
        stream.write(iv);       
        stream.flush();
    }

where we introduce a writeObject() method as per Serializable, for the sake of conformity.

This byte array will be encoded using Base64 and stored in our PASSWORD column in the database.

In order to authenticate a user's password, we unpack the byte array retrieved from the database.

       
    public PasswordHash(byte[] bytes) throws IOException {
        InputStream stream = new ByteArrayInputStream(bytes);
        int version = stream.read();       
        if (version != VERSION) {
            throw new IOException("Version mismatch: " + version);
        }
        readObject(new ObjectInputStream(stream));
    }

    private void readObject(ObjectInputStream stream) throws IOException {
        iterationCount = stream.readInt();
        keySize = stream.readShort();
        hash = new byte[stream.read()];
        salt = new byte[stream.read()];
        iv = new byte[stream.read()];
        stream.read(hash);
        stream.read(salt);
        stream.read(iv);       
    }

We provide a method to authenticate a password against this hash, using its accompanying parameters.

    public boolean matches(char[] password) throws GeneralSecurityException {
        millis = System.currentTimeMillis();
        try {
            return Arrays.equals(hash, Passwords.hashPassword(password, salt, iterationCount, keySize));
        } finally {
            millis = Millis.elapsed(millis);
        }
    }

where we record the time taken to authenticate the password, for monitoring purposes, in order to assess the chosen iterationCount parameter in our production environment.

Testing

Let's test this and see what we end up with.

    @Test
    public void testPasswordHashMinimumKeySize() throws Exception {
        testPasswordHash(30000, 128);
    }
   
    private void testPasswordHash(int iterationCount, int keySize) throws Exception {
        char[] password = "12345678".toCharArray();
        PasswordHash passwordHash = new PasswordHash(password, iterationCount, keySize);
        byte[] hashBytes = passwordHash.getBytes();
        String encodedString = Base64.encode(hashBytes);
        passwordHash = new PasswordHash(hashBytes);
        assertEquals("iterationCount", iterationCount, passwordHash.getIterationCount());
        assertEquals("keySize", keySize, passwordHash.getKeySize());
        assertTrue(PasswordHash.verifyBytes(hashBytes));
        assertFalse(passwordHash.matches("wrong".toCharArray()));
        assertTrue(passwordHash.matches(password));
        System.out.printf("iterationCount: %d\n", iterationCount);
        System.out.printf("keySize: %d\n", keySize);
        System.out.printf("byte array length: %d\n", hashBytes.length);
        System.out.printf("encoded string: %s\n", encodedString);
        System.out.printf("encoded length: %d\n", encodedString.length());
        System.out.printf("millis: %d\n", passwordHash.getMillis());
    }

which prints,

iterationCount: 30000
keySize: 128
byte array length: 48
encoded string: /6ztAAV3KQAAdTAAgBAQADaOT6lY7axaXF56GJvOPjKMrHGQhyihJQWVzeqjyK+6
encoded length: 64
millis: 137ms

We note the array length is 48, which should be larger than our legacy hashes, so we can differentiate those by their shorter length.

Seeing that the Base64-encoded length is 64 characters, our PASSWORD column capacity should be altered to VARCHAR(64) at least.

Migration

We provide a static method to confirm that the bytes are what our PasswordHash constructor would expect.

public class PasswordHash {
    ...
    public static boolean verifyBytes(byte[] bytes) {
        return bytes.length >= 48;
    }  
}

We assume that the length of our legacy unsalted password hashes is less than that of our PasswordHash serialized array, and so use the above method to differentiate those.

Finally we migrate to salty passwords, on the fly, as follows.

    public boolean matches(String user, char[] password, byte[] packedBytes) throws Exception {
        if (PasswordHash.verifyBytes(packedBytes)) {
            PasswordHash passwordHash = new PasswordHash(packedBytes);
            if (passwordHash.matches(password)) {
                monitor(passwordHash.getMillis());
                if (passwordHash.getIterationCount() != Passwords.ITERATION_COUNT
                        || passwordHash.getKeySize() != Passwords.KEY_SIZE) {
                    passwordHash = new PasswordHash(password,
                            Passwords.ITERATION_COUNT, Passwords.KEY_SIZE);
                    persistRevisedPasswordHash(user, passwordHash.getBytes());
                }
                return true;
            }
            return false;
        }
        if (matchesUnsalted(password, packedBytes)) {
            packedBytes = PackedPasswords.hashPassword(password);
            persistRevisedPasswordHash(user, packedBytes);
            return true;
        }
        return false;
    }

where if the password is correct, but not at the latest revision, or still a legacy unsalted hash, we take the opportunity of migrating that user's password hash to the latest salty non-cracker.

As PCI compliance requires passwords to be changed every 90 days, admittedly it's not really necessary to migrate existing passwords to higher parameters, because a new password hash will be created soon enough :)

Finally, we monitor() the time taken to authenticate the password, e.g. to log hints to revise our iteration count. An upcoming article in the Timestamped series will illustrate how we can gather time-series stats. We will record the sample size, minumum, maximum, average, and distribution of the duration of the hashing operation, for different iteration counts, aggregated by hour and day. Of course, this must be nicely graphed so we can visualise the state of affairs, at a quick glance :)

Salt cipher

The aforementioned version of the OWASP cheat sheet suggested "salt isolation" as follows,

An additional password storage defense mechanism involves storing the salt in a different location than the password hash.

Use of the server's filesystem is one commonly used mechanism for salt isolation, assuming the password hashes are stored in a different location such as a database.

As discussed in the prequel, it'd be simpler to encrypt the salt in the database, and store just the salt-encrypting key on the filesystem.

Indeed, the iv field of PasswordHash is an "initialization vector" as required for AES encryption of the salt. In the finale of this trilogy, we'll present that aspect. However, is "salt isolation" really necessary? Please share your opinions in the comments section below :)

Summary

While SHA-2 is recommended these days for general hashing, we should use computationally expensive algorithms for password hashing, so that the passwords are harder to crack.

In the prequel, we presented an implementation using PBKDF2WithHmacSHA1, with a high number of iterations.

Since the hashing operation should take as long as we are willing to make the user wait, the algorithm parameters must be tweaked according to our host's CPU.

We should store of the number of iterations and key size, to enable revision thereof.

We decide to encapsulate the hash, salt and parameters into a PasswordHash object. We serialize this object into a byte array, and encode with Base64 to store in our SQL database. Migration from legacy hashes is somewhat simplied thereby.

We can migrate to revised hashes when the user logs in and their password is thus on hand. Having said that, and seeing that PCI compliance requires passwords to be changed every 90 days, it is probably not necessary to migrate existing passwords to higher parameters when a new password hash will be created soon enough.

Coming up

In "Password Cipher," the finale of this sub-trilogy, we'll encrypt the password salt in our database, using... password-based encryption :)

Also, an upcoming article in the Timestamped series will illustrate how we can gather time-series stats, including the time taken to authenticate the password. Such stats are required to revise our iteration count.

We really should try out bcrypt and scrypt, and hopefully we will :)

Resources

https://github.com/evanx/vellum/wiki - see PasswordHash.java.

@evanxsummers