密码学哈希 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、SHA-3 等）和非密码学哈希（MurmurHash、xxHash、wyhash 等），以及夹在两者之间的特殊存在——SipHash。我们会深入 Merkle-Damgård 和海绵构造的内部机制，解析 HashDoS 攻击的实战细节，并给出一份完整的 SipHash-2-4 的 C 实现。

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

一、哈希函数的两个世界：速度与安全

哈希函数的用途极其广泛——哈希表、校验和、数字签名、消息认证、密钥派生、去重、负载均衡、布隆过滤器……但如果你仔细看这些用途，会发现它们对哈希函数的要求截然不同。

一端是哈希表：键值对的查找速度是唯一的优化目标，你需要哈希函数尽可能快，分布尽可能均匀。哈希表的场景里，碰撞是”不幸”但不是”灾难”——最坏情况下，性能下降一点而已。

另一端是数字签名：你需要保证任何人都无法伪造签名，哈希函数的安全性是生死攸关的。攻击者有强大的动机和资源去寻找碰撞——一次碰撞就可能意味着伪造证书、篡改软件更新包、甚至伪造金融交易。

这两个极端催生了两类完全不同的设计哲学。它们共享”哈希”这个名字，却几乎没有什么设计原则上的交集。

为什么需要两类设计？ 根本原因在于安全性和性能之间存在不可调和的矛盾。密码学哈希为了抵御攻击者的分析，必须经过大量的混合轮数——SHA-256 对每个 512-bit 消息块执行 64 轮压缩；SHA-3 的 Keccak-f[1600] 置换执行 24 轮。这些轮数是经过密码分析社区多年攻防博弈后确定的安全下界。减少轮数就意味着暴露在已知攻击之下。

非密码学哈希则完全不需要抵抗主动攻击者。它只需要在”随机”输入上表现良好——分布均匀、碰撞率接近理论下界。因此它可以用更少的操作获得”足够好”的混合效果。wyhash 整个函数体不到 60 行 C 代码，核心只有几次乘法和异或。

二、非密码学哈希的设计目标

非密码学哈希函数的核心使命是为哈希表服务。一个好的哈希表哈希函数需要满足以下四个目标：

雪崩效应

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

对于非密码学哈希，我们通常不要求严格满足 SAC，而是要求统计雪崩——大部分输出 bit 会变化，偏差在可接受范围内。衡量方法如下：

void avalanche_test(uint64_t (*hash)(const void*, size_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, sizeof(x));

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

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

    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.0)\n",
           total_bias / 64);
}

实测结果：

FNV-1a 和 DJB2 这类”经典”哈希函数的雪崩效应远不如现代设计。

分布均匀性

一个理想的哈希函数应该把任意输入集合均匀地映射到输出空间。形式化地说，对于任意合理的输入分布 \(D\)，\(H(x)\) 的输出分布应该接近均匀分布 \(U_{2^n}\)。

实践中的测试方法是使用 \(\chi^2\) 检验。把 \(N\) 个输入映射到 \(B\) 个桶中，计算：

\[\chi^2 = \sum_{i=0}^{B-1} \frac{(O_i - E)^2}{E}\]

其中 \(O_i\) 是第 \(i\) 个桶的实际计数，\(E = N/B\) 是期望计数。好的哈希函数的 \(\chi^2\) 值应该接近 \(B - 1\)（自由度）。

速度

非密码学哈希的速度直接影响哈希表的吞吐量。现代哈希函数的速度通常以两种方式衡量：

• 短键延迟（cycles/hash）：对 8-32 字节的键，单次哈希消耗的 CPU 周期数。这是哈希表场景最重要的指标。
• 长键吞吐量（GB/s）：对 1KB 以上的数据块，每秒处理的数据量。这在文件校验和、去重等场景更重要。

两个指标往往不成正比。xxHash3 在长键上（利用 SIMD）远超 wyhash，但在短键上反而略慢，因为 SIMD 的初始化开销在短键上被放大。选择哈希函数时必须明确你的主要场景。

适合哈希表

除了上述三点，哈希表场景还有一些特殊要求：

• 短键优化：真实世界中，哈希表的键往往很短（整数、短字符串）。好的哈希函数必须在短键上表现优秀，不能只在长数据上快。
• 低开销初始化：哈希表可能在热路径上被频繁创建和销毁，哈希函数的初始化成本不能太高。
• 可内联：函数体要足够小，编译器能将其内联到调用点，消除函数调用开销。

三、密码学哈希的安全性质

密码学哈希函数 \(H: \{0,1\}^* \to \{0,1\}^n\) 必须满足三个递进的安全性质。理解这三者的层级关系至关重要。

抗原像性（Preimage Resistance）

给定一个哈希值 \(y\)，在计算上不可能找到任意 \(x\) 使得 \(H(x) = y\)。

