Thursday, August 9, 2012

Password Hashing: Best Practice

Last week I read a post on Brian Krebs’ blog where security researcher Thomas Ptacek was interviewed about his thoughts on the current landscape of password hashing. I found Thomas’ insights into this topic quite pertinent and would like to reiterate his sentiments by talking a little about the importance of choosing the right password hashing scheme.
The idea of storing passwords in a “secret” form (as opposed to plain-text) is no new notion. In 1976 the Unix operating system would store password hash representations using the crypt one-way cryptographic hashing function.  As one can imagine, the processing power back then was significantly less than that of current day standards. With crypt only being able to hash fewer than 4 passwords per second on 1976 hardware, the designers of the Unix operating system decided there was no need to protect the password file as any attack would, by enlarge, be computationally infeasible. Whilst this assertion was certainly true in 1976, an important oversight was made when implementing this design decision: Moore’s Law.
Moore’s Law states that computing power will double approximately every two years. To date, this notion has held true since it was first coined by Gordon Moore in 1965. Because of this law, we find that password hashing functions (such as crypt) do not withstand the test of time as they have no way of compensating for the continual increase in computing power. The problem we find with cryptographic hashing functions is that whilst computing power continually increases over time, password entropy (or randomness) does not.
If we fast-forward to the current day environment we see that not much has changed since the early implementations of password hashing.  One-way cryptographic hashing functions are still in widespread use today, with SHA-1, SHA-256, SHA-512, MD5 and MD4 all commonly used algorithms. Like crypt on the old Unix platform, these functions have no way of compensating for an increase in computing power and therefore will become increasingly vulnerable to password-guessing attacks in the future.
Fortunately, this problem was solved in 1999 by two researches working on the OpenBSD Project, Niels Provos and David Mazieres. In their paper, entitled ‘A Furture-Adaptable Password Scheme’, Provos and Mazieres describe a cost-adaptable algorithm that adjusts to hardware improvements and preservers password security well into the future.
Based on Bruce Shneier’s blowfish algorithm, EksBlowfish (or expensive key scheduling blowfish), is a cost-parameterizable and salted block cipher which takes a user-chosen password and key and can resist attacks on those keys. This algorithm was implemented in a password hashing scheme called bcrypt.
Provos and Mazieres identified that in order for their bcrypt password scheme to be hardened against password guessing, it would need the following design criteria:
  1. Finding partial information about the password is as hard as guessing the password itself. This is accomplished by using a random salt.
  2. The algorithm should guarantee collision resistance.
  3. Password should not be hashed by a single function with a fixed computational cost, but rather by of a family of functions with arbitrarily high cost.
The first two points here are fairly standard among password hashing algorithms. The last point, however, is somewhat of a different concept to what we are used to seeing.
If we think about cryptographic hashing functions in use today - be it MD5, SHA-1, or MD4 - we notice they all have one thing in common: speed. Each of these algorithms is incredibly quick at computing its respective output. As hardware gets better, so too does the speed at which these algorithms can operate. Whilst this may potentially be seen as a positive thing where usability is concerned, it is certainly an undesirable trait from a security standpoint. The quicker these algorithms are able to compute their output, the less time it takes for the passwords to be cracked.
Provos and Mazieres were able to solve this problem by deliberately designing bcrypt to be computationally expensive. In addition, they introduced a tunable cost parameter which is able to increase the algorithm’s completion time by a factor of 2 each time it is incremented(effectively doubling the time it takes to compute the result). This means that bcrypt can be tuned (i.e. incremented every 2 years) to keep up with Moore’s Law.
Let’s have a quick look at how bcrypt compares against other hashing algorithms. Let’s say we have a list of 1000 salted SHA-1 hashes that we wish to crack. Because they are salted, we can’t use a pre-computed list of hashes against this list. We can, however, crack the hashes one by one. Let’s say on modern hardware it takes a microsecond (000000.1 seconds) to make a guess at the password. This means that per second we could generate 1 million password guesses per hash.
In contrast, say we have the same list but instead of SHA-1 the hashes have been derived using bcrypt. If the hashes were say computed with a cost of 12, we are able to compute a password guess roughly every 500 milliseconds. That is, we can only guess 2 passwords a second. Now if you think we have 1000 password hashes, we can only generate 7,200 guesses per hour. As it would be more efficient targeting all 1000 hashes (as opposed to just one), we would be limited to approximately 7 guesses per hash.
Below is the output of a quick program I created to display the time it takes to compute a bcrypt comparison as the cost value is incremented. The test was conducted on a RHEL system running a Xeon X5670 @ 2.9Ghz with 1024MB of memory.

The source code for this program can be found here.
The bcrypt password hashing scheme is currently available in many languages including Java, C#, Objective-C, perl, python, and Javascript among others.
I hope this post highlights the importance of using stronger password hashing schemes for modern day applications. 


  1. Very good blog post. I definitely love this
    site. Thanks!

    Feel free to surf to my page ... speed reading courses
    Also visit my weblog :: speed reading exercises

  2. It's a pity you don't have a donate button! I'd without a doubt donate to this brilliant blog! I guess for now i'll settle for bookmarking and adding your RSS feed
    to my Google account. I look forward to fresh updates and will share
    this website with my Facebook group. Talk soon!
    My web page > Betting Both Sides

  3. Whу vieωerѕ ѕtill mаke use of to
    reaԁ news pаpers when in this technologіcal globе аll is
    acceѕsіble оn web?

    Stop by my page - Seopressor Version5

  4. My brother recommended I might like this blog.

    He was totally right. This post actually made my day.
    You cann't imagine just how much time I had spent for this information! Thanks!

    my webpage ... designer patio furniture

  5. Νο mattеr if some onе seаrches for hiѕ ѵital thing, so
    hе/shе nеeԁs to be available that іn
    dеtail, ѕo that thing іѕ maintained оveг hеrе.

    my ωebpage ...

  6. Hеllο There. I founԁ your blog using msn.
    This is a very well written article. I'll make sure to bookmark it and come back to learn more of your useful info. Thanks for the post. I will definitely comeback.

    Feel free to surf to my site ::

  7. Hello there! Do you know if they make any plugins
    to assist with seo?
    I'm trying to get my blog to rank for some targeted keywords but I'm not
    seeing very good success. If you know of any please share.

  8. Аn іmpressiѵe shaгe!
    ӏ haνе just foгωarded thiѕ onto
    а сo-ωοrkеr who waѕ cοnԁucting a lіttlе геsearch on this.
    And he in fact bοught mе dіnner due to
    the fact thаt I stumblеd upon it foг him.
    .. lοl. Ѕo let me rewοrd thiѕ.
    ... Тhanκs foг the meal!! Вut уeah,
    thаnx for spending somе time tо
    discuss this iѕѕue heгe on уοur internet ѕitе.

    Here is my hοmeрage - SEOPressor V5 review

  9. continuously i used to read smaller posts that also clear their motive, and that is also happening with this paragraph which
    I am reading now.

    Stop by my webpage: justin tv

  10. For most recent information you have to pay a quick visit web and on internet I found this web
    site as a most excellent web page for hottest updates.

    My homepage - Tv Izle Net

  11. My brother recommended I might like this web site.
    He was totally right. This post actually made my day. You cann't imagine just how much time I had spent for this info! Thanks!

    my webpage SEO

  12. I was quite unconvinced about diet plan supplements, yet then I heard the popular TELEVISION Medical professional's explore Garcinia Cambogia.

    Feel free to visit my page - garcinia cambogia gnc rightway