密码学哈希 vs 非密码学哈希：设计哲学的分野

2011 年 12 月 28 日，在第 28 届混沌通信大会（28C3）上，Alexander Klink 和 Julian Wälde 演示了一种攻击：通过精心构造的 HTTP POST 参数，他们能让一台 PHP 服务器的 CPU 使用率飙升到 100%，并持续数分钟。攻击的原理极其简单——构造大量哈希碰撞的键名，让 PHP 的哈希表退化为链表。

这就是著名的 HashDoS 攻击，它直接影响了 PHP、Java、Python、Ruby、Node.js 等几乎所有主流语言的哈希表实现。此后，“哈希函数的安全性”从一个纯理论问题变成了每个语言运行时都必须面对的工程问题。

这篇文章讨论两类哈希函数的设计哲学：密码学哈希（SHA-256、BLAKE3 等）和非密码学哈希（MurmurHash、xxHash、wyhash 等），以及夹在两者之间的特殊存在——SipHash。

下图展示了哈希函数的安全性-性能光谱和典型用途：

一、两类哈希函数的设计目标

密码学哈希的三大性质

密码学哈希函数 \(H: \{0,1\}^* \to \{0,1\}^n\) 必须满足三个安全性质：

1. 抗原像性（Pre-image resistance）：给定 \(y\)，找不到 \(x\) 使得 \(H(x) = y\)
2. 抗第二原像性（Second pre-image resistance）：给定 \(x_1\)，找不到 \(x_2 \neq x_1\) 使得 \(H(x_1) = H(x_2)\)
3. 抗碰撞性（Collision resistance）：找不到任意 \((x_1, x_2)\) 使得 \(H(x_1) = H(x_2)\)

这三个性质的强度递增：抗碰撞性蕴含抗第二原像性。

密码学哈希的输出通常很长（256 bit+），计算相对较慢（SHA-256 约 500 MB/s），但安全性是刚性要求——差一点都不行。

非密码学哈希的设计目标

非密码学哈希函数的目标完全不同：

1. 速度：越快越好，通常以 GB/s 或 cycles/hash 衡量
2. 分布均匀性：输出应该”看起来随机”，减少碰撞
3. 雪崩效应（Avalanche effect）：输入改变 1 bit，输出平均改变 50% 的 bit

注意第 3 点——雪崩效应在两类哈希中的含义不同：

• 密码学哈希需要严格雪崩：每个输出 bit 依赖每个输入 bit，且改变概率精确为 50%
• 非密码学哈希只需要统计雪崩：大部分输出 bit 会变化，分布大致均匀即可

二、雪崩效应的量化分析

严格雪崩准则（SAC）

1985 年，Webster 和 Tavares 提出了严格雪崩准则（Strict Avalanche Criterion, SAC）：如果输入翻转一个 bit，每个输出 bit 以恰好 50% 的概率翻转，则满足 SAC。

测量方法：

// 测量哈希函数的雪崩效应
void avalanche_test(uint64_t (*hash)(uint64_t), int num_samples) {
    double bias[64] = {0};

    for (int i = 0; i < num_samples; i++) {
        uint64_t x = random_uint64();
        uint64_t h0 = hash(x);

        for (int bit = 0; bit < 64; bit++) {
            uint64_t h1 = hash(x ^ (1ULL << bit));
            uint64_t diff = h0 ^ h1;

            for (int j = 0; j < 64; j++) {
                if (diff & (1ULL << j))
                    bias[j] += 1.0;
            }
        }
    }

    // 理想情况：每个 bias[j] ≈ 0.5 * num_samples * 64
    double total_bias = 0;
    for (int j = 0; j < 64; j++) {
        double expected = 0.5 * num_samples * 64;
        double actual = bias[j];
        total_bias += fabs(actual / expected - 1.0);
    }
    printf("Average avalanche bias: %.6f (ideal: 0.000000)\n",
           total_bias / 64);
}

实测结果

FNV-1a 和 DJB2 这类”经典”哈希函数的雪崩效应远不如现代设计。这也是它们在现代系统中逐渐被淘汰的原因之一。

三、HashDoS 攻击的原理与影响

攻击原理

大多数哈希表使用链式或开放寻址解决冲突。当大量键碰撞到同一个 bucket 时：

