PBKDF2 vs bcrypt for key derivation

[misog]

Hi, according to this https://paragonie.com/blog/2016/02/how-safely-store-password-in-2016 "nearly everyone except FIPS agrees PBKDF2 is the worst of the acceptable options, but is still acceptable". If we tune up bcrypt and PBKDF2 in such way that they have the same computing times on PCs, then it takes more time on GPUs to compute bcrypt than PBKDF2. http://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage

GPUs and ASICs are used to mine Bitcoins and other Altcoins. The rise in computing power for Bitcoin was this strong: https://bitcoinwisdom.com/bitcoin/difficulty For example, Bitcoin uses SHA-256, Litecoin uses Scrypt. Even if ASIC (maybe) can not be modified to compute PBKDF2, there are many GPUs in mining industry which can compute more algorithms universally. Did you considere this?

The second thing is this: bcrypt is the recommended algo for password hashing in PHP (password_hash uses bcrypt). When user password is used as input in BPKDF2 for key derivation, then the use of bcrypt for storage is useless because the PBKDF2 is less secure then bcrypt and it is sufficient to break the PBKDF2 to reveal encryption key AND the user password. Assuming no key protection or hacked server.

However, bcrypt has disadvantages:

• bcrypt has 184 bit pseudorandom output (key)
• I am not sure if the entropy is the same as in case of PBKDF2
• there is limit of ~74 bytes for input data (but PBKDF2 has the DoS implied limit too)

Why not to allow to choose bcrypt over BPKDF2 in the library? What do you think?

[paragonie-scott]

Yes: Bcrypt is better than PBKDF2 for password verification, but bcrypt will only ever produce 192 bits, whereas PBKDF2 can be used to generate any output size.

We need something:

• Acceptable as a password-based KDF
• Built in to PHP 5
• That offers 256-bit binary string outputs

Unfortunately, the only solution that fits the ticket is PBKDF2. PBKDF2 is fine, especially with random salts and a high iteration count. Our iteration count is 100,000, which is on most devices comparable to a bcrypt cost of 11.

The best solution, Argon2i, is currently available to users right now through libsodium-php. If you want a simple interface through which to use libsodium, I wrote (and maintain) Halite. I'm trying to bring libsodium to PHP 7.1 so everyone can use it.

[misog]

libsodium/Halite without PECL would be great!

1. "Most devices" are GPUs and ASICs too?
2. Can the iteration count be adjusted by parameter?
3. PBKDF2 SHA-256 vs Bitcoin (SHA-256) GPU/ASIC miners?

[defuse]

Good answer @paragonie-scott.

As to why it's not going to be an option to use bcrypt, and also no option to change the iteration count, is that adds complexity to the API and users will have to wonder what they should chose. Let's choose the best option ourselves, and if it's wrong then it's our fault. Anytime we can make it our fault that something went wrong and not our users fault that's a win for usable security.

[defuse]

I'm willing to consider using bcrypt alongside PBKDF2 but I think it would just end up being an unreviewable kludge. We're more likely to introduce a bad security bug attempting that that than we would expect to get in advantages from having bcrypt.

[paragonie-scott]

There's a bit of a divide between the use case of password hashing and KDFs that's hard to articulate, but I'll try:

• Password hashing: You're storing a hash and trying to defend against an attacker identifying the input. The output is considered "public" from a threat model perspective.
• KDF: You're deriving another secret which shouldn't be persisted.

An attacker can grab a password hash and try billions of combinations per second to try to identify the password. Attacking PBKDF2-SHA256 then AES-256-CTR+HMAC-SHA-256 is a different use case. You don't know the output of the algorithm so testing becomes much slower. It's a high bandwidth operation, whereas if you already have the hash all you need to emit is "yes, we found an input that produces this hash with the same salt" or "not found yet".

"Most devices" are GPUs and ASICs too?

GPUs give you a 10x to 20x speedup over CPUs. Bcrypt with a cost of 11 is actually generally equated to a PBKDF2-SHA256 iteration of 86,000, but we rounded up to 100,000 for simplicity.

Can the iteration count be adjusted by parameter?

No, 100,000 is sufficient. If you need higher security, use Argon2i. (Which means: suck it up and install libsodium from PECL until PHP 7.1 is out.)

PBKDF2 SHA-256 vs Bitcoin (SHA-256) GPU/ASIC miners?

Where PBKDF2 is fine (sub-optimal, but not insecure) for passwords, SHA256 is woefully inadequate.

If we want 128 bits for key and 128 bits for HMAC, the first 128 bits can be from bcrypt and the last 128 bits from PBKDF2. password_hash and bcrypt would have the same security, HMAC less security.

Version 2 uses AES-256-CTR and HMAC-SHA-256. We use a KDF (PBKDF2 or HKDF, both using SHA256) to split the input into an encryption key and an authentication key. As long as the input is either:

• A sufficiently strong password, or
• A cryptographically secure key (generated from the library)

...then these algorithms can reliably produce outputs at the 256-bit security level.

[defuse]

I'm not going to try the PBKDF2+bcrypt approach because it would delay the release further (and technically the code is frozen for security review).