直觉上：哈希函数是”单向”的——你可以轻松地从消息算出摘要，但无法从摘要反推出消息。对于 \(n\) 位输出，暴力搜索的期望代价是 \(O(2^n)\)。

实际应用：密码存储。即使数据库泄露了 \(H(\text{password})\)，攻击者也无法直接恢复明文密码（当然，弱密码仍然可以通过字典攻击破解，这是密码本身的问题而非哈希函数的问题）。

抗第二原像性（Second Preimage Resistance）

给定 \(x_1\)，在计算上不可能找到 \(x_2 \neq x_1\) 使得 \(H(x_1) = H(x_2)\)。

直觉上：你无法”替换”一个已知消息。这比抗原像性更强——攻击者不仅知道目标哈希值，还知道一个具体的原像 \(x_1\)，但仍然无法找到另一个碰撞。

实际应用：软件签名。攻击者知道合法软件包 \(x_1\) 及其哈希 \(H(x_1)\)，但无法构造一个恶意软件包 \(x_2\) 使得 \(H(x_2) = H(x_1)\)。

抗碰撞性（Collision Resistance）

在计算上不可能找到任意一对 \((x_1, x_2)\)，\(x_1 \neq x_2\)，使得 \(H(x_1) = H(x_2)\)。

这是最强的性质。攻击者有完全的自由度——可以同时选择两个输入。由于生日悖论，暴力搜索的期望代价是 \(O(2^{n/2})\)，这就是为什么 SHA-256 提供的碰撞安全级别是 128 bit 而非 256 bit。

三者的层级关系

抗碰撞性 (Collision Resistance)
    │
    ├── 蕴含 → 抗第二原像性 (Second Preimage Resistance)
    │
    └── 不蕴含 → 抗原像性 (Preimage Resistance)

抗第二原像性
    │
    └── 不蕴含 → 抗原像性（需要额外条件）

关键点：抗碰撞性蕴含抗第二原像性（如果你连自由选择两个输入都找不到碰撞，那固定一个输入当然也找不到），但不蕴含抗原像性。存在人为构造的反例：可以设计一个抗碰撞但不抗原像的函数（虽然在实际密码学哈希中这种情况不会出现）。

密码学哈希的输出通常至少 256 bit，计算速度相对较慢（SHA-256 约 500 MB/s），但安全性是刚性要求——差一点都不行。MD5（128 bit 输出）的碰撞已被实际攻破，任何仍在使用 MD5 做安全用途的系统都应该立即迁移。

真实世界中的碰撞攻击

MD5 的碰撞攻击史值得一提，因为它完美展示了”安全性是刚性要求”这句话的含义：

• 2004 年：王小云团队发表了 MD5 碰撞攻击，能在数小时内找到碰撞对。学术界震惊，但工业界反应迟钝——“理论攻击而已”。
• 2008 年：研究者利用 MD5 碰撞伪造了一个合法的 CA 证书。这意味着攻击者可以冒充任意 HTTPS 网站。工业界开始认真对待。
• 2012 年：Flame 恶意软件利用 MD5 碰撞伪造了微软的 Windows Update 签名，在中东地区进行间谍活动。这是 MD5 碰撞攻击的第一次国家级实战应用。
• 2017 年：Google 发布 SHAttered 攻击，首次展示了 SHA-1 的实际碰撞——两个不同的 PDF 文件产生相同的 SHA-1 摘要。攻击消耗了约 6500 CPU 年的算力。

教训：从理论攻击到实际利用，通常只需要 5-10 年。密码学社区说”不要用”的时候，就真的不要用。

四、Merkle-Damgard 构造与长度扩展攻击

压缩函数迭代

Merkle-Damgård 构造是 1979 年由 Ralph Merkle 和 Ivan Damgård 独立提出的，它是 MD5、SHA-1、SHA-256 等经典密码学哈希的基础架构。

核心思想是把变长输入的哈希问题归约为固定长度的压缩函数问题。设压缩函数为 \(f: \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n\)，它接收一个 \(n\) 位的链接变量（chaining value）和一个 \(b\) 位的消息块，输出一个新的 \(n\) 位链接变量。

处理流程：

消息 M: [m_1] [m_2] [m_3] ... [m_k] [padding || length]

IV ──→ f(IV, m_1) ──→ f(h_1, m_2) ──→ ... ──→ f(h_{k}, pad) ──→ H(M)
       ↑                ↑                           ↑
      h_1              h_2                         h_final

1. 把消息按 \(b\) 位分块
2. 最后一块进行填充（padding），并附加消息的原始长度
3. 从一个固定的初始向量 IV 开始，依次用压缩函数处理每个块
4. 最后一个压缩函数的输出就是最终哈希值

以 SHA-256 为例：\(n = 256\)，\(b = 512\)。压缩函数内部有 64 轮运算，每轮使用不同的轮常数，涉及选择函数（Ch）、多数函数（Maj）、循环右移、模加等操作。

