IntroductionDue to the latest row of high profile websites being compromised and parts of the password hashes being published here's a quick crash course on storing passwords "securely", for those that want a quick heads up. In this case I'd define securely as "Offering a suitable time window of resistance against recovery after being compromised". I will keep this post short and sweet and use links where possible for those interested in more information.
Update: After reading this blog post read the interview of Brian Krebs with Thomas H. Ptacek on the matter.
Update: Wrong bcrypt link fixed, update the Year bcrypt was presented.
Putting things into perspective, below are the most common forms of storing passwords (order from worse to best) :
- Storing credentials in clear text
- Storing credentials using a hash (MD5, SHA, SHA256)
- Storing credentials using unique salt per entry and a hash (MD5, SHA, SHA256)
- Storing credentials using bit/key stretching mechanisms or being overall time expensive (PBKDF2, bcrypt, scrypt, phpass)
It is a common occurrence that even high profile sites (linked-in.com) stored the credentials with a simple hash, there is no reason to do so today and in my view it's borderline to negligence. There are different way to strengthen the resistance against brute-force attacks or precomputed rainbow table , adding a unique salt per entry is one, however looking at the big picture it is clear that using a unique SALT is not good enough for most password stores.
Let's start by realising how old the different techniques are: 
- Storing credentials in clear text : Ever since
- Storing credentials using a hash : early 70s
- Storing credentials using unique salt per entry and a hash : late 70s (DES crypt)
- Storing credentials using bit/key stretching : bcrypt (1999) / scrypt (2009) / PBKDF2 (2009)
Suitable Resistance per KDF
|Technique / KDF||Year||Bruteforce||Dictionnary||RT||GPU||FPGA||ASIC|
* High iteration counts assumed
** Due to Memory Access
Estimated (ASIC) costs to crack one password in a year
|Technique / KDF||6LL||8 LL||8 chars||10 chars|
|DES CRYPT||< 1$||< 1$||< 1$||< 1$|
|MD5||< 1$||< 1$||< 1$||1.1K$|
|MD5 CRYPT||< 1$||< 1$||130$||1.1M$|
|PBKDF2 (100ms)||< 1$||< 1$||18k$||160M$|
|bcrypt (95ms)||< 1$||4$||130K$||1.2B$|
|scrypt (64ms)||< 1$||150$||4.8M$||43B$|
|PBKDF2 (5.0s)||< 1$||29$||920K$||8.3B$|
|bcrypt (3.0s)||< 1$||130$||4.3M$||39B$|
Source: Colin Percival 
- "DES CRYPT" and "MD5 Crypt" are salted
- "LL" : Lower case letter - example "aeterws"
- "chars" : 95 printable 7-bit ASCII characters - example "6,uh3y[a"
- The numbers in the parenthesis are the time it took to go through the setup/iterations, this depends on the CPU power and settings/iteration counts. It is notable how bcrypt offers a higher recovery costs at a lesser setup time thean PBKDF2, the same holds true for scrypt vs. bcrypt.
All key derivation functions that are expensive to setup rely on the fact that (in case of a website) the authentication step requires the the setup to be done once while an attacker that has the pasword store dumped has to do the setup hundreds of thousands or millions of times. On the downside as the setup is expensive this might put load on the web-server and depending on the website you operate the number of iterations you configure (PBKDF2, bcrypt, scrypt) are a trade off to make between speed and "security". As 98% of the website don't deal with massive amount of new logins per second this is usually acceptable.
Another case to consider is that due to the expensive setup time that you could open the door to denial of service attacks with somebody trying to authenticate over and over again. This can however be relatively easily determined and blocked in most cases.
More information :
-  History: http://www.openwall.com/presentations/PHDays2012-Password-Security/
-  About the why: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html
-  Standards : http://csrc.nist.gov/publications/nistpubs/800-132/nist-sp800-132.pdf
-  http://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage
-  FPGA and SHA : http://www.east.isi.edu/~bschott/pubs/grembowski02comparative.pdf
-  KDF - Key Deriviation Function: http://en.wikipedia.org/wiki/Key_derivation_function
-  Scrypt: http://www.bsdcan.org/2009/schedule/attachments/86_scrypt_slides.pdf