How to Break MD5 and Other Hash Functions -震惊全球论文，王小云教授如何攻破MD5

作者toby来源How to Break MD5 and Other Hash Functions -震惊全球论文王小云教授如何攻破MD5toby老师才工作时MD5撞库是黑客领域专业词汇。今天看了王小云教授的论文《How to Break MD5 and Other Hash Functions》后不由感叹这是一场改变密码学历史的数学革命王小云教授真乃顶级风控大师。王小云Xiaoyun Wang于红波Hongbo Yu山东大学中国济南论文来源EUROCRYPT 2005, LNCS 3494, pp.19-35原文标题How to Break MD5 and Other Hash Functions一、引言为什么MD5的倒塌如此重要MD5是当今使用最广泛的密码学哈希函数之一由Ron Rivest于1992年设计作为MD4的加强版。哈希函数是现代信息安全的基石——数字签名、数据完整性验证、电子现金等众多密码学协议都依赖其安全性。在王小云教授的工作之前MD5的最佳攻击结果仅停留在半自由起始碰撞semi free-start collision——攻击者可以自选初始值但无法使用MD5的标准初始值。这意味着真正的碰撞仍然遥不可及。王小云团队的核心突破首次在标准初始值下找到MD5的真实碰撞计算时间仅需15分钟至1小时IBM P690服务器。这一攻击不仅适用于MD5还可推广至MD4、HAVAL-128、RIPEMD等哈希函数。• • •二、MD5的数学结构MD5采用Merkle-Damgård迭代结构将任意长度的消息压缩为128位的哈希值。其核心是压缩函数处理512位的消息块输出128位的链值。Hi1 f(Hi, Mi)其中 H0 IV0 为固定初始值每个512位消息块被分为16个32位字 (m0, m1, …, m15)经过4轮、每轮16步的运算。每步操作如下// MD5单步运算以a链为例 a b ((a φi(b,c,d) wi ti) si) // 四轮使用不同的非线性函数// 第1轮0-15步: F(X,Y,Z) (X∧Y) ∨ (¬X∧Z)// 第2轮16-31步: F(X,Y,Z) (X∧Z) ∨ (Y∧¬Z)// 第3轮32-47步: F(X,Y,Z) X ⊕ Y ⊕ Z// 第4轮48-63步: F(X,Y,Z) Y ⊕ (X∨¬Z)初始链值为固定常数a0 0x67452301 b0 0xEFCDAB89 c0 0x98BADCFE d0 0x10325476• • •三、核心创新模差分攻击王小云团队的最大创新在于提出了一种全新的差分分析方法——模差分Modular Differential。传统差分攻击如Biham-Shamir对DES的分析使用异或XOR作为差异度量。而王小云团队改用模整数减法作为差异度量ΔX X′ − X 模 232而非传统的 ΔX X′ ⊕ X这种差异定义的优势在于更精确的进位控制——模减法差异能捕捉进位传播的细节而异或差异会丢失进位信息双重特征描述——同时记录模减法差异和XOR差异提供比单一差异更丰富的信息消息修改技术——通过主动修改消息字来满足差分路径中的充分条件**关键洞察**当模减法差异为 ΔX 26 时对应的XOR差异可能有多种形式——单比特差异、双比特差异进位传播、三比特差异等。通过精确控制这些进位攻击者可以引导哈希计算走向预期的碰撞路径。• • •四、两区块碰撞攻击流程王小云的攻击构造了一对由两个512位消息块组成的消息共1024位使得它们在标准初始值下产生相同的MD5哈希值。攻击整体结构1.选择第一区块 (M0, M0′)使 ΔH1 (231, 231225, 231225, 231225)↓2.选择第二区块 (M1, M1′)使输出差异恰好抵消 ΔH1↓3.最终输出MD5(M0‖M1) MD5(M0′‖M1′)消息差异向量设计如下// 第一区块差异仅第5、12、15字非零 ΔM0 (0, 0, 0, 0, 231, 0, 0, 0, 0, 0, 0, 215, 0, 0, 231, 0) // 第二区块差异第12字符号相反 ΔM1 (0, 0, 0, 0, 231, 0, 0, 0, 0, 0, 0, -215, 0, 0, 231, 0)• • •五、消息修改技术让不可能变为可能攻击的核心难点在于即使设计了精妙的差分路径随机选择的消息满足所有条件的概率极低。王小云团队发明了消息修改技术Message Modification来大幅提升成功率。单消息修改Single-Message Modification通过直接修改消息字确保第一轮前16步的所有差分条件以概率1成立。例如为确保c1的3个比特条件修改m2c1new ← c1old − c1,7old·26 − c1,12old·211 − c1,20old·219 m2new ← ((c1new − c1old) 17) m2old多消息修改Multi-Message Modification更进一步通过级联修改多个消息字m1至m5可以满足第二轮中的部分条件。例如修正a5,32的条件时需要确保修改从第2步到第6步产生部分碰撞同时保持第一轮所有条件不变。• • •六、真实的MD5碰撞示例以下是论文中公开的两对MD5碰撞消息每对共享相同的第一个512位区块 碰撞对 [#1](javascript:消息 M M₀ ‖ M₁十六进制小端序M₀: 2dd31d1c 4eee6c56 9a3d695c f9af9887 b5ca2fab 7e46123e 58044089 7ffbb863 4ad552b3 f4098388 e4835a41 7125e825 51089fc9 cdf7f2bd 1dd95b3c 3780M₁: d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf06 6f129308 fb109d17 97f2775e b5cd530b aade8225 c15cc79d dcb74ed6 dd3c55fd 80a9bb1e 3a7cc35消息 M′ M₀′ ‖ M₁′差异位已标红M₀′: 2dd31d1c 4eee6c56 9a3d695c f9af9887 b5ca2fab 7e46123e 58044089 7ffbb863 4ad552b3 f4098388 e4835a41 f125e825 51089fc9 cdf772bd 1dd95b3c 3780M₁′: d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 cfdebf06 6f129308 fb109d17 97f2775e b5cd530b aade8225 c154c79d dcb74ed6 dd3c55fd 580a9bb1e 3a7cc35共同哈希值 H小端序无填充9603161f a30f9dbf 9f65ffbc f41fc7ef共同哈希值 H*大端序含填充a4c0d35c 95a63a80 5915367d cfe6b751 碰撞对 [#2](javascript:共享相同的M₀共同哈希值 H小端序无填充8d5e7019 61804e08 715d6b58 6324c015共同哈希值 H*大端序含填充79054025 255fb1a2 6e4bc422 aef54eb4注意两对碰撞的M₀区块几乎相同仅在3个32位字中存在微小差异第5字最高位、第12字第15位、第15字最高位这正是ΔM0设计的精妙之处。• • •七、攻击的普适性不止MD5同样的模差分攻击框架可推广至多种哈希函数论文给出了各算法的碰撞复杂度值得注意的是同一时期Crypto 2004Eli Biham和Rafi Chen也发表了SHA-0的近碰撞攻击随后Antoine Joux实现了SHA-0的完整四区块碰撞。这些工作共同推动了NIST加速发布SHA-2标准。• • •八、历史意义与影响2004年8月Crypto 2004大会Rump Session上王小云团队首次公开MD5、MD4、HAVAL-128、RIPEMD的碰撞结果震惊全场2005年论文正式发表于EUROCRYPT 2005成为密码学经典文献2005年后MD5逐步退出安全敏感领域SSL证书、软件签名等场景开始禁用MD52008年研究人员利用MD5碰撞成功伪造CA证书证明理论攻击可转化为实际威胁2012年Flame病毒被发现使用MD5碰撞伪造Windows更新证书王小云教授的工作不仅是技术突破更深刻改变了密码学的安全评估范式从可证明安全到实际可攻击——理论上的碰撞存在性被转化为可执行的攻击算法中国密码学的崛起——首次由亚洲学者主导破解西方主流密码标准推动标准演进——直接加速了SHA-2的普及和SHA-3竞赛的启动结语王小云教授对MD5的攻破是密码学史上最具里程碑意义的事件之一。她提出的模差分攻击和消息修改技术不仅颠覆了曾被认为足够安全的哈希函数更为后续密码分析开辟了全新的方法论路径。从15分钟的碰撞计算到改变全球安全标准这项工作提醒我们在密码学中没有永恒的安全只有不断进化的攻防博弈。王小云老师补充介绍王小云1966年生于山东诸城是中国著名密码学家、中国科学院院士现任清华大学高等研究院杨振宁讲座教授、中国密码学会理事长。她师从著名数学家潘承洞于山东大学数学系获得博士学位后深耕密码学领域2004年至2005年间带领团队先后破解了MD5、SHA-1等五个国际通用哈希函数算法提出密码哈希函数的碰撞攻击理论震惊全球密码学界此后她又主持设计了我国哈希函数标准SM3广泛应用于金融、交通、电力等国家关键领域并于2018年成为ISO/IEC国际标准。她曾获未来科学大奖、世界杰出女科学家奖、国际密码学会最具时间价值奖等荣誉2017年当选中国科学院院士2019年当选国际密码协会会士为中国密码理论与技术跻身世界前列作出了开创性贡献。王小云院士有很多奇闻轶事例如她曾2小时学会C语言其智力和数学天赋无法斗量。大家可以多去关注其论文。版权声明文章来自公众号(python风控模型),未经许可不得抄袭。遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。