Merkle-Damgård 哈希结构原理：从迭代压缩到长度扩展攻击

概述

Merkle-Damgård 结构（简称 MD 结构）是密码学哈希函数中最古老、应用最广泛的迭代构造方案。由 Ralph Merkle 于 1979 年在博士论文中提出，Stefan Dawgards 于 1989 年形式化了其安全性证明。这一结构奠定了 MD5、SHA-1、SHA-2（SHA-256/SHA-512）、国密 SM3 等所有主流哈希算法的基础。

理解 Merkle-Damgård 结构的关键在于把握一个核心思想：如何用一个只能处理固定长度输入的压缩函数，构造出能处理任意长度消息的哈希函数。

基本设计思想

从压缩函数到哈希函数

假设我们有一个压缩函数 $f$，它接收两个固定长度的输入：

• 状态值 $h$（长度为 $n$ 位，初始化为常量 IV）
• 消息块 $M_i$（长度为 $b$ 位）

消息填充机制

任意长度消息 $m$ 无法直接分割为固定长度的块。Merkle-Damgård 要求对消息进行填充（padding），使总长度为 $b$ 的整数倍。

填充规则遵循 ISO/IEC 10116-2 标准：

1. 附加比特 '1'：在消息末尾追加一个值为 1 的比特
2. 填充零比特：追加 k 个值为 0 的比特，使总长度 ≡ -64 (mod b)
3. 附加消息长度：追加原始消息长度（模 2^64），占用 64 位

以 SHA-256 为例（$b = 512$ 位）：

原始消息 m（长度 L 位）
    ↓
附加 '1' 比特
    ↓
追加 k 个 '0'，使长度 ≡ 448 (mod 512)
    ↓
追加 64 位长度字段（L mod 2^64）
    ↓
总长度 = 512 × n 位（n 个完整块）

填充为什么能防止碰撞？ 关键设计点是长度字段的存在。如果两条消息 $m_1$ 和 $m_2$ 产生相同的填充后消息，那么它们必须有相同的原始长度。这保证了即使是前缀关系的消息（如 "abc" 和 "abcdef"），填充后也永远不会相同。

迭代压缩过程

填充后的消息 $m'$ 被分割为 $n$ 个 $b$ 位块 $M_1, M_2, \ldots, M_n$。迭代过程如下：

h₀ = IV                              # 初始化向量
h₁ = f(h₀, M₁)                      # 第一轮压缩
h₂ = f(h₁, M₂)                      # 第二轮压缩
...
hₙ = f(hₙ₋₁, Mₙ)                    # 最后一轮压缩
h  = H(m) = hₙ                      # 最终输出

其中 $H(m)$ 表示对整个消息 $m$ 的哈希值。最终输出通常就是最后一次压缩函数的输出，也可能经过额外的后缀处理（如 SHA-3 的 sponge 不同）。

形式化定义

压缩函数

设 $f: \{0,1\}^n \times \{0,1\}^b \rightarrow \{0,1\}^n$ 为一个压缩函数，其中：

• $n$ 为输出长度（也称为"内部状态大小"）
• $b$ 为消息块长度（通常 $b > n$）

• 抗碰撞性：找到 $(h, M) \neq (h', M')$ 使得 $f(h, M) = f(h', M')$ 在计算上不可行
• 单向性：给定 $h$，难以找到 $M$ 使得 $f(h, M) = h'$

哈希函数构造

Merkle-Damgård 哈希函数 $H$ 定义为：

$$H(m) = f(f(f(\text{IV}, M_1), M_2), \ldots, M_n)$$

其中 $m = M_1 \| M_2 \| \ldots \| M_n$ 是消息 $m$ 经过填充和分块后的结果。

增强型 Merkle-Damgård（MD⁺）

原始 MD 结构存在长度扩展漏洞。Merkle 和 Damgård 后来提出了改进版本 MD⁺，在压缩函数中增加了对消息块长度信息的编码：

$$f_{\text{MD}^+}(h, M_i) = f(h \| M_i \| \text{len}(M_i))$$

其中 $\text{len}(M_i)$ 是当前已处理的消息总长度。这一改进使得攻击者无法通过修改最后一块来延长消息而不被发现。

安全性证明

原始 MD 结构的安全性缺陷

Merkle-Damgård 在其原始形式下存在一个关键弱点：长度扩展攻击。

给定哈希值 $H(m) = h_n$，攻击者可以：

