Open Clock

Merkle-Damgård 结构

Merkle-Damgård 结构是 MD5、SHA-1、SHA-2 等经典哈希函数的基础框架。

工作原理

1. 填充：将消息填充到块大小的整数倍，最后包含原始消息长度（长度填充/Merkle-Damgård strengthening）
2. 分块：将填充后的消息分成 n 个固定大小的块 M₁, M₂, ..., M_n
3. 迭代压缩：h₀ = IV（初始值），h_i = f(h_i-1, M_i)，其中 f 是压缩函数
4. 输出：最终状态 h_n 作为哈希值

安全证明

如果压缩函数 f 是抗碰撞的，那么整个 Merkle-Damgård 哈希函数也是抗碰撞的。

局限性

• 长度扩展攻击（Length Extension Attack）：知道 H(M) 和 len(M) 但不知道 M 本身，可以计算 H(M || padding || M') 的值。因为攻击者可以从 H(M) 恢复内部状态，然后继续处理新数据。
• 多碰撞攻击：可以以相对低的代价构造 2^k 个消息的碰撞组。

长度扩展攻击与防御

攻击原理

假设服务器验证方式为 H(secret || message)。攻击者知道 message 和 H(secret || message)，但不知道 secret。

利用 Merkle-Damgård 结构，攻击者可以：

1. 从 H(secret || message) 恢复压缩函数的内部状态
2. 追加 padding + 任意数据 M'
3. 计算出 H(secret || message || padding || M')

无需知道 secret 就能伪造有效的 MAC。

防御方法

• HMAC：H(K, H(K, M))，双层哈希防止长度扩展
• SHA-3 / 海绵结构：天然免疫
• 截断输出：不暴露完整内部状态

海绵结构（Sponge Construction）

SHA-3 采用的结构，解决了 Merkle-Damgård 的固有弱点。

参数

• 状态大小 b = r + c（比特率 + 容量）
• SHA-3-256：b = 1600, r = 1088, c = 512

优势

• 天然免疫长度扩展攻击
• 可变长度输出（XOF 模式）
• 安全性证明更简洁
• 一个置换函数可用于哈希、MAC、流密码等多种用途

生日攻击

利用生日悖论对哈希函数进行碰撞搜索：

1. 生成 2^n/2 个不同的消息
2. 计算每个消息的哈希值
3. 检查是否有两个消息的哈希值相同

这是理论最优的通用碰撞攻击。对于 n 位哈希函数，需要约 2^n/2 次哈希计算和 2^n/2 的存储。

改进：Pollard's Rho 方法

空间复杂度从 O(2^n/2) 降到 O(1)，时间复杂度不变。使用 Floyd 环检测算法找到碰撞。

差分密码分析

研究输入差异如何传播到输出差异。

对于哈希函数：寻找一对输入 M 和 M' 使得 H(M) 和 H(M') 满足特定的差分关系。

王小云的 MD5 攻击正是差分分析的杰作：找到了一条经过全部轮函数的差分路径，使得碰撞概率远高于随机期望。

差分分析的关键步骤：

1. 选择输入差分 ΔM
2. 追踪差分在轮函数中的传播（差分路径）
3. 计算满足该路径的概率
4. 若概率足够高，可以高效搜索碰撞

线性密码分析

寻找输入比特、输出比特之间的线性近似关系。

对于哈希函数：寻找一组输入比特和输出比特的线性组合，使其偏移显著偏离 1/2。

线性分析通常与差分分析结合使用，用于评估压缩函数的非线性程度。