【笔记】PBKDF2算法

PBKDF2是什么

PBKDF2(Password-Based Key Derivation Function)是一个用来导出密钥的函数，常用于生成加密的密码。

它的基本原理是通过一个伪随机函数（例如HMAC函数），把明文和一个盐值作为输入参数，然后重复进行运算，并最终产生密钥。

如果重复的次数足够大，破解的成本就会变得很高。而盐值的添加也会增加“彩虹表”攻击的难度。

破解PBKDF2生成的密码要多久

上图是14年在一台多GPU的高端PC上进行的测试，可以看到，在4个单词（随机从Diceware列表选择）的情况下，如果每秒能猜2万个密码，则要猜出密码平均需要2890年。如果密码的长度再高点，则这个时间是天文数字了。

PBKDF2函数的定义

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

• PRF是一个伪随机函数，例如HASH_HMAC函数，它会输出长度为hLen的结果。

• Password是用来生成密钥的原文密码。

• Salt是一个加密用的盐值。

• c是进行重复计算的次数。

• dkLen是期望得到的密钥的长度。

• DK是最后产生的密钥。

PBKDF2的算法流程

DK的值由一个以上的block拼接而成。block的数量是dkLen/hLen的值。就是说如果PRF输出的结果比期望得到的密钥长度要短，则要通过拼接多个结果以满足密钥的长度：

DK = T1 || T2 || ... || Tdklen/hlen

而每个block则通过则通过函数F得到：

Ti = F(Password, Salt, c, i)

在函数F里，PRF会进行c次的运算，然后把得到的结果进行异或运算，得到最终的值。

F(Password, Salt, c, i) = U1 ^ U2 ^ ... ^ Uc

第一次，PRF会使用Password作为key，Salt拼接上编码成大字节序的32位整型的i作为盐值进行运算。

U1 = PRF(Password, Salt || INT_32_BE(i))

而后续的c-1次则会使用上次得到的结果作为盐值。

U2 = PRF(Password, U1)
...
Uc = PRF(Password, Uc-1)

函数F大致的流程图如下：

PBKDF2算法在PHP中的使用

从PHP5.5版本开始，PHP提供了原生的函数hash_pbkdf2实现PBKDF2算法：

string hash_pbkdf2 ( string $algo , string $password , string $salt , int $iterations [, int $length = 0 [, bool $raw_output = false ]] )

具体用法请看：http://php.net/manual/en/function.hash-pbkdf2.php

而在这个版本之前，我们可以使用其他用户写的兼容方法，例如：

<?php
if (!function_exists('hash_pbkdf2'))
{
    function hash_pbkdf2($algo, $password, $salt, $count, $length = 0, $raw_output = false)
    {
        if (!in_array(strtolower($algo), hash_algos())) trigger_error(__FUNCTION__ . '(): Unknown hashing algorithm: ' . $algo, E_USER_WARNING);
        if (!is_numeric($count)) trigger_error(__FUNCTION__ . '(): expects parameter 4 to be long, ' . gettype($count) . ' given', E_USER_WARNING);
        if (!is_numeric($length)) trigger_error(__FUNCTION__ . '(): expects parameter 5 to be long, ' . gettype($length) . ' given', E_USER_WARNING);
        if ($count <= 0) trigger_error(__FUNCTION__ . '(): Iterations must be a positive integer: ' . $count, E_USER_WARNING);
        if ($length < 0) trigger_error(__FUNCTION__ . '(): Length must be greater than or equal to 0: ' . $length, E_USER_WARNING);
 
        $output = '';
        $block_count = $length ? ceil($length / strlen(hash($algo, '', $raw_output))) : 1;
        for ($i = 1; $i <= $block_count; $i++)
        {
            $last = $xorsum = hash_hmac($algo, $salt . pack('N', $i), $password, true);
            for ($j = 1; $j < $count; $j++)
            {
                $xorsum ^= ($last = hash_hmac($algo, $last, $password, true));
            }
            $output .= $xorsum;
        }
 
        if (!$raw_output) $output = bin2hex($output);
        return $length ? substr($output, 0, $length) : $output;
    }
}

又或者这个：https://github.com/rchouinard/hash_pbkdf2-compat

基于安全考虑，需要注意以下几点：

1. $algo建议选择SHA256或更安全的哈希算法。

2. $salt至少为8字节，且要为随机数。

3. $count迭代次数建议至少为50000次，除非有严格的性能要求。

参考

1. http://en.wikipedia.org/wiki/PBKDF2

2. http://php.net/manual/en/function.hash-pbkdf2.php

3. https://blog.agilebits.com/2014/03/10/crackers-report-great-news-for-1password-4/