Storing password securely - hashses, salts and bit stretching put into context
| 0 comments ]


Introduction

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.

 

Details

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: [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 :



0 comments

Post a Comment