A Recipe For Password Security

CodeProjectIntroduction

Several months ago, I helped architect a password security scheme for a client. During that process, I learned quite a bit about how to encrypt passwords in a secure fashion.

Encryption vs. Hashing

Most developers have heard the term "encryption", which means that data is encoded in such a way that it is not human-readable. But in the context of password security, the word “encryption” implies that the encoding can be decoded, that is, it’s a “two-way” encryption. While it may be advantageous to decode a user’s password, especially in situations where they have forgotten it, it opens up a security hole. Simply put, if someone attacking your security implementation can guess the algorithm and parameters used to encrypt passwords, they can then decrypt all the passwords in your system! At this point, you have the equivalent of passwords stored in your system in plaintext – not an excellent approach.

A much more secure method for storing encrypted passwords is to use a cryptographically secure hash¹. A “hash” is an algorithm that will take a block of data and from that information, generate a value such that if any of the data is changed, the hashed value will change as well. The block of data is generally called a “message” and the hashed value is called a “digest”. What is valuable about cryptographic hashes with regard to password security is that they are “one-way”, that is once the password has been hashed, it cannot be decrypted back to its original plaintext form. This eliminates the security vulnerability that exists with two way encryption.

By now, I’m sure some of you have thought, “Great, if I have this hashed value, how do I validate that against the plaintext password typed in by the user?” The answer is, you don’t. When the user types in their password, you hash the value that they entered using the same hash algorithm. You then compare that hashed value with the hashed password stored in your system. If they match, then the user is authenticated.

Adding Some Salt

So we now have a process for storing passwords in our system in a secure form that cannot be decrypted, thus closing the door that allows attackers access to all the passwords stored in the system. But determined attackers are not so easily thwarted. They will use a rainbow of methods to gain access to your systems, which segues (in a ham-handed fashion) into the next topic, rainbow tables.

Since they can no longer decrypt your passwords, attackers will try the next best thing. They’ll take a large list of common words and passwords and hash them using some of the well-known standard algorithms. They’ll then compare this list of hashed words to your password list. Any matches will immediately indicate a successful password search. Given users’ penchant for commonly used passwords, the chances are good that the attacker will end up with quite a few successes.

The generally accepted practice for prohibiting this practice is to use a “password salt”². A salt value is just a randomly generated value that is added to the user’s password before hashing. The salt value is then stored with the user’s hashed password so that the authentication method can use it to hash a password entered by the user.

Now I’m sure some of you are wondering how this prevents rainbow table attacks if the salt value is easily accessible. What the salt value does is require the attacker to regenerate all the values in their rainbow table using the specified salt value. Even if they have a match, it will only work for the one user for which that particular salt value was used. While it doesn’t prevent a successful attack, it certainly limits it to one success and makes it very slow and cumbersome for the attacker to make additional attempts on other passwords.

Needs Some Pepper

So how can we make it even more difficult for the determined attacker? Well, we can add a “secret salt” value not stored in the database to the password before we hash it. This value would be well known to the system so that it can reproduce it as necessary for authentication but would not be stored in the database. This type of value is commonly known as a “pepper” value. The fact that it is not published or stored makes it even more difficult for an attacker to guess what the plaintext value was before hashing. Unless they have access to the source code for generating the pepper value, they may never be able to generate a successful rainbow table.

Simmer Slowly

So it seems like we’ve covered all the bases. But we can’t forget about Moore’s Law³. As CPUs and GPUs get faster and faster, it becomes easier to generate multiple rainbow tables so that an attacker can take many guesses at an encrypted password list. What’s a poor, security-minded developer to do?

Well, how about we purposely slow them down?

There are several well known cryptographic hash algorithms⁴, such as the Message Digest derivatives (MD2, MD4, MD5) and the Secure Hash Algorithms from the National Security Agency (SHA-1, SHA-256) but many of these were designed to work quickly. In some cases, like MD5, the algorithm is considered “cryptographically broken”⁵. What we really need is a hash algorithm that can be adapted so that it is slow enough to discourage the generation of multiple rainbow tables but fast enough to hash a password quickly after a user types it in for authentication.

Enter bcrypt⁶. Bcrypt is a hashing function based on the well-regarded Blowfish encryption algorithm that includes an iteration count to make it process more slowly. Even if the attacker knows that bcrypt is the algorithm in use if a properly selected iteration count is employed, it renders the generation of rainbow tables very expensive. Furthermore, the iteration count is stored in the hashed result value so it’s forward compatible; that is as computing power continues to increase the iteration count can be increased and applied to existing password hashes so that the generation of rainbow tables continues to be expensive.