SHA-256 压缩函数的一轮伪代码：

// SHA-256 压缩函数的单轮（共 64 轮）
T1 = h + Sigma1(e) + Ch(e,f,g) + K[i] + W[i];
T2 = Sigma0(a) + Maj(a,b,c);
h = g; g = f; f = e; e = d + T1;
d = c; c = b; b = a; a = T1 + T2;

// 其中：
// Ch(e,f,g) = (e & f) ^ (~e & g)          选择函数
// Maj(a,b,c) = (a & b) ^ (a & c) ^ (b & c) 多数函数
// Sigma0(a) = ROTR(a,2) ^ ROTR(a,13) ^ ROTR(a,22)
// Sigma1(e) = ROTR(e,6) ^ ROTR(e,11) ^ ROTR(e,25)

Merkle-Damgård 有一个关键的安全证明：如果压缩函数 \(f\) 是抗碰撞的，那么由它构造的哈希函数 \(H\) 也是抗碰撞的。这个证明是通过反证法完成的——如果能在 \(H\) 上找到碰撞，就能在 \(f\) 上找到碰撞。

填充规则的重要性

Merkle-Damgård 构造要求对消息进行特定的填充（padding）：

1. 在消息末尾追加一个 1 bit
2. 追加若干 0 bit，使总长度对 512 取模余 448
3. 追加原始消息长度的 64-bit 大端编码

这个填充方案叫做 MD 强化（Merkle-Damgård strengthening）。追加长度看似多余，实际上是安全证明的关键——它防止了一种攻击：攻击者通过在消息末尾添加额外块来制造碰撞。没有长度字段，两条不同长度的消息可能在填充后共享相同的块序列。

长度扩展攻击

然而，Merkle-Damgård 构造有一个致命的结构性缺陷：最终哈希值就是最后一步压缩函数的内部状态。这导致了长度扩展攻击（length extension attack）。

攻击场景：假设服务端使用 \(\text{MAC} = \text{SHA256}(\text{secret} \| \text{message})\) 来验证消息完整性。攻击者不知道 secret，但知道 message 和对应的 MAC 值。

攻击步骤：

1. 攻击者拿到合法的 \(H(\text{secret} \| \text{msg})\)
2. 这个哈希值就是 SHA-256 处理完所有块后的内部状态 \((a, b, c, d, e, f, g, h)\)
3. 攻击者把这个状态作为新的”IV”，继续”喂入”额外的消息块 \(\text{extra}\)
4. 攻击者得到 \(H(\text{secret} \| \text{msg} \| \text{padding} \| \text{extra})\)，而无需知道 secret

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

// 正确：使用 HMAC
// HMAC(k, m) = H((k ^ opad) || H((k ^ ipad) || m))
// 双层哈希结构彻底阻断了长度扩展
uint8_t good_mac[32];
hmac_sha256(secret, secret_len, msg, msg_len, good_mac);

为什么 SHA-256 有这个漏洞

根本原因在于 Merkle-Damgård 构造的输出没有经过”终结化”处理——最终哈希值直接暴露了内部状态的全部信息。攻击者知道了内部状态，就等于拿到了一个完全合法的”中间计算结果”，可以从这里继续计算下去。

SHA-256、SHA-512、MD5、SHA-1 都有这个问题。HMAC 的双层哈希结构是一种修补方案，但更根本的解决办法是换用不同的构造——比如海绵构造。

五、海绵构造：SHA-3 的核心

从竞赛到标准

2006 年，Wang Xiaoyun 等人对 SHA-1 的碰撞攻击取得重大突破，NIST 决定举办公开竞赛选择新的哈希标准 SHA-3。2012 年，Guido Bertoni、Joan Daemen、Michaël Peeters 和 Gilles Van Assche 设计的 Keccak 赢得了 SHA-3 竞赛。

Keccak 的核心不是 Merkle-Damgård，而是一种全新的构造——海绵构造（Sponge Construction）。

海绵构造的原理

海绵构造基于一个固定宽度的置换函数 \(f: \{0,1\}^w \to \{0,1\}^w\)。状态宽度 \(w\) 被分为两部分：

• 比特率（bitrate）\(r\)：与外部交互的部分
• 容量（capacity）\(c\)：隐藏的内部状态，永远不直接暴露

\(w = r + c\)，其中 Keccak-f[1600] 的 \(w = 1600\)。对于 SHA3-256，\(r = 1088\)，\(c = 512\)。

处理分为两个阶段：

吸收阶段（Absorb）：

初始状态：S = 0 (全零)

对每个消息块 m_i（r bit）：
    S[0..r-1] ^= m_i     // 将消息块异或到状态的前 r bit
    S = f(S)               // 对整个状态执行置换

注意：容量部分 S[r..w-1] 从不直接与输入交互

