Password Hashing: PBKDF2, Scrypt, Bcrypt

Do we gain security by using multiple slow-hashing functions to safely store a password?

A question has been recently raised to me on password hashing:

Do we gain security by using multiple slow-hashing functions to safely store a password?

While all of these functions are pretty much safe given a proper implementation and good cost parameters (and therefore there’s no need to increase architectural complexity), I wanted to give a wider retrospective on the real security of such a system and I’ll post it here as well.

In 2015, if you’re storing passwords I hope that we’re already assuming that you’re going to store the hashed version of them. The hashing process is a one-way process which given some data it turns that into an unique string of fixed length. And that process will always return that string for that data. This allows a system to check the validity of a password with no knowledge of the original data, at least in theory (plaintext password). (Disclaimer: some hashing functions have collisions which means that different data might result in the same output. This means that the used cryptographic algorithm is broken; this is true for MD5, SHA1 and several others.)

So given a random attacker Mallory that is able to dump/read all user passwords, he would have to:

  • Determine the hashing function generating that output
  • If he’s lucky enough to have MD5 (or something similar) hashes, you’ll have an happy attacker
  • If the System OP used slow-hashing functions things might get slightly more complicated (unless system OP choose too weak cost parameters or bad parameters in general)
  • He could run a statistical analysis to find a partial password list He could run a bruteforce on them

So, in theory, if an attacker is up to crack all your passwords by bruteforce, unless he’s insane, he also has the resources to do so (no laptop allowed here :) ) and therefore he would use an ASIC (or GPU rigs) or FPGA hardware to do so.

ASIC and FPGA are just very optimized hardware to accomplish ONE task; an ASIC is a static circuit (meaning that the hardware is STRICTLY built for that algorithm), a FPGA can be reprogrammed.

Let’s talk more about slow-hashing functions.

PBKDF2 is a pretty easy function: it performs the HMAC as many times as specified by the ‘iterations’ parameter. This doesn’t look that good if Mallory owns a decent GPU or GPU rigs, as they’re designed in a different way: they have multiple cores that shines when you need to do parallel work on a lot of data. Each core can execute an instruction against thousands and thousands of data at the same time. While PBKDF2 is a hard job on a CPU, it’s a quite easy job for a GPU system.

BCrypt is from 1999 and is GPU-ASIC resilient by design as it’s also a memory hardening function: it’s not just CPU intensive, but also RAM-intensive to execute a bcrypt hash.

However times have changed and a sophisticated and maybe rich attacker will use big and powerful FPGA, and the contemporary models have now embedded RAM blocks, which greatly optimize this job. So while Bcrypt does a good job at making life difficult for an ASIC attacker, it does little against a FPGA one.

Scrypt solves this since 2009 as it doesn’t just use exponential time, but also exponential memory.

From the scrypt paper: estimated cost of hardware to crack a password in 1 year.

So, as the question was whether the combination of multiple slow-hashing functions was a good idea or not, I’ll try to synthesize all of this shortly.

First of all, allow me to remember that we’re relying on slow-hashing functions to fight the attacker on equal grounds: your power unit (CPU/GPU/…) VS his; scrypt equalizes this further more by optimizing functions for the kind of hardware you’re running on, instead of letting this optimization up to the attacker on his side.

So, say that you wanna run pbkdf2 on a scrypt digest or vice-versa; is it worth it? Well, if we spend half computational time on PBKDF2, I guess it is not really worth it since the attacker can turn PBKDF2 into dust just by taking advantage of simple GPUs.

So the combination of the two doesn’t make it more difficult for an attacker to crack all of your passwords; the best suggestion I’d give is to rely on the algorithm that has the best crypto records and stick with it.

In this case, bcrypt has the best ones a cryptographic algorithm can desire:

  • it has been vetted by the entire crypto community as it’s now 15 years old
  • it has been out there in the field for almost 15 years and yet remains unbroken
  • it is also widely used, supported and implemented in efficient ways

From a security perspective, I’d say that bcrypt is the best of the three.

However, Scrypt is also 6 years old now, it won’t take that much until we can say it’s a proven secure algorithm.


Originally published at mpreziu.so on March 11, 2015.