Taste While Cooking

So we've got a recipe for encrypting passwords, what does this look like when you're cooking it? Here's some sample code to illustrate, as per request by CP user George Jonsson.

First, we'll need a table in our database to store user information. I use SQL Server predominantly, so here's a table creation script for that database management system.

IF OBJECT_ID( 'Users' ) IS NOT NULL
	DROP TABLE Users
GO

CREATE TABLE Users(
	UserId			int				IDENTITY NOT NULL,
	Username		varchar( 50 )	NOT NULL UNIQUE,
	Password		varchar( 128 )		NULL,
	CONSTRAINT PKUsers
		PRIMARY KEY( UserId )
)
GO

You'll notice that I left the password column nullable. The reason will become clear in the code, where I use the user ID for part of the pepper value, but I can't get tthis value until I insert a row.

Then we'll need a POCO object to model the data...

using System;

namespace BcryptExample.Model
{
    class User
    {
        public int UserId { get; set; }
        public string Username { get; set; }
        public string Password { get; set; }
    }
}

...and a controller to handle the CRUD plumbing.

using System;
using System.Configuration;
using System.Data;
using System.Data.SqlClient;
using System.Linq;
using Dapper;
using log4net;

namespace BcryptExample.Controllers
{
    class UserController
    {
        private ILog logger = LogManager.GetLogger( "BcryptExample" );
        private readonly string connectionString;

        public UserController()
        {
            connectionString = ConfigurationManager.ConnectionStrings[ "ExamplesDb" ].ConnectionString;
        }

        public Model.User AddUser( Model.User user )
        {
            try {
                using( IDbConnection conn = new SqlConnection( connectionString ) ) {
                    conn.Open();

                    using( IDbTransaction trans = conn.BeginTransaction() ) {
                        try {
                            user.UserId = conn.Query<int>( "INSERT INTO Users( Username ) 
                                                      OUTPUT inserted.UserId 
                                                      VALUES( @UserName ) ",
                                                       new { Username = user.Username },
                                                       trans,
                                                       commandType : CommandType.Text ).FirstOrDefault();

                            string cryptPw = PasswordHash.HashPassword( user.Password, 
                                                                        user.Username, 
                                                                        user.UserId );
                                
                            user.Password = cryptPw;

                            conn.Execute( "UPDATE Users SET Password = @Password WHERE Userid = @UserId",
                                          new { Password = cryptPw, user.UserId }, 
                                          trans );

                            trans.Commit();
                        }
                        catch( Exception ex ) {
                            trans.Rollback();
                            logger.Error( "Error in UserController.AddUser transaction.", ex );
                        }
                    }

                    conn.Close();
                }
            }
            catch( Exception ex ) {
                logger.Error( "Error in UserController.AddUser.", ex );
                throw;
            }

            return user;
        }

        public Model.User GetUser( string username )
        {
            Model.User user = null;

            try {
                using( IDbConnection conn = new SqlConnection( connectionString ) ) {
                    conn.Open();

                    user = conn.Query<model.user>( "SELECT UserId, Username, Password 
                                                         FROM Users 
                                                         WHERE Username = @Username",
                                                    new { Username = username },
                                                    commandType: CommandType.Text ).FirstOrDefault();
                    conn.Close();
                }
            }
            catch( Exception ex ) {
                logger.Error( "Error in UserController.GetUser.", ex );
                throw;
            }

            return user;
        }
    }
}
</model.user></int>

There are a few items to note in the controller code.

• I used Marc Gravell and Sam Saffron's superb Micro-ORM, Dapper for database usage. I find it less intrusive than EF and other heavy ORMs, but if that's what you like than feel free to use that;
• I used log4net for output logging. Again, if this is not your preference feel free to swap out;
• I loaded both the previously mentioned libraries using NuGet, also highly recommended;

The AddUser method inserts a row into the user table without a password and uses the SQL Server OUTPUT clause to return the new User ID. This ID, along with the user name, are used to create a pepper value, using a process that is shown below. However, it is not necessarily recommended that you use these values for a cryptography pepper. You would generally want the pepper value to be immutable, and username is something that, while not very volatile, is most likely not immutable. It is used here strictly for purposes of illustration.

This is the code for the class where password hashing is performed.

using System;
using System.Linq;

