hash_pbkdf2() wastes time by repeatedly hashing the HMAC key blocks

Description

As mentioned in a 2015 blog post titled "PBKDF2: performance matters", hash_pbkdf2() is missing an important optimization that relates specifically to the use of HMAC for the underlying pseudorandom function. This means it "[...] is at least two times slower than it otherwise could be."

The author of the blog post linked to a pull request he had made against PHP 5.6 (#1387), which unfortunately did not get a review before it was closed as stale in 2017. I have attempted to update his patch for PHP 8.0 (the lowest supported version at the time I am writing this report), and I am creating a new pull request for it. I hope that this time the PHP developers will take a look.

Below is a test script that demonstrates that the optimization is missing.

The following code:

<?php
function test_native() {
    $st = hrtime(true);
    $h = hash_pbkdf2('sha256', 'password', 'salt', 100000);
    $et = hrtime(true);
    return [$h, $et - $st];
}
function test_emulated() {
    $st = hrtime(true);
    $K = str_pad('password', 64, "\0");
    $K ^= str_repeat("\x36", 64);
    $ictx = hash_init('sha256');
    hash_update($ictx, $K);
    $K ^= str_repeat("\x6a", 64);
    $octx = hash_init('sha256');
    hash_update($octx, $K);
    $DK = str_repeat("\0", 32);
    $prev = "salt\0\0\0\1";
    for ($j = 0; $j < 100000; ++$j) {
        $ctx = hash_copy($ictx);
        hash_update($ctx, $prev);
        $temp = hash_final($ctx, true);
        $ctx = hash_copy($octx);
        hash_update($ctx, $temp);
        $prev = hash_final($ctx, true);
        $DK ^= $prev;
    }
    $h = bin2hex($DK);
    $et = hrtime(true);
    return [$h, $et - $st];
}
$nr = test_native();
$er = test_emulated();
var_dump($nr[0]);
var_dump($er[0]);
var_dump($nr[1] <= $er[1]);

Resulted in this output:

string(64) "0394a2ede332c9a13eb82e9b24631604c31df978b4e2f0fbd2c549944f9d79a5"
string(64) "0394a2ede332c9a13eb82e9b24631604c31df978b4e2f0fbd2c549944f9d79a5"
bool(false)

But I expected this output instead:

string(64) "0394a2ede332c9a13eb82e9b24631604c31df978b4e2f0fbd2c549944f9d79a5"
string(64) "0394a2ede332c9a13eb82e9b24631604c31df978b4e2f0fbd2c549944f9d79a5"
bool(true)

PHP Version

PHP 8.1.10

Operating System

No response

Start at the hash_pbkdf2() entry point and reproduce the supplied PHP benchmark, comparing native PBKDF2 with the emulated version. The work is done when the optimization preserves the shown digest and the native timing meets the expected comparison.