What's the algorithm behind MySQL's sha256_password hashing scheme?

Question

MySQL's old mysql_native_password hashing scheme was the equivalent of this in PHP:

sha1(sha1('password', true));

That's a hex-encoded SHA-1 hash of a binary SHA-1 hash of the password, without any salting.

MySQL 8.0 introduced a two variants of a new hashing scheme based on SHA256 called caching_sha2_password and sha256_password, the former being the default (docs). Despite their name, neither appears to be vanilla SHA256.

(Yes, I know SHA256 is not a great choice for password hashing, but it's a lot better than SHA-1 and it wasn't up to me!)

Here's an example. I created a hash for the password password, and it created a mysql.users password hash like this:

$A$005$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

I'm guessing that (separating by $ chars), A means it's SHA256 (the scheme may support other SHA2 variants in future), and that the 005 is a salt, but the rest of the string isn't a common format - it doesn't look like either regular hex output or base64, nor is it raw binary.

Can anyone tell me the actual algorithms for these new schemes, in PHP or similar code?

Update

Thanks to @kelalaka for some important pointers, I had a crack at writing this in PHP:

$originalhash = 'wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3';
$binaryhash = base64_decode($originalhash);
$salt_length = 20;
$hash_length = 43;
$rawsalt = substr($binaryhash, 0, $salt_length);
$rawhash = substr($binaryhash, $salt_length);

$password = 'password';
$iterations = 5;
$iteration_multiplier = 1000;
$it = $iterations * $iteration_multiplier;
$hash = $rawsalt . $password;
for ($i = 0; $i < $it; $i++) {
    $hash = substr(hash('sha256', $hash, true), 0, $hash_length);
}
$hashoutput = base64_encode($rawsalt . $hash);
var_dump($originalhash, $hashoutput);

However, this doesn't produce matching output:

string(61) "wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3"
string(72) "wUH/k55fkPN4cvqu6bppuYjCvqgx75cg5UeVzAVpx0OzU7KS2Klujh3rbHzrAena3/MBAA=="

• It's too long
• I suspect the encoding scheme is not base64; notice the salt diverges from the original even though it is unchanged.
• I'm not sure whether the starting string should be salt + password or password + salt.
• I'm not clear when the truncation of the binary hash should be performed - in the loop, or after?

Answer 1

According to the MySQL Server Blog, it is:

The advantage of mysql_native_password is that it support challenge-response mechanism which is very quick and does not require encrypted connection. However, mysql_native_password relies on SHA1 algorithm and NIST has suggested to stop using it.

caching_sha2_password tries to combine the best of both worlds.

XOR( SHA256(pwd),SHA256(SHA256SHA256(pwd)) , Nonce)

\$A\$005\$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

From the source code sha2_password.cc

• Expected format

  DELIMITER[digest_type]DELIMITER[iterations]DELIMITER[salt][digest]

Where the delimiter is $

• digest_type:

  A => SHA256

• iterations:

  005 => 5*ITERATION_MULTIPLIER

• salt:

  Random string. Length SALT_LENGTH

• digest:

  SHA2 digest. Length STORED_SHA256_DIGEST_LENGTH

  From file i_sha2_password.h

• #define CRYPT_SALT_LENGTH 20

  const unsigned int STORED_SHA256_DIGEST_LENGTH = 43;

Answer 2

The algorithm implemented in hashcat works for me with mysql 8.0.

<?php

// based on https://github.com/hashcat/hashcat/blob/master/tools/test_modules/m07400.pm

function to64($v, $n) {
    # ('.', '/', '0'..'9', 'A'..'Z', 'a'..'z');
    $i64 = array_merge(array('.', '/'), range('0', '9'), range('A', 'Z'), range('a', 'z'));

    $str = '';
    while (--$n >= 0) {
        $str .= $i64[$v & 0x3F];
        $v >>= 6;
    }
    return $str;
}

function sha256($data) {
    return hash("sha256", $data, true);
}

