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

Bắt đầu tại điểm vào hash_pbkdf2() và tái tạo benchmark PHP được cung cấp, so sánh PBKDF2 gốc với phiên bản mô phỏng. Công việc hoàn tất khi tối ưu hóa vẫn giữ nguyên digest được hiển thị và thời gian thực thi gốc đáp ứng kết quả so sánh dự kiến.