应用密码学入门

从哈希到加密，一网打尽。

1哈希
2MAC
3未完待续......

起步

在非正式的定义上，哈希函数是将一个较大的定义域映射到一个固定的相对小范围的函数，例如将字节数组映射到一个小的定长字符串，或者映射到一个整数等。

例如如下就是一个简单的哈希函数：

fn simple_hash(input: u64): u64 {
    input % 64
}

我们可以使用这种哈希函数来构建哈希表。但是它的缺点很明显，即我们可以很容易构造出具有相同哈希值的两个不同的输入值。

在应用密码学中，一个好的哈希函数应该避免碰撞，这使得我们很难通过哈希值构造出输入值。例如，如果我们通过比较哈希值来判断两个文件是否一致，那么如果攻击者找到两个具有相同哈希值的文件，那么系统就错误地认为这两个文件一致，这很可能会带来一些安全问题。

当然，因为鸽巢原理，哈希函数总是存在碰撞，不过我们还是可以定义如下三种性质（其中 HH 为哈希函数）：

  • 抗碰撞性。即攻击者无法在合理时间内，找到任意两个不同的 x≠x′x \ne x'，使得 H(x)=H(x′)H(x) = H(x')。
  • 抗第二原像性。即给定 xx，攻击者无法在合理时间内找到 x′x'，使得 x≠x′x \ne x'，且 H(x)=H(x′)H(x) = H(x')。
  • 抗第一原像性。即给定 yy（其中 y=H(x)y = H(x)，而 xx 未知），攻击者无法在合理时间内找到 x′x'，使得 H(x′)=yH(x') = y。

如果一个哈希函数满足这三个性质，那么此时我们称其为密码学安全的哈希函数。虽然抗碰撞性不代表它抗第一原像，但是实践中，我们谈论抗碰撞哈希函数的时候，一般我们也隐式地表示其也抗第一原像和第二原像性。

此外我们还有其他性质：

  • 雪崩效应。即我们对输入数据做微小的改动，输出的结果也会发生显著的变化。
  • 伪随机性。即输出值看起来就像是随机噪声一样。这一点使得哈希函数的输出均匀分布在值域中。如果一个经过特殊设计的、能接收额外的密钥参数的哈希函数，其结果和随机函数在计算上不可区分（需要经过证明），那么我们也将其称为 PRF（伪随机函数）。

将字符串转换为一个定长的值是很有用的：

  • 我们可以使用它来以极小的成本标识一个大字符串（比如一个文件）。同时因为抗第二原像性，我们在实践中可以认为输出的哈希值即原值的指纹，而我们可以仅根据指纹就来判断两个原值是否相同。例如 Git 使用哈希值来判断两个文件是否一致。
  • 因为伪随机性，我们可以利用哈希函数来将输入均匀地分散在值域中。例如我们可以将值的哈希值模 256，并将其分发到对应的槽位，那么我们让多个值均匀地分布到多个槽位中。我们可以这样来将负载均衡在不同的槽位。

我们还需要注意到一些哈希函数可能存在长度扩展攻击问题。即，给定一个未知消息 mm 的哈希值 H(m)H(m)、未知消息 mm 的长度 L(m)L(m)，那么攻击者可以在不知道 mm 的前提下，知道扩展消息 m+padding+xm + \text{padding} + x（符号 “++” 表示字符串拼接）的哈希值 H(m+padding+x)H(m + \text{padding} + x)。这在某些情况下可能会存在问题（因此，使用哈希函数来计算消息认证码的时候，实践中我们使用双重哈希等方式来避免）。

经典防碰撞哈希算法有：

  • MD5 和 SHA-1。不过已经多次被成功攻击，建议尽量不要使用。它们都已经构建出了碰撞，即其不满足抗碰撞性。虽然我们认为它们还是抗第一原像的，但是仍然不建议使用。
  • SHA-2。包括 SHA-256 和 SHA-512 等，没有碰撞，但是存在长度扩展攻击问题。
  • SHA-3。包括 SHA3-256 和 SHA3-512 等。
  • BLAKE3。一种安全、快速的哈希算法。

我们有一个经典的用例会使用到哈希算法。即我们希望在数据库中存储用户名和密码，这样，用户登录的时候，我们会将登录请求中的密码和数据库中的密码比较来进行认证。但是将密码明文保存在数据库中是不安全的（一旦数据库泄露，那么用户的密码就会泄露，而用户往往会在多个网站使用相同的密码）。作为一个负责任的工程师，我们需要降低密码泄露导致的风险。我们很容易想到在数据库中存储密码的哈希值，这样，我们会将登录请求中的密码计算一次哈希后，再和数据库中密码的哈希值来比较。这相比于存储密码明文而言安全很多，但是仍然有风险：

