Merkle–Damgård是一种算法，由Ralph Merkle和Ivan Damgård提出。它通过迭代调用压缩函数来计算消息的哈希值。

应用

拿SHA-2举例，首先我们需要对需要进行哈希运算的输入做填充，然后将填充后的输入划分为等长的分组，每个分组的长度等于压缩函数的输入长度。填充的意思就是在输入中添加特定的字节，使输入的长度变成分组大小的整数倍。

然后，将压缩函数应用于消息的所有分组，在每次迭代过程中，都将上一轮的输出作为压缩函数的第二个输入参数，而将消息的某个分组作为它的第一个输入参数。将压缩函数最终的输出作为消息的摘要。

如果压缩函数本身是抗碰撞的，那么就可以证明Merkle–Damgård结构是抗碰撞的。这样一来，输入长度不固定的哈希函数的安全性就简化为输入长度固定的压缩函数的安全性。

构造

Merkle–Damgård结构的目标是从压缩函数 $f$ 构造一个哈希函数 $h$ ：

$f: \left \{ 0,1 \right \}^{m+t+1}\rightarrow \left \{ 0,1 \right \}^{m}$

$h: \left \{ 0,1 \right \}^{*}\rightarrow \left \{ 0,1 \right \}^{m}$

给定任意长度的消息x，使得：

给定一个压缩函数f：

$f: \left \{ 0,1 \right \}^{128+512+1}\rightarrow \left \{ 0,1 \right \}^{128}$

消息x有1000bits：

$y_{1}$ 是x的前512bits
$y_{2}$ 是 $x\left | \right |0^{24}$ 的后488bits
$y_{3}$ 是24的 $0^{480}\left | \right |32-bit$ 二进制表示
$z_{1} = f\left ( 0^{129}\left | \right |y_{1} \right )$ ， $z_{1}$ 有128bits
$z_{2} = f\left ( z_{1}\left | \right |1\left | \right |y_{2} \right )$
$z_{3} = f\left ( z_{2}\left | \right |1\left | \right |y_{3} \right )$ ， $z_{3}$ 是h(x)的消息摘要

为什么如果压缩函数本身是抗碰撞的，Merkle–Damgård结构就是抗碰撞的呢？

给定压缩函数 $f$ 和Merkle–Damgård结构 $h$ ：

$f: \left \{ 0,1 \right \}^{m+t+1}\rightarrow \left \{ 0,1 \right \}^{m}$

$h: \left \{ 0,1 \right \}^{*}\rightarrow \left \{ 0,1 \right \}^{m}$

假设我们找到 $x\neq x'$ 所以h(x) $\neq$ h(x')，所以 $f$ 可以找到碰撞。
让 $y(x) = y_{1}\left | \right |y_{2}\left | \right |...\left | \right |y_{k+1}$
让h(x)的中间结果等于 $z_{1},z_{2},...,z_{k+1}$ ，然后 $h(x) = z_{k+1} = f(z_{k}\left | \right |1\left | \right |y_{k+1})$
让h(x')的中间结果等于 $z'_{1},z'_{2},...,z'_{n+1}$ 和 $y(x') = y'_{1}\left | \right |y'_{2}\left | \right |...\left | \right |y'_{n+1}$ 然后， $h(x') = z'_{n+1} = f(z_{k}\left | \right |1\left | \right |y_{k+1}) = f(z'_{n}\left | \right |1\left | \right |y'_{n+1})$
$f(z_{k}\left | \right |1\left | \right |y_{k+1}) = f(z'_{n}\left | \right |1\left | \right |y'_{n+1})$
情况1：
$|x| \neq |x'|\: mod \; t$ (填充位的数量不同)，然后 $y_{k+1}\neq y'_{n+1}$ ，发现碰撞
情况2：
$|x| = |x'|$ 然后k=n，要么 $z_{k} \neq z'_{k}$ 发现碰撞；要么 $z_{k} = z'_{k}$ ， $z_{k} = z'_{k} = f(z_{k-1}\left | \right |1\left | \right |y_{k}) = f(z'_{k-1}\left | \right |1\left | \right |y'_{k})$ ，如果 $y_{k} \neq y'_{k}$ ，发现碰撞；如果 $z_{k-1}\neq z'_{k-1}$ ，则发现碰撞，否则返回。一定有一个数字j使得 $y_{j}\neq y'_{j}$ 。
情况3：
$|x| \neq |x'|$ ，跟情况1相似，除了我们可以一直回到其中一个字符串的开头并且有 $f(0^{m+1}\left | \right |y_{1}) = f(z'_{j}\left | \right |1\left | \right |y'_{j+1})$ ，碰撞被发现。