密钥派生算法介绍

https://blog.csdn.net/xcxhzjl/article/details/127297263

一、定义

密钥派生函数(Key Derivation Function)就是从一个密码产生出一个或多个密钥，具体就是从一个master key，password或者passphrase派生出一个或多个密钥，派生的过程使用PRF(Pseudo Random Function)。是一种实现key stretching(密钥延长算法，即一种更慢的哈希算法，用于将初始密钥转换成增强密钥，在计算过程中刻意延长时间或者消耗空间，这样有利于保护弱密码)的方法。

●最简单的KDF可以直接使用某种密码学散列算法，如：SHA256。将一个密码转换为一个散列值作为密钥。但易受字典攻击。

二、分类

根据派生源的不同，我们可以将密钥派生算法简单分为两种：

●HKDF(HMAC-based key derivation)，基于HMAC的密钥派生算法

使用另一个随机数(salt)作为输入密钥，利用如HMAC-SHA256的HMAC算法对既有密钥派生新的密钥，并将salt与派生密钥一起存储，用于以后再次从这个既有密钥中派生出相同的派生密钥。salt通常不是私密的，并且可以重用。加盐(salt)可以防止彩虹表导致的密码泄露。

●从一个密码派生出一个或多个密钥：PBKDF2、Bcrypt、Scrypt、Argon2 

三、两种密钥派生算法

1、PBKDF2(CPU-Hard algorithm)

是一种基于密钥派生出密钥的算法，需要消耗很多算力，可防止暴力破解加密。

1. passphrase -> [dklen, salt, c] > 1000] -> hash

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

其中，

passphrase：用于用户认证或者加密程序的操作步骤

dklen：派生所产生的密钥的长度

salt：盐值是一串随机生成的比特

c：迭代的次数

DK：期望的密钥derived key

PRF(Pseudorandom function)：伪随机数产生的密钥，如：hmac-sha256

2、Scrypt(Memory-Hard algorithm)

是一种password-base KDF算法，比起PBKDF2需要消耗更多的资源。Scrypt内部用的是PBKDF2算法，不过内部会长时间的维护一组比特数据，这些数据会在生成复杂的salt的过程中反复加密。

3、区别

总结：PBKDF2是算力消耗性的，Scrypt是资源消耗性的。

PBKDF2和Scrypt都是密钥派生函数(KDFs)，它们通过故意减慢计算速度来实现密钥延长，特别是通过用一个可调参数来控制速度。不同之处在于，Scryp需要大量且可调整的内存量才能进行高效计算。这样能防止专有硬件ASIC/FPGA的暴力破解。

参考博客（比较深入）：

密码学学习笔记_01_密码学综述 - 知乎 (zhihu.com)

创建数字钱包（零）KDF 密钥派生算法 - 腾讯云开发者社区-腾讯云 (tencent.com)

密码学学习笔记_03_随机数与密钥派生 - 知乎 (zhihu.com)

-----------------------------(分割线)--------------------------------

密钥派生函数 Scrypt、Bcrypt 与 Argon2 - 写给开发者的实用密码学

https://zhuanlan.zhihu.com/p/612120129

https://zhuanlan.zhihu.com/p/557583762

以下介绍了三种密钥派生函数（ KDF ）的特点与使用建议，并给出了 Python 演示代码

相关的原文链接：

Bcrypt - Practical Cryptography for Developers (nakov.com)
Scrypt - Practical Cryptography for Developers (nakov.com)
Argon2 - Practical Cryptography for Developers (nakov.com)

PBKDF2(已经过时)  https://zhuanlan.zhihu.com/p/557583762

PBKDF2是一个简单的从密码派生密钥的KDF，它可以抵抗字典攻击和彩虹表攻击。

