密码学哈希函数的安全属性：碰撞抵抗、原像抵抗与第二原像抵抗

密码学概念 · 2026-10-05

概述

密码学哈希函数是将任意长度输入映射为固定长度输出的确定性函数。与普通的非密码学哈希（如 CRC、FNV）不同，密码学哈希函数的安全性并非来自结构复杂度，而是建立在三个严格定义的数学属性之上：原像抵抗、第二原像抵抗和碰撞抵抗。

这三个属性构成了哈希函数安全性的完整体系，也是评估 SHA-2、SHA-3、SM3 等算法安全强度的理论基础。理解它们的层次关系和攻击模型，是分析哈希算法安全性、设计密码协议的基础。

形式化定义

设 $H: \{0,1\}^* \rightarrow \{0,1\}^n$ 为一个密码学哈希函数，输出长度为 $n$ 位。

1. 原像抵抗（Preimage Resistance）

定义：给定哈希输出 $y = H(x)$，计算任意输入 $x'$ 使得 $H(x') = y$ 在计算上不可行。

形式化表述： $$\forall y \in \{0,1\}^n, \Pr[\text{Find } x': H(x') = y] \leq \epsilon$$

其中 $\epsilon$ 为可忽略函数（negligible function），即对于足够大的安全参数 $\lambda$，$\epsilon(\lambda) < 1/p(\lambda)$，$p(\cdot)$ 为任意多项式。

直观理解：哈希函数是"单向"的——正向计算容易，逆向求解困难。这类似于单向函数的概念。

攻击场景：攻击者已知某个消息的哈希值，试图找到产生该哈希值的原始消息。典型应用：密码存储（已知哈希，求原密码）。

2. 第二原像抵抗（Second Preimage Resistance）

定义：给定输入 $x$，找到另一个不同输入 $x' \neq x$ 使得 $H(x) = H(x')$ 在计算上不可行。

形式化表述： $$\forall x \in \{0,1\}^*, \Pr[\text{Find } x' \neq x: H(x') = H(x)] \leq \epsilon$$

直观理解：即使知道原始消息，也难以找到另一个产生相同哈希值的消息。这与原像抵抗的关键区别在于：攻击者已知其中一个输入。

攻击场景：攻击者已知合法消息 $x$ 及其哈希值，试图构造一个不同的消息 $x'$ 产生相同哈希值，从而伪造文档或合同。

3. 碰撞抵抗（Collision Resistance）

定义：找到任意两个不同输入 $x \neq x'$ 使得 $H(x) = H(x')$ 在计算上不可行。

形式化表述： $$\Pr[\text{Find } x \neq x': H(x) = H(x')] \leq \epsilon$$

直观理解：不存在任何一对消息能够产生相同的哈希值。与前两个属性的关键区别：攻击者可以自由构造两个输入，无需预先知道任何一个。

攻击场景：攻击者构造两个不同文档（如合法合同和恶意合同）产生相同哈希值，然后获取用户对合法文档的签名，再用该签名伪造恶意文档。

强度层次关系

三个安全属性之间存在严格的强度层次：

CODE

碰撞抵抗 ≥ 第二原像抵抗 ≥ 原像抵抗

蕴含关系证明

定理：碰撞抵抗蕴含第二原像抵抗。

证明：假设 $H$ 是碰撞抵抗的，但存在多项式时间算法 $A$ 能够以不可忽略概率找到第二原像。给定输入 $x$，算法 $A(x)$ 输出 $x' \neq x$ 使得 $H(x) = H(x')$。

构造碰撞找到算法 $B$：