挤压阶段（Squeeze）：

输出所需的哈希值（可以是任意长度）：
    取 S[0..r-1] 作为输出的一部分
    如果需要更多输出：
        S = f(S)
        继续取 S[0..r-1]
    重复直到输出够长

用伪代码表示整个过程：

def sponge_hash(message, output_len, r, c):
    w = r + c
    state = [0] * w

    # 填充：10*1 padding
    padded = pad(message, r)
    blocks = split(padded, r)

    # 吸收阶段
    for block in blocks:
        for i in range(r):
            state[i] ^= block[i]
        state = keccak_f(state)  # 24 轮置换

    # 挤压阶段
    output = []
    while len(output) < output_len:
        output.extend(state[:r])
        if len(output) < output_len:
            state = keccak_f(state)

    return output[:output_len]

为什么天然免疫长度扩展攻击

海绵构造天然免疫长度扩展攻击，原因有二：

第一，输出不暴露完整内部状态。 SHA3-256 的输出只有 256 bit，但内部状态有 1600 bit。即使攻击者知道了输出，还有 \(c = 512\) bit 的容量部分是完全未知的。攻击者无法恢复完整的内部状态，因此无法从输出点继续计算。

第二，容量提供了信息论上的安全屏障。 容量部分在整个计算过程中从不与外部直接交互——消息只异或到比特率部分，输出也只从比特率部分提取。容量就像一个”黑箱”，外部观察者无法探测其内容。

对比 Merkle-Damgård：SHA-256 的输出就是全部 256 bit 的内部状态，没有任何隐藏信息。这就是两种构造在安全性上的根本区别。

这也是为什么 SHA-3 不需要 HMAC 那样的双层结构——直接用 \(H(\text{key} \| \text{message})\) 就是安全的（当然实际中仍建议使用标准化的 KMAC 方案）。

Keccak-f 置换的内部结构

SHA-3 的核心是 Keccak-f[1600] 置换，它在 1600-bit（\(5 \times 5 \times 64\)）的三维状态上执行 24 轮变换。每轮由五个步骤组成：

1. \(\theta\)（theta）：列校验位扩散。计算每列的奇偶校验，然后扩散到相邻列。这一步提供了快速的线性扩散。
2. \(\rho\)（rho）：位旋转。对 25 个 64-bit 字分别执行不同偏移量的循环左移。偏移量由一个简单的递推公式确定。
3. \(\pi\)（pi）：位置置换。重新排列 25 个字的位置。
4. \(\chi\)（chi）：非线性变换。这是唯一的非线性步骤：\(a[x] = a[x] \oplus (\lnot a[x+1] \land a[x+2])\)。它提供了混淆（confusion）性质。
5. \(\iota\)（iota）：轮常数异或。防止轮之间的对称性。

\(\theta\) 和 \(\rho\) 提供扩散（diffusion），\(\chi\) 提供混淆，\(\pi\) 打破对齐。五步协同工作，确保每轮之后状态的每一位都依赖更多的输入位。24 轮之后，达到完全扩散——任意一个输入位的改变会影响所有 1600 个状态位。

这种设计与 SHA-256 的 Merkle-Damgård 构造在哲学上截然不同：SHA-256 的安全性依赖于压缩函数的”黑箱”复杂性，而 Keccak 的安全性来自简单操作的大量重复——每个单独的步骤都很简单（可以在一行代码中实现），但 24 轮组合起来提供了充分的安全余量。

六、SipHash 深入

为什么是 Keyed Hash

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

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

“带密钥”意味着 SipHash 接受一个 128-bit 密钥 \((k_0, k_1)\) 作为参数。密钥在进程启动时随机生成，对外部不可见。PRF（伪随机函数）安全性保证：给定随机密钥 \(k\)，\(\text{SipHash}_k(x)\) 的行为与真随机函数在计算上不可区分。

具体来说，即使攻击者看到了任意多组 \((x_i, \text{SipHash}_k(x_i))\) 的输入输出对，也无法： - 预测新输入 \(x_{n+1}\) 的输出 - 在不知道密钥的情况下构造碰撞对 - 从输入输出对中恢复密钥

这与普通的随机种子（random seed）有本质区别。像 MurmurHash3 那样加一个 32-bit 种子，只是增加了攻击者暴力搜索的难度——\(2^{32}\) 次尝试就能枚举所有可能的种子。而 SipHash 的 128-bit 密钥空间使得暴力搜索不可行，且 PRF 安全性保证了即使观察大量输入输出对也无法推断密钥。

更形式化地说，PRF 安全性通过一个区分游戏（distinguishing game）来定义：给攻击者一个黑箱预言机，这个预言机要么是 \(\text{SipHash}_k\)（\(k\) 随机选取），要么是一个真随机函数 \(R: \{0,1\}^* \to \{0,1\}^{64}\)。攻击者可以自适应地查询任意多次，然后猜测预言机的身份。PRF 安全性要求：任何多项式时间攻击者的猜测优势（advantage）是可忽略的。

128-bit 密钥的作用

SipHash 的状态初始化直接依赖密钥：

v0 = k0 ^ 0x736f6d6570736575ULL;  // "somepseu"
v1 = k1 ^ 0x646f72616e646f6dULL;  // "dorandom"
v2 = k0 ^ 0x6c7967656e657261ULL;  // "lygenera"
v3 = k1 ^ 0x7465646279746573ULL;  // "tedbytes"

四个 64-bit 状态变量分别与密钥的两个半部异或不同的常数。这些常数是 ASCII 字符串 “somepseudorandomlygeneratedbytes” 的编码。密钥的两半 \(k_0\) 和 \(k_1\) 各被使用两次，确保所有四个状态变量都依赖于完整的 128-bit 密钥。

SipHash-2-4 与 SipHash-1-3

SipHash-c-d 表示每个消息块执行 \(c\) 轮压缩（compression rounds），终结化执行 \(d\) 轮（finalization rounds）。

• SipHash-2-4：标准版。每个 8 字节块执行 2 轮 SipRound，终结化执行 4 轮。这是 Python 3.3、Perl 5.18 最初采用的版本，安全余量最大。
• SipHash-1-3：快速版。压缩减为 1 轮，终结化减为 3 轮。Rust 标准库的 DefaultHasher 使用此变体。Python 3.4 也从 2-4 切换到了 1-3，因为分析表明 1-3 对哈希表场景已有足够的安全余量。

安全余量的含义：已知最好的攻击对 SipHash-1-0（1 轮压缩、0 轮终结化）有效，因此 SipHash-2-4 有至少 1 轮压缩和 4 轮终结化的余量，而 SipHash-1-3 的余量更小但仍被认为安全。

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

#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)

一轮 SipRound 包含 6 次加法、6 次旋转和 4 次异或——全部都是在现代 CPU 上单周期完成的操作，没有查表、没有分支、没有乘法。旋转常数（13, 32, 16, 21, 17, 32）经过精心选择，使得两轮 SipRound 就能达到完全扩散（full diffusion）：每个输出 bit 都依赖每个输入 bit。

七、HashDoS 攻击实战

攻击的核心：构造碰撞链

HashDoS 的威力来自一个简单的算法复杂度退化。假设一个哈希表使用链式法解决冲突：

• 正常情况：\(n\) 次插入，每次 \(O(1)\)，总计 \(O(n)\)
• 全碰撞：\(n\) 个键映射到同一个桶，第 \(i\) 次插入需要遍历长度为 \(i-1\) 的链表

全碰撞情况下的总操作数：

\[\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)\]

当 \(n = 100000\) 时，正常情况约 \(10^5\) 次操作，退化情况约 \(5 \times 10^9\) 次操作——慢了五万倍。

对于确定性哈希函数（没有随机密钥），攻击者可以离线构造碰撞集合。以 PHP 5.x 使用的 DJBX33A 为例：

def djbx33a(s):
    """PHP 5.x 使用的哈希函数（简化版）"""
    h = 5381
    for c in s:
        h = ((h * 33) + ord(c)) & 0xFFFFFFFF
    return h

# DJBX33A 的代数结构使得碰撞构造极其高效
# 关键观察：如果 hash("Ez") == hash("FY")
# 那么对于任意字符串 s：
#   hash("Ez" + s) == hash("FY" + s)（前缀碰撞传播）
#
# 利用这个性质，可以组合式地构造指数级碰撞集：
# {"EzEz", "EzFY", "FYEz", "FYFY"} 全部碰撞
# {"EzEzEz", "EzEzFY", "EzFYEz", ...} 8 个碰撞
# 以此类推，k 个碰撞对可以组合出 2^k 个碰撞

这种组合式碰撞构造的成本是 \(O(k)\)（找 \(k\) 个碰撞对），却能产生 \(2^k\) 个碰撞键——构造成本是对数级的。

O(n^2) 退化的实际威力

一个典型的 HashDoS 攻击 payload 只需要约 1MB（包含约 65000 个碰撞键名），通过一个 HTTP POST 请求发送。服务器解析这个请求时需要将所有参数插入哈希表，由于全碰撞导致 \(O(n^2)\) 退化，CPU 会被占用数分钟。

攻击的不对称性极其严重： - 攻击者带宽成本：约 1MB/请求 - 服务器 CPU 成本：数分钟满载 - 放大倍数：\(> 10^6\)

Python、Java、Ruby 的历史事件与修复

Python 的修复历程：

• Python 2.x/3.0-3.2：使用自定义的 FNV 变体，无随机种子。2011 年 12 月曝光后，CPython 2.6.8、3.2.3 加入了 -R 命令行选项启用哈希随机化，但默认关闭。
• Python 3.3（2012 年 9 月）：默认启用哈希随机化，使用 SipHash-2-4 作为字符串哈希函数。环境变量 PYTHONHASHSEED 可以控制种子。
• Python 3.4（2014 年 3 月）：切换到 SipHash-1-3（更快，安全余量仍然充足）。

# Python 3.3+ 的哈希值每次运行都不同
# 运行 1:
>>> hash("hello")
-1221029976358040312

# 运行 2:
>>> hash("hello")
8762379578082856346

# 固定种子（仅用于调试/测试）:
# PYTHONHASHSEED=42 python3 -c "print(hash('hello'))"

Java 的修复方案：

Java 采取了不同的策略。由于 String.hashCode() 的返回值被写入了 Java 语言规范（s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]），改变哈希函数会破坏向后兼容性。因此 Java 8 选择了结构兜底方案：

• 当一个 bucket 的链表长度超过 8 时，自动将链表转换为红黑树
• 最坏情况从 \(O(n)\) 降为 \(O(\log n)\)
• 总操作从 \(O(n^2)\) 降为 \(O(n \log n)\)
• 红黑树的比较使用 System.identityHashCode() 作为 tiebreaker

Ruby 的修复：

• Ruby 1.9.3-p327（2012 年 11 月）：紧急安全补丁，加入哈希随机化
• Ruby 2.0（2013 年 2 月）：切换到 SipHash-2-4
• Ruby 社区是最快完成修复的语言之一

Node.js 的修复：

• V8 引擎在 2012 年后逐步引入了哈希随机化
• 在某些版本中使用了基于平台的不同策略
• 后续版本统一使用了带随机种子的哈希

这些事件深刻改变了整个行业对哈希表安全性的认知：任何接受不可信输入的哈希表都必须使用随机化哈希。

各语言运行时的当前选择

经过 HashDoS 事件的洗礼，不同语言对默认哈希函数的选择反映了不同的安全与性能权衡：

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

八、现代非密码学哈希速览

这一节快速介绍六个有代表性的现代非密码学哈希函数。

MurmurHash3（2011）

Austin Appleby 设计。是最早通过 SMHasher 全部测试的通用哈希函数之一。提供 32-bit 和 128-bit 两种输出宽度。核心操作是乘法-移位-异或（multiply-shift-xor）。

优点：质量优秀、代码简洁、广泛标准化（Apache Cassandra、Elasticsearch、libstdc++ 都用它）。缺点：速度已被后来者超越，且没有密钥化设计，不防 HashDoS。

CityHash（2011）

Google 出品，由 Geoff Pike 和 Jyrki Alakuijala 设计。针对 x86-64 优化，短键快于 MurmurHash3。内部使用 CRC32C 指令加速（如果可用）。

CityHash 在 Google 内部曾广泛使用，但现已被 FarmHash 取代。

FarmHash（2014）

Google 的 CityHash 继任者，同样由 Geoff Pike 设计。主要改进是更好的跨平台一致性和在不同 CPU 架构上的适应性。内部根据可用指令集自动选择实现路径（CRC32、AES-NI 等）。

wyhash（2019）

王一（Wang Yi）设计。可能是目前最快的通用非密码学哈希函数。核心只用 MUM（Multiply-and-Mix） 操作：

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 折叠。整个函数不到 60 行 C 代码。wyhash 通过 SMHasher 全部测试，且在短键和长键上都极快。Go 1.17+ 的 runtime.memhash 在 wyhash 的思路上有所借鉴。

wyhash 的设计哲学是”乘法就是最好的混合器”。128-bit 乘法天然具有优秀的扩散性——两个 64-bit 输入的每一位都会影响 128-bit 乘积的大部分位。XOR 折叠（把高 64 位和低 64 位异或）将这 128 位的信息压缩回 64 位，损失最小。这种简洁性使得 wyhash 极易移植和审计。

需要注意的是，wyhash 在不同版本之间曾多次修改算法细节（从 v1 到 v4），因此不适合用于需要跨版本一致性的场景（如持久化存储的哈希索引）。

xxHash3（2019）

Yann Collet（也是 LZ4 和 Zstandard 的作者）设计。xxHash3 是 xxHash 家族的第三代，专门针对现代 CPU 的 SIMD 能力优化：

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

对于大文件哈希（如校验和计算），xxHash3 可达 30+ GB/s，接近内存带宽极限。它是目前长输入场景下最快的非密码学哈希。

xxHash3 的一个重要特性是稳定性承诺：从 v0.8.0 开始，xxHash3 的输出值被冻结，未来版本不会改变。这使得它可以安全地用于持久化场景（如文件校验和的格式规范），这是很多非密码学哈希所不具备的保证。

Komihash（2021）

