哈希函数与MD4碰撞攻击

一、密码学哈希函数基础

1. 定义与核心特性

• 功能：将任意长度的输入（消息）压缩成固定长度的输出（摘要/哈希值）。
• 三大基本安全要求：
  1. 抗碰撞性 (Collision Resistance)：找到任意两个不同的消息 $M_1\ne M_2$，使得 $H(M_1)=H(M_2)$ 在计算上不可行。
  2. 第二原像抗性 (Second-Preimage Resistance)：给定消息 $M_1$，找到另一个不同的消息 $M_2$ 使得 $H(M_1)=H(M_2)$ 在计算上不可行。
  3. 原像抗性 (Preimage Resistance)：给定一个哈希值 $h$，找到任何消息 $M$ 使得 $H(M)=h$ 在计算上不可行。

重要关系：抗碰撞性 ⇒ 第二原像抗性，但反之不成立。

2. 主要应用场景

• 数字签名：对消息摘要签名，而非整个消息（依赖抗碰撞性）。
• 密码保护：存储密码的哈希值而非明文（依赖原像抗性）。
• 完整性验证：验证文件或数据是否被篡改（依赖第二原像抗性）。
• 证书伪造：如果哈希函数不抗碰撞，攻击者可为恶意软件伪造合法的数字证书（如“火焰病毒”案例）。

---

二、生日攻击 (Birthday Attack)

1. 生日悖论

• 在一个23人的房间里，有超过50%的概率至少有两人生日相同。
• 通用公式：在一个大小为 $N$ 的空间中，产生碰撞所需的随机样本数约为 $\sqrt{N}$。

2. 对哈希函数的攻击

• 对于一个输出长度为 $n$ 位的哈希函数，其输出空间大小为 $N=2^n$。
• 生日界：通过生日攻击找到碰撞的预期复杂度为 $O(2^{n/2})$。
• 示例：MD5 (128位) 的理论碰撞复杂度为 $2^{64}$；SHA-1 (160位) 为 $2^{80}$。

---

三、哈希函数的设计：Merkle-Damgård (MD) 构造

1. 核心组件

• 压缩函数 (Compression Function) f：一个固定输入/输出的函数，通常是哈希算法的安全核心。
• 初始向量 (IV)：一个固定的常量。
• 填充规则 (Padding Rule)：将任意长度的消息填充成固定块大小的整数倍。
  • 标准填充：消息 | 1 | 0...0 | 消息长度（64位）
  • 目的：使填充规则成为后缀自由 (suffix-free) 的，从而保证压缩函数的抗碰撞性能推出整个哈希函数的抗碰撞性。

2. 工作流程

1. 将消息按块分割 ($M_1,M_2,...,M_k$)。
2. 初始化链变量为 IV。
3. 迭代调用压缩函数：CV_i = f(CV_{i-1}, M_i)。
4. 最终的链变量 CV_k 即为哈希值。

主流哈希函数：MD4, MD5, SHA-1, SHA-2 都基于 MD 构造。

---

四、MD4 算法简介

• 设计者：Ronald Rivest (1990年)。
• 参数：消息块大小 512 位，输出摘要 128 位。
• 结构：3 轮，共 48 步。每轮使用不同的非线性布尔函数 (F, G, H)。
• 历史：因安全性问题很快被 MD5 取代，但其简洁性使其成为研究碰撞攻击的理想目标。

---

五、Dobbertin 对 MD4 的碰撞攻击（核心）

这是一种差分分析与方程求解相结合的巧妙攻击，能在极短时间内（秒级）找到单块碰撞。

1. 攻击策略总览

• 目标：找到两个仅在一个消息字（例如第12个字）上相差1的消息 $M$ 和 $M^{\prime }$，使得它们的哈希值相同。
• 关键洞察：精心选择消息，使得在第19步产生的特定差分，在经过第19到35步后，能以高概率完全消散（即差分变为零）。

2. 攻击三阶段

阶段一：差分分析 (Steps 19-35)

• 假设：在第19步，内部状态的差分为 ${\mathrm{\Delta }}_{19}=(2^{25},-2^5,0,0)$。
• 分析：通过追踪这个差分在后续16步（使用G和H函数）中的传播，证明它最终变为零差分 ${\mathrm{\Delta }}_{35}=(0,0,0,0)$ 的概率非常高（至少 $1/2^{30}$）。这限制了需要精确控制的步骤范围。

阶段二：方程求解 (Steps 12-19)