首先是 彩虹表攻击。用户可能会使用弱密码。攻击者可以事先采集常用的弱密码，并对其进行哈希。这使得攻击者拿到了密码的哈希值就很容易推导出密码的真实值。

我们可以通过加盐的形式来避免。我们可以选择一个随机字符串，将随机字符串和真实密码拼接并哈希。而且，我们可以对每个用户都随机一个盐，这使得攻击者期望通过构建一个彩虹表就能轻松获取到大部分使用弱密码的用户的真实密码的天真想法正式泡汤。

不过攻击者仍然可以攻击。例如攻击者想要获取到某个用户的密码，那么他可以遍历所有的弱密码，并加盐哈希并尝试破解它，或者暴力迭代。为了提高安全性，我们需要尽可能提高哈希计算成本。比如，可以通过重复计算哈希来提高成本，例如重复计算 2122^{12} 次哈希。

密码哈希算法有：

  • bcrypt。基于 Blowfish 的自适应密码哈希方案。它通过 cost 参数控制计算成本，并且自带盐。它长期被广泛使用，不过内存占用不高，抗 GPU / ASIC 暴力破解的能力不如更新的内存硬方案；此外它还有密码长度截断等工程限制。
  • Argon2。它是典型的内存硬密码哈希算法。它除了提高 CPU 成本，也主动提高内存成本，从而让并行暴力破解和专用硬件攻击更贵。今天新系统里更常推荐使用 Argon2id。

但是在另一边，我们还需要一种极致快速的哈希算法，甚至我们愿意为了它而牺牲一些密码学安全特性。我们会在哈希表等数据结构中使用它，有：

  • SipHash。带密钥的短输入哈希 / PRF，常用于哈希表键值的哈希计算，目标之一是抵御哈希洪泛攻击。它比纯追求速度的非密码学哈希更安全，但也更慢，因此通常用于“输入可能来自不可信方”的哈希表场景，而不是做文件摘要或密码存储。
  • fxhash。极快的非密码学哈希，常见于 Rust 编译器一类“输入可信、追求吞吐”的内部数据结构。它不提供抗碰撞性，也不考虑抗 DoS，因此不适合直接暴露给不可信输入。

最后，还有一些和哈希函数相关的概念：

  • PRF。伪随机函数。如前所述，其接收密钥和输入，并给出一个输出。其他人无法区分 PRF 和一个真随机函数。
  • MAC。消息认证码。其接收密钥和输入，并给出一个输出。它的目的主要是使得掌握密钥的能够验证消息的完整性和真实性，用于防止篡改。
  • KDF。密钥派生函数。用于给定一个密钥，派生出多个密钥。
  • XOF。可扩展输出函数。它是哈希函数的一种推广，使得能够生成指定长度的比特串。

实现

SHA-2

SHA-2 主要包括 SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224 和 SHA-512/256。最常见的的是 SHA-256 和 SHA-512。

我们使用 SHA-2 算法的时候，它会：

  • 将数据填充为块长度的整数倍（末尾有 64 位记录原始长度）。然后分为多个块。
  • 对于每个块，将其和上一个块的中间结果一起使用压缩函数，将其转换为一个中间结果。其中对于第一个块，因为其没有上一个块，所以使用一些常数来代替。

它按固定大小的 block 处理消息，并维护一组链式状态，最终输出的 digest 长度取决于具体变体。我们将其称为迭代压缩。不过也正因为此，它存在长度扩展攻击，所以使用它的时候，需要确保不会收到这种攻击的影响。

SHA-3

SHA-3 包括：

  • SHA3-224、SHA3-256、SHA3-384、SHA3-512。和 SHA-2 一样，生成固定长度的输出。
  • SHAKE128、SHAKE256 这类可扩展输出函数（extendable-output function，XOF），可以按需输出任意长度的结果。

SHA-3 的底层是 Keccak 算法，核心结构是 sponge（海绵）构造。它维护一个固定大小的内部状态（对于 SHA3-256 是 1600 比特），处理流程分两阶段：absorb（吸收）和 squeeze（挤压）阶段。相比 SHA-2 而言它不存在长度扩展函数。

