哈希与认证基础（二）：生日攻击：为什么 n-bit 哈希只有 n/2-bit 碰撞安全性

3@[TOC](哈希与认证基础（二）：生日攻击：为什么 n-bit 哈希只有 n/2-bit 碰撞安全性)

前言

在上一篇文章中，我们区分了哈希函数的三种安全目标：

• 原像抗性；
• 第二原像抗性；
• 碰撞抗性。

对于输出长度为

n

n

n 位的理想哈希函数，通常可以得到这样的安全性估算：

原像攻击

≈

2

n

第二原像攻击

≈

2

n

碰撞攻击

≈

2

n

/

2

\\begin{aligned} \\text{原像攻击}&\\approx2^n\\\\ \\text{第二原像攻击}&\\approx2^n\\\\ \\text{碰撞攻击}&\\approx2^{n/2} \\end{aligned}

原像攻击第二原像攻击碰撞攻击​≈2n≈2n≈2n/2​

很多人第一次看到这个结论时都会有疑问：

哈希函数明明输出

n

n

n 位，摘要空间有

2

n

2^n

2n 种结果，为什么寻找碰撞只需要大约

2

n

/

2

2^{n/2}

2n/2 次计算？

原因就是著名的生日悖论。

生日悖论最初来自概率学，但在密码学中，它直接决定了哈希函数的通用碰撞安全上限。对于一个输出长度为

n

n

n 位的理想哈希函数，生日攻击能够将碰撞搜索复杂度从

2

n

2^n

2n 降低到

2

n

/

2

2^{n/2}

2n/2。NIST 对哈希函数安全强度的分析也采用这一基本结论：输出长度为

n

n

n 位的哈希函数，其通用碰撞安全强度约为

n

/

2

n/2

n/2 位。(nvlpubs.nist.gov)

本文不讨论具体哈希算法的内部结构，而是从概率模型出发，推导生日攻击为什么有效，并解释它与原像攻击、第二原像攻击之间的区别。

一、生日悖论到底反直觉在哪里

1.1 23 个人就有较高概率同生日

假设一年有 365 天，每个人的生日均匀分布在这 365 天中。

很多人会直觉认为：

至少需要 183 个人，才有超过一半的概率出现两个人同一天生日。

因为 183 约等于 365 的一半。

但实际情况并不是这样。

当房间里只有 23 个人时，至少两个人生日相同的概率就已经超过 50%。

这并不是因为某个特定的人特别容易和别人同生日，而是因为 23 个人之间存在很多组配对。

23 个人可以组成的两两组合数量为：

(

23

2

)

=

23

×

22

2

=

253

\\binom{23}{2}= \\frac{23\\times22}{2}= 253

(223​)=223×22​=253

也就是说，虽然只有 23 个人，但实际上有 253 对生日需要比较。

这就是生日悖论的核心：

碰撞不是只发生在“新对象和某一个固定对象”之间，而是可能发生在所有对象对之间。

1.2 哈希碰撞与生日问题的对应关系

把生日问题换成哈希问题：

• 365 天对应哈希输出空间；
• 人对应输入消息；
• 生日对应哈希摘要；
• 两个人同生日对应两条消息摘要相同。

假设哈希函数输出

n

n

n 位，那么摘要空间大小为：

N

=

2

n

N=2^n

N=2n

攻击者不断选择消息：

M

1

,

M

2

,

M

3

,

…

,

M

q

M_1,M_2,M_3,\\dots,M_q

M1​,M2​,M3​,…,Mq​

并计算：

H

(

M

1

)

,

H

(

M

2

)

,

…

,

H

(

M

q

)

H(M_1),H(M_2),\\dots,H(M_q)

H(M1​),H(M2​),…,H(Mq​)

攻击成功的条件是：

H

(

M

i

)

=

H

(

M

j

)

(

i

≠

j

)

H(M_i)=H(M_j) \\quad(i\\neq j)

H(Mi​)=H(Mj​)(i=j)

由于任意两条消息都可能形成一组比较对象，攻击者不需要把所有

2

n

2^n

2n 个摘要空间都遍历一遍，就有机会遇到重复摘要。

二、从“配对数量”理解生日攻击

2.1 $q$

假设攻击者准备了

q

q

q 条消息。

两条不同消息可以组成一组比较对象，因此一共有：

(

q

2

)

=

q

(

q

−

1

)

2

\\binom{q}{2}= \\frac{q(q-1)}{2}

(2q​)=2q(q−1)​

组消息对。

如果

q

q

q 比较小，消息对数量大约可以写成：

q

2

2

\\frac{q^2}{2}

2q2​

假设哈希输出空间大小为：

N

=

2

n

N=2^n

N=2n

理想情况下，每一对消息产生相同摘要的概率约为：

1

N

=

1

2

n

\\frac{1}{N}= \\frac{1}{2^n}

N1​=2n1​

因此，

q

q

q 条消息中出现碰撞的“期望配对数量”近似为：

λ

=

q

(

q

−

1

)

2

N

\\lambda= \\frac{q(q-1)}{2N}

λ=2Nq(q−1)​

当这个值接近 1 时，碰撞就不再罕见。

令：

q

2

2

N

≈

1

\\frac{q^2}{2N}\\approx1

2Nq2​≈1

可以得到：

q

2

≈

2

N

q^2\\approx2N

q2≈2N

因此：

q

≈

2

N

q\\approx\\sqrt{2N}

q≈2N

​

由于：

N

=

2

n

N=2^n

N=2n

所以：

q

≈

2

×

2

n

q\\approx\\sqrt{2\\times2^n}

q≈2×2n

​

进一步整理：

q

≈

2

×

2

n

/

2

q\\approx\\sqrt{2}\\times2^{n/2}

q≈2

​×2n/2

忽略常数

2

\\sqrt{2}

2

​ 后，碰撞搜索复杂度就是：

2

n

/

2

2^{n/2}

2n/2

这就是

n

n

n 位哈希函数只有

n

/

2

n/2

n/2 位碰撞安全性的根本原因。

2.2 一个简单的 8 位例子

假设某个哈希函数只有 8 位输出：

n

=

8

n=8

n=8

摘要空间大小为：

N

=

2

8

=

256

N=2^8=256

N=28=256

如果按照原像攻击的思路，指定一个摘要并寻找对应消息，理论上需要约：

2

8

=

256

2^8=256

28=256

次尝试。

但寻找任意碰撞时，根据生日攻击，只需要约：

2

8

/

2

=

2

4

=

16

2^{8/2}=2^4=16

28/2=24=16

次尝试，就可能遇到碰撞。

更精确地说，达到 50% 碰撞概率所需的样本数量约为：

1.1774

×

2

n

/

2

1.1774\\times2^{n/2}

1.1774×2n/2

代入

n

=

8

n=8

n=8：

1.1774

×

2

4

≈

18.84

1.1774\\times2^4 \\approx18.84

1.1774×24≈18.84

所以，大约准备 19 条消息，就有接近 50% 的概率出现摘要碰撞。

这就是生日悖论最直观的体现：

摘要空间有 256 种结果，
但只需要大约 19 个样本，
就有较高概率出现重复。

三、碰撞概率的严格推导

3.1 先计算“不发生碰撞”的概率

直接计算“发生碰撞”的概率不太方便，因此先计算相反事件：

计算前

q

q

q 条消息的摘要全部不同的概率。

假设摘要空间大小为

N

N

N。

第 1 条消息的摘要可以是空间中的任意值，因此：

P

1

=

1

P_1=1

P1​=1

第 2 条消息不能和第 1 条相同，因此：

P

2

=

N

−

1

N

P_2=\\frac{N-1}{N}

P2​=NN−1​

第 3 条消息不能和前两条相同，因此：

P

3

=

N

−

2

N

P_3=\\frac{N-2}{N}

P3​=NN−2​

第

q

q

q 条消息需要避开前面已经出现的

q

−

1

q-1

q−1 个摘要，因此：

P

q

=

N

−

(

q

−

1

)

N

P_q=\\frac{N-(q-1)}{N}