• 链式哈希：退化为链表，查找从 O(1) 变成 O(n)
• 开放寻址：探测链变长，性能严重下降

攻击者需要做的就是：找到 \(n\) 个不同的键，使它们的哈希值相同（或映射到同一个 bucket）。

对于确定性哈希函数（没有随机种子），攻击者可以离线计算碰撞。例如 MurmurHash2 没有种子参数时：

# 概念演示：寻找 MurmurHash2 碰撞
# 真实攻击中，利用 MurmurHash2 的代数结构可以高效构造碰撞
# 而不需要暴力搜索
def find_collisions(target_hash, n):
    # 利用 differential cryptanalysis 技巧
    # MurmurHash2 的混合函数是可逆的
    # 因此可以从输出反推输入
    pass

影响范围（2011-2012）

• PHP 5.x：使用 DJBX33A（DJB2 变体），碰撞构造极其简单
• Java HashMap：使用乘法哈希，碰撞可以用等价类构造（Java 8 后改为红黑树兜底）
• Python dict：使用自定义的 FNV 变体，碰撞可构造（Python 3.3 后改为 SipHash）
• Ruby Hash：类似问题（后改为 SipHash）
• Node.js：V8 的哈希表也受影响

防御方案

主要有三种防御思路：

1. 随机化种子：启动时随机生成哈希种子，攻击者无法离线构造碰撞
2. 使用 PRF 类哈希：SipHash 被设计为伪随机函数（PRF），即使攻击者知道输入输出对，也无法预测新输入的输出
3. 二级结构兜底：Java 8 的做法——当链表长度超过 8 时，转换为红黑树，把最坏情况从 O(n) 降到 O(log n)

四、SipHash：哈希表的守护者

设计背景

2012 年，Jean-Philippe Aumasson 和 Daniel J. Bernstein 发表了 SipHash。论文标题直白：SipHash: a fast short-input PRF。

SipHash 的定位很独特——它不是密码学哈希（不提供抗碰撞性），也不是普通的非密码学哈希（它提供 PRF 安全性）。它是一个带密钥的哈希函数，专为哈希表设计。

PRF 安全性

PRF（伪随机函数）的定义：给定随机密钥 \(k\)，\(\text{SipHash}_k(x)\) 的行为与真随机函数不可区分。

这意味着：即使攻击者看到了任意多组 \((x_i, \text{SipHash}_k(x_i))\)，也无法： - 预测新输入 \(x_{n+1}\) 的输出 - 构造碰撞对

SipHash 的内部结构

SipHash-c-d 表示 \(c\) 轮压缩和 \(d\) 轮终结化。常用变体：

• SipHash-2-4：标准版，安全性最高（Python、Rust 默认）
• SipHash-1-3：快速版，安全性稍低但足够（Rust 的 ahash 在某些平台用它）

核心是 ARX（Add-Rotate-XOR）结构，每轮操作：

// SipHash 的 SipRound
#define SIPROUND                        \
    v0 += v1; v1 = ROTL64(v1, 13);    \
    v1 ^= v0; v0 = ROTL64(v0, 32);    \
    v2 += v3; v3 = ROTL64(v3, 16);    \
    v3 ^= v2;                          \
    v0 += v3; v3 = ROTL64(v3, 21);    \
    v3 ^= v0;                          \
    v2 += v1; v1 = ROTL64(v1, 17);    \
    v1 ^= v2; v2 = ROTL64(v2, 32)

完整实现：

// siphash.c — SipHash-2-4 参考实现
#include <stdint.h>
#include <string.h>

#define ROTL64(x, b) (((x) << (b)) | ((x) >> (64 - (b))))

#define SIPROUND do {                   \
    v0 += v1; v1 = ROTL64(v1, 13);    \
    v1 ^= v0; v0 = ROTL64(v0, 32);    \
    v2 += v3; v3 = ROTL64(v3, 16);    \
    v3 ^= v2;                          \
    v0 += v3; v3 = ROTL64(v3, 21);    \
    v3 ^= v0;                          \
    v2 += v1; v1 = ROTL64(v1, 17);    \
    v1 ^= v2; v2 = ROTL64(v2, 32);    \
} while(0)