BLAKE3

BLAKE3 是现代高性能哈希函数。它相比 SHA-2 和 SHA-3 而言：

  • 速度很高，尤其适合大文件和大量数据的摘要。
  • 支持增量处理和并行处理。BLAKE3 把输入切成多个 chunk（每个 1024 字节），每个 chunk 再切成多个内部 block，并用一棵二叉 Merkle 树把所有 chunk 的输出归约成最终摘要。
  • 不仅能做普通哈希，还能扩展成 XOF、KDF、PRF、MAC 等模式。

bcrypt

bcrypt 是一个密码哈希算法。它的输出看起来为：

$2b$12$nR8WQ5aHj6xYkV3mF0pOeOZ4s7TtUvJqL2dCwB1eXyA0zG9oHnNmK

可以看到，它包括：

  • 版本。即前缀 $2b$（也常见 $2a$、$2y$），表示 bcrypt 的算法版本。$2a$ 是原始实现，$2b$ 是 OpenBSD 修正了长度处理问题后的版本，$2y$ 多见于 crypt_blowfish 的兼容标识。三者输出格式兼容，验证端通常都能识别。
  • Cost。即代价，这里的 12。使用它来控制计算开销。我们会迭代 2C2^C 次，其中 CC 即为这个参数。
  • Salt。即盐，紧跟 cost 之后的 22 个字符，是 bcrypt 内部使用的 128 比特盐值的 Base64 编码。它在哈希时随机生成并直接嵌在输出里，因此验证时不需要额外存储盐。
  • 哈希值。即末尾的 31 个字符，是用密码、盐和 cost 参数经过 2C2^C 轮 Blowfish 派生出的 184 比特输出的 Base64 编码。验证密码时，bcrypt 会取出输出里的 cost 和 salt，用同样的参数重新计算哈希，再和输出里的哈希值比较。

不过它也存在问题。bcrypt 更偏 CPU 密集，而不是内存密集。我们可以使用 Argon2id 来代替它，从而提供更好的安全性，不过 bcrypt 是主流的密码哈希算法。

Argon2

Argon2 是专门为密码哈希设计的内存硬函数。它会在计算过程中主动占用大量内存，并多轮混合这些内存块，从而提高 GPU、FPGA、ASIC 这类并行暴力破解的成本。

它有三个常见变体：

  • Argon2d。更依赖数据相关访问，偏向抗 GPU 攻击；
  • Argon2i。更强调数据无关访问，偏向降低某些侧信道风险；
  • Argon2id。综合两者特点，也是今天最常推荐的通用选择。

SipHash

SipHash 是带密钥的短输入 PRF。它常见的写法如 SipHash-2-4，其中前后的数字表示压缩轮数和终结轮数。

我们一般使用它来给哈希表中的 key 做哈希，同时它能够避免恶意攻击者导致的哈希算法。即，当我们不泄露密钥时（我们可以在程序初始化的时候随机一个密钥），攻击者无法构建多个 key 来实现哈希冲突，使得哈希表的性能下降。

fxhash

fxhash 是一种极度偏向性能的非密码学哈希。一般用在 Rust 社区中，比如 rustc 内部。

它的实现相当直接：对字节序列按机器字长（通常 usize）逐块读取，每个块用一条 multiply + rotate 的混合操作累加到当前 hash 状态，最后对尾部剩余的几个字节做单独处理。核心就是一个固定的乘数和旋转。对 CPU 分支预测器和流水线都很友好，速度非常接近内存带宽上限。

链接和引用

  1. 深入浅出密码学. [美] David Wong 著, 韩露露等译, 人民邮电出版社.
  2. 现代密码学——原理与协议. [美] Jonathan Katz 等著, 任伟译, 国防工业出版社.
  3. NIST / FIPS 180-4 / Secure Hash Standard: https://csrc.nist.gov/pubs/fips/180-4/upd1/final
  4. NIST / FIPS 202 / SHA-3 Standard: https://csrc.nist.gov/pubs/fips/202/final
  5. RFC 9106 / Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications: https://datatracker.ietf.org/doc/rfc9106/
  6. GitHub / BLAKE3-team / BLAKE3: https://github.com/BLAKE3-team/BLAKE3
  7. cr.yp.to / SipHash: https://cr.yp.to/siphash/siphash-20120918.pdf
  8. docs.rs / fxhash: https://docs.rs/crate/fxhash/latest
下一篇MAC