PBKDF2的思路是对密码和某些填充做多次迭代的HMAC来派生密钥。PBKDF2算法在RFC 2898 (PKCS #5).标准中有描述。

PBKDF2的算法公式描述如下:

key = pbkdf2(password, salt, iterations-count, hash-function, derived-key-len)

• password : 密码/口令等
• salt : 密码学安全伪随机数组
• iterations-count : 迭代次数，如1024
• hash-function : 用于HMAC的散列函数，如SHA256
• derived-key-len : 派生密钥长度(字节数)，如32

目前PBKDF2已经是一种过时的不安全的KDF算法，建议使用Scrypt或Argon2来代替它。

因为PBKDF2不抗GPU攻击( GPU-resistant)，也不抗ASIC攻击( ASIC-resistant)，因此在某些专业的服务器上被攻破的可能性较大，包括配置了专业显卡GPU的服务器或使用专门设计的硬件电路(ASIC)的服务器。
现代的KDF比如 Scrypt或 Argon2都能抵抗字典攻击、GPU攻击与ASIC攻击，因为它们的算法在设计上就要消耗大量CPU与RAM内存资源，且不能通过GPU或ASIC来实现快速的并行计算。
GPU攻击与ASIC攻击在本质上是一种野蛮的试图攻破散列函数的攻击，因此现代KDF的设计目标之一就是使这种野蛮破解的成本上升到实际不可能实现的程度。

Bcrypt (开始淘汰)

Bcrypt 也是一个 KDF ，问世时间早于 Scrypt ，对于 ASIC 、GPU 攻击的抗性相对弱一些。其虽然也可以配置迭代数，但由于对内存的压力较小，因此比较容易构建相应的硬件加速密码破解器。

来自 https://zhuanlan.zhihu.com/p/557583762 的说法： 

Bcrypt是一个开始被淘汰的密码学KDF。它提供可配置的迭代次数，但使用恒定的内存，因此相对来说，比较容易被硬件加速密码破解器所破解，在抗GPU攻击和抗ASIC攻击上已经不再安全。 

算法参数、盐、Hash 的共同存储

在很多的应用、框架和工具中（比如 WordPress 站点的数据库），Bcrypt 加密后的密码都是和算法设置以及盐保存在一起的，体现为一个单一的字符串（字符串有着特定的格式）。这个字符串包含数个部分，以 $ 符号分割。例如，密码 p@ss~123 以 Bcrypt 标准格式存储的形式就是下面这样的（给出三个例子是为了方便读者看清特征）：

$2a$07$wHirdrK4OLB0vk9r3fiseeYjQaCZ0bIeKY9qLsNep/I2nZAXbOb7m
$2a$12$UqBxs0PN/u106Fio1.FnDOhSRJztLz364AwpGemp1jt8OnJYNsr.e
$2a$12$8Ov4lfmZZbv8O5YKrXXCu.mdH9Dq9r72C5GnhVZbGNsIzTr8dSUfm

什么时候用 Bcrypt ？

在配置合适的前提下，Bcrypt 被认为是安全的 KDF 函数，在实践中应用广泛。但由于 Scrypt 比 Bcrypt 更加安全，因此很多应用更倾向于使用 Scrypt（或 Argon2 ）。但我个人更推荐使用 Argon2 。

Scrypt

Scrypt 是一个强大的密钥派生函数，其通过内存密集的计算方式来抵抗 GPU、ASIC、FPGA 这类密码破解硬件的攻击。

Scrypt 接收多个输入参数，进行计算后输出密钥：

key = Scrypt(password, salt, N, r, p, derived-key-len)

其中的参数被称为" Scrypt 配置参数"，说明如下：

• N - 迭代次数，将影响 CPU 和内存用量，例：16384 、2048 ；
• r - 块大小，将影响 CPU 和内存用量，例：8 ；
• p - 并行因数 （并行运行的线程数，将影响 CPU 和内存用量），通常为 1 ；
• password - 输入的密码（推荐至少为 8 - 10 个字符）；
• salt - 安全产生的随机字节序列（最小为 64 位，推荐 128 位）；
• derived-key-len - 输出的密钥要有多少字节长，例如 32 （256 位）

Scrypt 计算过程中的每一步都会 按照强相关的顺序 访问内存，这就让内存读写性能成为了算法速度的瓶颈。Scrypt 运行时所需的内存量可以通过下面的公式来计算：

所需内存 = 128 * N * r * p 字节

例如：128 * N * r * p = 128 * 16384 * 8 * 1 = 16MB（或 128 * 2048 * 8 * 1 = 2MB）

具体怎么选择参数，要取决于我们能够等待的时间和所需的安全等级（即抗破解的能力）：

• 用于交互式登录的示例参数：N=16384, r=8, p=1（RAM = 16MB）。交互式的登录一般耗时都要小于 0.5s ，所以必须快速完成计算。同样的，对于服务端而言，如果同时有很多用户登录，那么 Scrypt 的缓慢会拖慢整个系统；
• 用于文件加密的示例参数：N=1048576, r=8, p=1（RAM = 1GB）。当要加密硬盘时，通常不会频繁解密数据（一天可能只解密 2 ~ 3次），所以你可能会愿意多等 2 ~ 3 秒作为提升安全性的代价。

你可以在开发自己的 app 或系统的过程中，自己多选几组参数进行测试。应该总是选择所用语言和平台所支持的、速度最快的 Scrypt 实现，因为尝试破解密码的人一定会选用最快的这个库。某些实现（如 python 实现）可能会比最快的实现慢上 100 倍。

在 MyEtherWallet 加密钱包应用中，默认的参数是 N=8192, r=8, p=1 。对于此类应用而言，该强度不够高，但可以通过要求用户输入又长又复杂的密码来对抗密码破解攻击。

示例 - Python 中的 Scrypt

接下来，我们在 Python 中使用 Scrypt 来体验从密码派生密钥的过程。首先，使用 pip 安装 scrypt 包：

pip install scrypt

注意，scrypt 包依赖 OpenSSL ，所以要先在默认目录中安装 OpenSSL （Windows 下可能为： C:\OpenSSL-Win64），然后再安装 scrypt python 包。

装好 scrypt 包后，通过如下 Python 代码来计算 Scrypt hash 值：

（本例中使用了较小的迭代数，这么做只是希望减少所需的时间。实际应用中推荐使用 16384 ）

import pyscrypt
​
salt = b'aa1f2d3f4d23ac44e9c5a6c3d8f9ee8c'
passwd = b'p@$Sw0rD~7'
key = pyscrypt.hash(passwd, salt, 2048, 8, 1, 32)
print("Derived key:", key.hex())

Scrypt 接收的参数：password（字节序列）、salt（字节序列）、迭代数、每次迭代的块大小、并行因数、输出密钥长度（派生密钥的字节数）。上面代码的输出如下：

Derived key: b'e813a6f6ccc4e9110193bf9efb7c0a489d76655f9e36629dccbeaf2a73bc0c6f'

可以试着修改迭代数或块大小参数，来这些参数的变化对于执行时间的影响。不过别忘了，上面的 Python Scrypt 是一个比较慢的实现，如果要实际应用，可以试着找些更快的库

译注：所需要的密钥长度为 32 字节，而上面输出的实际长度为 64 字节，这是正确的结果。 我们在参数中写的"密钥长度"指的是【密钥二进制长度为32字节，即256位】，而由于真正包含8位信息的一个字节中的大部分是不可打印的，这就意味着它们无法被显示。因此，通行表示字节的方式是使用 16 进制字符（即字符 0 ~ f ）。这样的一个字符只能表示 4 位的信息量，所以我们需要两个这样的字符才能涵盖完整的 8 位（即 1 字节）信息。这也就造成了最终我们得到的密钥字符长度是实际二进制密钥长度的 2 倍

算法参数、盐、Hash 的共同存储

在很多的应用、框架和工具中，Scrypt 加密后的密码都是和算法设置以及盐保存在一起的，体现为一个单一的字符串（以特定的格式）。这个字符串包含数个部分，以 $ 符号分隔。例如，密码 p@ss~123 以 Scrypt 标准格式存储的形式就是下面这样的（给出三个例子是为了方便读者看清特征）：

16384$8$1$kytG1MHY1KU=$afc338d494dc89be40e317788e3cd9166d066709db0e6481f0801bd918710f46
16384$8$1$5gFGlElztY0=$560f6229356c281a525fad4e2fc4c209bb55c21dec789381335a32bb84888a5a
32768$8$4$VGhlIHF1aWo=$54d657cec8b3aaca675b407e790bccf1dddb0a23665cd5f994820a736d4b58ba

什么时候用 Scrypt ？

在配置合适的前提下，Scrypt 被认为是高度安全的 KDF 函数，所以可以用在任何需要 KDF 的地方——加密钱包、文件、App 密码等场景都可以

Argon2

Argon2 是一个现代的 抗ASIC、抗GPU 的安全密钥派生函数。在配置得当、且消耗资源相当的情况下，其相较于 PBKDF2、Bcrypt 和 Scrypt ，有着更强的密码破解抗性。

Argon2 变种

Argon2 有多个变种：

• Argon2d - 提供强大的 GPU 攻击抗性，但在非常特殊的情况下，会有被旁路攻击的风险；
• Argon2i - 提供弱一些的 GPU 攻击抗性，但没有被旁路攻击的风险；
• Argon2id - 是上面两种变体的混合版，推荐使用这个版本

Argon2 的配置参数

Argon2 有如下几个配置参数，和 Scrypt 很像：

• 密码 P ： 要被 hash 的密码（或消息 message ）；
• 盐 S ： 随机生成的盐（用于密码 hash 时，推荐使用 16 字节长度的盐）；
• 迭代数 t ： 要进行的迭代次数；
• memorySizeKB m ： 要使用的内存大小（单位为 kbytes） ；
• parallelism p ： 并行程度（即线程数）；
• outputKeyLength T ： 想要算法返回的字节长度

示例 - Python 中的 Argon2

接下来我们写一些代码，来在 Python 中使用 Argon2 进行密钥派生。

首先，用下面的命令安装 python 包 argon2_cffi ：

pip install argon2_cffi

用下面的代码来计算 Argon2 ：

import argon2, binascii
​
hash = argon2.hash_password_raw(
    time_cost=16, memory_cost=2**15, parallelism=2, hash_len=32,
    password=b'password', salt=b'some salt', type=argon2.low_level.Type.ID)
print("Argon2 raw hash:", binascii.hexlify(hash))
​
argon2Hasher = argon2.PasswordHasher(
    time_cost=16, memory_cost=2**15, parallelism=2, hash_len=32, salt_len=16)
hash = argon2Hasher.hash("password")
print("Argon2 hash (random salt):", hash)
​
verifyValid = argon2Hasher.verify(hash, "password")
print("Argon2 verify (correct password):", verifyValid)
​
try:
    argon2Hasher.verify(hash, "wrong123")
except:
    print("Argon2 verify (incorrect password):", False)

上面的代码首先生成一个 "raw hash" （256 位密钥），这一步是基于 argon2 的密钥派生，和 Scrypt 类似。下一步会派生一个 argon2 hash ，其中包含了算法参数、盐和派生密钥，可以用于后续的密码存储和验证。这段代码的最后将对密码进行验证。

Argon2 接收如下几个输入配置参数：time_cost（时间消耗，即迭代次数）、memory_cost（要使用的 KB 数）、parallelism（并行度，使用多少个线程）、hash_len（派生密钥的长度）、salt_len（随机生成盐的长度，通常是 128 位 / 16 字节）。

上面代码的示例输出如下：

Argon2 raw hash: b'157f21dd3fdf7bafb76d2923ccaffa0b7be7cbae394709474d2bc66ee7b09d3e'
Argon2 hash (random salt): $argon2id$v=19$m=32768,t=16,p=2$Rfy6J41W9idBU+n/8sZc6Q$i3QYYPtoogIAw78I2qqlUQ8vjzUXGG1V6QsBOq2NIp4
Argon2 verify (correct password): True
Argon2 verify (incorrect password): False

上面输出中的 argon2 hash 是标准格式的：【配置参数 + 派生密钥 + 随机盐】。按照设计，每次代码执行时所用的盐和派生密钥都应该是不同的。

试着多执行几次上面的代码，会发现派生密钥总是相同的（因为盐相同），而派生的 argon2 hash 则每次都不同（这部分所用的随机盐是每次执行时在算法内部重新生成的）。

可以试着修改 time_cost 和 memory_cost 设置，来感受一下它们将如何影响密钥派生时间。

算法参数、盐、Hash 的共同存储

在很多的应用、框架和工具中，Argon2 加密后的密码都是和算法设置以及盐保存在一起的，体现为一个单一的字符串（字符串有着特定的格式，就如上面展示的那样）。这个字符串包含数个部分，以 $ 符号分割。例如，密码 p@ss~123 以 Argon2 标准格式存储的形式就是下面这样的（给出三个例子是为了方便读者看清特征）：

$argon2d$v=19$m=1024,t=16,p=4$c2FsdDEyM3NhbHQxMjM$2dVtFVPCezhvjtyu2PaeXOeBR+RUZ6SqhtD/+QF4F1o
$argon2d$v=19$m=1024,t=16,p=4$YW5vdGhlcnNhbHRhbm90aGVyc2FsdA$KB7Nj7kK21YdGeEBQy7R3vKkYCz1cdR/I3QcArMhl/Q
$argon2i$v=19$m=8192,t=32,p=1$c21hbGxzYWx0$lmO1aPPy3x0CcvrKpFLi1TL/uSVJ/eO5hPHiWZFaWvY

上面的几个 hash 值都保存了相同的密码，但都有着不同的算法参数和不同的盐。

Argon2有三个变体:

• Argon2d : 速度比较快，对GPU攻击具有很高的抵抗力，适用于不受侧信道攻击威胁的应用程序，比如加密货币。
• Argon2i : 速度较慢，对GPU攻击抗力相对较弱，但不会受到侧信道攻击。
• Argon2id : Argon2i和Argon2d的混合体，即对GPU攻击具有很高的抵抗力，也不会受到侧信道攻击。推荐首选的Argon2算法。 

什么时候用 Argon2 ？

在配置合适的前提下，Argon2 被认为是高度安全的 KDF 函数，是目前产业界能用到的最佳选择之一，所以可以用在任何需要 KDF 的地方——加密钱包、文件、App 密码等场景都可以。一般来说，Argon2 是最为推荐的 KDF ，优于 Scrypt, Bcrypt 和 PBKDF2 。

总体而言，安全高度上： Argon2 > Scrypt > Bcrypt(开始淘汰) > PBKDF2(过时)