Pq​=NN−(q−1)​

将这些概率相乘，可以得到前

q

q

q 条消息完全没有碰撞的概率：

P

no collision

=

N

N

⋅

N

−

1

N

⋅

N

−

2

N

⋯

N

−

q

+

1

N

P_{\\text{no collision}}= \\frac{N}{N} \\cdot \\frac{N-1}{N} \\cdot \\frac{N-2}{N} \\cdots \\frac{N-q+1}{N}

Pno collision​=NN​⋅NN−1​⋅NN−2​⋯NN−q+1​

写成连乘形式：

P

no collision

=

∏

i

=

0

q

−

1

(

1

−

i

N

)

P_{\\text{no collision}}= \\prod_{i=0}^{q-1} \\left( 1-\\frac{i}{N} \\right)

Pno collision​=i=0∏q−1​(1−Ni​)

因此，至少出现一次碰撞的概率为：

P

collision

=

1

−

P

no collision

P_{\\text{collision}}= 1-P_{\\text{no collision}}

Pcollision​=1−Pno collision​

即：

P

collision

=

1

−

∏

i

=

0

q

−

1

(

1

−

i

N

)

P_{\\text{collision}}= 1- \\prod_{i=0}^{q-1} \\left( 1-\\frac{i}{N} \\right)

Pcollision​=1−i=0∏q−1​(1−Ni​)

3.2 指数近似

当

q

q

q 远小于

N

N

N 时，可以使用近似：

1

−

x

≈

e

−

x

1-x\\approx e^{-x}

1−x≈e−x

于是：

P

no collision

≈

exp

⁡

(

−

q

(

q

−

1

)

2

N

)

P_{\\text{no collision}} \\approx \\exp\\left( -\\frac{q(q-1)}{2N} \\right)

Pno collision​≈exp(−2Nq(q−1)​)

所以：

P

collision

≈

1

−

exp

⁡

(

−

q

(

q

−

1

)

2

N

)

P_{\\text{collision}} \\approx 1- \\exp\\left( -\\frac{q(q-1)}{2N} \\right)

Pcollision​≈1−exp(−2Nq(q−1)​)

代入：

N

=

2

n

N=2^n

N=2n

可以得到：

P

collision

≈

1

−

exp

⁡

(

−

q

(

q

−

1

)

2

n

+

1

)

P_{\\text{collision}} \\approx 1- \\exp\\left( -\\frac{q(q-1)}{2^{n+1}} \\right)

Pcollision​≈1−exp(−2n+1q(q−1)​)

这个公式可以用来估算：当输入数量为

q

q

q 时，出现至少一次碰撞的概率是多少。

3.3 50% 碰撞概率对应多少次计算

当碰撞概率达到 50% 时：

P

collision

=

1

2

P_{\\text{collision}}=\\frac12

Pcollision​=21​

因此：

P

no collision

=

1

2

P_{\\text{no collision}}=\\frac12

Pno collision​=21​

将近似公式代入：

exp

⁡

(

−

q

(

q

−

1

)

2

N

)

=

1

2

\\exp\\left( -\\frac{q(q-1)}{2N} \\right)= \\frac12

exp(−2Nq(q−1)​)=21​

两边取自然对数：

−

q

(

q

−

1

)

2

N

=

ln

⁡

1

2

-\\frac{q(q-1)}{2N}= \\ln\\frac12

−2Nq(q−1)​=ln21​

由于：

ln

⁡

1

2

=

−

ln

⁡

2

\\ln\\frac12=-\\ln2

ln21​=−ln2

因此：

q

(

q

−

1

)

2

N

=

ln

⁡

2

\\frac{q(q-1)}{2N}= \\ln2

2Nq(q−1)​=ln2

当

q

q

q 较大时，可以近似认为：

q

(

q

−

1

)

≈

q

2

q(q-1)\\approx q^2

q(q−1)≈q2

于是：

q

2

2

N

≈

ln

⁡

2

\\frac{q^2}{2N} \\approx \\ln2

2Nq2​≈ln2

整理得：

q

2

≈

2

N

ln