随机选择 $x$
运行 $A(x)$ 得到 $x'$
输出 $(x, x')$

由于 $A$ 以不可忽略概率成功，$B$ 也以不可忽略概率找到碰撞，与碰撞抵抗假设矛盾。

定理：第二原像抵抗蕴含原像抵抗。

证明：类似地，假设存在算法 $C$ 能找原像，构造第二原像找到算法：

随机选择 $x$
计算 $y = H(x)$
运行 $C(y)$ 得到 $x' \neq x$（因为原像抵抗定义中要求找到任意原像，而 $x$ 已是原像之一，若 $C$ 找到不同原像则完成）
输出 $(x, x')$

注意：这个蕴含关系成立的前提是原像找到算法总是返回不同于给定输入的新原像。在严格形式化定义下，第二原像抵抗确实强于原像抵抗。

强度对比表

安全属性	攻击者已知	攻击目标	理论安全强度
原像抵抗	无	找 $x'$ 使 $H(x')=y$	$2^n$ 次运算
第二原像抵抗	一个输入 $x$	找 $x' \neq x$ 使 $H(x')=H(x)$	$2^n$ 次运算
碰撞抵抗	无	找 $x \neq x'$ 使 $H(x)=H(x')$	$2^{n/2}$ 次运算（生日攻击）

关键点：碰撞抵抗的理论强度仅为 $2^{n/2}$，而原像和第二原像抵抗为 $2^n$。这是因为生日悖论使得碰撞查找的效率远高于原像查找。

攻击模型与复杂度分析

原像攻击（Preimage Attack）

暴力搜索：

随机选择输入 $x$，计算 $H(x)$，检查是否等于目标 $y$
期望尝试次数：$2^n$
对于 SHA-256（$n=256$）：$2^{256}$ 次运算，当前技术不可行

优化攻击：

Rainbow Table（彩虹表）：预计算表，空间换时间
适用场景：目标哈希值固定且较小（如 128 位以下）
对长哈希值（如 256 位）无效

第二原像攻击（Second Preimage Attack）

暴力搜索：

固定 $x$，随机选择 $x'$ 直到 $H(x') = H(x)$
期望尝试次数：$2^n$
与暴力原像攻击复杂度相同

Joux 多碰撞攻击：

Jean-Philippe Joux（2004）提出针对 Merkle-Damgård 结构的多碰撞攻击
对于 $d$ 轮迭代，可以构造 $2^d$ 个碰撞
但对第二原像攻击的实际影响有限

碰撞攻击（Collision Attack）

生日攻击（Birthday Attack）：

基于生日悖论：在 $2^{n/2}$ 个随机输入中，期望找到一个碰撞
对于 SHA-256：约 $2^{128}$ 次运算
这是通用碰撞攻击的理论下界

差分碰撞攻击：

针对特定哈希结构设计的攻击
MD5：2004 年王小云团队提出差分路径，实际碰撞复杂度降至 $2^{18}$ 量级
SHA-1：2005 年降低至 $2^{63}$，2017 年 SHAttered 攻击实现实际碰撞

结构攻击：

针对 Merkle-Damgård 增强型（MD-enhancement）的攻击

-length extension attack（长度扩展攻击）：已知 $H(x)$，可计算 $H(x || padding || y)$

适用于 SHA-2、SM3 等结构，但不影响碰撞抵抗属性

各算法的安全属性分析

SHA-2 系列

变体	输出长度	原像安全	第二原像安全	碰撞安全	结构
SHA-256	256 bit	$2^{256}$	$2^{256}$	$2^{128}$	Merkle-Damgård
SHA-512	512 bit	$2^{512}$	$2^{512}$	$2^{256}$	Merkle-Damgård

安全状态：截至 2026 年，SHA-2 未发现优于生日攻击的碰撞攻击。NIST 确认 SHA-256/SHA-512 仍满足密码学安全要求。

长度扩展攻击：SHA-2 的 Merkle-Damgård 结构存在长度扩展漏洞。解决方案：

使用 HMAC 结构（内部/外部填充）
使用 SHA-3（海绵结构，天然免疫）
在哈希后附加密钥：$H(key || H(key || message))$

SHA-3（Keccak）

参数	输出长度	容量 $c$	碰撞安全
SHA3-224	224 bit	448 bit	$2^{224}$
SHA3-256	256 bit	512 bit	$2^{256}$
SHA3-384	384 bit	768 bit	$2^{384}$
SHA3-512	512 bit	1024 bit	$2^{512}$

海绵结构优势：

容量 $c$ 提供额外的安全边界
碰撞安全强度为 $2^{c/2}$，而非 $2^{n/2}$
天然免疫长度扩展攻击

安全强度对比：

SHA3-256 的碰撞安全为 $2^{256}$（容量 512 位）
远超 SHA-256 的 $2^{128}$

