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

Inizia dal punto di ingresso hash_pbkdf2() e riproduci il benchmark PHP fornito, confrontando PBKDF2 nativo con la versione emulata. Il lavoro è completato quando l’ottimizzazione preserva il digest mostrato e il tempo di esecuzione nativo soddisfa il confronto previsto.