Merkle-Damgård 构造:哈希函数如何从 Rabin 的漏洞中诞生?

原创
alex 5小时前 阅读数 3 #头条

Merkle-Damgård 构造:哈希函数如何从 Rabin 的漏洞中诞生?

Rabin 的哈希梦:1978 年的漏洞与 1979 年的"诈骗"

1978 年,Michael O. Rabin 提出他的哈希函数。那时候哈希函数已经不算新鲜,Diffie-Hellman 早在几年前就给数字签名设计过单向函数。但 Rabin 的版本有一个 Diffie-Hellman 版没有的性质。输入不必再是短消息,靠一条链接机制,一个函数就能给整本书算出指纹。来源:HN 这个性质在后来看起来理所当然,但在当时是迈了一大步。

这个性质很快被证明是幻觉。1979 年,Gideon Yuval 发了一篇文章,标题叫《How to swindle Rabin》,直白地指出:Rabin 忘了检查哈希函数最重要的属性之一,碰撞阻力。来源:HN 当时的惯例是,攻击者需要暴力尝试超过 256 次操作,构造才算不可破解,这个数字来自生日悖论公式 2n/2,n 是输出长度。来源:HN 对 Rabin 的函数,只需 232 次操作就能找到两个不同输入产生相同输出。从 256 降到 232,差出 224 倍的工作量。来源:HN Yuval 用了 swindle 这个词,想说的不只是攻破,还有 Rabin 被自己的方案骗了。

Rabin 的做法是把消息切成块,每块当作 DES 的密钥,搭一条传送带。第一个明文输入是预定义初始状态 IV,之后每轮的输入是上一轮 DES 的携带输出。来源:HN 问题出在 DES 自己身上。它是块密码,能压缩输入,可它也能被解密逆推。地基是这种可逆的东西,上面的链条怎么可能安全?来源:HN

Merkle-Damgård 构造:链接、分块与 Python 实现

Merkle-Damgård 构造保留了 Rabin 的分块和链接思路:消息分成 M1、M2、M3……,每块作为 DES 的密钥,前一轮输出接下一轮输入,形成 IV → DES → DES → ... → DES → h(M)。来源:HN 固定 IV 作为第一个明文输入,后续块的输入是上一轮的携带输出,任意长度消息都被压缩进固定长度。IV 是约定的起点,所有人用同一个,不然不同长度的消息没法放在一起比较。来源:HN

关键修复是一个 XOR。作者给出 Davies-Meyer 压缩函数:f(key, plaintext) = ENCRYPT(key, plaintext) XOR plaintext。来源:原文 它打破了块密码的可逆性。就算你试图把 f 的输出当作 DES 输出去解密,也得不到两个合法的输入。原文在这里截断了,但意思清楚:加密之后跟原明文异或,解密就再也凑不回去。这个 XOR 是小事一桩,但整个构造的灵魂就在这一下。Rabin 当年缺的就是它。

作者在 GitHub 仓库放了一个 Python 实现,演示这套 1989 年的经典设计。来源:HN 这个构造的数学基础可以追溯到 1989 年,与 Rabin 1978 年的方案相隔 11 年。在这 11 年里,碰撞问题被正式写进了定义。来源:HN

反直觉观察与多源交叉验证:从历史漏洞到 HN 冷遇

作者在文章里给了一个明确判断:Rabin 的构造本身不算复杂,真正的疏忽是没检查碰撞阻力。碰撞阻力是设计时该检查的属性,Rabin 漏了它。来源:HN 更反直觉的地方是 DES 这个组件:它能压缩输入,看起来是现成的,可逆性却让它天然不适合当哈希核心。Merkle-Damgård 用 Davies-Meyer 的 XOR 把可逆性掰断了,才把矛盾解开。来源:原文

把 1978 年 Rabin 的乐观设想和 1979 年 Yuval 的攻破放在一起看,一个看起来可靠的构造,一年后就被拆穿了。来源:HN 作者在文章里把这种对照做得干净利落,没有把 Rabin 说得一无是处,只是指出他少检查了一项。三个时间点,1978、1979、1989,分别对应提出、攻破、修正,凑成哈希函数演进史的一条完整线索。来源:HN

最有意思的反差在 Hacker News 上。这篇文章的帖子只拿到 1 分,0 条评论,截至我抓取时。来源:HN 内容讲的是哈希函数安全性最核心的一个问题,却没激起什么水花。这种落差让我想了一会儿,不过我不确定是不是技术数学话题在社区里天然被冷落,也可能只是发帖时间不巧,或者大家忙着讨论别的。这个猜测我没有更多数据支持,就直说我不确定。来源:HN

可逆的组件做不了不可逆的承诺,除非你愿意加一个 XOR。Rabin 的链条本身没问题,他缺的只是一个异或,以及检查碰撞阻力那一步。Merkle 和 Damgård 在 1989 年把这两样补上,哈希函数才真正立住。来源:原文


原文:

How to build a collision-resistant hash function? – Merkle-Damgård · 来源:Hacker News

作者:itfan123 值班编辑 · 发布于 2026年11月17日

版权声明

所有资源都来源于爬虫采集,如有侵权请联系我们,我们将立即删除