土法炼钢兴趣小组的算法知识备份

【密码学百科】密码学哈希函数：MD5→SHA-2→SHA-3 的进化之路

2026-04-04 · cryptography · #hash-function #MD5 #SHA-1 #SHA-2 #SHA-3 #Keccak #sponge #collision #birthday-attack #Merkle-Damgard

文章导航

分类入口
cryptography
标签入口
#hash-function#MD5#SHA-1#SHA-2#SHA-3#Keccak#sponge#collision#birthday-attack#Merkle-Damgard

目录

密码学哈希函数（Cryptographic Hash Function）是现代密码学体系中最基础、最普遍的原语之一。无论是数字签名、消息认证码、密钥派生、承诺方案，还是区块链中的工作量证明，其背后都离不开一个可靠的哈希函数。从直觉上讲，哈希函数将任意长度的输入映射为固定长度的输出——这个输出通常被称为摘要（Digest）或指纹（Fingerprint）。然而，并非所有哈希函数都具备密码学安全性；密码学哈希函数必须满足一组严格的安全属性，才能在对抗性环境中承担”信任锚点”的角色。

本文将从安全属性的形式化定义出发，沿着时间线追溯从 MD5 到 SHA-3 的演进历程，深入剖析碰撞攻击的数学原理与海绵构造的设计革命，最后概览哈希函数在密码学协议中的多样化应用。

Merkle-Damgård 构造：迭代哈希的经典范式

一、哈希函数的三个安全属性

一个密码学哈希函数 \(H: \{0,1\}^* \to \{0,1\}^n\) 需要满足以下三个核心安全属性，它们从弱到强呈递进关系。

抗原像性（Preimage Resistance），也称单向性（One-wayness）：给定一个随机选取的哈希值 \(y\)，找到任意 \(x\) 使得 \(H(x) = y\) 在计算上是不可行的。形式化地，对于任何概率多项式时间（PPT）敌手 \(\mathcal{A}\)，以下概率关于安全参数 \(n\) 是可忽略的：

\[\Pr[x \leftarrow \mathcal{A}(y) : H(x) = y] \leq \text{negl}(n)\]

其中 \(y\) 由对随机消息求哈希得到。抗原像性保证哈希函数是一条”单行道”：从输出反推输入在计算上不可行。这在密码存储、承诺方案等场景中至关重要。

抗第二原像性（Second Preimage Resistance）：给定一个消息 \(x_1\)，找到另一个 \(x_2 \neq x_1\) 使得 \(H(x_1) = H(x_2)\) 在计算上是不可行的。与抗原像性的区别在于，此处敌手已经知道一个具体的原像 \(x_1\)，目标是找到与之碰撞的第二个原像。这一属性在数字签名中尤为关键：如果攻击者能为已签名的文档找到具有相同哈希值的恶意文档，签名便可被转移。

抗碰撞性（Collision Resistance）：找到任意一对不同消息 \((x_1, x_2)\)，\(x_1 \neq x_2\)，使得 \(H(x_1) = H(x_2)\)，在计算上是不可行的。注意这里与抗第二原像性的关键区别：攻击者可以自由选择两个消息，而非被给定其中一个。这使得碰撞攻击通常比第二原像攻击更容易发动——如我们将在下一节中看到的，生日攻击正是利用了这一自由度。

三个属性之间存在明确的蕴含关系：抗碰撞性蕴含抗第二原像性。这很容易证明：如果敌手能在给定 \(x_1\) 后找到碰撞的 \(x_2\)，那么它同样找到了一个碰撞对，违背了抗碰撞性。然而，反方向并不成立——存在抗第二原像但不抗碰撞的哈希函数。同样地，抗第二原像性与抗原像性之间的关系也并非简单的蕴含。在实际的安全性论证中，我们通常要求哈希函数同时满足三个属性，且对 \(n\) 比特输出的哈希函数，最优通用攻击的复杂度分别为：抗原像 \(O(2^n)\)、抗第二原像 \(O(2^n)\)、抗碰撞 \(O(2^{n/2})\)。

值得一提的是，以上定义使用的是渐近复杂性的语言。在具体安全性（Concrete Security）框架下，我们更关注在给定计算资源（时间与内存）下攻击成功的概率上界，这对于参数选择（如哈希输出长度的确定）具有更直接的指导意义。

二、生日攻击

生日攻击（Birthday Attack）得名于概率论中著名的生日悖论（Birthday Paradox）：在一个有 23 个人的房间里，至少两人生日相同的概率就超过了 50%。这个看似违反直觉的结果源于一个深刻的组合事实——碰撞的数量随样本数呈平方增长。

设哈希函数的输出空间大小为 \(N = 2^n\)。如果我们独立且均匀地随机采样 \(q\) 个哈希值，则不存在碰撞的概率为：

\[\Pr[\text{无碰撞}] = \prod_{i=1}^{q-1}\left(1 - \frac{i}{N}\right) \approx e^{-q(q-1)/(2N)}\]

当 \(q \approx 1.177 \sqrt{N} = 1.177 \cdot 2^{n/2}\) 时，碰撞概率达到 50%。这就是著名的生日界（Birthday Bound）：对 \(n\) 比特输出的哈希函数，通用碰撞攻击只需约 \(O(2^{n/2})\) 次哈希计算。

以下 Python 代码直观展示了生日攻击的概率计算：

import math

def birthday_collision_prob(n_bits, q):
    """
    计算 n_bits 位哈希函数在 q 次采样后出现至少一次碰撞的概率。
    使用对数近似避免浮点下溢。
    """
    N = 2 ** n_bits
    # ln(P[无碰撞]) ≈ -q(q-1)/(2N)
    log_no_collision = -q * (q - 1) / (2 * N)
    prob_collision = 1 - math.exp(log_no_collision)
    return prob_collision

def birthday_bound(n_bits, target_prob=0.5):
    """
    计算达到目标碰撞概率所需的采样次数（生日界）。
    由 q ≈ sqrt(2N * ln(1/(1-p))) 推导。
    """
    N = 2 ** n_bits
    q = math.sqrt(2 * N * math.log(1 / (1 - target_prob)))
    return int(math.ceil(q))

# 不同输出长度的生日界
for bits in [64, 128, 160, 256]:
    q50 = birthday_bound(bits, 0.5)
    print(f"哈希输出 {bits:>3} 位: 50% 碰撞概率需要约 2^{math.log2(q50):.1f} 次采样")

# 具体示例：SHA-256 采样 2^80 次后的碰撞概率
prob = birthday_collision_prob(256, 2**80)
print(f"\nSHA-256 采样 2^80 次后碰撞概率: {prob:.2e}")

生日攻击对哈希函数设计的直接影响是：若要求抗碰撞安全级别达到 \(k\) 比特（即攻击需要 \(2^k\) 次运算），则哈希输出长度必须至少为 \(2k\) 比特。这就是为什么 128 比特安全级别对应 SHA-256（256 比特输出），而 SHA-512 提供 256 比特的抗碰撞安全性。

生日攻击有多种高效实现方式。朴素方法需要 \(O(2^{n/2})\) 的内存来存储已计算的哈希值。Floyd 的环检测算法（Cycle Detection）和 Nivasch 的 distinguished point 方法可以将内存开销降至 \(O(1)\) 或 \(O(2^{n/4})\)，同时保持相同的时间复杂度。在并行计算环境中，van Oorschot 与 Wiener 提出的并行碰撞搜索算法可以利用 \(p\) 个处理器将时间降至 \(O(2^{n/2}/p)\)，使得分布式碰撞攻击成为现实威胁。

三、Merkle-Damgård 构造

先看一张图，把这一节的关键关系串起来。

flowchart LR
    A[消息] --> B[压缩函数]
    B --> C[摘要]
    C --> D[完整性]
    C --> E[签名与 KDF]

Merkle-Damgård 构造是自 1989 年以来密码学哈希函数最主流的设计范式，由 Ralph Merkle 和 Ivan Damgård 独立提出。其核心思想极为优雅：将一个处理固定长度输入的压缩函数（Compression Function）迭代地应用于消息分组，最终输出哈希值。

基本结构：设压缩函数 \(f: \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n\)，其中 \(n\) 为链值（Chaining Value）长度，\(b\) 为消息块长度。Merkle-Damgård 构造的工作流程如下：

  1. 填充（Padding）：将消息 \(M\) 填充至 \(b\) 的整数倍长度。Merkle-Damgård 强化填充（Merkle-Damgård Strengthening）要求在填充中编码原始消息长度——通常的做法是先追加一个 1 比特，然后追加若干 0 比特，最后追加消息长度的 64 比特编码。
  2. 分组：将填充后的消息分为 \(m_1, m_2, \ldots, m_L\) 共 \(L\) 个块。
  3. 迭代压缩：从固定的初始向量（IV）\(h_0\) 出发，依次计算 \(h_i = f(h_{i-1}, m_i)\)，最终输出 \(h_L\) 作为哈希值。

以下 Python 代码展示了 Merkle-Damgård 构造的简化结构：

import struct
import hashlib

def simple_compress(chaining_value: bytes, block: bytes) -> bytes:
    """
    简化的压缩函数示意（实际密码学哈希使用复杂的多轮变换）。
    此处仅用于演示 Merkle-Damgård 结构的迭代过程。
    """
    combined = chaining_value + block
    return hashlib.sha256(combined).digest()[:16]  # 截取 128 位作为演示

def merkle_damgard_hash(message: bytes, block_size: int = 32) -> bytes:
    """
    Merkle-Damgård 构造示意。
    """
    # 第一步：Merkle-Damgård 强化填充
    original_length = len(message)
    message += b'\x80'  # 追加 1 比特（以字节边界对齐）
    # 填充至 block_size 的整数倍，预留 8 字节编码长度
    while (len(message) + 8) % block_size != 0:
        message += b'\x00'
    # 追加原始消息长度（大端序，64 位）
    message += struct.pack('>Q', original_length * 8)

    # 第二步：分组
    blocks = [message[i:i+block_size] for i in range(0, len(message), block_size)]

    # 第三步：迭代压缩
    iv = b'\x00' * 16  # 固定初始向量
    chaining_value = iv
    for block in blocks:
        chaining_value = simple_compress(chaining_value, block)

    return chaining_value

# 演示
msg = "密码学哈希函数演示".encode('utf-8')
digest = merkle_damgard_hash(msg)
print(f"消息: {msg}")
print(f"哈希: {digest.hex()}")
print(f"长度: {len(digest) * 8} 位")

Merkle-Damgård 构造有一个极其重要的安全性归约定理：如果压缩函数 \(f\) 是抗碰撞的，则基于该压缩函数构建的 Merkle-Damgård 哈希函数也是抗碰撞的。 这一定理的证明思路是反证法——如果能找到完整哈希函数的碰撞，则沿着链值序列回溯，必定能在某一步找到压缩函数的碰撞。Merkle-Damgård 强化填充在此证明中起关键作用：它确保了不同长度的消息在填充后不会产生相同的最后一个块，从而保证了归约的完整性。

然而，Merkle-Damgård 构造也存在固有的结构性弱点，其中最为人知的是长度扩展攻击（Length Extension Attack）。

长度扩展攻击的原理：由于 Merkle-Damgård 构造的最终哈希值 \(H(M)\) 就是最后一步压缩函数的输出，它同时也是处理消息 \(M\) 之后的内部链值状态。攻击者在不知道原始消息 \(M\) 的情况下（但知道其长度），可以从 \(H(M)\) 出发继续”接力”压缩过程，计算出 \(H(M \| \text{padding} \| M')\) 的哈希值，其中 \(M'\) 是攻击者选择的任意后缀。

以下代码概念性地演示长度扩展攻击的思路：

def length_extension_demo():
    """
    长度扩展攻击概念演示。
    攻击者知道 H(secret || message) 和 len(secret || message)，
    可以计算 H(secret || message || padding || suffix) 而无需知道 secret。
    """
    # 假设的场景：服务器用 H(secret || data) 做消息认证
    secret = b"server_secret_key"
    original_data = b"amount=100&to=alice"
    original_msg = secret + original_data

    # 攻击者观察到的信息
    known_hash = merkle_damgard_hash(original_msg)
    known_total_len = len(original_msg)  # 攻击者可能通过侧信道得知

    # 攻击者想要追加的恶意数据
    attacker_suffix = b"&to=mallory"

    # 长度扩展攻击的核心：
    # 1. 用已知的哈希值作为新的链值（而非 IV）
    # 2. 计算原始消息的填充
    # 3. 在填充之后继续处理攻击者的后缀
    print("=== 长度扩展攻击概念演示 ===")
    print(f"已知哈希值: {known_hash.hex()}")
    print(f"攻击者后缀: {attacker_suffix}")
    print("攻击要点: 用已知哈希值替代 IV，从该状态继续压缩")
    print("这就是为什么 H(secret || message) 不能用作 MAC！")
    print("正确做法: 使用 HMAC 或带密钥的哈希构造")

length_extension_demo()

长度扩展攻击直接说明了为什么简单地使用 \(H(\text{key} \| \text{message})\) 作为消息认证码（MAC）是不安全的——这也是 HMAC 被发明的重要动机之一。SHA-3 的海绵构造从根本上免疫了长度扩展攻击，这是其设计上的重要优势。

除长度扩展攻击外，Merkle-Damgård 构造还容易受到多碰撞攻击（Multicollision Attack）的威胁。Joux 在 2004 年证明，对于 Merkle-Damgård 哈希函数，找到 \(2^t\) 个碰撞消息只需约 \(t \cdot 2^{n/2}\) 次压缩函数调用——这比理想哈希函数的预期复杂度低得多。这一结果进一步激发了密码学界对新型哈希构造的探索。

四、MD5 的兴衰

MD5（Message Digest Algorithm 5）由 Ron Rivest 于 1991 年设计，作为其前作 MD4 的加强版本发布（RFC 1321）。MD5 产生 128 比特的哈希输出，内部使用 Merkle-Damgård 构造，消息块大小为 512 比特，链值为 128 比特（四个 32 位字）。

MD5 的内部结构：MD5 的压缩函数由 4 轮组成，每轮包含 16 步操作，共计 64 步。每一步使用不同的非线性布尔函数（F、G、H、I）、模 \(2^{32}\) 加法和循环左移。四个非线性函数分别定义为：

每一步还使用了正弦函数的整数部分作为常数（\(T_i = \lfloor 2^{32} \cdot |\sin(i)| \rfloor\)），这种”无后门”（Nothing-up-my-sleeve）的常数生成方式旨在增强公众对设计透明性的信心。

MD5 的崩塌：早期的密码分析已经对 MD5 发出了警告。1996 年，Hans Dobbertin 发现了 MD5 压缩函数的碰撞（注意，这是压缩函数而非完整哈希函数的碰撞），引起了密码学界的高度关注。

转折点发生在 2004 年。中国密码学家王小云（Xiaoyun Wang）及其团队在 CRYPTO 2004 会议上宣布了对 MD5 完整哈希函数的实用碰撞攻击——这是从”理论可攻”到”现实被打爆”的里程碑。

王小云的差分攻击方法：该攻击的核心是差分密码分析（Differential Cryptanalysis），但其精妙之处在于两项关键技术的结合。

第一项技术是差分路径的构造。攻击者需要找到一条高概率的差分路径（Differential Path），即一组精确的比特差分值，描述两个消息块 \(M\) 和 \(M'\) 在压缩函数 64 步运算中的差分传播模式。MD5 的结构弱点使这成为可能：四个非线性函数 F、G、H、I 中，H 函数（\(B \oplus C \oplus D\)）是完全线性的，差分以概率 1 通过；F 和 G 函数虽然非线性，但其差分传播概率可以被精确计算。此外，MD5 各轮使用的循环左移量是固定且公开的，攻击者可以据此精确预测差分在模加法和移位操作中的传播行为。这些结构特征的叠加使得 MD5 的差分路径比 SHA 系列更容易构造。

第二项技术是消息修改（Message Modification），这是王小云团队最具原创性的贡献。即便找到了一条差分路径，随机选取的消息满足该路径所有中间条件（称为充分条件）的概率仍然极低。消息修改技术的思路是：先随机选取一个消息块，然后通过修改特定的消息字（Message Word），直接强制中间链值满足差分路径所要求的充分条件。对于前几轮的条件，由于链值与消息字之间的关系相对直接，可以采用单步修改（Single-step Modification）精确满足；对于后续轮次，链值与消息字的依赖关系变得复杂，则需要多步修改（Multi-step Modification），通过精心调整早期的消息字来间接影响后续的链值。消息修改技术将碰撞搜索的计算复杂度从差分路径的理论概率（可能低至 \(2^{-60}\) 以下）提升到实际可行的范围。

两块碰撞结构：王小云的 MD5 碰撞攻击使用两个连续的消息块完成碰撞。第一个消息块 \((M_0, M_0')\) 被精心构造，使得经过压缩函数后产生一个特定的链值差分 \(\Delta h_1\)；第二个消息块 \((M_1, M_1')\) 则在该差分的基础上继续运算，最终将链值差分消除为零——即 \(h_2 = h_2'\)。两块结构使得攻击者可以将差分路径分为两个阶段，每个阶段的约束条件更容易满足，从而大幅降低了整体攻击复杂度。最初的攻击在普通 PC 上需要不到一小时；后续由 Vlastimil Klima、Marc Stevens 等人的改进将碰撞生成时间降至几秒钟，最终在现代硬件上甚至可以在一秒内完成。

Merkle-Damgard 构造对 MD5 的”助攻”：MD5 的脆弱性不仅来自压缩函数本身，还与 Merkle-Damgard 构造的结构性弱点密切相关。如第三节所述，Merkle-Damgard 构造的最终输出就是最后一步压缩的链值，这直接暴露了内部状态，使得长度扩展攻击成为可能。更深层地，由于碰撞发生在链值层面（\(h_i = h_i'\)），一旦在某个中间块处达成碰撞，之后无论追加什么相同的消息块，最终哈希值都保持碰撞——这就是所谓的碰撞继承性。攻击者可以利用这一性质构造具有任意公共后缀的碰撞消息对，大幅扩展了碰撞攻击的实际利用空间。

从理论到武器化：碰撞攻击从学术论文走向了真实威胁。2008 年，Alexander Sotirov 等研究人员利用 MD5 碰撞伪造了一个 RapidSSL 中间 CA 证书，证明攻击者可以签发任意域名的合法 TLS 证书——这是对互联网 PKI 信任体系的直接打击。

而 2012 年被曝光的 Flame 恶意软件则将 MD5 碰撞攻击推向了国家级网络战争的舞台。Flame 的攻击者利用 MD5 碰撞伪造了微软终端服务器许可证服务（Terminal Server Licensing Service）的代码签名证书。具体而言，攻击者对微软合法证书中使用 MD5 签名的字段实施了选择前缀碰撞攻击（Chosen-prefix Collision），生成了一个拥有不同公钥但与合法证书具有相同 MD5 签名的伪造证书。凭借该伪造证书，Flame 能够通过 Windows Update 机制向目标计算机推送恶意更新，受害机器会将恶意软件视为微软官方更新予以信任和执行。安全研究人员分析指出，Flame 所使用的碰撞技术超越了当时已公开的学术成果，这意味着攻击者——被广泛认为是国家级行为体——可能独立开发了更先进的 MD5 碰撞算法。这一事件是密码学攻击在实战中造成严重后果的最具代表性的案例之一。

如今，MD5 已被密码学界完全废弃。NIST 明确建议不再将 MD5 用于任何密码学目的。然而遗憾的是，MD5 仍然在一些遗留系统和非安全用途（如文件完整性校验的快速比对）中被使用。任何新系统的设计都不应再考虑 MD5。

五、SHA-1 的退役

SHA-1（Secure Hash Algorithm 1）由美国国家安全局（NSA）设计，于 1995 年由 NIST 发布为联邦信息处理标准（FIPS 180-1）。SHA-1 产生 160 比特的哈希输出，同样采用 Merkle-Damgård 构造，压缩函数包含 80 步操作，分为 4 轮，每轮 20 步。

SHA-1 在 MD5 被攻破后一度被视为替代方案，但它自身的安全性也在逐步瓦解。2005 年，王小云团队再次出手，发表了对 SHA-1 的理论碰撞攻击，将碰撞搜索的复杂度从生日攻击的 \(2^{80}\) 降至约 \(2^{69}\)——虽然在当时尚不足以实际执行，但已经敲响了警钟。

决定性的一击来自 2017 年。Google 与荷兰国家数学和计算机科学研究中心（CWI Amsterdam）合作完成了 SHAttered 攻击，生成了两个具有不同内容但 SHA-1 哈希值相同的 PDF 文件。这一攻击消耗了约 \(2^{63.1}\) 次 SHA-1 计算，等价于 6500 年的单 CPU 计算或 110 年的单 GPU 计算，总计算成本估计在数十万美元级别。SHAttered 攻击不仅是理论上的碰撞，更产生了两个在视觉上完全不同的 PDF 文档——证明了碰撞攻击的实际危害。

2020 年，Gaëtan Leurent 和 Thomas Peyrin 进一步将攻击升级为选择前缀碰撞（Chosen-prefix Collision），复杂度约为 \(2^{63.4}\)。选择前缀碰撞比普通碰撞更具实际威胁——攻击者可以让两个碰撞文档分别以任意指定的前缀开头，这使得伪造证书等攻击场景更加现实。

SHA-1 的退役时间线清晰地反映了密码学社区对安全威胁的渐进响应：2011 年 NIST 正式建议停止使用 SHA-1 用于数字签名；2015 年微软、Google、Mozilla 相继宣布其浏览器将在 2017 年停止信任使用 SHA-1 签名的 TLS 证书；2017 年各大证书颁发机构（CA）停止签发 SHA-1 证书。到 2020 年，SHA-1 在大多数安全协议中已被彻底淘汰。Git 版本控制系统从 2.29 版本开始支持 SHA-256 作为替代哈希算法，尽管出于兼容性考虑，默认仍使用 SHA-1。

从 MD5 到 SHA-1 再到 SHA-3 的演进历程，表面上是一个纯技术的故事——旧算法被攻破，新算法取而代之。但笔者认为，这段历史揭示的关于密码学「社会学」的内容远比技术本身更深刻。MD5 在 1996 年压缩函数碰撞被发现后仍被广泛使用了整整八年，直到 2004 年王小云的完整碰撞攻击才真正触发迁移；SHA-1 在 2005 年理论攻击发表后又存活了十二年，直到 2017 年 SHAttered 实际碰撞的出现才加速退役。这种惊人的滞后说明了一个残酷的现实：密码学标准的更迭不是由数学驱动的，而是由可演示的攻击、媒体关注度和合规压力共同驱动的。「理论上不安全」和「已被公开攻破」之间的心理鸿沟，对于工程决策者来说是巨大的。这也解释了为什么 NIST 在 SHA-2 尚未被攻破的情况下就启动了 SHA-3 竞赛——密码学界从 MD5 和 SHA-1 的经历中学到：等到算法真正崩塌再寻找替代品为时已晚，必须未雨绸缪。

六、SHA-2 家族

SHA-2 家族由 NSA 设计，于 2001 年由 NIST 发布。它包含六个变体：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224 和 SHA-512/256，其中 SHA-256 和 SHA-512 是两个核心算法，其余变体均由这两者截断而来。

SHA-256 的设计：SHA-256 产生 256 比特输出，使用 512 比特的消息块和 256 比特的链值（八个 32 位字 \(a, b, c, d, e, f, g, h\)）。压缩函数包含 64 轮，每一轮使用两个非线性函数 \(\text{Ch}\) 和 \(\text{Maj}\)：

以及两组复合旋转操作 \(\Sigma_0, \Sigma_1\) 和 \(\sigma_0, \sigma_1\)。消息扩展（Message Schedule）将 16 个 32 位输入字扩展为 64 个字，使用递推关系 \(W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16}\)。轮常数取自前 64 个素数立方根的小数部分，继承了”无后门”的设计哲学。

SHA-512 的设计：SHA-512 与 SHA-256 在结构上高度相似，但所有运算基于 64 位字而非 32 位字，消息块为 1024 比特，压缩函数包含 80 轮。在 64 位处理器上，SHA-512 的性能通常优于 SHA-256——这是因为 64 位运算在现代处理器上是原生支持的。SHA-384 是 SHA-512 的截断版本，使用不同的初始向量并截取前 384 比特输出。

安全性现状：截至目前，SHA-2 家族尚未被发现任何实际的密码学弱点。针对 SHA-256 的最佳公开攻击仅能达到简化轮数版本（约 46 轮，满轮为 64 轮），且远未接近实际威胁的边界。SHA-2 的安全裕度（Security Margin）——即满轮数与已攻破轮数之间的差距——仍然相当充裕。

NIST 当前推荐 SHA-256 作为大多数应用的默认选择，SHA-384 和 SHA-512 则适用于需要更高安全级别或更长输出的场景。SHA-2 也是 TLS 1.3、比特币、PGP 等众多协议和系统的核心哈希算法。然而，SHA-2 与 MD5/SHA-1 共享 Merkle-Damgård 构造，因此天然继承了长度扩展攻击等结构性弱点——这也是 NIST 推动 SHA-3 竞赛的重要动因之一。

七、SHA-3 与海绵构造

2007 年，鉴于 MD5 和 SHA-1 的接连沦陷以及 SHA-2 与它们之间的结构相似性，NIST 发起了一场公开竞赛，旨在遴选下一代哈希函数标准——SHA-3。这是继 AES 竞赛之后密码学界规模最大的公开标准化进程，初始提交了 64 个候选算法，经过三轮筛选，最终于 2010 年 12 月公布了五个决赛候选算法（Finalists）：

SHA-3 的五个决赛候选算法：

Keccak 的胜出理由：2012 年 10 月，NIST 宣布 Keccak 为 SHA-3 标准。这一选择并非仅基于性能或安全裕度的单一维度，而是基于多方面的综合考量：

第一，构造层面的创新性与算法多样性。NIST 评审报告明确指出，SHA-3 的一个核心目标是提供与 SHA-2 在设计哲学上”根本不同”的替代方案。SHA-2 基于 Merkle-Damgard 构造和 ARX 运算，而五个候选中 BLAKE 和 Skein 也采用了 ARX 结构，Grostl 和 JH 仍基于 Merkle-Damgard 变体。唯有 Keccak 的海绵构造是全新的设计范式——如果未来出现针对 Merkle-Damgard 或 ARX 的系统性攻击，SHA-3 不会与 SHA-2 同时沦陷。这种”不要把鸡蛋放在同一个篮子里”的策略是 Keccak 胜出的首要原因。

第二，硬件实现效率。Keccak 在硬件实现中表现优异，其置换函数的逻辑门数量少、关键路径短，在 FPGA 和 ASIC 上的吞吐率远高于其他候选算法。对于嵌入式设备和硬件加速器等资源受限的场景，这一优势尤为关键。

第三，安全裕度与密码分析抵抗力。经过五年的公开密码分析，Keccak 的 24 轮置换中只有少量简化轮数版本被攻破（最佳公开攻击约达到 8 轮），安全裕度充分。海绵构造的安全性可以在理想置换模型下给出严格的可证明安全归约，这为安全性评估提供了坚实的理论基础。

值得一提的是，其他候选算法各有所长：BLAKE 在纯软件速度上实际优于 Keccak（这也是 BLAKE2/BLAKE3 后来在工程实践中被广泛采用的原因）；Skein 的灵活性和多模式集成设计在实用性方面极具吸引力。NIST 在评审报告中对所有五个候选算法的安全性均给予了正面评价——落选并不意味着不安全，而是 Keccak 在”与 SHA-2 互补”这一战略维度上的优势最为突出。

由 Guido Bertoni、Joan Daemen、Michael Peeters 和 Gilles Van Assche 设计的 Keccak 于 2015 年正式成为 FIPS 202 标准。Keccak 的革命性在于它完全摒弃了 Merkle-Damgard 构造，转而采用一种全新的设计范式——海绵构造（Sponge Construction）。

海绵构造的原理：海绵构造维护一个 \(b = r + c\) 比特的内部状态，其中 \(r\) 称为速率（Rate），\(c\) 称为容量（Capacity）。处理过程分为两个阶段：

  1. 吸收阶段（Absorbing Phase）：将消息填充后分为 \(r\) 比特的块。对于每个块，将其与内部状态的前 \(r\) 比特异或，然后对整个 \(b\) 比特状态施加一个固定的置换函数 \(f\)。容量部分（后 \(c\) 比特）不直接受消息输入影响——这是安全性的关键。
  2. 挤出阶段（Squeezing Phase）：每次从内部状态的前 \(r\) 比特提取输出，然后再次施加置换 \(f\)，重复此过程直到获得所需长度的输出。

Keccak 的核心置换 \(f\) 作用于 \(b = 1600\) 比特的状态（5×5×64 比特的三维数组），由五个子步骤组成——\(\theta\)（列校验）、\(\rho\)（比特旋转）、\(\pi\)（位置置换）、\(\chi\)（非线性变换）和 \(\iota\)（轮常数注入），重复 24 轮。这五个步骤的设计兼顾了扩散性、非线性和对称性破坏，经过了大量的密码分析验证。

容量与安全性：海绵构造的安全性证明表明，如果底层置换 \(f\) 是理想置换，则海绵构造提供 \(\min(2^{c/2}, 2^{|output|})\) 级别的安全性。这意味着容量 \(c\) 决定了安全裕度：SHA-3-256 使用 \(c = 512\)（\(r = 1088\)），提供 256 比特的抗碰撞安全性和 256 比特的抗原像安全性。

SHA-3 的天然优势：海绵构造从根本上免疫了长度扩展攻击——因为哈希输出只暴露了内部状态的一部分（\(r\) 比特），容量部分（\(c\) 比特）对外完全不可见，攻击者无法从输出恢复完整的内部状态。此外，海绵构造天然支持可变长度输出——这催生了 SHAKE128 和 SHAKE256 两个可扩展输出函数（XOF, Extendable-Output Function）。

SHA-3 与 SHAKE 的区别：SHA-3-256 固定输出 256 比特，与 SHA-256 功能对标；SHAKE256 则允许输出任意长度的伪随机比特流，适用于密钥派生、随机数生成等需要灵活输出的场景。SHAKE128 提供 128 比特安全级别（\(c = 256\)），SHAKE256 提供 256 比特安全级别（\(c = 512\)）。

从设计哲学上看，SHA-3 与 SHA-2 之间的互补性远大于替代性。SHA-2 基于传统的加法-旋转-异或（ARX）结构，SHA-3 基于置换的海绵构造——两者的设计理念截然不同，因此不太可能被同一种密码分析技术同时攻破。NIST 将两者并列推荐，形成了密码学哈希函数的”双保险”格局。

八、BLAKE2 与 BLAKE3

在 SHA-3 竞赛中进入决赛的五个候选算法中，BLAKE 以其出色的性能和坚实的安全性分析给密码学界留下了深刻印象，尽管最终未能胜出。其后续版本 BLAKE2 和 BLAKE3 在实际部署中获得了广泛采用。

BLAKE2（2012 年）：由 Jean-Philippe Aumasson、Samuel Neves、Zooko Wilcox-O’Hearn 和 Christian Winnerlein 基于 BLAKE 优化设计。BLAKE2 有两个主要变体：BLAKE2b 针对 64 位平台优化，输出最长 512 比特；BLAKE2s 针对 32 位和嵌入式平台优化，输出最长 256 比特。

BLAKE2 的核心是基于 ChaCha 流密码的四分之一轮函数（Quarter Round），结合 HAIFA 迭代框架。相比 SHA-3（Keccak），BLAKE2 在大多数软件平台上速度显著更快——在 x86-64 处理器上，BLAKE2b 的吞吐率通常是 SHA-256 的 2 到 3 倍，甚至接近 MD5 的速度，同时提供远超 MD5 的安全性。BLAKE2 内建了密钥化模式（Keyed Hashing）、盐值（Salt）、个性化字符串（Personalization）等功能，无需额外的 HMAC 封装即可用作 MAC。

BLAKE2 已被广泛采用：Linux 内核（4.12 起）将其用于内部哈希；WireGuard VPN 协议使用 BLAKE2s；libsodium 密码库将 BLAKE2b 作为默认通用哈希；Argon2 密码哈希竞赛的获胜算法也以 BLAKE2b 为内部组件。

BLAKE3（2020 年）：由 Jack O’Connor、Jean-Philippe Aumasson、Samuel Neves 和 Zooko Wilcox-O’Hearn 设计，是 BLAKE 系列的最新成员。BLAKE3 的突破在于引入了基于 Merkle 树的并行化架构：消息被分为 1 KiB 的块，每个块独立压缩后组织为二叉树结构，树根的哈希即为最终输出。

这种树哈希（Tree Hashing）架构带来了巨大的并行加速潜力——在多核处理器和 SIMD 指令集的加持下，BLAKE3 的速度可以随核心数近线性扩展。在单核性能上，BLAKE3 也将压缩轮数从 BLAKE2 的 12 轮（BLAKE2b）或 10 轮（BLAKE2s）削减至 7 轮，进一步提升了吞吐率。BLAKE3 同时也是 XOF（可扩展输出函数），与 SHAKE 类似，支持任意长度输出。此外，BLAKE3 内建了 KDF（密钥派生函数）和 MAC 模式，是一个高度集成的密码学原语。

在性能对比中，BLAKE3 通常比 SHA-256 快 5 到 15 倍（取决于平台和并行度），比 SHA-3-256 快 10 倍以上。当然，BLAKE3 的安全裕度相对较小（7 轮 vs BLAKE2b 的 12 轮），因此在对安全性要求极端保守的场景中，SHA-2 或 SHA-3 仍然是更稳妥的选择。

笔者认为，BLAKE3 代表的不仅仅是哈希函数性能的又一次提升，而是哈希函数设计哲学的一次根本性转向——从「串行优先」到「并行优先」。传统哈希函数（从 MD5 到 SHA-3）的核心计算结构是本质串行的：每一步压缩依赖于上一步的输出，无法并行化。这在单核时代是合理的设计选择，但在多核处理器、GPU 和 SIMD 指令集主导的今天，串行设计意味着哈希函数无法充分利用硬件的计算能力。BLAKE3 通过 Merkle 树结构将并行性内建到哈希函数的核心架构中——这不是一个外部的并行化包装，而是算法本身的设计就是为并行执行而生的。这一思想的影响可能远超哈希函数本身：随着硬件并行度持续增长，我们可能会看到越来越多的密码学原语采用类似的「并行优先」设计范式。

构造范式对比

回顾上文讨论的四种主要哈希构造范式，以下表格提供了一个结构化的对比视角：

维度 Merkle-Damgård 海绵构造（Sponge） HAIFA 树哈希（Tree Hashing）
代表算法 MD5、SHA-1、SHA-2 SHA-3（Keccak）、SHAKE BLAKE2 BLAKE3
核心思想 固定压缩函数的迭代链 吸收-挤出 + 宽置换 带计数器和盐值的迭代压缩 并行压缩 + Merkle 树聚合
内部状态 链值 = 输出长度 状态 = 速率 + 容量（\(r + c\)，\(c\) 不外露） 链值 + 消息块计数器 + 盐值 每块独立状态 + 树聚合
长度扩展抗性 无（天然脆弱） 有（容量部分隐藏） 有（计数器阻断扩展） 有（树根不暴露中间状态）
多碰撞抗性 弱（Joux 攻击：\(t \cdot 2^{n/2}\)） 强（接近理想） 较强 强
并行性 无（本质串行） 无（本质串行） 无（本质串行） 原生并行（随核心数线性扩展）
可变长度输出 否（固定输出） 是（XOF：挤出任意长度） 否 是（XOF）
安全性归约 压缩函数抗碰撞 → 哈希抗碰撞 底层置换为理想置换 → \(\min(2^{c/2}, 2^n)\) 安全性 类似 MD 但消除了长度扩展 压缩函数安全性 + 树结构归约

这张对比表揭示了一个清晰的设计演进趋势：从 Merkle-Damgård 到海绵构造，核心改进是消除了结构性弱点（长度扩展、多碰撞）；从海绵构造到树哈希，核心改进是引入了并行性。每一代构造都是对前一代局限性的精确回应。

九、哈希输出长度的选择

在实际系统设计中，选择合适的哈希输出长度是一个至关重要的工程决策。输出长度直接决定了碰撞抗性和原像抗性的安全界，同时也影响存储开销、传输带宽和计算性能。以下表格汇总了主流输出长度的安全性现状和推荐用途：

输出长度 代表算法 碰撞抗性（理论/实际） 原像抗性 安全状态 推荐用途
128 位 MD5 理论 \(2^{64}\)，实际约 \(2^{18}\)（秒级碰撞） \(2^{128}\)（理论），实际未被攻破 已废弃 仅限非安全用途（校验和、去重），禁止用于任何密码学场景
160 位 SHA-1 理论 \(2^{80}\)，实际约 \(2^{63}\)（SHAttered） \(2^{160}\)（理论），实际未被攻破 已废弃 遗留系统兼容（如旧版 Git），新系统禁止使用
256 位 SHA-256、SHA-3-256、BLAKE2s \(2^{128}\) \(2^{256}\) 安全，推荐 通用默认选择：数字签名、证书、TLS、区块链、HMAC、完整性校验
384 位 SHA-384 \(2^{192}\) \(2^{384}\) 安全，推荐 政府/金融等高安全级别场景，TLS 1.3 中的高强度套件
512 位 SHA-512、SHA-3-512、BLAKE2b \(2^{256}\) \(2^{512}\) 安全，推荐 长期存档签名、需要额外安全裕度的场景、密钥派生输入

安全界说明：对于一个 \(n\) 比特输出的理想哈希函数，碰撞抗性的通用上界为 \(O(2^{n/2})\)（由生日攻击决定），原像抗性的通用上界为 \(O(2^n)\)。当某个具体算法的最佳已知攻击复杂度显著低于这些通用上界时（如 MD5 的碰撞复杂度从 \(2^{64}\) 降至约 \(2^{18}\)），表明该算法存在严重的结构性弱点，应立即停止使用。

需要强调的是，上表中”理论”值是指在算法本身无弱点的理想情况下的通用攻击复杂度，而”实际”值是指当前最佳已知攻击的复杂度。两者之间的差距越大，算法越危险。SHA-256 及以上的算法目前的最佳已知攻击均未突破其通用安全界，因此被认为是安全的。

选择建议：在无特殊约束的情况下，256 位输出（即 128 比特碰撞安全级别）是当前最广泛推荐的默认选择，在安全性与性能之间取得了良好的平衡。若系统需要抵抗未来数十年内可能出现的密码分析进展——例如长期有效的数字签名或国家级保密数据——应考虑 384 位或 512 位输出以提供额外的安全裕度。对于后量子安全性的考量，Grover 算法可将原像搜索的量子复杂度降至 \(O(2^{n/2})\)、碰撞搜索降至 \(O(2^{n/3})\)，因此量子安全场景下 256 位输出仍可提供 128 比特的原像安全性，但碰撞安全性降至约 85 比特——此时应选择更长的输出。

十、哈希函数的密码学应用

哈希函数的应用远不止于计算消息摘要。在现代密码学中，哈希函数以多种形态参与构建各类安全协议和原语，其角色之多样令人惊叹。

最基础的应用是承诺方案（Commitment Scheme）。承诺者计算 \(c = H(m \| r)\)（其中 \(r\) 是随机盲化因子）并公布 \(c\)，揭示阶段再公开 \(m\) 和 \(r\) 供验证。抗原像性保证隐藏性——验证者无法从 \(c\) 推断 \(m\)；抗碰撞性保证绑定性——承诺者无法找到不同的 \((m', r')\) 满足 \(H(m' \| r') = c\)。承诺方案看似简单，却是零知识证明、安全多方计算和区块链协议的基础构件。

在安全性证明中，哈希函数常被理想化为随机预言机（Random Oracle）——一个对每个查询返回真正随机且一致回答的黑盒。尽管 Canetti、Goldreich 和 Halevi 在 1998 年证明了随机预言机模型与标准模型之间存在不可消除的理论间隙，但这一范式仍是最有效的设计启发工具。基于此的 Fiat-Shamir 启发式将交互式证明转化为非交互式版本——用哈希函数替代验证者的角色，证明者以自己的承诺作为哈希输入、以哈希输出作为挑战。Schnorr 签名、EdDSA 以及现代 zk-SNARK 系统的非交互化都依赖这一技术。

在后量子密码学的浪潮中，基于哈希的签名（如 XMSS 和 SPHINCS+/SLH-DSA）因其安全性仅依赖哈希函数而非数论困难问题，成为抗量子攻击的天然选择。NIST 已将 SLH-DSA 选定为三个后量子签名标准之一——它完全建立在哈希函数之上，从 WOTS+（Winternitz 单次签名）到 FORS（Few-Time Signature），每一层都是哈希函数的精巧组合。

需要特别警示的是密码哈希的常见误区：直接使用 SHA-256 等通用哈希函数进行密码哈希是错误的。通用哈希函数被设计为尽可能快速，而密码哈希恰恰需要刻意的计算缓慢（Memory-hard 和 CPU-hard）以抵抗暴力搜索。正确的选择是 bcrypt、scrypt 或 Argon2（推荐 Argon2id 混合模式），它们通过可调节的时间和内存成本参数确保暴力破解的代价足够高昂。

最后，Merkle 树是哈希函数最优雅的组合应用。叶节点是数据块的哈希值，非叶节点是子节点哈希拼接后再哈希的结果，树根即为整个数据集的承诺。其核心优势是 \(O(\log n)\) 的成员证明——这一特性使 Merkle 树在区块链交易验证、证书透明度（Certificate Transparency）和内容寻址存储（IPFS）中不可替代。

一个在上述所有应用中都至关重要、但经常被忽略的技术细节是域分离（Domain Separation）。当同一个哈希函数被用于不同的密码学用途时——例如同时用于承诺方案和密钥派生——如果不在输入中明确标注用途（如添加不同的前缀或上下文字符串），就可能产生跨协议攻击：一个协议中的合法哈希值可能在另一个协议中被重新解释为有效的密码学对象。这类攻击极其微妙，因为每个协议孤立来看都是安全的，只有在组合使用时才会暴露问题。域分离的思想很简单——为每种用途的哈希输入添加唯一的、不可混淆的标签——但它的重要性怎么强调都不为过。SHA-3 和 BLAKE3 都在设计层面内建了域分离机制（SHA-3 通过不同的后缀位区分哈希和 XOF；BLAKE3 通过标志字节区分哈希、KDF 和 MAC），这反映了密码学界对域分离重要性的日益共识。从工程实践来看，笔者强烈建议：任何使用哈希函数的协议设计都应将域分离作为默认实践，而非事后补救。

密码学哈希函数的演进史是一部攻防交替的精彩叙事：MD5 的迅速崛起与黯然退场，SHA-1 从标准之位跌落，SHA-2 在稳健中坚守，SHA-3 以海绵构造开辟新径，BLAKE 家族在性能边界上不断突破。每一次攻击都推动了设计的进步，每一次标准的更迭都加深了我们对安全性本质的理解。在选择哈希函数时，开发者应根据具体场景权衡安全裕度、性能、标准合规性和抗未来攻击能力——没有一劳永逸的选择，只有持续演进的最佳实践。

密码学百科系列 · 第 10 篇

← 上一篇：流密码 | 系列目录 | 下一篇：MAC 与 HMAC →

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2025-07-15 · algorithms

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

为什么 Python 3.3 突然把字典的哈希函数换成了 SipHash？为什么 Rust 的默认 HashMap 不用最快的 wyhash 而用 SipHash-1-3？当你的哈希表面向不可信输入时，速度最快的哈希函数可能是最危险的。

By .