Sunday, September 2, 2012

Password Hashing Best Practices

With recent events all over the news about website passwords hacking (Blizzard, Yahoo, LinkedIn, Sony and there are probably others we have yet to hear about) its time to refresh password encryption/hashing best practices.

So, what is the reason you'd like to keep passwords in your user database? 

If you care about the password being tough to guess, you can always validate, check 8-10 minimum characters, check at least one capital and one lower case and even throw in a number or a symbol, but I've yet to see a good reason to keep the password in any way other than hashing. If you'd like to implement the "forgot password" feature, you don't need the password for that, you can always create a change password link and mail it to the user.

So what are password hashing? is it secured? If done properly, they are as secure as it can be.

Hashing is an algorithm that maps a dataset into a predefined length dataset in one direction only as opposed to encoding/encrypting, its impossible to decode or decrypt the resulting dataset back to the original dataset, common hashing functions are the SHA group and Message-Digest group, such as MD4, MD5, MD6.

When you hash a password you'll get a byte array that you can compare to the stored byte array from the previously set password in the database.

But its not all roses, hashing has its own set of security vulnerabilities, dictionary attacks, rainbow tables, brute force attacks, timing attacks, luckily, most of them can be solved pretty easily with a little bit of salt and for those problems that can't, PBKDF2 was invented.

The document about PBKDF2, called PKCS #5 v2.0 was written at March 1999 and was turned to RFC-2898 at September 2000, about a year and half later, which makes it even more surprising that so many breeches are caught in the news even now.

Since then two more significant password derivative functions were created, bcrypt which is based on blowfish (as opposed to SHA1 in PBKDF1/2) and scrypt, which was designed to resist implementation on cheap hardware by using more resources, you can find both of these implementations in the CryptSharp library, however this article is more focused on the framework's implementation, I felt the need to bring those two additional algorithms for completeness.

scrypt documentation has an estimation for cracking 1 password on each algorithm:

Its important to note that if you're working with US Federal Government that SHA is FIPS approved and PBKDF2 is a NIST Standard.
So what is salt?

Salt is adding random bits of information to the hashing process, making the output of the same password different, according to the documentation, the salt should be at least 64 bits, or 8 bytes, I've seen many people going overboard and recommending 256bit salt, in my honest opinion 232 is sufficient for most uses.

The salt is stored with the password and when you authenticate the user you get the stored salt and hash the entered password with it, this way you'll always get the same result, you shouldn't use the same salt for multiple passwords.

Its very important to use cryptographic strength random generator, suppose we have this code:

Random rnd1 = new Random(0);
Random rnd2 = new Random(0);
byte[] bytes1 = new byte[40];
byte[] bytes2 = new byte[40];

//On my machine and I guess on yours, produces similar results.
Console.WriteLine("1st " + BitConverter.ToString(bytes1).Replace("-", ""));
Console.WriteLine("2nd " + BitConverter.ToString(bytes2).Replace("-", ""));

If you execute it, you'll get the same results for both bytes1 and bytes2.

This is why we use RNGCryptoServiceProvider for anything related to cryptography.

If you need to get a truely random integer from the above class, a function such as this might do the trick:

private static int Random(int min, int max)
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();

    byte[] intbytes = new byte[4];
    int rndval = BitConverter.ToInt32(intbytes, 0);
    int range = max - min;
    return Math.Abs( (rndval % range)) + min;

But even salting your password is not secure enough, PBKDF2 was written to address some of the vulnerabilites, it does so by taking the salt, the password and a number of iterations to do it again and again, slowing down the process of getting the hash but not slow enough to affect the system, so if hashing it once takes 1ms, and now it takes 10ms, instead of trying to brute force 1000 passwords a second, you can only do a 100. its all a matter of choice, CPU, traffic etc' in your system, the minimum, recommended iterations at the year 2000 was 1000, so you should use larger numbers. You can make it a random number and store it with the salt to alleviate the rainbow tables attack, btw, iOS uses 10,000 iterations.

Here's an example of a user entity:

class User
    public string Username {get;set;}
    public byte[] Salt {get;set;}
    public int Iterations {get;set;}
    public byte[] Password {get;set;}