• 已知消息长度 $|m|$
• 选择任意扩展消息 $m'$
• 计算 $H(m \| m')$ 而无需知道 $m$

MD⁺ 的安全性证明

Merkle 和 Damgård 证明了：如果压缩函数 $f$ 是抗碰撞的，那么 MD⁺ 结构产生的哈希函数也是抗碰撞的。

证明思路采用归约法：

假设存在一个对抗 MD⁺ 哈希的碰撞攻击者 $\mathcal{A}$，我们可以构造一个对抗压缩函数 $f$ 的碰撞攻击者 $\mathcal{B}$：

• $\mathcal{B}$ 运行 $\mathcal{A}$，模拟 MD⁺ 哈希环境
• 当 $\mathcal{A}$ 输出碰撞 $(m, m')$ 时
• $\mathcal{B}$ 追踪迭代过程，找到第一个压缩函数输出发生碰撞的位置
• 该位置即为 $f$ 的碰撞，$\mathcal{B}$ 输出

长度扩展攻击的具体机制

对于原始 MD 结构，攻击者利用内部状态等于最终输出的特性：

已知：H(m) = h_n
攻击者构造：m' = m || padding || M_ext

其中：
- padding 是根据 |m| 计算的标准填充
- M_ext 是攻击者选择的扩展消息块

计算：H(m') = f(f(...f(h_n, M_ext)...), ... )
         = f(f(...f(H(m), M_ext)...), ... )

攻击者无需知道 $m$ 的具体内容，只需知道其哈希值和长度，就可以计算任意扩展消息的哈希值。这一特性被广泛应用于：

• HMAC 构造（但 HMAC 通过内hash+外hash结构规避了此问题）
• 某些自定义协议中的消息认证

长度扩展攻击实例

攻击场景

假设系统使用原始 MD 结构进行消息认证：

认证码 = H(secret || message)

攻击者已知：

• $H(secret || message)$ 的值
• $|message|$ 的长度
• 目标消息 $message_{new} = message || padding || ext$

H(secret || message || padding || ext)

即使不知道 $secret$，也能伪造认证码。

防护方案

现代哈希函数采用以下方案防护长度扩展攻击：

• MD⁺ 增强结构：在压缩函数中加入长度信息
• HMAC 结构：使用双重哈希隔离密钥
• KMAC：Keccak 家族采用 key-prefix 模式
• Sponge 结构：SHA-3 完全不使用 MD 结构

HMAC 的工作机制

HMAC（Hash-based Message Authentication Code）通过巧妙设计规避了长度扩展攻击：

$$\text{HMAC}(K, m) = H((K \oplus opad) \| H((K \oplus ipad) \| m))$$

其中：

• $K$ 是密钥
• $ipad = 0x36 \times block\_size$
• $opad = 0x5c \times block\_size$
• $m$ 是消息

主流哈希算法的 MD 结构实现

SHA-256

SM3

• 消息扩展函数使用不同的非线性变换
• 布尔函数采用不同的设计选择
• IV 值不同（避免与 SHA-256 共享初始状态）

与 MD5/SHA-1 的区别

MD5 和 SHA-1 是最早广泛使用的 MD 结构哈希函数，但它们都存在已知的碰撞攻击：

海绵结构（Sponge）的对比

随着 SHA-3 的标准化，海绵结构成为 MD 结构的主要替代方案。两者的核心差异如下：

Sponge 的吸收- squeezing 过程

吸收阶段（Absorbing）：
  1. 将输入分块，每块与速率部分 r 异或
  2. 对整个状态应用置换函数 f
  3. 重复直到所有输入消耗完毕

挤压阶段（Squeezing）：
  1. 从状态中提取 r 位作为输出
  2. 如需更多输出，再次应用 f 并提取

海绵结构的核心优势在于容量 $c$ 的存在——这部分状态永不输出，提供了抵御各种攻击的安全余量。

工程实践要点

填充验证

实现 MD 结构哈希时，必须正确处理填充：

def pad_message(message: bytes, block_size: int = 64) -> bytes:
    """实现 Merkle-Damgård 标准填充"""
    msg_len = len(message) * 8  # 转换为比特
    
    # 添加 '1' 比特
    padded = message + b'\x80'
    
    # 计算需要填充的零比特数
    # 目标：总长度 ≡ -8 (mod block_size) 即 ≡ block_size - 8
    padding_len = (block_size - 8 - (len(padded) % block_size)) % block_size
    padded += b'\x00' * padding_len
    
    # 附加原始消息长度（64位，小端序）
    padded += msg_len.to_bytes(8, byteorder='little')
    
    return padded

避免使用已破解算法

由于 MD5 和 SHA-1 存在实际可行的碰撞攻击，生产环境中严禁使用：

❌ MD5：已被广泛利用，碰撞攻击仅需数千美元
❌ SHA-1：SHAttered 攻击已实现，证书伪造风险极高
✅ SHA-256 / SHA-3：当前推荐标准
✅ SM3：国密合规要求

国密场景下的注意事项

在中国商用密码应用场景中，需注意以下规范：

• GM/T 0004-2012《SM3 密码杂凑算法》明确规定了 SM3 的填充规则和迭代过程
• 密评要求中对哈希算法的选择有明确要求，不得降级使用已破解算法
• SM3 的填充方式与 SHA-256 类似，但消息扩展函数不同，互不兼容

总结

Merkle-Damgård 结构是密码学历史上最重要的构造之一，其简洁性和高效性使其成为过去四十年的哈希函数主流设计。理解该结构的关键要点包括：

• 迭代压缩：通过固定长度压缩函数处理任意长度消息
• 填充机制：确保消息唯一性，防止前缀攻击
• MD⁺ 增强：加入长度信息，缓解长度扩展攻击
• 与现代结构的对比：海绵结构在灵活性上更优，MD 结构在性能上仍有优势

参考资源

• GM/T 0004-2012 SM3 密码杂凑算法
• NIST FIPS 180-4 Secure Hash Standard
• Merkle, R. E. (1979). Digitalized Documents and Signatures
• Damgård, I. B. (1989). A Design Principle for Hash Functions
• RFC 2104 HMAC: Keyed-Hashing for Message Authentication