⁡

2

q^2\\approx2N\\ln2

q2≈2Nln2

因此：

q

≈

2

N

ln

⁡

2

q\\approx\\sqrt{2N\\ln2}

q≈2Nln2

​

代入

N

=

2

n

N=2^n

N=2n：

q

≈

2

ln

⁡

2

×

2

n

/

2

q\\approx \\sqrt{2\\ln2}\\times2^{n/2}

q≈2ln2

​×2n/2

由于：

2

ln

⁡

2

≈

1.1774

\\sqrt{2\\ln2}\\approx1.1774

2ln2

​≈1.1774

最终得到：

q

≈

1.1774

×

2

n

/

2

\\boxed{ q\\approx1.1774\\times2^{n/2} }

q≈1.1774×2n/2​

这就是“50% 碰撞概率”对应的样本数量。

在密码学安全强度的表达中，通常忽略前面的常数

1.1774

1.1774

1.1774，直接记作：

2

n

/

2

\\boxed{2^{n/2}}

2n/2​

四、为什么原像攻击不是 $2^{n/2}$

4.1 原像攻击只有一个目标

假设攻击者已经知道目标摘要：

h

h

h

每次随机选择一条消息

M

i

M_i

Mi​，成功概率都是：

P

(

H

(

M

i

)

=

h

)

=

1

2

n

P(H(M_i)=h)=\\frac{1}{2^n}

P(H(Mi​)=h)=2n1​

经过

q

q

q 次尝试，成功概率约为：

q

2

n

\\frac{q}{2^n}

2nq​

如果希望成功概率达到较高水平，就需要：

q

≈

2

n

q\\approx2^n

q≈2n

这里没有“多个摘要之间互相比较”的过程。

攻击者每次都在尝试匹配同一个固定目标：

H(M1) 是否等于 h？
H(M2) 是否等于 h？
H(M3) 是否等于 h？

因此，生日攻击无法直接把原像攻击降到

2

n

/

2

2^{n/2}

2n/2。

4.2 碰撞攻击有大量比较对象

碰撞攻击则不同。

攻击者生成

q

q

q 条消息后，不是只把每条摘要和某一个固定目标比较，而是比较所有消息对：

(

M

1

,

M

2

)

,

(

M

1

,

M

3

)

,

…

,

(

M

q

−

1

,

M

q

)

(M_1,M_2),(M_1,M_3),\\dots,(M_{q-1},M_q)

(M1​,M2​),(M1​,M3​),…,(Mq−1​,Mq​)

消息对的数量为：

q

(

q

−

1

)

2

\\frac{q(q-1)}{2}

2q(q−1)​

当

q

q

q 达到

2

n

/

2

2^{n/2}

2n/2 量级时，消息对数量就达到约

2

n

2^n

2n 量级，碰撞概率开始显著增加。

所以，生日攻击的本质不是“猜得更快”，而是：

通过大量样本之间的两两比较，放大了碰撞出现的机会。

五、用代码观察生日碰撞

5.1 截断哈希构造实验

真实的 SHA-256 输出为 256 位，直接寻找碰撞需要极高计算量，不适合普通电脑演示。

为了观察生日攻击，可以截取 SHA-256 的前

t

t

t 位，构造一个实验函数：

H

t

(

M

)

=

Truncate

⁡

t

(

SHA256

⁡

(

M

)

)

H_t(M)=\\operatorname{Truncate}_t(\\operatorname{SHA256}(M))

Ht​(M)=Truncatet​(SHA256(M))

这里把 SHA-256 截取为 16 位：

t

=

16

t=16

t=16

那么摘要空间只有：

2

16

=

65536

2^{16}=65536

216=65536

种结果。

根据生日攻击估算，50% 碰撞概率大约需要：

1.1774

×

2

8

≈

301

1.1774\\times2^8 \\approx301

1.1774×28≈301

条消息。

注意，这个实验只是在模拟“较短摘要的生日碰撞”，并不代表完整 SHA-256 的安全性只有 16 位。

5.2 Python 实验代码

import hashlib

