Due 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 ( 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: [1]
  • 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

Hash 1970 No No No No No No

Salted Hash 1976 No No Yes No No No

PBKDF2 * 2000 Yes Yes Yes Partial No No

Bcrypt 1999 Yes Yes Yes Yes** ?? No

Scrypt * 2009 Yes Yes Yes Yes** Yes Yes

* 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$
scrypt (3.8s) 900$ 610K$ 19B$ 175T$
 Source: Colin Percival [7]

Explanations :
  • "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.


To Consider

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 :


Bobby Wertman said... @ 10 June, 2012 20:54

Correction: An a 8 LL password encrypted with scrypt takes 610k$, not 610$.

thierryzoller said... @ 10 June, 2012 21:18

Thanks, corrected

Bobby Hardcore said... @ 11 June, 2012 01:23

Great post! One question: what does "RT" mean?

Givon Zirkind said... @ 15 June, 2012 11:38

LinkedIn and others, should be using non-decryptable encryption.

It only leaves the brute force option. But, the # of permutations and necessary tries are astronomical. The permutations make this encryption very different from a street algebraic approach. Which means, an infinitesimal chance of decryption. A much better way, IMHO. Theoretically & practically. Certainly better than the razz-majazz of hashing.

Non-decryptable encryption has been around since 1930s with one time key encryption.  this is restricted to military use. In limited forms, it should be permitted for civilian use, IMHO.  Newer methods permit many such keys can be easily generated.

thierryzoller said... @ 19 June, 2012 21:30

RT stands for "Rainbow Tables"

EAP-TTLS said... @ 11 December, 2012 12:19

The wireless AP should be able to work with different operational modes: Access point, Repeater, Network Bridge, and wireless Client mode. In the Wireless Access Point Mode, the device allows for any existing wired network to go wireless by simply attaching the device using the Ethernet cable to an open port in your router or switch.

Post a Comment