uint64_t siphash(const void *src, size_t len,
                 uint64_t k0, uint64_t k1) {
    uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
    uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
    uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
    uint64_t v3 = k1 ^ 0x7465646279746573ULL;

    const uint8_t *p = (const uint8_t *)src;
    const uint8_t *end = p + (len & ~7ULL);
    uint64_t b = (uint64_t)len << 56;

    // 处理完整的 8 字节块
    while (p < end) {
        uint64_t m;
        memcpy(&m, p, 8);
        v3 ^= m;
        SIPROUND; SIPROUND;  // c = 2
        v0 ^= m;
        p += 8;
    }

    // 处理尾部（0-7 字节）
    switch (len & 7) {
        case 7: b |= (uint64_t)p[6] << 48; /* fall through */
        case 6: b |= (uint64_t)p[5] << 40; /* fall through */
        case 5: b |= (uint64_t)p[4] << 32; /* fall through */
        case 4: b |= (uint64_t)p[3] << 24; /* fall through */
        case 3: b |= (uint64_t)p[2] << 16; /* fall through */
        case 2: b |= (uint64_t)p[1] << 8;  /* fall through */
        case 1: b |= (uint64_t)p[0];        break;
        case 0: break;
    }

    v3 ^= b;
    SIPROUND; SIPROUND;  // c = 2
    v0 ^= b;

    // 终结化
    v2 ^= 0xff;
    SIPROUND; SIPROUND; SIPROUND; SIPROUND;  // d = 4

    return v0 ^ v1 ^ v2 ^ v3;
}

性能特点

SipHash 不是最快的哈希——但它足够快：

SipHash-2-4 比 wyhash 慢约 3-4 倍，但对于哈希表来说，哈希计算通常不是瓶颈——cache miss 才是。

五、Length Extension Attack：密码学哈希的隐藏陷阱

什么是长度扩展攻击