Aleksey Vaneev 设计。Komihash 的特点是在不使用 128-bit 乘法的架构上也能保持高性能。它使用了一种称为”Lehmer-style”的乘法链结构，每步只需要 64-bit 乘法和一些位操作。

在 ARM 等不支持高效 128-bit 乘法的平台上，Komihash 的性能优于 wyhash。通过 SMHasher 全部测试。

性能对比

以下基准在 x86-64 平台上测试（GCC -O3），仅供相对比较：

九、如何选择：决策树

选择哈希函数时，第一个问题永远是：输入是否可信？

你的输入来自哪里？
│
├── 不可信来源（网络请求、用户输入、外部文件）
│   │
│   ├── 用途：哈希表
│   │   ├── 安全优先 → SipHash-2-4
│   │   └── 性能优先但仍需安全 → SipHash-1-3
│   │
│   ├── 用途：消息认证（MAC）
│   │   └── HMAC-SHA256 或 BLAKE3-keyed
│   │
│   └── 用途：数字签名 / 完整性校验
│       ├── 需要兼容性 → SHA-256
│       └── 可以自由选择 → BLAKE3
│
├── 可信来源（程序内部生成、编译期已知）
│   │
│   ├── 键很短（< 32 字节）→ wyhash
│   ├── 键很长（> 1KB）→ xxHash3（SIMD 优势大）
│   ├── 需要跨平台确定性 → MurmurHash3（广泛标准化）
│   └── 需要跨版本持久化 → 密码学哈希（SHA-256 / BLAKE3）
│       （非密码学哈希随时可能更新算法，哈希值会变）
│
└── 混合场景
    └── 默认选安全的（SipHash），
        用 profiling 证明是瓶颈后再换快的

几条实用原则：

1. 可信输入用快速哈希——编译器的符号表、内部 ID 查找等场景，用 wyhash 或 xxHash3。
2. 不可信输入用 SipHash——Web 框架的请求参数、DNS 解析缓存、任何接受外部数据的哈希表。
3. 需要持久化的哈希值用密码学哈希——非密码学哈希的算法和种子可能跨版本变化，持久化到磁盘或网络传输的哈希值必须用 SHA-256 或 BLAKE3。
4. 不确定时选安全的——SipHash-1-3 比 wyhash 只慢 2-3 倍，而哈希计算在大多数应用中不是瓶颈（cache miss 才是），所以安全的默认选择几乎没有可测量的性能代价。

不要做的事

1. 不要自己设计哈希函数：哈希函数设计需要深厚的密码学和统计学背景。SMHasher 测试套件可以帮助发现明显的统计缺陷，但通过所有测试不等于安全——它无法检测代数弱点或密码分析攻击。
2. 不要用密码学哈希做哈希表：SHA-256 做哈希表键会浪费 10 倍以上的性能，而且它的安全性质（抗碰撞、抗原像）在哈希表场景中完全用不上。
3. 不要用 CRC32 做通用哈希：CRC32 是线性函数（\(\text{CRC}(a \oplus b) = \text{CRC}(a) \oplus \text{CRC}(b)\)），碰撞可以在常数时间内构造。
4. 不要忽略密钥/种子：所有用于哈希表的非密码学哈希都应该加随机种子。即使当前系统不面向网络，未来的重构可能改变这一点。
5. 不要用密码学哈希存密码：SHA-256 太快了——GPU 暴力破解每秒可尝试数十亿次。密码存储必须用专用的慢速哈希：Argon2id、bcrypt 或 scrypt。

十、完整实现：SipHash-2-4

以下是 SipHash-2-4 的完整 C 实现，约 80 行。这份代码基于 Aumasson 和 Bernstein 的参考实现，做了可读性上的调整。

/* siphash24.c -- SipHash-2-4 完整实现
 *
 * 输入：任意长度的字节序列 + 128-bit 密钥
 * 输出：64-bit 哈希值
 *
 * 参考：Jean-Philippe Aumasson, Daniel J. Bernstein.
 *       "SipHash: a fast short-input PRF", 2012.
 */

#include <stdint.h>
#include <stddef.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)

static inline uint64_t u8to64_le(const uint8_t *p) {
    uint64_t v;
    memcpy(&v, p, 8);
    return v;  /* 假定小端序，大端需要 bswap */
}

