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

hash_pbkdf2() エントリポイントから開始し、提供された PHP ベンチマークを再現して、ネイティブ PBKDF2 とエミュレート版を比較します。最適化によって表示されたダイジェストが維持され、ネイティブの実行時間が想定される比較結果を満たした時点で作業は完了です。