SM3

参数	值
输出长度	256 bit
结构	Merkle-Damgård 增强型
原像安全	$2^{256}$
碰撞安全	$2^{128}$
IV	固定常数（来自 $\pi$ 和 $e$ 的二进制位）

国密标准：GM/T 0004-2012《SM3 密码杂凑算法》规定 SM3 必须满足三个安全属性。与 SHA-256 结构类似，但：

消息扩展算法不同（SM3 使用 CF 压缩函数）
初始向量不同
轮数：64 轮（与 SHA-256 相同）

安全属性的实际应用映射

应用场景	所需安全属性	原因
数字签名	碰撞抵抗	防止伪造签名
消息认证码（HMAC）	第二原像抵抗	防止伪造消息
密码存储	原像抵抗	防止还原密码
证书指纹	碰撞抵抗	防止证书伪造
区块链挖矿	原像抵抗 + 第二原像抵抗	工作证明难度
时间戳服务	第二原像抵抗	防止时间戳伪造

数字签名场景详解

数字签名要求签名者与消息绑定，攻击者无法找到两个不同消息产生相同签名。这要求：

碰撞抵抗：攻击者不能构造两个不同消息 $m_1, m_2$ 使得 $\text{Sign}(m_1) = \text{Sign}(m_2)$
第二原像抵抗：攻击者已知签名消息 $m$，不能找到 $m' \neq m$ 使得签名相同

对于 RSA-PSS 等概率签名方案，还需考虑签名方案的不可伪造性（EUF-CMA），但这已超出哈希函数安全属性的范畴。

从安全属性到算法设计的启示

Merkle-Damgård 结构的局限

Merkle-Damgård 结构（SHA-2、MD5、SHA-1）存在长度扩展攻击。虽然不影响碰撞抵抗，但在 HMAC 之外的应用场景需要额外处理。

NMAC/HMAC 解决方案：

CODE

HMAC(K, m) = H((K ⊕ opad) || H((K ⊕ ipad) || m))

通过内外两次哈希和密钥混合，消除长度扩展影响。

海绵结构的优势

SHA-3 的海绵结构（Keccak）：

内部状态分为速率 $r$ 和容量 $c$
输出仅暴露速率部分
碰撞安全强度为 $2^{c/2}$，可独立于输出长度设计

这使得 SHA-3 可以在保持 256 位输出的同时，提供 $2^{256}$ 的碰撞安全（而非 SHA-2 的 $2^{128}$）。

后量子安全考量

量子计算对哈希函数安全属性的影响：

Grover 算法：将原像搜索从 $2^n$ 降至 $2^{n/2}$
BHT 算法：将碰撞搜索从 $2^{n/2}$ 降至 $2^{n/3}$

因此，后量子安全要求：

原像安全：至少 256 位输出（抵御 Grover）
碰撞安全：至少 512 位输出（抵御 BHT）或选择 SHA-3-512

总结

密码学哈希函数的三个安全属性构成完整的防御体系：

原像抵抗保证单向性，是密码存储的基础
第二原像抵抗保证抗伪造性，是消息认证的核心
碰撞抵抗保证唯一映射，是数字签名的前提

强度层次为：碰撞抵抗 ≥ 第二原像抵抗 ≥ 原像抵抗。实际算法设计中，碰撞抵抗往往是最难保证的属性（生日攻击下界为 $2^{n/2}$），因此现代哈希函数（如 SHA-3）通过结构创新提升碰撞安全边界。

国密 SM3 与国际标准 SHA-2 在安全属性上等价，但在结构细节上各有特点。在密码协议设计中，应根据应用场景选择对应的安全属性要求，而非简单比较输出长度。

参考来源

NIST FIPS 180-4: Secure Hash Standard
ISO/IEC 10118-3: Hash-functions - Part 3: Dedicated hash-functions
GM/T 0004-2012: _SM3 密码杂凑算法_
Joux, A. (2004). _Multicollisions in iterated hash functions. Applications to cryptanalytic constructions._
Wang, X. et al. (2004). _Collision Attacks on Hash Functions: New Techniques, New Results, and New Challenges._