这个攻击利用了 Merkle-Damgård 构造的一个”特性”：如果你知道 \(H(m)\)，你可以在不知道 \(m\) 的情况下计算 \(H(m \| \text{padding} \| m')\)。

原因：Merkle-Damgård 构造中，\(H(m)\) 就是最后一个压缩函数的输出（即内部状态）。攻击者可以从这个状态继续”压缩”新的数据块。

受影响的哈希函数：MD5、SHA-1、SHA-256。不受影响的：SHA-3（Keccak 使用 sponge 构造）、BLAKE2/BLAKE3（使用 HAIFA 构造）。

实际危害

很多系统错误地使用 \(H(\text{secret} \| \text{message})\) 作为 MAC（消息认证码）。这不安全——攻击者可以扩展消息。

正确的做法是使用 HMAC：\(\text{HMAC}(k, m) = H((k \oplus \text{opad}) \| H((k \oplus \text{ipad}) \| m))\)。

或者直接使用不受此攻击影响的 BLAKE3。

// 错误：直接拼接密钥和消息
// 攻击者知道 H(secret || msg)，可以构造 H(secret || msg || padding || extra)
uint8_t bad_mac[32];
sha256(secret_concat_msg, secret_len + msg_len, bad_mac);

// 正确：使用 HMAC
uint8_t good_mac[32];
hmac_sha256(secret, secret_len, msg, msg_len, good_mac);

六、现代非密码学哈希：wyhash 与 xxHash3

wyhash：极简主义的胜利

wyhash（王一，2019）可能是目前最快的通用非密码学哈希函数。它的核心思想极其简单——只用 MUM (Multiply-and-Mix) 操作：

// wyhash 的核心操作
static inline uint64_t wymum(uint64_t a, uint64_t b) {
    __uint128_t r = (__uint128_t)a * b;
    a = (uint64_t)r;
    b = (uint64_t)(r >> 64);
    return a ^ b;
}

一次 128-bit 乘法 + XOR 折叠，就能获得优秀的混合效果。wyhash 的全部代码不到 60 行。

xxHash3：SIMD 加速的长输入哈希

xxHash3（Yann Collet，2019）针对长输入使用 SIMD 加速：

• 短键（1-16 字节）：标量路径，利用乘法混合
• 中键（17-128 字节）：累加器路径
• 长键（128+ 字节）：AVX2/SSE2 向量化，8 个 64-bit 累加器并行

对于大文件哈希（如检验和计算），xxHash3 可达 30+ GB/s，接近内存带宽极限。

AES-NI 加速哈希

现代 CPU 的 AES-NI 指令（aesenc、aesdec）可以被”滥用”来实现极快的非密码学哈希。AES 的一轮加密提供了极好的扩散性（一次操作就满足 SAC），而 AES-NI 指令只需要 1 个时钟周期。

一些利用 AES-NI 的哈希函数： - aHash：Rust 的 ahash crate，HashMap 的高性能替代 - CLHASH：基于 CLMUL 的乘法哈希 - meow_hash：Casey Muratori 设计的 AES-NI 哈希（已不推荐，有安全问题）

缺点：不可移植（ARM 上需要不同的指令），且不是真正的加密——用于哈希表可以，用于安全目的不行。

七、BLAKE3：密码学哈希的新标杆

从 BLAKE 到 BLAKE3 的演进

BLAKE 家族是密码学哈希的一个重要分支，它的进化路径值得细看：

• BLAKE（2008）：SHA-3 竞赛候选者，基于 ChaCha 的 ARX 结构
• BLAKE2（2013）：BLAKE 的简化加速版，比 SHA-256 快 3 倍，广泛用于 Argon2 密码哈希
• BLAKE3（2020）：革命性重设计，基于 Merkle 树结构，可无限并行化

BLAKE3 的核心创新是将 Merkle 树与压缩函数结合：

              root
             /    \
          node    node
         /   \   /   \
        C0   C1 C2   C3    ← 1KB chunk 的压缩结果

每个 1KB chunk 独立压缩，然后用二叉树合并。这意味着： - 多线程：不同 chunk 可以并行处理 - SIMD：4 路 / 8 路 / 16 路并行压缩 - 增量哈希：追加数据只需要更新受影响的子树

BLAKE3 性能数据

在现代硬件上（AMD Ryzen 9，单线程，AVX-512）：

BLAKE3 的单线程速度已经接近非密码学哈希（只慢 4 倍），多线程时可以接近内存带宽。这重新定义了”密码学哈希很慢”的固有印象。

何时用 BLAKE3 替代 SHA-256

建议替代的场景： - 文件完整性校验（比 SHA-256 快 15 倍） - Merkle 树构建（BLAKE3 本身就是 Merkle 树） - 密钥派生（KDF 模式，替代 HKDF-SHA256） - 消息认证（keyed 模式，替代 HMAC-SHA256）

不建议替代的场景： - TLS 证书签名（兼容性要求 SHA-256） - 比特币 PoW（矿机硬编码 SHA-256） - 合规要求指定 SHA-2 的场景

八、整数哈希的特殊考量

很多时候，哈希表的键是整数（如用户 ID、文件描述符、内存地址）。对整数做哈希有一些特殊技巧。

直接使用整数的问题

最天真的做法是 bucket = key % num_buckets。问题在于： - 连续的整数映射到连续的 bucket（没有分散效果） - 如果 num_buckets 是 2 的幂，只有低位参与选择（高位信息丢失）

splitmix64

Java 的 java.util.SplittableRandom 使用的混合函数，也是整数哈希的优秀选择：

uint64_t splitmix64(uint64_t x) {
    x ^= x >> 30;
    x *= 0xbf58476d1ce4e5b9ULL;
    x ^= x >> 27;
    x *= 0x94d049bb133111ebULL;
    x ^= x >> 31;
    return x;
}

三次 XOR-shift 加两次乘法，满足 SAC，且是双射（bijection）——不同输入保证不同输出。

Fibonacci hashing

一种更轻量的替代方案：

// Fibonacci hashing: 适用于 2^n 大小的哈希表
uint32_t fibonacci_hash(uint32_t key, int shift) {
    return (key * 2654435769u) >> shift;
    // 2654435769 = 2^32 / phi (黄金比例)
}

利用黄金比例的无理数性质，连续整数会被均匀分散到不同的 bucket。Knuth 在 TAOCP 第三卷中详细分析了这个方法。

九、综合性能基准

以下基准在 AMD Ryzen 9 7950X 上测试，使用 SMHasher3 测试框架，编译器 GCC 13 -O3。

短键性能（8 字节整数，最常见的哈希表场景）

Throughput (Mhash/s) for 8-byte keys:
  wyhash        ████████████████████████████████████████  420
  xxHash3       ██████████████████████████████████████  390
  aHash(AES-NI) █████████████████████████████████████  380
  FNV-1a        ███████████████████████████████  310
  MurmurHash3   ████████████████████████████  280
  SipHash-1-3   ██████████████████████  215
  SipHash-2-4   ███████████████  150
  BLAKE3        ████████  80
  SHA-256        ███  35

长键性能（1MB 数据块，文件校验和场景）

Throughput (GB/s) for 1MB input:
  xxHash3(AVX2) ████████████████████████████████████████  32.0
  wyhash        ██████████████████████████████████  28.0
  BLAKE3(AVX2)  █████████████████████████  7.0
  aHash(AES-NI) ███████████████████████  6.5
  MurmurHash3   ████████  3.0
  SipHash-2-4   ███████  2.5
  SHA-256(HW)   ██████  2.0
  SHA-256(SW)   ██  0.5

质量评分（SMHasher 通过测试数 / 总测试数）

FNV-1a 和 DJB2 的质量得分触目惊心——它们在现代测试套件下表现极差。任何新项目都不应该使用这两个哈希函数。

十、各语言运行时的选择

不同语言对默认哈希函数的选择反映了不同的安全与性能权衡：

一个有趣的观察：库和框架倾向于选择更快但不安全的哈希（如 abseil 的 wyhash），而语言运行时倾向于安全的哈希（如 Python/Rust 的 SipHash）。这是因为语言运行时必须假设最坏情况——用户可能把不可信的网络输入作为 key。

十一、如何选择哈希函数

决策树

输入是否来自不可信来源（网络、用户输入）？
├── 是 → 需要 PRF 安全性
│   ├── 目标是哈希表 → SipHash-1-3 或 SipHash-2-4
│   └── 目标是 MAC  → HMAC-SHA256 或 BLAKE3-keyed
│
└── 否 → 不需要 PRF 安全性
    ├── 键很短（<32 字节）→ wyhash 或 xxHash3
    ├── 键很长（>1KB）→ xxHash3（SIMD 优势明显）
    ├── 需要确定性（跨平台一致）→ MurmurHash3（广泛标准化）
    └── 需要密码学安全 → SHA-256 / BLAKE3

不要做的事

1. 不要自己设计哈希函数：哈希函数设计需要深厚的密码学背景，SMHasher 测试套件可以帮助验证，但通过测试不等于安全
2. 不要用密码学哈希做哈希表：SHA-256 做哈希表键会浪费 10 倍以上的性能
3. 不要用 CRC32 做通用哈希：CRC32 是线性的，碰撞可以轻松构造
4. 不要忽略种子/密钥：所有非密码学哈希都应该加随机种子

十二、工程陷阱清单

十三、总结与个人思考

哈希函数是计算机科学中最基础的构件之一，但”选哈希函数”这件事比大多数工程师想象的复杂得多。

我的核心观点：

一、安全与性能不是二选一，而是光谱。 密码学哈希和非密码学哈希之间存在一个连续的安全-性能光谱。SipHash 开创了一个中间地带——它不提供完整的密码学安全，但提供足够的安全来抵御 HashDoS。在大多数场景下，这个中间地带才是正确的选择。

二、默认应该安全。 语言运行时的默认 HashMap 必须使用安全哈希——因为你无法预测用户会把什么数据放进去。性能敏感的代码可以显式 opt-in 更快的哈希（如 Rust 的 ahash），但默认值必须安全。这是 “secure by default” 原则的具体体现。

三、硬件改变了游戏规则。 AES-NI 的出现彻底改变了哈希函数的性能格局。以前，安全哈希比非安全哈希慢一个数量级；现在，利用 AES-NI 的 ahash 既快又安全。随着 ARM 的 PMULL 和 AES 指令普及，硬件加速的安全哈希将成为新的默认。

如果你只记住一件事：面向不可信输入时，一定要用带密钥的哈希函数（SipHash 或类似的 PRF）。性能差异远没有安全差异重要。

上一篇: Bloom Filter 全家族 下一篇: 向量化哈希：xxHash3 与 wyhash 的 SIMD 实现

相关阅读: - 哈希表内部 - Swiss Table - TLS 1.3 握手