• 目标：确保在第12步之后，能够达到阶段一所要求的 ${\mathrm{\Delta }}_{19}$ 状态。
• 方法：这是一个非线性方程组求解问题。攻击者将部分内部状态变量设为自由变量，然后推导出必须满足的约束条件（检查方程）。
• 技巧：使用“连续逼近法 (Continuous Approximation)”。通过微调自由变量，逐步满足所有检查方程，而不是进行暴力搜索，从而将工作量从 $2^{96}$ 降低到可接受水平。

阶段三：前向构造 (Steps 0-11)

• 目标：从初始向量 (IV) 开始，通过选择剩余未确定的消息字，使得加密过程在第11步结束时，恰好到达阶段二所确定的内部状态 $(Q_8,Q_9,Q_{10},Q_{11})$。
• 难度：这是最简单的一步，因为此时有大量自由度（可选的消息字），很容易满足要求。

3. 攻击总结

• 输入差异：两个消息仅在一个字上相差1。
• 核心：利用差分路径的高概率消散 + 非线性方程的智能求解。
• 效率：一旦找到合适的内部状态，构造完整碰撞消息非常快速。

---

六、后续发展与结论

• 更高效的攻击：王小云等人在2004年提出了针对MD4/MD5的更强大、更快速的碰撞攻击方法。
• 预像攻击：2008年，MD4的原像抗性也被攻破。
• 教训：MD4 的失败凸显了在哈希函数设计中，抵抗差分分析和保证非线性组件的强混淆能力至关重要。

---

📝 复习题与答案

题目 1：解释为什么数字签名方案的安全性主要依赖于哈希函数的抗碰撞性，而不是原像抗性？

答： 在数字签名中，通常是对消息的哈希值 $h=H(M)$ 进行签名，得到签名 $S$。

• 攻击场景：攻击者首先诱使受害者对一个看似无害的“好”消息 $M_{good}$ 签名，获得 $(M_{good},S)$。
• 伪造：如果哈希函数不抗碰撞，攻击者可以找到一个恶意的“坏”消息 $M_{bad}$，使得 $H(M_{bad})=H(M_{good})=h$。
• 结果：由于签名 $S$ 是对 $h$ 的有效签名，它同样也是对 $M_{bad}$ 的有效签名。攻击者成功伪造了签名。
• 关键点：这里攻击者是先有 $M_{good}$，再找 $M_{bad}$，这正是第二原像攻击。而抗碰撞性比第二原像抗性更强，因此是更根本的要求。原像抗性在此场景下无法阻止这种伪造。

---

题目 2：简述 Merkle-Damgård 构造中，为什么填充规则必须包含原始消息的长度？

答： 包含消息长度是为了使填充规则成为“后缀自由 (suffix-free)”的。

• 后缀自由定义：对于任意两个不同的消息 $M$ 和 $M^{\prime }$，pad(M) 不可能是 pad(M') 的后缀。
• 安全意义：如果填充不是后缀自由的，那么可能存在 $M$ 和 $M^{\prime }$，使得 pad(M') = X || pad(M)。这意味着，如果攻击者找到了一对压缩函数的碰撞 f(IV, X) = f(IV, Y)，他就可以立即构造出整个哈希函数的碰撞：H(X || M) = H(Y || M)。
• 结论：通过包含长度，可以将整个哈希函数的抗碰撞性规约到其底层压缩函数的抗碰撞性，从而简化了安全性证明。

---

题目 3：Dobbertin 对 MD4 的攻击中，“连续逼近法”解决了什么问题？为什么它比暴力搜索高效得多？

答：

• 解决的问题：在攻击的第二阶段（Steps 12-19），需要求解一个复杂的非线性方程组来找到满足特定差分条件的内部状态。直接暴力搜索所有可能的状态，其复杂度高达 $2^{96}$，完全不现实。
• 工作原理：“连续逼近法”是一种启发式搜索算法。它首先随机生成一组内部状态变量，然后检查是否满足第一个“检查方程”。如果不满足，就对变量进行微小的、一次只改变一位的调整，并保留那些能让方程“更接近”满足的调整。通过这种渐进式的优化，算法能够高效地收敛到一个满足所有方程的解。
• 高效原因：该方法利用了MD4轮函数（F, G）的一个特性——输入的微小变化通常只会导致输出的微小变化。这使得局部搜索成为可能，避免了在整个巨大的状态空间中进行盲目搜索，从而将实际工作量降低到可以在普通计算机上秒级完成的水平。