function sha_crypts($func, $bits, $key, $salt, $loops) {
    $bytes = $bits / 8;
    $b = $func($key . $salt . $key);

    # Add for any character in the key one byte of the alternate sum.

    $tmp = $key . $salt;

    for ($i = strlen($key); $i > 0; $i -= $bytes) {
        if ($i > $bytes) {
            $tmp .= $b;
        } else {
            $tmp .= substr ($b, 0, $i);
        }
    }

    # Take the binary representation of the length of the key and for every 1 add the alternate sum, for every 0 the key.

    for ($i = strlen($key); $i > 0; $i >>= 1) {
        if (($i & 1) != 0) {
            $tmp .= $b;
        } else {
            $tmp .= $key;
        }
    }

    $a = $func($tmp);

    # NOTE, this will be the 'initial' $c value in the inner loop.

    # For every character in the password add the entire password.  produces DP

    $tmp = "";

    for ($i = 0; $i < strlen($key); $i++) {
        $tmp .= $key;
    }

    $dp = $func($tmp);

    # Create byte sequence P

    $p = "";

    for ($i = strlen($key); $i > 0; $i -= $bytes) {
        if ($i > $bytes) {
            $p .= $dp;
        } else {
            $p .= substr ($dp, 0, $i);
        }
    }

    # produce ds

    $tmp = "";

    $til = 16 + ord (substr ($a, 0, 1));

    for ($i = 0; $i < $til; $i++) {
        $tmp .= $salt;
    }

    $ds = $func($tmp);

    # Create byte sequence S

    $s = "";

    for ($i = strlen($salt); $i > 0; $i -= $bytes) {
        if ($i > $bytes) {
            $s .= $ds;
        } else {
            $s .= substr ($ds, 0, $i);
        }
    }

    $c = $a; # Ok, we saved this, which will 'seed' our crypt value here in the loop.

    # now we do 5000 iterations of SHA2 (256 or 512)

    for ($i = 0; $i < $loops; $i++) {
        if ($i & 1) { $tmp  = $p; }
        else        { $tmp  = $c; }

        if ($i % 3) { $tmp .= $s; }
        if ($i % 7) { $tmp .= $p; }

        if ($i & 1) { $tmp .= $c; }
        else        { $tmp .= $p; }

        $c = $func($tmp);
    }

    #my $inc1; my $inc2; my $mod; my $end;

    if ($bits == 256) { $inc1 = 10; $inc2 = 21; $mod = 30; $end =  0; }
    else              { $inc1 = 21; $inc2 = 22; $mod = 63; $end = 21; }

    $i = 0;
    $tmp = "";

    do {
        $tmp .= to64 ((ord (substr ($c, $i, 1)) << 16) | (ord (substr ($c, ($i + $inc1) % $mod, 1)) << 8) | ord (substr ($c, ($i + $inc1 * 2) % $mod, 1)), 4);
        $i = ($i + $inc2) % $mod;
    } while ($i != $end);

    if ($bits == 256) { $tmp .= to64 ((ord (substr ($c, 31, 1)) << 8) | ord (substr ($c, 30, 1)), 3); }
    else              { $tmp .= to64  (ord (substr ($c, 63, 1)), 2); }

    return $tmp;
}

# pass - string
# salt - 20 bytes in utf8 compatible binary form
function mysql_caching_sha2_password($pass, $saltbin) {
    $count = 5;
    $iter = 1000 * $count;

    $dgst = sha_crypts("sha256", 256, $pass, $saltbin, $iter);

    $hash = sprintf ("\\\$A\\\$%03d\\\$%s%s", $count, $saltbin, $dgst);
    return $hash;
}

function gen_utf8_salt($len) {
    $r = '';
    for ($i = 0; $i < $len; $i++) {
        // Generate a random Unicode code point between U+0020 and U+007E
        $codePoint = mt_rand(0x0020, 0x007E);
        // Convert the code point to a UTF-8 string
        $r .= mb_convert_encoding('&#'.intval($codePoint).';', 'UTF-8', 'HTML-ENTITIES');
    }
    return $r;
}


$pass = "ąśóżźńÓĄŻŹŃ";
print("for password: $pass\n");
$saltbin = gen_utf8_salt(20);
$hash = mysql_caching_sha2_password($pass, $saltbin);
print("newbin: " . $hash . "\n");
print("newhex: " . strtoupper(current(unpack("H*", $hash))) . "\n");

Format used is:

$A$count$<salt><hash>

salt: 20 bytes binary (needs to be in utf-8 range)

hash: sha256 crypt of count*1000 rounds of binary data and salt