uint64_t siphash_2_4(const void *src, size_t len,
                     uint64_t k0, uint64_t k1)
{
    /* 初始化：将密钥混入四个状态变量 */
    uint64_t v0 = k0 ^ UINT64_C(0x736f6d6570736575);
    uint64_t v1 = k1 ^ UINT64_C(0x646f72616e646f6d);
    uint64_t v2 = k0 ^ UINT64_C(0x6c7967656e657261);
    uint64_t v3 = k1 ^ UINT64_C(0x7465646279746573);

    const uint8_t *p   = (const uint8_t *)src;
    const uint8_t *end = p + (len - (len % 8));

    /* 尾部字节编码：最高字节存放原始长度 mod 256 */
    uint64_t b = (uint64_t)len << 56;

    /* ---- 压缩阶段：每 8 字节为一块 ---- */
    while (p < end) {
        uint64_t m = u8to64_le(p);
        v3 ^= m;
        SIPROUND;           /* 第 1 轮压缩 */
        SIPROUND;           /* 第 2 轮压缩 (c=2) */
        v0 ^= m;
        p += 8;
    }

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

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

    /* ---- 终结化阶段 ---- */
    v2 ^= 0xff;
    SIPROUND;               /* 第 1 轮终结化 */
    SIPROUND;               /* 第 2 轮终结化 */
    SIPROUND;               /* 第 3 轮终结化 */
    SIPROUND;               /* 第 4 轮终结化 (d=4) */

    return v0 ^ v1 ^ v2 ^ v3;
}

代码要点说明：

1. 初始化常数：0x736f6d6570736575 等四个常数是 “somepseudorandomlygeneratedbytes” 的 ASCII 编码，选择这些常数纯粹是为了避免全零初始状态，没有”后门”。

2. 消息注入的对称性：每个消息块 \(m\) 先异或到 \(v3\)（在 SipRound 之前），再异或到 \(v0\)（在 SipRound 之后）。这种”夹心”结构确保消息块与状态的交互是非线性的。

3. 尾部处理：使用 switch-case 的 fall-through 特性来处理 0-7 字节的尾部，最高字节固定存放消息总长度 mod 256。这确保了不同长度的消息即使内容相同也会产生不同的哈希值。

4. 终结化标记：v2 ^= 0xff 是一个域分隔符（domain separator），用于区分压缩阶段和终结化阶段，防止某些类型的内部碰撞。

使用示例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    /* 进程启动时随机生成 128-bit 密钥 */
    srand48(time(NULL) ^ getpid());
    uint64_t k0 = ((uint64_t)lrand48() << 32) | lrand48();
    uint64_t k1 = ((uint64_t)lrand48() << 32) | lrand48();

    const char *key = "hello";
    uint64_t h = siphash_2_4(key, 5, k0, k1);
    printf("SipHash-2-4(\"%s\") = %016llx\n", key, (unsigned long long)h);

    /* 每次运行结果不同，因为密钥是随机的 */
    return 0;
}

在生产环境中，密钥的生成应该使用密码学安全的随机数源（如 Linux 的 getrandom() 或 /dev/urandom），而非 lrand48()。

十一、工程陷阱表

十二、个人观点

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

一、安全与性能不是二选一，而是一个光谱。 密码学哈希和非密码学哈希之间存在一个连续的安全-性能光谱。SipHash 开创了一个重要的中间地带——它不提供完整的密码学安全性，但提供足够的 PRF 安全来抵御 HashDoS。在大多数面向网络的应用中，这个中间地带才是正确的选择点。我见过太多系统在两个极端之间做选择——要么用 SHA-256 做哈希表（慢十倍），要么用 MurmurHash 处理网络输入（不安全）——而忽略了中间的 SipHash。

二、默认应该安全。 语言运行时的默认 HashMap 必须使用安全哈希——因为你无法预测用户会把什么数据放进去。性能敏感的代码可以显式 opt-in 更快的哈希（如 Rust 的 ahash crate），但默认值必须安全。Rust 在这一点上做得最好：标准库默认安全的 SipHash，但通过 BuildHasher trait 允许零成本替换为 ahash。Python 也做对了——PYTHONHASHSEED 默认随机化。

三、Merkle-Damgård 的长度扩展问题是一个设计教训。 SHA-256 的长度扩展漏洞不是实现 bug，而是构造层面的结构性缺陷。海绵构造通过隐藏容量（capacity）部分，从根源上消除了这个问题。这告诉我们：安全性必须从架构层面考虑，而不能依赖使用者”正确地使用”一个有缺陷的原语。HMAC 是一种修补，SHA-3 才是根治。

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

五、了解你的哈希函数的保证边界。 wyhash 通过了 SMHasher 的全部测试，但它不是 PRF——一个能观察输入输出的攻击者可以预测新输入的哈希值。SipHash 是 PRF，但不是密码学哈希——它不提供抗碰撞性（攻击者有密钥时可以找到碰撞）。SHA-256 是密码学哈希，但有长度扩展漏洞。每个工具都有其适用范围，超出范围使用就是安全隐患。

如果你只记住一件事：面向不可信输入时，一定要用带密钥的哈希函数（SipHash 或类似的 PRF）。 性能差异远没有安全差异重要——SipHash-1-3 比 wyhash 慢不到 3 倍，但它能挡住一整类攻击。

系列导航： - 上一篇：Bloom Filter 全家族 - 下一篇：向量化哈希：xxHash3 与 wyhash

相关阅读： - 哈希表内部 - 完美哈希