def truncated_sha256(message, bits=16):
"""
截取 SHA-256 的前 bits 位。
这里只用于观察生日碰撞，不用于实际安全场景。
"""
if bits % 8 != 0:
raise ValueError("本示例要求 bits 是 8 的倍数")

digest = hashlib.sha256(message).digest()
return digest[:bits // 8]

seen = {}
collision = None

for i in range(100000):
message = f"message-{i}".encode()
digest = truncated_sha256(message, bits=16)

if digest in seen:
old_message = seen[digest]

if old_message != message:
collision = (
old_message,
message,
digest
)
break

seen[digest] = message

if collision is not None:
message_1, message_2, digest = collision

print("发现碰撞")
print("消息 1：", message_1)
print("消息 2：", message_2)
print("摘要：", digest.hex())
print("消息是否不同：", message_1 != message_2)
print(
"摘要是否相同：",
truncated_sha256(message_1) == truncated_sha256(message_2)
)
else:
print("本次实验没有发现碰撞")

得到以下输出：

由于摘要只有 16 位，碰撞通常很快就会出现。

5.3 记录碰撞出现的轮次

为了观察不同摘要长度对碰撞速度的影响，可以重复实验：

import hashlib

def find_collision(bits, limit=1_000_000):
seen = {}
# 掩码：保留最低bits位，实现任意比特截断
mask = (1 << bits) – 1

for i in range(limit):
message = f"message-{i}".encode()
# 算出完整sha256哈希，转为大整数
full_digest = hashlib.sha256(message).digest()
hash_int = int.from_bytes(full_digest, byteorder="big")
# 截取指定比特长度
truncated = hash_int & mask

if truncated in seen:
return i, seen[truncated], message, hex(truncated)
seen[truncated] = message

return None

# 测试序列
for bits in [8, 12, 16, 20, 24]:
result = find_collision(bits)
if result is None:
print(f"{bits} 位摘要：在限制范围内没有找到碰撞")
else:
count, message_1, message_2, digest = result
print(f"{bits:2d} 位摘要：第 {count:5d} 次尝试发现碰撞，摘要为 {digest}")

得到以下输出

理论上，摘要长度增加 1 位，生日攻击的复杂度只增加约：

2

1

/

2

=

2

2^{1/2}=\\sqrt2

21/2=2

​

而不是增加一倍。

摘要长度从 16 位增加到 32 位，碰撞复杂度大约从：

2

8

2^8

28

增加到：

2

16

2^{16}

216

摘要长度从 32 位增加到 256 位，碰撞复杂度则从：

2

16

2^{16}

216

增加到：

2

128

2^{128}

2128

这体现了摘要长度与碰撞安全性之间的平方根关系。

六、生日攻击的实际含义

6.1 n-bit 摘要不是 n-bit 碰撞安全

如果一个哈希函数输出

n

n

n 位摘要，不能直接说它具有

n

n

n 位碰撞安全性。

更准确的说法是：

碰撞安全强度

≈

n

2

\\text{碰撞安全强度}\\approx\\frac n2

碰撞安全强度≈2n​

例如：

这也是 SHA-256 常被描述为“约 128 位碰撞安全强度”的原因。

6.2 截断哈希的安全性

如果完整哈希输出为 256 位，但系统只保留前 64 位：

H

′

(

M

)

=

Truncate

⁡

64

(

H

(

M

)

)

H'(M)=\\operatorname{Truncate}_{64}(H(M))

H′(M)=Truncate64​(H(M))

那么实际使用的摘要长度就是 64 位。

它的理想化碰撞安全性只有：

2

64

/

2

=

2

32

2^{64/2}=2^{32}

264/2=232

此时不能因为底层算法是 SHA-256，就声称系统使用了 256 位哈希安全性。

摘要截断后，安全强度必须按照截断后的实际输出长度重新计算。

6.3 并行计算不会改变理论指数

生日攻击天然适合并行化。

如果有大量计算设备，可以让不同设备分别计算不同消息的摘要，然后集中比较结果。

并行计算能够降低实际运行时间，但不会改变通用攻击的理论指数：

2

n

/

2

2^{n/2}

2n/2

仍然是碰撞攻击的基本复杂度量级。

例如，

2

128

2^{128}

2128 次操作仍然是极高的计算量。它不是因为生日攻击就“很容易完成”，而是相较于原像攻击的

2

256

2^{256}

2256，安全指数降低了一半。

七、生日攻击并不等于所有碰撞攻击

7.1 生日攻击是通用攻击

生日攻击假设哈希函数的输出近似随机，并且攻击者没有利用算法内部结构。

因此它适用于：

• 理想哈希函数；
• 没有已知结构性弱点的哈希函数；
• 估算碰撞安全性的基础模型。

它给出了一个通用上限：

2

n

/

2

2^{n/2}

2n/2

但如果哈希算法存在结构性缺陷，实际攻击可能比生日攻击更快。

7.2 结构性攻击可能降低复杂度

理想情况下，攻击者只能把哈希函数当作随机映射。

但实际算法由：

• 消息扩展；
• 压缩函数；
• 轮函数；
• 线性变换；
• 非线性变换；
• 常量和状态更新；

共同组成。

如果这些结构存在缺陷，攻击者可能构造出比随机搜索更高效的碰撞方法。

因此，哈希函数的实际安全性应取决于：

实际安全性

=

min

⁡

(

通用攻击复杂度

,

已知结构性攻击复杂度

)

\\text{实际安全性}= \\min( \\text{通用攻击复杂度}, \\text{已知结构性攻击复杂度} )

实际安全性=min(通用攻击复杂度,已知结构性攻击复杂度)

这也是为什么不能只看摘要长度。

7.3 碰撞攻击还有不同类型

在实际密码分析中，碰撞攻击还可以进一步区分为：

• 普通碰撞；
• 选择前缀碰撞；
• 选定前缀碰撞；
• 部分碰撞；
• 多碰撞；
• 相关消息碰撞。

它们对攻击者的能力要求不同。

例如：

• 普通碰撞：攻击者自由选择两条消息；
• 选择前缀碰撞：攻击者先给出两个前缀，再构造后缀使摘要相同；
• 选定前缀碰撞：攻击者可能在特定格式约束下构造碰撞。

这些内容属于后续哈希结构和实际攻击分析的范畴，本文先不展开。

八、三个安全目标在实际场景中的对应关系

需要注意，表格中的“主要关注”不代表某个场景只依赖一种性质。

例如，数字签名通常同时依赖：

• 哈希函数的碰撞抗性；
• 第二原像抗性；
• 签名算法的不可伪造性；
• 公钥体系的可信性。

而密码存储的核心问题，也不是单纯把哈希函数换成更长的摘要，而是提高攻击者进行离线猜测的成本。

总结

生日攻击的关键不在于“哈希函数被逆向了”，而在于：

攻击者不需要匹配一个指定摘要，只要让任意两条消息出现相同摘要即可。

对于输出空间大小为：

N

=

2

n

N=2^n

N=2n

的哈希函数，生成

q

q

q 条消息后，可以形成：

(

q

2

)

=

q

(

q

−

1

)

2

\\binom q2= \\frac{q(q-1)}2

(2q​)=2q(q−1)​

组消息对。

当消息对数量达到

2

n

2^n

2n 量级时，就有较高概率出现摘要重复。于是：

q

2

2

≈

2

n

\\frac{q^2}{2}\\approx2^n

2q2​≈2n

得到：

q

≈

2

n

/

2

q\\approx2^{n/2}

q≈2n/2

因此：

n

 位哈希的通用碰撞安全性约为 

n

/

2

 位

n\\text{ 位哈希的通用碰撞安全性约为 }n/2\\text{ 位}

n 位哈希的通用碰撞安全性约为 n/2 位

需要记住以下结论：

下一篇将继续讨论：

哈希与认证基础（三）：Merkle-Damgård 结构：从 MD5、SHA-1 到 SHA-256、SM3

重点解释传统迭代型哈希函数如何把长消息拆成多个分组，以及消息分组、压缩函数和内部链式状态之间的关系。