namespace BcryptExample
{
    class PasswordHash
    {
        private const int WORK_FACTOR = 10;
        private const int PEPPER_KEY = 7591232;

        public static string HashPassword( string password, string username, int userId )
        {
            string temp = PepperPassword( password, username, userId );
            return BCrypt.Net.BCrypt.HashPassword( temp, WORK_FACTOR );
        }

        public static bool VerifyPassword( string password, string username, int userId, string cryptText )
        {
            string temp = PepperPassword( password, username, userId );
            return BCrypt.Net.BCrypt.Verify( temp, cryptText );
        }

        private static string PepperPassword( string password, string username, int userId )
        {
            string temp = String.Format( "{0}{1}{2:0000000}", password, username, userId );
            return Shuffle( temp, PEPPER_KEY );
        }

        private static string Shuffle( string source, int randKey )
        {
            // Simple Knuth-Fisher-Yates deterministic shuffle of a string
            // as adapted from pseudo-code at http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
            char[] chars = source.ToArray();
            Random rand = new Random( randKey );    // to insure consistent randomizing (huh?!?)
            char swap;

            for( int charIdx = chars.Length - 1; charIdx > 0; charIdx-- ) {
                int n = rand.Next( charIdx );
                swap = chars[ n ];
                chars[ n ] = chars[ charIdx ];
                chars[ charIdx ] = swap;
            }

            return new string( chars );
        }
    }
}

The notable items in this code snippet are:

• I used the open source BCrypt.Net library for secure hashing with a work factor, as described earlier. If installing from NuGet this library is the one that says "official";
• The password pepper generation takes three inputs: the plaintext password, the username, and the user ID, concatenates them into a string, which then has its component characters shuffled in a deterministic fashion so that we can recreate it for validation;
• BCrypt.Net provides its own handy validation method that you pass the plain text and the stored hashed password. It will then take the salt value, which is included in the encrpyted data, and the work factor, also included in the encrypted data, and hash the plaintext password to compare;
• The Shuffle method uses an algorithm created by Fisher and Yates that was published by Knuth that provides good random distribution. I used a random seed to insure that the shuffle is deterministic, meaning that it will always return the same value given the same inputs.

The BCrypt library will turn the plain text password, for example "password99", into something like "$2a$10$InkLvHP9ZYIFl5zBNt13uuYdU8GY6eUZRsYWybHzmsHiGG4azBSj6". This is a base 64 encoded string, the first segments of which indicate the version and work factor in that order. The salt value is also embedded in the string, and the BCrypt library knows how to extract it at verification time. See this StackOverflow article (http://stackoverflow.com/a/6833165/49954) for an explanation of the portions of a BCrypt hash.

And here's a small sample program that will illustrate the usage:

using System;

namespace BcryptExample
{
    class Program
    {
        static void Main( string[] args )
        {
            Controllers.UserController controller = new Controllers.UserController();

            Model.User user = controller.GetUser( "newuser" );
            if( user == null ) {
                Model.User newUser = new Model.User { Username = "newuser", Password = "password99" };
                user = controller.AddUser( newUser );
            }

            Console.Write( "Enter password for newuser: " );
            string password = Console.ReadLine();

            if( PasswordHash.VerifyPassword( password, user.Username, user.UserId, user.Password ) ) {
                Console.WriteLine( "You entered an valid password" );
            }
            else {
                Console.WriteLine( "You entered an invalid password" );
            }
        }
    }
}

The code at the top of the routine attempts to retrieve the user's information from the database. If it's not found, then create it.

The code at the bottom of the routine prompts for the password, which is then validated using the recipe outline in the article.

A Spicy Meatball

So by using a combination of the right spices (salt and pepper) and the proper cook time (iterations), we can end up with an excellently prepared plate of hash. It’s not perfect - no security approach ever is - but we can certainly make our systems less vulnerable to the point where an attacker will look for victims that are less well-protected. And that’s all we can really hope for, that they look somewhere else.

Additional References

Coding Horror: You're Probably Storing Passwords Incorrectly

1. http://en.wikipedia.org/wiki/Cryptographic_hash_function
2. http://en.wikipedia.org/wiki/Salt_(cryptography)
3. http://en.wikipedia.org/wiki/Moores_law
4. http://en.wikipedia.org/wiki/Cryptographic_hash_function#Cryptographic_hash_algorithms
5. http://en.wikipedia.org/wiki/MD5
6. http://en.wikipedia.org/wiki/Bcrypt