Keith Brown wrote a C# implementation for PBKDF2, he used SHA256 instead of SHA1 specified in the standard, I've modified it a bit so you can choose your own hashing function.

// implementation of PKCS#5 v2.0
// Password Based Key Derivation Function 2
// For the HMAC function, see RFC 2104
// Source: Keith Brown -
class PBKDF2
    // SHA-256 has a 512-bit block size and gives a 256-bit output
    const int BLOCK_SIZE_IN_BYTES = 64;
    const byte IPAD = 0x36;
    const byte OPAD = 0x5C;

    public static byte[] SHA1GetBytes(byte[] password, byte[] salt, int iterations, int howManyBytes)
        return GetBytes(new SHA1Managed(), password, salt, iterations, howManyBytes);

    public static byte[] GetBytes(HashAlgorithm hashAlgo, byte[] password,
        byte[] salt, int iterations, int howManyBytes)
        HashAlgorithm innerHash = hashAlgo;
        HashAlgorithm outerHash = hashAlgo;

        var HASH_SIZE_IN_BYTES = (innerHash.HashSize/8);

        // round up
        uint cBlocks = (uint)((howManyBytes +

        // seed for the pseudo-random fcn: salt + block index
        byte[] saltAndIndex = new byte[salt.Length + 4];
        Array.Copy(salt, 0, saltAndIndex, 0, salt.Length);

        byte[] output = new byte[cBlocks * HASH_SIZE_IN_BYTES];
        int outputOffset = 0;


        // HMAC says the key must be hashed or padded with zeros
        // so it fits into a single block of the hash in use
        if (password.Length > BLOCK_SIZE_IN_BYTES)
            password = innerHash.ComputeHash(password);
        byte[] key = new byte[BLOCK_SIZE_IN_BYTES];
        Array.Copy(password, 0, key, 0, password.Length);

        byte[] InnerKey = new byte[BLOCK_SIZE_IN_BYTES];
        byte[] OuterKey = new byte[BLOCK_SIZE_IN_BYTES];
        for (int i = 0; i < BLOCK_SIZE_IN_BYTES; ++i)
            InnerKey[i] = (byte)(key[i] ^ IPAD);
            OuterKey[i] = (byte)(key[i] ^ OPAD);

        // for each block of desired output
        for (int iBlock = 0; iBlock < cBlocks; ++iBlock)
            // seed HMAC with salt & block index
            _incrementBigEndianIndex(saltAndIndex, salt.Length);
            byte[] U = saltAndIndex;

            for (int i = 0; i < iterations; ++i)
                // simple implementation of HMAC-SHA-256
                innerHash.TransformBlock(InnerKey, 0,
                    BLOCK_SIZE_IN_BYTES, InnerKey, 0);
                innerHash.TransformFinalBlock(U, 0, U.Length);

                byte[] temp = innerHash.Hash;

                outerHash.TransformBlock(OuterKey, 0,
                    BLOCK_SIZE_IN_BYTES, OuterKey, 0);
                outerHash.TransformFinalBlock(temp, 0, temp.Length);

                U = outerHash.Hash; // U = result of HMAC

                // xor result into output buffer
                _xorByteArray(U, 0, HASH_SIZE_IN_BYTES,
                    output, outputOffset);
            outputOffset += HASH_SIZE_IN_BYTES;
        byte[] result = new byte[howManyBytes];
        Array.Copy(output, 0, result, 0, howManyBytes);
        return result;
    // treat the four bytes starting at buf[offset]
    // as a big endian integer, and increment it
    static void _incrementBigEndianIndex(byte[] buf, int offset)
            if (0 == ++buf[offset + 3])
                if (0 == ++buf[offset + 2])
                    if (0 == ++buf[offset + 1])
                        if (0 == ++buf[offset + 0])
                            throw new OverflowException();
    static void _xorByteArray(byte[] src,
        int srcOffset, int cb, byte[] dest, int destOffset)
        int end = checked(srcOffset + cb);
        while (srcOffset != end)
            dest[destOffset] ^= src[srcOffset];

Here's an implementation example of PBKDF1 according to the documentation, its included only for reference and should not be used, the principle in both versions is similar, hash the password + salt, then hash the result for a number of iterations, it is possible to use this function  with MD5, if you need it for compatibility.

public static byte[] SHA1GetBytes(byte[] password,
    byte[] salt, int iterations, int howManyBytes)
    return ComputePBKDF1(new SHA1Managed(), password, salt, iterations, howManyBytes);

private static byte[] ComputePBKDF1(HashAlgorithm hashAlgo, byte[] password, byte[] salt, int iterations, int howManyBytes)
    if (howManyBytes > (hashAlgo.HashSize/8))
        throw new ArgumentOutOfRangeException("howManyBytes should be smaller than " + (hashAlgo.HashSize/8).ToString());
    byte[] passandsalt = new byte[password.Length + salt.Length];
    Array.Copy(password, 0, passandsalt, 0, password.Length);
    Array.Copy(salt, 0, passandsalt, password.Length, salt.Length);

    var hash = hashAlgo.ComputeHash(passandsalt);

    for (int i = 1; i < iterations; i++)
        hash = hashAlgo.ComputeHash(hash);

    byte[] hashsubset = new byte[howManyBytes];
    Array.Copy(hash, hashsubset, howManyBytes);
    return hashsubset;

There's also .NET's implementation of PBKDF1 and PBKDF2, called PasswordDeriveBytes and Rfc2898DeriveBytes respectively.

Which ever security policy you decide to use, when you detect a breech to your database and its extent, its a good idea to email a notice to the users affected by the attack and recommend them to change their password, attempting to ignore the breech and hope for the best might further harm your users if their accounts are compromised, don't forget to tell them that their passwords are protected and the chance of being hacked is low, but its still better safe than sorry, no hashing scheme is 100% safe.

So why shouldn't I invent my own security scheme? I can do something someone never thought about before or modify an existing scheme and make my application more secure!

Well, it doesn't work this way, if you didn't learn cryptography and a you're not a math expert I wouldn't recommend it, even if your're smart, chances are someone somewhere is smarter than you and given enough incentive they will attempt and I'm tempted to say succeed in hacking your super-duper-hack-proof-scheme, here's an example you probably didn't think about, remember, security through obscurity is never a good idea.

So how do we use these functions to provide the best security to our users?

Here is the change password method:

static void ChangePassword(User user, string password)
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    byte[] salt = new byte[8];

    int iterations = Random(10000,11000);

    Rfc2898DeriveBytes rfc2898 = new Rfc2898DeriveBytes(password, salt, iterations);

    user.Salt = salt;
    user.Password = rfc2898.GetBytes(40);
    user.Iterations = iterations;

And the validate password method:

static bool ValidatePassword(User user, string password)
    Rfc2898DeriveBytes rfc2898 = new Rfc2898DeriveBytes(password, user.Salt, user.Iterations);
    var hashedpassword = rfc2898.GetBytes(40);
    if (ArrayCompare(hashedpassword, user.Password))
        return true;
    return false;

The major drawback I can think about in using these algorithms is that it makes it very easy as DDoS targets, but it should be pretty simple to solve by limiting the number of login attempts per interval from a single IP.

If you're into security, Dan Boneh has a cool online course about cryptography, check it out its a very cool basics course, shows you the history of cryptography and where we are today, what is secured, how things got hacked and why you shouldn't invent cryptography yourself.

Also, here's a comparison of hash functions and known attacks.

As a side note, I'd like to direct your attention to SQL Injection attacks as they are still very common and there is no reason to leave your system vulnerable to that attack, read through the wikipedia article, the .NET code will be similar to this:
SqlConnection conn = new SqlConnection("connstr");
var cmd = conn.CreateCommand();
cmd.CommandText = "select * from users where username = @username";
cmd.CommandType = System.Data.CommandType.Text;
cmd.Parameters.Add(new SqlParameter("@username", "testuser"));

or, if you're using Entity Framework you're basically covered as long as you're working with LINQ and not writing Command Text yourself, if you do write command texts, you should use parameters, just like the ADO.NET example above. You can find the test code here:

No comments:

Post a Comment