返回资讯中心
外部精选
软件工程
#开发者实时流

Merkle-Damgård 结构:如何构造抗碰撞哈希函数

来源标题:How to build a collision-resistant hash function? – Merkle-Damgård

1978年 Rabin 提出用链式机制让哈希函数可处理任意长度输入,但因未满足抗碰撞性,1979年被 Yuval 的论文指出仅需 2^32 次操作即可找到碰撞,远低于当时认为安全的 2^56 次。这一缺陷推动了后续 Merkle-Damgård 结构的研究。

Hacker News 最新denismenace2026/11/16 · 昨天25 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

1978年,Michael O. Rabin 提出了他的哈希函数构想。但这有什么特别之处呢?哈希函数在当时并不是什么新鲜事物。早在几年前,Diffie-Hellman 就已经提出了他们用于数字签名的单向函数版本。不过,Rabin 的函数具有一个 Diffie-Hellman 所缺乏的非常有用的特性:输入不再必须是短消息。借助一种链式机制,一个函数就能为整本书生成指纹!

遗憾的是,这个哈希函数并不安全。仅仅一年之后的1979年,Gideon Yuval 发表了一篇题为《如何诈骗 Rabin》的文章,清楚地揭示了问题所在:Rabin 忘记检查一个好哈希函数最重要的特性之一——抗碰撞性。在当时,如果攻击者需要执行超过 $2^{56}$ 次暴力破解操作才能攻破一个构造,它就被认为是不可攻破的。这个数字来自碰撞公式 $2^{n/2}$,其中 $n$ 是输出长度,该公式源于生日问题。而对于 Rabin 的函数,只需经过 $2^{32}$ 次操作,就有可能找到两个不同的输入产生相同的输出。

我们不必从零开始,而是尝试升级 Rabin 的构想。他将消息分成若干块,然后用 DES 应用构建了一条类似传送带的链条,并将每个块用作 DES 的密钥。传送带接收的第一个明文是一个预定义的初始状态(IV)。随后,明文输入被用于上一轮的进位输出。

M1 M2 M3 | | | IV -> DES -> DES -> ... -> DES -> h(M)

看起来一切运转良好,但是……DES 是一种分组密码。所以没错,它压缩了输入,但它仍然可以通过解密被逆转。如果链条的基础如此脆弱,链条本身又怎么能安全呢?

不过,这个问题有一个快速的修复方法。我们所要做的就是将 DES 的输出与原始明文进行 XOR:

这就是所谓的 Davies-Meyer 压缩函数。它破坏了分组密码的可逆性。现在,即使你试图将 $f$ 的输出视为 DES 输出,解密它并得到两个有效输入,要制造碰撞,你仍然必须将这些输入再次通过 $f$ 运行,而 XOR 会破坏所找到的“碰撞”。因此,找到输入的唯一方法就是暴力破解。

另一个小改动:我们不再将消息块用作密钥,而是将完整的 DES 输入视为消息块的字段。这样每轮就能接收更多的比特。

我们构建的东西被称为压缩函数。我们本可以就此打住,但 $f$ 真的抗碰撞吗?

目前 $f$ 的输出只有 64 比特长,输入是 120 比特。根据我们之前提到的碰撞公式,要达到 $2^{56}$ 比特的安全级别,我们至少需要 112 比特的输出。那么,我们能做些什么来最终得到 112 比特呢?并不复杂。让我们将 $f$ 函数的两个输出拼接起来,称之为 $F_1$:

输出必须不同,否则这种拼接就没有多大意义。这就是为什么我们使用了两个预定义比特:第一个输入用“0”,第二个输入用“1”。当然,我们不得不将 $F_1$ 的输入缩短一个比特,但为了安全性,这并不算太大的代价。

我们的哈希函数需要安全,同时也要高效。没有人愿意等待数小时才计算出一个指纹。所以让我们计算一下 $F_1$ 的效率:

目前我们的压缩函数 $F_1$ 每次迭代只接收 7 个新比特。而且由于每次迭代有两次 DES 应用,我们每 3.5 个比特就要使用一次 DES(这是我们构造中最长、计算成本最高的部分)。我敢说我们可以做得更好。

我们可以增大输入与输出之间的差异。为此,让我们尝试每个周期使用更多的 DES。乍听起来效率不高,但我们先别急着下结论。

我们记得,每次 DES 应用都有自己预定义的比特来确保输入的差异。对于四次 DES,我们将不得不使用比特 00、01、11 和 10,因此 $f$ 的每个输入现在只有 118 比特长。

是时候评估 $F_2$ 的效率了:

所以升级后的压缩函数每次迭代接收 44 个新比特,并且每 11 个比特才应用一次 DES。这已经比我们第一次尝试后好多了。

增加更多的 DES 起了作用,所以让我们坚持下去:

这次升级让我们每次迭代可以增加 106 个新比特,这意味着我们只需每 17.7 个比特应用一次 DES。这才叫进步!

$F_3$ 的比特运算方案看起来像一棵二叉树,这意味着理论上它可以不断增大。

然而,有两个“需要注意”的点:获得的比特之间的间距越来越小($3.5 \rightarrow 11 \rightarrow 17.7$),而在没有额外安全措施的情况下,碰撞的概率越来越大。注意,对于下一次升级,128 比特已经不足以维持 $2^{56}$ 次操作的安全级别了。所以可能并不值得。

这里没有什么新东西。我们可以直接采用 Rabin 的链式结构,但不用 DES 块,而是使用我们的 $F_3$ 函数(我们将其记作 $F$,并为每个周期加上下标):

M1 M2 Mn | | | IV -> F_1 -> F_2 -> ... -> F_n -> H(M)

我们将初始值定义为零,这样第一个块 $M_1$ 就可以接收所有输入比特。注意每个消息块应具有相同的长度。这就是为什么如果 $M_n$ 太短,我们就用填充零来补全它。

然而,添加填充零会带来一个新问题。想象我们有两个短于一个块长度的消息:

假设每个块必须是 16 比特。那么填充之后,$\mathrm{Mn}_1$ 和 $\mathrm{Mn}_2$ 都会得到两个相同的字符串:

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →