PBKDF2 polyfill vulnerable to "long password DoS"

[timoh6]

The PBKDF2 polyfill in Core.php (which should run only for PHP 5.4 users) doesn't pre-hash the password before PBKDF2 inner loop if the password's length is greater than the underlying hash algorithm's output length.

This could lead to DoS situation if a malicious user is able to input long passwords to the PBKDF2 function. I.e. on my machine, 100000 byte password and 25000 iterations (with SHA256 and 32 byte output) took ~16 seconds.

I suggest we add a conditional pre-hash step before the outer PBKDF2 loop to mitigate this issue: check the password lenght, and if it is greater than $hash_length, do a pre-hash.

Roughly something like:

if (Core::ourStrlen($password) > $hash_length) {
    $password = \hash($algorithm, $password, true);
}

[defuse]

Wouldn't this then not actually implement PBKDF2? An alternative is to throw an exception if the password is longer than 1000 characters (or some small factor of $hash_length). What do you think?

[defuse]

Thanks for looking, by the way!

[defuse]

Related:

• http://arstechnica.com/security/2013/09/long-passwords-are-good-but-too-much-length-can-be-bad-for-security/
• https://www.helpnetsecurity.com/2013/09/17/too-long-passwords-can-dos-some-servers/

Let's see what Django (and other things) did, and if it's pre-hashing, I'm fine with deviating from PBKDF2 spec as long as we rename the function to indicate we did.

[defuse]

Django just fails if it's longer than 4096 bytes: https://www.djangoproject.com/weblog/2013/sep/15/security/

[defuse]

Proposed fix:

1. Don't modify the PBKDF2 code, keep it standards-compliant, but add a warning comment about the DoS vector.
2. Change our KDF in KeyOrPassword to always hash the password before giving it to PBKDF2 (even short passwords).

What do you think of that @timoh6?

[defuse]

I wonder what PHP's implementation of hash_pbkdf2 does for long passwords? If it does something special like pre-hashing long passwords then we need to make sure the polyfill behaves the same, otherwise upgrading will break ciphertexts.

[paragonie-scott]

If you put the pre-hash logic here: https://github.com/defuse/php-encryption/blob/v2.0/src/Core.php#L398

...then it won't break anything.

[defuse]

@paragonie-scott: Yeah, I mean, is PHP already doing something like this, in which case the polyfill is already broken because it's not doing the exact same thing? Or is PHP computing the DoS-vulnerable but standards-compliant version of PBKDF2?

[paragonie-scott]

• https://github.com/php/php-src/blob/1c295d4a9ac78fcc2f77d6695987598bb7abcb83/ext/hash/hash.c#L600-L723
• https://github.com/php/php-src/blob/1c295d4a9ac78fcc2f77d6695987598bb7abcb83/ext/hash/hash.c#L648
• https://github.com/php/php-src/blob/1c295d4a9ac78fcc2f77d6695987598bb7abcb83/ext/hash/hash.c#L209-L221

Yes, they do this.

[defuse]

@paragonie-scott: That's just standard HMAC isn't it?

[defuse]

@paragonie-scott: Oh, I see. $password is the key argument to HMAC, so if php has a way to do streaming HMAC with state copying (I think we do that in File) then we can eliminate the DoS without giving up standards-compliance.

[timoh6]

@defuse I'd go with the option 2 (pre-hash). But on the other hand, I don't think there will be any downsides if we just modify the PBKDF2 function to pre-hash if the input is longer than allowed in HMAC.

It is a simple fix that "just works".

In addition to that, some sort of "upper bound" to the allowed password length sounds indeed a good idea. Maybe that 4096 bytes will do?

[paragonie-scott]

I'd like to not make it conditional. Otherwise you end up with situations like this: http://www.openwall.com/presentations/PHDays2014-Yescrypt/mgp00009.html

Or this: https://3v4l.org/39uX2

It's ugly. But deviating from the standards is probably the "wrong" solution.

[defuse]

Yeah, a function called pbkdf2 should compute the function as specified by the standard. If we add prehashing it'll go in KeyOrPassword and will be an explicit step in the CryptoDetails.md docs.

[timoh6]

@paragonie-scott @defuse Good points. Pre-hashing in KeyOrPassword sounds reasonable to me.

[paragonie-scott]

@defuse That sounds great to me.

[defuse]

I've decided on prehashing the password in KeyOrPassword and not adding any length restrictions.

[defuse]

Needs review over in #234.

[defuse]

Done.